C - 徒歩圏内 概要 長さNの非負整数列X(i X[j] - X[i] ≦ D かつ X[k] - X[j] ≦ D かつ X[k] - X[i] > D 制約 3 ≦ N ≦ 10^5 0 ≦ X[i], D ≦ 10^9 方針 このままだと数えづらいので、下記2つの数を数えることにする。 A：X[j] - X[i] ≦ D かつ X[k] - X[j] ≦ D …

C - 部分文字列と括弧 概要 '('と')'からなる長さNの文字列Sがある。1 ≦ i 制約 1 ≦ N ≦ 10^5 方針 i文字目からj文字目までのSの部分文字列が括弧の対応が取れていることを確認するためには次のことが成り立てばよい。 ポインタpを準備、p=0と初期化 S[i]か…

D - Three Letters 概要 英小文字・英大文字からなる文字列AiがN個与えられる。英小文字・英大文字からなる3文字の文字列の中で、N個の文字列のうち最も多くの文字列の部分列（連続でなくてよい）になっているものを答えよ。なお答えが複数ある場合は、辞書…

C - 菱型カウント 概要 R行C列のマスがあり、各マスにはoかxのいずれかが記入されている。 整数Kが与えられる。次のような(x, y)の組(R ≦ x ≦ R + K - 1, C ≦ y ≦ C + K - 1)の個数がいくつあるか答えよ。 |i -x| + |j - y| ≦ K - 1を満たすi, j については…

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が使え…

E - Virus Tree 2 概要 N頂点の木を下記の要領で塗り分ける。塗り分けにK色まで使えるとき、塗り分けの通り数を求めよ。(mod 10^9 + 7 して出力) 2つの異なる頂点x, yについて、xとyの間の距離が2以下ならxとyは異なる色で塗られる。 制約 1 ≦ N, K ≦ 10^5 …

E - Cell Distance 概要 N行M列のマス目にK個コマを置く。すべてのコマの置き方について、下記の合計を求めよ。 コマ1が(x1, y1)、コマ2が(x2, y2)、… 、コマKが(xK, yK)に置かれたとき、1 ≦ i 制約 2 ≦ N * M ≦ 2 * 10^5 2 ≦ K ≦ N * M 方針 行、列独立に考…

E - 連呼 概要 "A"をN個、"B"をM個含むN+M文字の文字列のうち、次の条件を満たすものの通り数を求めよ。(mod 10^9+7して出力) 開始文字が"A"、終了文字が"B" 文字列中に"AAA"を含む 制約 1 ≦ N, M ≦ 10^5 方針 Comb(N, K)は2項係数を表す。 「文字列中に”AAA…