PS 이야기

카자흐스탄 알마티에서 열리는 IOI 2015가 오늘 개막했다. 이전 IOI와 다르게 이번 IOI는 한국대표단에 조교로 소속되어 학생들과 같이 현장에 왔다. 출국 전 3주 동안 합숙 훈련을 마친 학생들에게 좋은 성적을 기대해본다. 원래 연습 세션 문제는 풀이를 적지 않지만, 문제가 상당히 괜찮아보여 처음으로 적어보려한다. 관련 자료들은 여기에서 다운받을 수 있다. 1. search 문제: 정렬되어 있는 배열이 입력으로 들어오므로 이분 검색을 통해 위치를 구하면 되는 아주 쉬운 문제다. 배열의 크기가 최대 100번이므로 7번의 질문으로 위치를 구할 수 있다. #include "graderlib.h" int find(int sub, int N, int X) { int s = 0, e = N-1, t; whil..

문제 링크 A. Pegman $N \times M$ 크기의 직사각형 모양에서 임의의 위치에서 시작해서 움직인다. 본인이 서 있는 위치에 화살표가 있으면 그 방향으로 다음 화살표를 만날 때까지 걸어가고, 만약 서 있는 위치에 화살표가 없으면 움직이지 않는다. 이 때, 놓여있는 화살표의 방향을 최소한으로 바꿔서 어떤 위치에서 시작하는지와 상관 없이 직사각형 밖으로 넘어가지 않게하는 문제다. 아주 당연히, 화살표가 있는 위치들에 대해서만 고려해주면 된다. 화살표가 있는 위치에 대해서 화살표가 가르키면 안되는 방향들을 바로 구할 수 있다. 그 방향에만 놓지 않도록 최소 개수로 화살표를 바꾸면 된다. #include using namespace std; int yy[]={-1, 0, 1, 0}, xx[]={0, ..

문제 링크 A. Amalgamated Artichokes 1부터 N까지 정수 k가 있을 때, price(k) 에 대해 최대 감소폭을 구하는 문제다. 이전까지 나온 최대 값을 저장해두고 현재 값이 최대값 보다 같거나 작다면 최대 감소폭에 차이를 갱신해주고, 현재 값이 최대값 보다 크다면 최대값을 갱신해주면 된다. 시간복잡도는 $O(N)$이다. #include using namespace std; int P, A, B, C, D, N; int main() { double mx = -2e9, ans = 0; scanf("%d%d%d%d%d%d", &P, &A, &B, &C, &D, &N); for (int i=1;i v) ans = max(ans , mx - v); else mx = v; } printf("%..