AtCoder Beginner Contest 040 - アルゴリズマーの備忘録

久々の更新です。

この間まで部活動や物理チャレンジのレポートで競プロどころじゃなかったので（AtCoderだけは意地で続けてましたが）、随分と実力が落ちてました。

何とか全完出来たので、とりあえず残り時間で書こうと思います。

バブルソートみたいな感じで青のブロックを動かすのですが、どっちの端へ動かす方が早いかが分かればOK。

なので両方調べましょう。具体的に考えると分かりやすいので、N=6、x=3の例で考えます。

左端に寄せる場合は2回の移動で行けます。x-1回と言えそうです。

右端のときは3回。こちらはN-x回のようですね。

これらうち、小さい方を答えればOKです。

縦の幅をh[m]とすると、タイルの横幅がw=n/hで決まります。残ったタイルはn-h*w個なので、abs(h-w)+n-h*wを最小化すればOKです。

hは1～nまで全て試しても問題ないのでそのまま。

基本的なDPですね。

n本目の柱へのコストはn-1本目の柱までのコストとn-2本目までのコストの内、小さい方です。n-1本目、n-2本目にも同じようなことが言えます。

これを再帰関数で書いて、1度行った計算を再度してしまわないように配列に記録しておけばOKです。

または、1本目のコストが0なので、そこから1本ずつ先へ進んで行くときに、2本先までの柱のコストを更新してもいいですね。自分はそうしました。

「年代が新しい順に問題を解けばよい」ということに気が付けば早いです。

クエリを先読みして、年代の新しい順にソートします。

同様に辺のデータも辺として保存せず、ただ配列に「いつできたか、どことどこがつながったか」を記録して年代順にソートします。

そうしたら、クエリの年代の新しい順に問題を解いていくのですが、i番目のクエリで、w_i年より後に出来た辺は全て考えてよいです。それらの辺でつながっている頂点の数を高速なアルゴリズムで考えたいのですが、Union Findを用いて、頂点を1つにまとめてしまいましょう。

このときに、グループ番号と、そのグループにいくつ頂点が含まれているかを記録しておきます。

あとは各クエリにおいて、それ以前に作られた道をUnion Findでつないで、求めるクエリの頂点のグループにいくつ頂点が属しているかを答えればOKです。

D問題がなかなか思いつかなかったので、実力落ちましたね…ちゃんと実力落とさないように努力します。