Solved.ac Grand Arena 후기 (?)

고수가 많다 :fearful:

그래도 한 문제 빼고 다 풀어서 행복했다 :thumbsup:

전체적으로 codeforce 느낌이 나는 셋이었다.

 

 

 

대략적인 풀이(스포)

 

 

 

 

 

 

A - 구현하면 된다.

 

B - 구현하면 된다.

 

C - 나는 그리디로 풀었다. 앞에서부터 현재 합을 구하면서 

 

• 현재 수가 음수면
  • 현재 합이 양수고 더해서 음수가 되는 상황이 아니라면 이전 것과 병합한다

 

• 현재 수가 양수면
  • 현재 합이 양수거나, 현재 합에 더해서 음수가 되는 상황일 때 이전 것과 분리한다.

를 반복하면 풀 수 있다.

 

D - 못풀었다. 뭔가 세그같은 냄새가 난다.

 

E - 어떤 수 a가 있을 때, a mod K + b mod K 가 0일 경우 a와 b는 같은 조합에 존재할 수 없다. 이 사실을 알면 간단한 조합론 문제로 풀 수 있다.

 

F - 재밌다. 뒤에서부터 순회하면서 움직일 수 있는 돌 / 없는 돌을 판별해준 이후, 움직일 수 있는 돌을 모두 움직였을때 백이 더 많이 이동할 수 있는지, 흑이 더 많이 이동할 수 있는지 구하면 된다.

그러나 움직일 수 있는 돌과 없는 돌의 판별이 까다롭다. 

간단하게, 어떤 돌 뒤에 움직일 수 없는 돌이 나오기 전까지의 움직일 수 있는 돌들 중 상대의 돌의 개수가 내 돌의 개수보다 더 크다면, 그 돌은 움직일 수 없는 돌이다.

 

G - 간단한 dp이다. 에라토스테네스의 체와 비슷한 구현으로 풀 수 있다.

 

H - 미리 각 열/행별로 추가되는 값을 저장해놓았다가, 어떤 칸의 열 / 행 값을 더해서 칸마다 출력하면 된다.

 

I - 왼쪽 위 칸을 기준으로, 행과 열에 대하여 연산 조합마다 필요한 총 연산의 개수를 브루트포싱 할 수 있다. 한 행/열에 대하여 한번 이상의 연산이 필요 없는 것은 자명하다.