ABでペナルティを重ね、Cまで三完。Dは解けなくちゃいけなかったようだが、全く思いつかなかった。
D. Cut
解説AC。
「ダブリング」というキーワードを見ても分からず、解説を読んでようやく理解した。
ダブリングは「何歩進んだときどこへ到達するか？」を調べるときに使うイメージがあったけど、この問題のように「ある場所へ到達するまで何歩か？」を調べるときにも使えるのね。
典型らしいので頭に入れておかねば。
ただ、自分の実装だとlogが二つ付く気がするんだけど、これで合ってるんだろうか。
また、その前の、全ての要素について互いの素な部分を求めるパートは、事前に約数列挙して、尺取り法によりできる。ダブリングすると分かればこのパートはできると思うけど、そんな簡単には感じないので、こちらで躓かないようにしたい。
類題だというこの問題もACしました。
同じ解法で解ける問題なのに、添え字などの実装でミスしてしまい良くない……。なお、解説を見ると、logは一つと書いてありますね。うーん、どうやってlog一つ落とすのだろう。
0 件のコメント:
コメントを投稿