5完2WA

各問題

A - Attack

A / B の切り上げが答えで、これ自体は簡単な算数です。で、割り算が切り捨ての言語でこれを簡単に求める方法として (A + B - 1) / B という有名な計算方法があります。

全探索すればよいです。グリッド走査の練習問題。

N, M ともにとても小さいため、next_permutation で全探索すればよいです。一文字変えて同じにできるの判定は愚直にやればいいのですが、自分はレーベンシュタイン距離を求めるスニペットを用意してあったのでそれをペタリしました。

B をソートして、A の各要素から lower_bound(B.begin(), B.end(), A_i + D) を使うなどしてとりえる最大の B の要素を探せばよいです。

最初 A_i - D からスタートして B を探索するとかいう無駄なことをして 1WA。次に lower_bound(B.begin(), B.end(), A_i + D) で見つけたBの要素が A_i + D より大きい可能性があることを失念して 1WA。ちょっとボケてる...。

どの辺がどの辺とつながっているかを map<int, set<int>> で持って、辺があるかどうかを都度チェックして答えを書き換えていけばよいです。

素直に辺を張ってダイクストラすると一つだけ WA が。一つだけだったので定数倍削減で頑張ろうとしてしばらくはまってしまいました。

次に 1 を持つ集合と M を持つ集合をひとまとめにしようとしましたが実装をこじらせてしまい解ききれず。

結局、それもだめっぽくて、すべての整数に対して超頂点を持つのがよかった模様。なるほどなー。

苦戦した人が多かったらしい C がライブラリの助けもあってかなり早く解けたため、5完の中ではそこそこ上位だったようでパフォ的には助かってますが、Fは解きたかったなー。