サルを落とさないで

サルの総数を $S$ とする。毎回 $1$ 階を取り除くので、手番は全部で $H$ 回である。最後の手番を担当しないプレイヤーを $P$ とする。

$P$ の手番では残っている階の数は常に偶数であり、少なくとも $2$ 階ある。よって、$P$ は毎回、残っている最下階以外を取り除ける。その階のサルは別の階へ移動するため、$P$ はサルを獲得しない。この戦略なら相手の行動に関係なく $0$ 匹を保証できる。これより少なくはできないので最適である。

ゲーム終了時にはすべてのサルがいずれかのプレイヤーに渡る。したがって、最後の手番を担当するプレイヤーが $S$ 匹すべてを獲得する。$H$ が奇数なら最後は Ishigami なので答えは $(S,0)$、偶数なら $(0,S)$ である。$S=0$ の場合も成り立つ。

入力を読みながら合計すれば、時間計算量は $O(H)$、追加空間計算量は $O(1)$ である。$S \le 10^{15}$ なので、合計と出力には符号付き $64$ ビット整数を用いる。

Solution written by GPT