コンテストへのリンク
D - String Formation
一々文字列を反転させていたら時間がかかってしまうので、反転は最後にまとめて行い、文字列追加の際、反転の回数が偶数なら後ろに、奇数なら前に追加する。先頭への文字の追加は、Pythonならcollections.dequeを使う。
E - Divisible Substring
各桁に注目して、たとえば1234という四桁の数字を
4+3*10+2*10^2+1*10^3
に分けて考える、というのはよくあるテクニック。
この要領で、1桁目～各桁までの値をPに関する剰余で分類し、それが一致している範囲を求める。
ただし、P=2や5のときに気を付けなくてはいけないことに注意。これらは10と互いに素でないので、この方法では上手くいかないため、例外処理しなくてはいけない。
コンテスト中はこれに気付かずWAを出した後、全探索のコードを書いて比較することで気付けた。
結構気付きにくいようにも思うので、上手くリカバーできて良かった。
F - Removing Robots
とりあえずソート。
すると、「そのロボットを起動させたとき、どのロボットまで連動して起動するか」が分かればDPで答えを求められそう、と分かる。
なので、それをセグメント木を用いて求めていく。
0 件のコメント:
コメントを投稿