ABC195 E Lucky 7 Battle
DP. $ dp_{i,j} := $ i回目のラウンドまで終わって, 7で割ったときの余りが$ jのとき高橋君が勝つか? と定義する.
ゲームは後ろから見ていくという典型を用いる. まず, $ dp_{N,0} = trueとし, それ以外は$ falseに初期化すればよい. 遷移は次のようになる.
$ X_i = Aのとき
$ dp_{i,j} =($ dp_{i + 1, (10j)\%7} = trueかつ$ dp_{i + 1, (10j+S_i)\%7} = true)
$ X_i = Tのとき
$ dp_{i,j} =($ dp_{i + 1, (10j)\%7} = trueまたは$ dp_{i + 1, (10j+S_i)\%7} = true)
このようにした後, $ dp_{0, 0}が$ trueのとき高橋君が, $ falseのとき青木君が勝利する. 計算量は$ O(N)である.