E - Balanced Path 概要 H × WのグリッドとH × Wの整数の配列A, Bが与えられる。 グリッドを右もしくは下に移動して(0,0)から(H-1,W-1)に移動する経路を考える。同時に経路に対応するA, Bの数値のいずれかを赤、もう片方を青色に塗り分ける。 各経路について…

B - Reversi 概要 長さNの正整数列Cが与えられる。この数列に以下の操作を好きなだけ行う。 C[i] = C[j] (i 上の操作の結果出来上がる整数列の種類数を答えよ。(mod 10^9 + 7 して出力) 制約 1 ≦ N ≦ 2 * 10^5 1 ≦ C[i] ≦ 2 * 10^5 方針 大まかにはDPを使う…

Problem - D - Codeforces 概要 長さnの数列a, bが与えられる。aの各要素は好きな回数+1してよく、a[i]を+1するごとにコストがb[i]かかる。 a[i]の隣接する各2項が等しくならないように上記操作を行うとき、コストの最小値を求めよ。 制約 1 ≦ n ≦ 3 * 10^5 …

F - Permutation Oddness 概要 数列{1, 2, ..., N}の順列{p1, p2, ..., pN}の奇妙さをΣ|pi - i| で定義する。 Σ|pi - i| = k なる順列の個数を求めよ。(mod 10^9 + 7 して出力) 制約 1 ≦ N ≦ 50 0 ≦ K ≦ N * N (もとの問題はN, Kともに小文字) 方針 DPが使え…

概要 長さNの整数列Sと長さTの整数列Mが与えられる。Sの部分列とTの部分列のなかで共通するものはいくつあるか。(mod 10^9+7 して出力) 制約 1 ≦ N, M ≦ 2 * 10^3 方針 DP。S = {1, 3, 2}, T = {1, 2, 3, 3, 2, 3}のケースを考える。このとき該当する部分列…

D - Flipping Signs 概要 N項の数列Aが与えられる。「1からN-1までの番号iを選び、A[i-1]とA[i]に-1を乗算する」という操作を好きなだけ行う。操作終了後の数列をBとするとき、Bの和の最大値を求めよ。 制約 2 ≦ N ≦ 10^5 -10^9 ≦ A[i] ≦ 10^9 方針① いろい…