htkb-proconの日記

初心者がPythonで問題解いた記録

CADDi 2018

oox- 1560 -> 1600

C - Product and GCD

AC: Submission #3840276 - CADDi 2018

ん〜これxのN乗がPを割り切るか√Pから2まで試してみればいいだけなんじゃないの?と思いそのまま書いたらTLE、何でTLEなのかすぐにピンと来ずpypyで投げ直してみようかと思ったがそうする前に気づけてよかった。制約よりN <= 10^12なのでx^Nなんて計算するといくら多倍長のpythonでも死んでしまう。が逆に言えばNが少し大きくなると余裕でPの上限である1012を超えるので、そのようなケースは試すまでもなく答えが1になる。2^40 = 1099511627776 > 10^12なのでNが40未満のケースのみシミュレーションすればいい。

D - Harlequin

AC: Submission #3841148 - CADDi 2018

少し前までゲーム系問題の互いに最適に動くというのが頭こんがらがってアレルギーで、その時いろんなgrundy数などを説明しているサイトを見て回ったのがとっても役立った。↓は説明下手くそなのでわからない人はgrundy数でググって見て回るといいとおもいます。

勝敗が確定している状態から逆回しに考えてみる。例えばりんごが1種類のみ1個残っていた場合、それを食べれば勝ちなので勝ち確定の状態。そしてりんご1種類のみ2個残っていた場合、同じ種類のりんごを2個以上食べることはできないので、1個だけ食べて1種類1個の勝ち確の状態を相手に回さなければならないため負け確。そして1種類のりんごが3個、あるいは2種類のりんごの個数が{1, 2}個の場合、適切に食べることで1種類2個の負け確の状態を相手に渡せるため勝ち確。……という風に逆回ししていくと、手番で奇数個のりんごがあればそれを処理してすべて偶数個にして相手に回し続けることで、相手がどう動こうとも最終的に1種類が2個のような状態を作れるため勝ち。逆に偶数個のりんごしかないと相手に同様の戦法を取られるので負け。

E - Negative Doubling

このインデックスから左は符号マイナス、右はプラスに決め打ちするという発想はあったが、そのインデックスを動かしたときの必要な操作回数が下に凸になると思ったので(正しいか不明)三分探索を試してみたがpypyであえなくTLE。インデックスを決め打ちした後の貪欲の実装がぐっちゃぐっちゃになったのもあるが……。解説みながら組んでもなんか通らないので後でやる(いつまでも記事が公開できないため)。