https://atcoder.jp/contests/abc135/tasks/abc135_f 前提知識 Suffix Array トポロジカルソート 解説 https://atcoder.jp/contests/abc135/submissions/6588977 まずは尖ったケースを考えてみる。 -1が尖っているので、この辺から考えてみる。 まずは、-1と…

https://atcoder.jp/contests/abc135/tasks/abc135_d 前提知識 桁DP 解説 https://atcoder.jp/contests/abc135/submissions/6588492 桁DPしていこう。 dp[dgt][mo] := dgt桁目まで確定していて、そこまでで13で割ったあまりがmoである組み合わせ ?でないとき…

https://atcoder.jp/contests/abc135/tasks/abc135_c 解説 https://atcoder.jp/contests/abc135/submissions/6588408 どこから考えようかという問題。 DPを考えてみると、dp[i][rest] := i人目までの勇者が倒し終わっていて、最後の街にrest体のモンスターが…

https://atcoder.jp/contests/abc135/tasks/abc135_b 解説 https://atcoder.jp/contests/abc135/submissions/6588394 入れ替え操作は全部でO(N2)なので、全通り試すことはできそう。 昇順になっているかの判定もO(N)でできるので、全部でO(N3)で間に合う。 C…

https://atcoder.jp/contests/abc135/tasks/abc135_a 解説 https://atcoder.jp/contests/abc135/submissions/6588371 abs(A-K)=abs(B-K)というのは、言い換えると、KはAとBのちょうど真ん中にある数ということになる。 これはA,Bの平均であると言えるため、…