Codeforces Round #114 (Div. 1)

結果。
1/5完。Aは読んでない。Bは問題文がよく分からなかったので適当にエスパーしながら通した。Cは、まあ実験ゲーだよなあと思いながら実験コードを書いて結果をじっと眺める。周期があるような気がしたけどTLE&WAなコードしか仕上げられなかった。
CodeForcesの問題が分かりにくいのは仕方ないのでこれからも積極的にAは無視しようと思った。

Codeforces Round #114 (Div. 1) B : Wizards and Huge Prize

問題概要

よく分からない。

解法

状態がN^3程度に収まるように注意しながらDPする。

Codeforces Round #114 (Div. 1) C : Wizards and Numbers

問題概要

ふたつの数A,B(A<=B)に対して

1. BからA^k(k>0)を引く。
2. BをB%Aで置き換える。

のいずれかの操作を施す。どちらかが0の状態で自分の番になったら負ける。勝つのが先手か後手か判定する問題。A,B<10^18、テストケース数10^4。

解法

(B%A, A)が負けの状態であるとき、その状態に遷移できるので(A,B)は勝ちである。(B%A, A)が勝ちの状態であるとき、どちらのプレイヤーも(B%A, A)に遷移しないようにしなければならない。
したがってBからAのべきを引くしかないのだが、BがAより小さくなったらそれは必ず(B%A, A)という状態である。何故ならBから引く数は必ずAの倍数だからである。
結局、BからA^k(k>0)を何回引くことができるか、というゲームに帰着される。これはk>=0であればSRM PotateGameなどで見た有名問題そのものである。この問題はk>0となっているが、BをB/A+1で考えればk>=0で考えるのと同じことになる。したがってB/A+1をk+1で割った余りを見てやればよい。
こんなん言われてやっと気づくレベル…。