読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

ABC 030 - D: へんてこ辞書

・問題
D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder

・アイデア
まず、色々例とかを紙に起こしてみて有向グラフみたいイメージで考えられるんじゃないかって思った。
そして、かならず1つはループが生じるということもわかった。なぜなら木にしたとした時に必ず根のほうへ戻ろうとする矢印が1つはあるから。
そして、ステップ数kを、
その閉路に到達するまでに必要なステップ数(必ず(頂点数N)以下になる!)
から引いたものから、閉路の大きさC(=step-start)で割ることによって位置をわりだすことが可能になる。

といって、満点はkが10^100000とかいう膨大なサイズだったので、「ああ多倍長なんだろうな、でも剰余とかめっちゃめんどそう」と思って、
とりあえず部分点の10^18はunsigned long long でおさまるからとりあえず部分点とりに行こうと時間内にまずそれで書いて50点で終了した(http://abc030.contest.atcoder.jp/submissions/537846)。

そして、解説をみて、こんな感じで剰余は簡単に求まるみたいっていうのがわかった、というかこれはホーナー法的な考え方だしいけたじゃん...みたいになって絶望した。多倍長と整数の一致判定だけ作りなおしたものがさっき完成させて満点になった(http://abc030.contest.atcoder.jp/submissions/538760)。

もうこれを見るとデバッグプリントがいっぱいあって苦労しながらやってたってのがバレる。
でも冒頭に書いたアイデアが解説と同じで、それをコンテスト内に気づけた点は良かった。というかそれに気づかないと部分点が取れないわけだが。