Eは解きたい難易度なんだけど、コンテスト後も自力ACできなかった。
コンテストへのリンク
A. Erasing Zeroes
"1"がなければ0
そうでないとき、最初に"1"が現れる位置と、最後に"1"が現れる位置を調べ、その間の"0"の個数を出力。
B. National Project
天候の良い日が多ければn日で終わる。
そうでないときは、高品質の舗装をするのに何日かかるか調べる。
C. Perfect Keyboard
隣り合っている文字を管理して、それらをグラフと見た（各文字が頂点、隣り合っている文字へ辺を張る）ときに、一直線にできるかどうか。
コンテスト中はUnion-findを使ったのですが、特に必要なかったですね。連結成分が二つ以上になる場合があると思ったのかな……。
D. Fill The Bag
mが2ベキなので、bitで考える。
nを二進数で表したとき、立っているbitは必ず埋めなくてはいけないので、下の桁から埋めていく。
箱が足りなければ上の桁から取ってくる。箱が2個以上余っていたら、一つ上の桁へ運ぶ。これを繰り返して、合計nにできるか調べる。
E. Erase Subsequences
公式解説を読んでAC。
・tを二つに分けて、それぞれがsの（連続しなくて良い）部分列になっており、共通部分がなければ良い
・sの長さが400なので（三乗で？）DPしそう。
というあたりは分かっていた。
これらを組み合わせれば、
・まずtをt1, t2の二つに分けるのを全探索→その上でDPを使って判定
と考えるのは自然かもしれない。けど、気付けなかった。
気付かなかったのは、DPを考え過ぎたせいかもしれない。今回は、
・全探索→DP
なので、最初からDPを考えるのはちょっと筋が悪かった。「何かで場合分けした上でDPを使う」というのは常套手段。頭に入れておきたい。
t1, t2に分けた後は、二次元DPが必要そうだけど、
・DP[i]でt1をi文字まで使ったとき、t2を最長何文字まで使えるか
として、sについて一文字ずつ更新していけば、一次元のDPで済む。
0 件のコメント:
コメントを投稿