A一完で、そのAも未証明でした。
A - Long Common Subsequence
"0"をN個、"1"をN個並べる解法は、問題を見た当初考えた。それで、どんなS+Sに対しても、前半部分から"0"N個を、後半部分から"1"N個を抽出できる。
その最初や最後に"0"や"1"をつけるという方法も考えたのだけど……。
S="111000"のときS+S="111000111000"で、
ANS="0"+"111000"とすると、
前半で三つの"1"を使ったら、その前に"0"が置けないので無理！ と思ってしまった。が、実は後半で"111000"全て消費できるので、部分列になっていた。
これに気付かず迷走。Sを元に作る解法を考えてWAを出した後、
最終的には、"0"*N+"1"*Nの前後に"0"や"1"を付け加えたもの全てに対して、実際に部分列になっているかどうか確かめるコードを書き、なっていたら答えとするものを書いてACした。
未証明だったけど、長さ2*Nで、部分列になっているものは作れているのだから、2*N+1もそれに近いもののはず！ と、信じられたのは良かったか。
そこそこ正しそうな方針を思い付いたら、その方針を元に考えた方が良いことが多いと思うので。（全然間違ってたってこともあるんだけど。まあ、そのときは仕方ない）
B - Tree Edges XOR
解説AC。
辺に関する条件は扱いにくいので、頂点に関する条件に読み替えられないか？ と考えるのがポイント。
その後も難しいけど、読み替えができたならいけそう。難しい問題だと、なんとか別の問題に言い換えられないかと考えるのは重要ですね。
0 件のコメント:
コメントを投稿