이 문제는 굉장히 어렵고 이 글에는 강력한 스포(풀이의 전체)가 있다. 2주가 넘는 시간동안 이 문제에 정말 많은 시간을 쏟아서 만들었다. 문제에 대해서 많은 고민을 해본 후에 이 풀이를 봐주셨으면 좋겠다.
일단 가장 먼저 발견해야하는 것은 게임판에 "유리도"라는 개념을 부착하는 것이다. 이 게임판이 A,B 둘 중 누구에게, 얼만큼의 유리함을 가져다 주는 지에 대한 값으로 정식 명칭은 아니지만 "유리도" 라고 부르려고 한다. 솔직히 아무것도 모르는 상태에서 "유리도"를 생각하는 것은 정말 말도 안되는 일이고, 따라서 판 뒤집음, 구간 게임판 사용등으로 한 게임판을 수치화 시켜야 된다는 일말의 힌트를 남겨놓긴 하였다.
이 게임의 가장 큰 특징은 내가 턴을 넘기면 무조건 이득이다. 절대로 턴을 넘겨서 손해보는 일은 없다. 이러한 경우의 게임을 조합게임론에서는 "cold game"이라고 한다. 온도 게임론에서 등장하는 용어이다. 이러한 게임에서 유리도를 적용시킬때 나타나는 게임의 결과는 다음과 같다.
- 사용하는 게임판의 유리도 값을 다 합쳤을 때 A가 더 유리하면 항상 A가 승리한다.
- 사용하는 게임판의 유리도 값을 다 합쳤을 때 B가 더 유리하면 항상 B가 승리한다.
- 사용하는 게임판의 유리도 값을 다 합쳤을 때 0이면 후공이 승리한다.
여기서 중요한 것은 3번째로 이를 통해서 어떠한 판의 유리도를 정확히 측정할 것이다. 또한 후공이 이기게 되는, 즉 유리도의 합이 0 인 경우를 무승부라고 칭하겠다.
※앞으로 A쪽으로 유리한 유리도는 양수 B쪽으로 유리한 유리도는 음수라고 하겠다.
예를 들어 게임판이 A 면 값은 1이고 AB 이면 -0.5이다. AB, AB, A 의 경우에 무승부이기 때문에 세 판의 유리도를 합치면 0 일 것이고 AB의 유리도는 -0.5가 되는 것이다.
만약 우리가 어떤 판의 유리도를 알 수 있다면 그 판을 A-B 교체하는 행동은 유리도에 음수를 취하는 것이고, 구간합은 세그먼트 트리를 이용하여 가볍게 처리해 줄 수 있으므로 문제를 해결 할 수 있게 된다.
이제부터 어떤 판의 유리도를 정하는 것을 하려고 한다. 본인은 이 유리도를 게임에서의 둘의 최선의 수를 생각하면서 하였다. 또한 앞으로 적는 판은 B가 1개인 판으로 고정하고 생각하려고 한다.
일단 B가 자신의 폭탄을 점화할 때 터지는 A폭탄이 없는 간단한 경우부터 생각하자. (이후 언급이 있기까지)
이때 중요한 것은 A의 선택이다. A가 자신의 폭탄을 점화시켜 A1,B1 개씩 터트리면 베스트이다. 그렇다면 B는 공짜로 자신의 턴 한 번을 이용하지 못하게 되는 것이다. 하지만 AN,B1개라고 생각해보자. 이때는 당연히 A가 N턴에 걸쳐서 자신의 폭탄을 점화하는 것이 베스트이다. 즉 B의 1턴을 망치려고 자신의 2이상의 턴을 망치는건 똑같거나 손해라는 것이다. - think1
판의 처음 형태가 A입장에서 A의 폭탄 하나만 점화시켜 자신의 다른 폭탄은 터트리지 않고 B의 폭탄을 터트릴 수 있는 상태를 freebomb 상태라고 하자. 아래의 그림에서 게임판 1과 2는 freebomb 상태이지만 3은 freebomb 상태가 아니다.
먼저 freebomb 상태의 게임판이 N개가 있다고 생각해보자. 이때 B가 그러한 게임판에서 B하나를 점화시키면 A는 당연히 B가 남아있는 게임판에 가서 A와 B를 같이 터트리는것이 이득이다. 즉 두 개의 게임판중 한 개의 게임판에 대해서만 B가 폭탄을 자신의 한 턴으로 사용할 수 있고, 따라서 절반만큼의 가중치 즉 -0.5만큼의 효율을 낸다는 것이다. 실제로 게임판 1의 유리도는 0.5이며 2의 유리도는 2.5이다.
이번엔 freebomb 상태가 아닌 게임판이 N개가 있다고 생각해보자. A가 이득을 보기 위해서는 최소한 어떤 판에 대하여 최소 한 개의 자신의 폭탄을 터트린 후 A한개 B한개를 같이 터트려야 된다. 이때 B의 입장에서 생각해보면, A가 자신의 것을 미리 터트려놔서 A가 이제 이득 볼 게임판에 있는 자신의 B 폭탄만 점화시키면 된다. 즉 항상 자신의 폭탄을 1턴의 가치로 사용할 수 있음이 보장 된다는 것이다. 따라서 freebomb 상태가 아닌 게임판에서는 -1 의 효율 전체를 내게 된다. 게임판 3의 경우에는 유리도 값이 1이 된다는 것이다. -think2
이번엔 B를 점화시킴으로써 없앨 수 있는 A가 k개 있다고 해보자. 또한 그러한 게임판이 $2^{k}$ 개가 있다고 생각해보자. 이때 A는 B가 없앨수 있는 폭탄을 점화시키는 것이 최선이고, B는 한 번에 최대한 많은 A의 폭탄을 없앨 수 있는 수가 최선이므로, 둘이 각각 $2^{k-1}$회의 턴을 함으로써 $2^{k-1}$개의 게임판에서는 B가 사라질 것이고 (그 뒷쪽에 있는 A만 남을 것이고) 나머지 $2^{k-1}$개의 게임판에서는 끝 쪽의 A가 1개씩 사라질 것이다. 이를 확장시켜 생각해보면 B가 같이 터트릴 수 있는 A가 남은 게임판 중에서 또 절반은 A가 1개씩 사라지고 절반은 B가 사라질 것이다. 또한, 이를 계속 반복할 것이다. 그렇게 최선의 플레이로 게임이 진행된다고 생각하면, B와 B가 터트릴 수 있는 k개의 A를 합친 부분의 가중치는 $-1/2^k$가 될 것이다. B와 B를 점화시킴으로써 없앨 수 있는 A가 k개 있고 그 뿐인 게임판 $2^{k}$개는 A 한 개만 있는 게임판과 무승부 상태를 이룬다. -think3
이제 think2와 think3를 접목시켜보자. 일단 B를 점화시킴으로서 같이 터지는 A의 갯수를 p개라고 하고, 그렇지 않은 A의 갯수를 q개라고 하면 일단 B와 p개를 생각하면 유리도는 $-1/2^p$ 일 것이고, 또한 이 판이 freebomb 상태이면 이 값에 절반을 취해야하며, 아니라면 이 값 그대로를 사용한다. 또한 그 뒤에 q개는 그냥 1턴씩을 모두 사용할 수 있기 때문에 q를 더해주면 된다.
전체 값들은 $2^{40}$을 취해줌으로써 쉽게 관리할 수 있고, 어떤 판에서 p와 q의 갯수세기, freebomb상태인지 판별하기는 모두 $O(r*c)$ 에 할 수 있다. 이를 통해 유리도를 구하고 위에서 언급한 것처럼 세그트리 등을 이용하여 쿼리를 처리해주면 $O(N*r*c+NlgN)$에 해결 할 수 있다.