ABの二完でした。Div.2でこれはひどい。
C. K-beautiful Strings
後ろから見ていく。
まず、各i文字目について、そこまでで各文字が何回ずつ使われているかを前計算。
それを使って、「i文字目までSと同じ文字列で、条件を満たすものがあるか？」を調べていく。
i文字目までに使われている各文字について、あと何回使えばkの倍数になるか？ を計算する。それを埋めるだけでn文字まで埋まってしまうようなら、i+1文字目を、「その中でS[i+1]より大きい最小のもの」にして、後はソートして埋めるのが最適。
そうじゃないとき、i+1文字目はS[i+1]より一つ大きいものになる。（S[i+1]が"z"のときは上手くいかないので、次の文字を見る）
一文字付け加えたとき、「あと何回使えばkの倍数になるか？」を再計算。それでも余った部分は"a"を付け加え、ソートしたもので埋めるのが最適。
……というような感じで、コンテスト後にACした。
「こんな感じ」という、おおまかな方針は立つけれど、正確に記述するのは難しい問題。上の説明でも、iが0文字のときなどを省略しているけれど、その辺を適当に書くと落ちてしまう。
この問題は、おおまかな方針が立ったらコードを書きだしたのは間違っていなかったと思う（もっとしっかり考察した方が良かった、ということも多いけれど、この問題はそうではないと思う）けれど、詰まったときどうすれば良かったんだろう。難しい。
D. GCD of an Array
解説を見てAC。
エラトステネスの篩のような方法で、2*10^5までの素因数分解は前計算しておく。
GCDはセグ木で管理できるので、素因数分解したものをセグ木に載せる方法を試したけど上手くいかず。
公式解説を見ると、
・答えは単調増加なのだから、一々計算してはダメ。増えた分を差分計算しなさい、とある。
なるほど、と思い、そこを直すも、セグ木のままだとTLEが取れなかった。（ただ、自分の書き方が悪いだけで、これでも通せるはずです）
もう一度公式解説を読むと、各素因数について、最小値だけを管理すれば良い、とある。ただ、multisetを使う、という部分がよく分からなくて困った。
結局、各素因数について、
・どのindexでそこを使ったかをsetで管理→setの要素数がn以上になれば、その素因数をGCDに持つ。
・(素因数の重み, index)をheapqに入れて管理、シミュレーション。heapqの最小要素が実際の値より小さいなら、popする。
のようにしたところACできた。
ただ、制限時間ギリギリなので、あまり良い書き方ではないですね……。（PyPyで、もっとまともな実行時間でACしている人がたくさんいます）
0 件のコメント:
コメントを投稿