AtCoder Regular Contest 125

 

A. Dial Up (00:18, +1) *442

제자리에서 계속 더하다 처음 다른 값이 나오면 가장 가까운 곳으로 이동하고, 이후에는 나오는 값에 따라 1이나 2를 더해주면 된다. 불가능한 경우 처리는 쉬우니 생략하도록 하겠다.

 

 

B. Squares (00:54, +) *1273

\(1\)부터 \(sqrt(N)\)까지는 모든 경우가 되므로 다 더해준다. 그러면 각 \(x\)당 가능한 \(y\)의 개수가 \(O(sqrt(N))\)개가 된다. 따라서 각 경우에 대해 구간의 길이를 곱해 더해주면 된다.

 

C. LIS to Original Sequence (01:42, +4) *1896

다음과 같은 과정을 따른다. LIS의 원소를 \(A_1..A_k\)라 했을때

(1) \(i<k\)

\(A_i\)를 출력한 후, 아직 출력하지 않은 원소중 \(A_i\)보다 작은 것이 있다면 그 중 가장 작은 것을 출력한다.

(2) \(i==k\)

아직 출력하지 않은 모든 수를 내림차순으로 출력한다.