Eまで五完。
FはSA-ISを書かないとACできない。SA-ISを理解していないため後回し……。
G - Connectivity 2
解説放送を聞いてAC。
$3^N$のDPなのだけど、そこがポイントではなく、
・DP[S]=S内の辺についてみたとき、Sが連結になる場合の数
とおいて上手くいくと気付くのが重要。
こうおいてDPが回るというのも意外だし、これを使って答えが求められるというのもなかなか思いつかないし理解し辛い。
なお、解説放送ではこれを使って答えをどう表すか、ということは前半の解説部分で話しておらずコードを書くところでそれに触れている。
私は前半を見て理解したつもりになってコードを書きだしたもののそこで詰まり、結局解説放送後半部分も見ることになってしまった。DPの遷移と大体同じ考え方なのに、ピンと来なかったんだよねぇ……。
ただ、こんな風に重複なく数える、というのは、部分文字列を走査するDPと考え方としては似ているか。
重複なく数えるために「1と連結なもっとも小さい集合を見る」というのは、部分文字列を走査するDPで「次に現れる文字のうち一番近い文字を見る」というのと対応しているのだと思う。
H - Stroll
解説放送を聞いてAC。
分割統治FFTというのはこういう処理なのですね。
解説放送では自己ループのみがある場合で説明しているため、道がたくさんある場合でどうすれば良いかちょっと戸惑ったが、各道ごとに同じ処理を行えば良いということで納得した。
なお、再帰で通常通り書いたらTLEしたため、他の人のコードのFFTの実装を見たら、配列の長さが小さい場合は直接計算しているようだったので、（FFTのライブラリ自体は書き換えずにDPの遷移の処理を）配列の長さで場合分けしたらACできた。
FFTライブラリ自体を書き換えた方が後々のためには良いのだろうけど、どれくらいで分けるのが良いのだろう。AtCoderのライブラリでは、「畳み込む配列のうち小さい方が60以下かどうか」で場合分けしてそうだけど、自分の実装でもこれが良いのだろうか。
0 件のコメント:
コメントを投稿