■A - Repression
sortするなり全パターン試すなり、合計から最小値引くなり
■B - Hydrate
A + B * x <= C * D * x
A<= (C * D - B) * x
不等式は負で割ると向きが変わるように注意。
■C - Many Segments
場合分けはしたくないし、少数も扱いたくない。
なので、二倍して+-1すれば扱いやすくなります。
■D - Congruence Points
幾何。Dの難易度じゃないです。
複素平面上で考え、complexを使えば回転が容易になることを知った。
頂点数が1のときは絶対Yesなので別処理を行い、
2以上の時は、頂点0,1をi,jに回転してくっつけようと考える。
辺の長さが異なるときは当然ng前述の通り回転を行い、
すべての頂点に対して一致する頂点が存在するかを調べる。
■E - Mod i
このテクって常識なんですか？
dp[i][j]:=i番目までで、jグループ分けを行う場合の通り数。
これを素直に遷移させればN^3かかるのでTLEする
これを公式解説の様にしてN^2に減らす。
■F - Tree Patrolling
DよりもEよりも簡単です。
要するにdpテーブルをマージする木dpをするのですが
計算量がN^3なので無理と思いきや、N^2で収まる。(最終的に完全グラフになるので)
ということを知っていれば良い。
以下のようにdpを定義する。
dp[i][j][k] := 根っこiの下の部分木でj個の頂点が警備されている通り数
但し、頂点iの状態は、自分で警備されている、他人に警備されている、誰にも警備されていない。
とし、これをkに持たせる。
これをkとkのマージに注意しながら計算して遷移すれば良い。
