問題分と入出力 前提知識 最大クリーク 解説 M≦40なので、ビット的な計算量が出てくるだろうと仮定を立てる。 しかも、40というのは微妙な所で2^Mというのは間に合わない。 だが、2^(M/2)なら間に合う。 半分全列挙である。 ここで終わった。 最大クリークら…

問題文と入出力 前提知識 動的計画法 今回の問題はパッと見て、編集距離DPっぽい。 競プロの問題で、典型的な問題と形が似ている問題は、元の問題の解き方をアレンジして解く場合が多い。 そのため、編集距離を求めるDPを元にして考えていこう。 Add, Erase,…

問題文と入出力 前提知識 01-BFS 解説 今回の問題は、 damage(sx, sy, tx, ty) := 座標(sx,sy)から座標(tx, ty)へ移るための最小ダメージ として、damage(X[0], Y[0], X[1], Y[1]) + damage(X[1], Y[1], X[2], Y[2]) + ...をしていけばいい。 damage関数の中…

問題と入出力 解説 それぞれが払うべき金額は、A[i]円かM/N円のどちらか安い方なので、 その総和を答えると答え。 int N, M, A[101]; //--------------------------------------------------------------------------------------------------- void solve()…