https://codeforces.com/contest/1214

A - Optimal Currency Exchange (Code)

설명이 너무 이해하기 어렵게 써져있어서 짜증났습니다. 결론적으로 그냥 $d, 5e$로 $n$을 잘 나누어가져 최대한 남는 것이 적도록 하는 문제이고 $O(n)$에 해결이 가능합니다.

B - Badges (Code)

얘도 좀 난해하게 써져있었는데 그냥 $O(n)$을 다 해보면 됩니다. B가 더 쉬운데 왜 A와 B의 순서가 이렇게 되어있는지 이해가 안갔습니다.

C - Bad Sequence (Code)

그냥 가장 오른쪽의 ( 하나를 제일 앞으로 옮기는게 최적임을 쉽게 알 수 있고, 이에 따라 코드를 작성하면 됩니다. 더 나아가 생각해보면 +1 -1을 붙이는 방식으로 계산할 때 -1 밑으로 가지 않고 전체의 합이 0이 되면 무조건 가능함도 알 수 있습니다.

E - Petya and Construction Set (Code)

거리가 먼 순으로 정렬해놓고 일단 홀수들을 일자로 늘어놓은 뒤 짝수를 어떻게 연결하면 될지를 고민해보면 답을 알아낼 수 있을 것입니다.

D 맞왜틀ㅡㅡ

https://codeforces.com/contest/1208

A - XORinacci (Code)

주기가 3인게 자명합니다.

B - Uniqueness (Code)

모든 l, r에 대해 다 해보면 되는데 l을 고정하고 r을 오른쪽으로 늘려가면서 누적시키는 방법으로 해야 $O(N^2)$에 해결할 수 있습니다.

C - Magic Grid (Code)

그다지 엄밀한 증명 없이 그냥 4*4 단위 칸을 쓰면 되겠다고 생각헀고 실제로 맞았습니다. 왜 맞는지는 아직도 잘 모르겠네요ㅎㅎ..

D - Restore Permutation (Code)

Segment Tree를 이용해 뒤에서부터 현재 x라는 수가 왔을 때 $s_i$가 일치하는 x를 이진탐색으로 찾으면 됩니다.

E - Let Them Slide (Code)

segment tree를 하나 들고다니면서 각 가로에 대해 최댓값이 움직일 수 있는 부분은 그냥 업데이트 시키고, 나머지 부분은 따로 처리를 해주고 뭐 그런식으로 경우를 잘 나눠서 해결하면 됩니다. 구현에서 실수를 하기 쉬웠습니다.

https://www.acmicpc.net/problem/10464

이런 류의 문제는 늘 참 뭔가 까다롭지만, 재귀적으로 잘 해결하면 됩니다.

예를 들어 1부터 10110101(2) 까지의 XOR값을 구하고 싶다고 할 때, 1부터 1111111(2)까지의 XOR값은 0이니 떼버리고 뭐 그런식으로 구했습니다.

https://github.com/blisstoner/BOJ/blob/master/10464.cpp