Eまで五完。
コンテスト後のツイート
第三回日本最強プログラマー学生選手権-予選-（ABC262） Eまで五完。
— titia (@titia_til) July 31, 2022
B 全探索
C A[i]=iとなるもの同士か、そうでないもの同士かで分けて考える。
D 選ぶ個数ごとにDP。四乗で若干不安だった。
E 次数が奇数の頂点に何個おくか。結構最初から次数は考えたはずなのに時間かかったのはダメ。
F - Erase and Rotate
解説AC。
ある数字を先頭に持ってくるためには、
・それより前を全て消す
・それより後の数字を全て消すもしくは先頭へ移動させた後、その数字も先頭へ持っていく
のいずれかの方法がとれる。
コンテスト中は二番目の方法しか考えていなかったためダメでした。
一旦先頭へ持っていった後は、範囲最小値が分かるセグ木を使って、あるindex iからi+Kの間にP[i]より小さい数字があればindex iを消去、というのを繰り返せば良い。（先頭への移動がない場合も、この方法で作ればOK）
ただし、Kが余っていたら、最後にPの後ろを消すのを忘れずに。
G - LIS with Stack
解説放送を見てAC。
解法を理解するのも実装するのも難しい。
indexがどこに移るか考えて、「区間で何かする」という発想に思い至れば思いつけるのかなぁ。
Ex - Max Limited Sequence
解説放送を見てAC。
解法（の高速化以外の部分）を理解するのはそれほど難しくないけど、普通にやろうとするとDPが二乗になってしまう。確かに高速化できそうではあるのだが、実装方針が難しいし、方針を理解しても実際の実装には非常に苦労した。
解説の方法で実装したけど、遅延セグ木を使った方が実装しやすいのかなぁ。どっちみち大変そう。
0 件のコメント:
コメントを投稿