https://atcoder.jp/contests/abc133/tasks/abc133_a 解説 https://atcoder.jp/contests/abc133/submissions/6311780選択肢は2つある。全員電車か、全員タクシーである。 よって、min(N * A, B)が答え。 int N, A, B; //-----------------------------------…

https://yukicoder.me/problems/no/848 前提知識 ダイクストラ 解説 https://yukicoder.me/submissions/357498星2.5にしては、かなり難しい問題に見える。 こういう場合は、制約からエスパーするに限るのだが、N≦2000というのが弱点っぽい。 N^2っぽいので、…

https://yukicoder.me/problems/no/847 前提知識 枝刈り全探索 解説 https://yukicoder.me/submissions/357485まず、N^Kの正の約数であって、M以下のものというのはそんなに個数がなさそうな感じがする。 N^Kを素因数分解をして、適当な枝刈りをしながらDFS…

https://yukicoder.me/problems/no/846 解説 ceil(N/P)=AであるNの範囲は、[P*(A-1)+1,P*A]である。 他のメダルについても同様に条件を満たすNの範囲が存在する。 他のメダルについては、そのメダルだけの枚数で計算することになってしまうので、B+=A, C+=B…

問題分と入出力 前提知識 最大クリーク 解説 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()…