CADDi 2018 D Harlequinの解説

D - Harlequin

問題概要

N色のリンゴがあり、各色のリンゴはそれぞれa_i個ある。
先手と後手が以下の行動を交互に行うようなゲームを考える。

一個以上のリンゴを選んで食べる。ただし、同じ色のリンゴを2個以上食べてはいけない。

このとき、最後のリンゴを食べたほうが勝ちになるとする。
先手と後手が双方最善を尽くした時、どちらが勝つか?

考え方の方針

この手のゲームの問題は、"先手必勝の局面"の特徴は何か、ということを考えるとうまく行くことがあります。
もっと簡単な例でいうと、子供のころにやった遊びで、

先手と後手が交互に数字を1から昇順に数える
それぞれの手番では1つ以上3つ以下まで数を数えることができる
最後に30を言ったほうが勝ち

というものがあると思います。

このゲームは

30を言ったほうが勝ち
26を言える状況ならば26を言った後に相手に手番を譲る。そうすると相手は27~29のいずれかまでしか数えることができず、どの場合でも自分のターンで30を言うことができる。したがって26を言えたら勝ち。
同様の理屈で22を言ったら勝ち
同様の理屈で2を言ったら勝ち

というわけで、正しくやれば先手が必ず勝ちます。
最初のターンで2までをカウントして、次に相手が3~5のどの数値までを数えたとしても、次に6を言って手番を譲り... ということを繰り返せば最終的に30を言うことができます。

この手のゲーム(いわゆる石取りゲーム)では、"相手が何を言っても最終的には勝てる"というような状態(必勝状態*1 )を決して手放さないような手順を考えることが大事になることが多いです。
この30を言うゲームでの必勝状態は"自分の手番で2+4nの数値までを言った"という状態です(n>=0)。
相手がその次にどのような手を指したとしても、自分のターンでまたこの状態に持ってくる、ということを繰り返すと最終的に勝つことになります。

NimやNimKなどで出てくるGrundy数の解析によって問題を解くのもこの考え方の延長で、"最善を尽くせば後手が必ず勝てるような局面"はGrundy数が0になっていて、局面のGrundy数を数えることで先手と後手のどちらが勝つかがわかります*2。

というわけで、このゲームでもそのような"先手か後手のどちらかが必ず勝てる状態"がないかを探してみましょう。

どういうときに必勝の局面が現れるか?

まず簡単のため、一色しかリンゴがない場合を考えましょう。
リンゴの数が

1個の時: これは先手が1個食べておしまいなので、先手勝ち
2個の時: 先手は1個しか食べることができず、一個残った状態で後手の手番にわたる。したがって後手勝ち
3個の時: 同じ理屈で先手の勝ち
以下省略

というわけで、リンゴの数が奇数: 先手勝ち、偶数:後手勝ち、という結果になります。

このことから、どうも各色のリンゴの数の偶奇が大事そうな雰囲気がしてきます*3。
最後のリンゴを食べたほうが勝ちなので、リンゴの数が偶数個の時に手番を譲られたほうが不利のような気がしてきます。
そこで、このゲームをプレイするときの戦略として、

各色のリンゴについて、リンゴの数が奇数ならばリンゴを食べる、偶数ならば食べない

という方針でやったら勝てそうです(今は全部偶数の場合は考えないことにします)。

この方針で実際にゲームに勝つことができて、

相手に手番がわたるときには必ず各色のリンゴの数はすべて偶数になっています(0も偶数です)。
相手がどのような手を指してきても、相手が食べた色のリンゴを次のターンで食べることで、その次もすべての色のリンゴが偶数の状態で相手に手番を渡すことができます。
最終的に勝てる人は手番で残っている色のリンゴの数が1個だけになっているような人である(つまり奇数)。したがって、偶数の状態で手番が回ってくる人は必ず負けてしまいます。

というわけで、このゲームにおいて、手番が回ってきたときに"すべての色のリンゴの数が偶数"の時は必ず負ける、逆に"どれか一つでもリンゴの数が奇数の色があるとき"には必勝になります。
最初の局面のリンゴの数、すなわち各a_iの偶奇を判定すればよく、コード自体は以下のようにとてもシンプルになります。

提出コード

Submission #25883195 - CADDi 2018

def main():
    N = int(input())
    a = [int(input()) for _ in range(N)]
    odd_count = sum([(val%2) for val in a]) # aの中の奇数の数の個数を数える
    if odd_count==0: # 奇数の数が0の時、すなわちすべて偶数の時には先手負け
        print("second")
    else:
        print("first")
    
if __name__ == "__main__":
    main()

*1:すいません、これは勝手に名前を付けただけです。この記事の外では使われていないので気を付けてください。

*2:ここではGrundy数については解説しません。たくさんの人が良い記事を書いてくれているので、そちらを探してみてください。AtCoderではABCの水色~青くらいの問題でGrundy数の解析が前提になる問題が出ることがあると思います。Grundy数を知っておくと、与えられた問題をどうやってGrundy数を数えるか、という問題に言い換えることができ、解答への糸口を得られることが多いです

*3:ここから先はあんまり論理的な展開ではないので語尾を濁しています。上のように簡単な例を使って考えると結果的に正しい方針を思いつけることが多いと思います。方針を思いつくまではエスパーでも、それが正しいことが説明できればOKだと思います。