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 - Cell Inversion 概要 正整数Nに対し、BとWからなる長さ2 * Nの文字列が与えられる。 この文字列の異なる2文字を選び、その間の文字を反転する(B->W, W->B)操作を繰り返す。 「全ての文字を1度ずつ選んで文字列に操作を行い、操作後の文字列が全てWとなる…

C - Time Gap 概要 0からNまでの番号が付けられたN+1人について、番号1～Nまでの人の住む都市の時刻は、番号0の人（高橋君）の時刻と比べて差がDiある。 このとき、N+1人の時刻の差の最小値のうち、ありうる最大値を答えよ。 制約 1 ≦ N ≦ 50 0 ≦ Di ≦ 12 方…

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 については…

C - Blue Bird 概要 N頂点M辺の無向グラフについて、頂点0から少なくとも1つの辺を通り、かつ同じ辺を通らずに再び頂点0に戻る経路のうち、最短の長さを答えよ。 制約 1 ≦ N ≦ 300 方針 頂点0と０を含む辺を除いたグラフでワーシャルフロイドする。 その後、…

概要 0, ..., N-1と番号付けられたN個のハスが横一列にならんでいる。現在ハス0にいる。 正の整数A, Bを選び、0, A, A - B, 2 * A - B, 2 * A - 2 * B, ...の順番で対応する番号のハスを行き来し、最終的にハスN-1に到達したい。ただし、同じハスに2度行くこ…

概要 整数Nが与えられる。高橋君、青木君の二人ゲームを考える。 ・最初の整数を1とする。 ・現在の整数をxとするとき、プレイヤーはxを2xもしくは2x+1に置き換える操作を交互に行う。 ・先手は高橋君 整数がNを超えたとき、最後に操作を行ったプレイヤーを…

B - PackDrop 概要 頂点番号が0～N-1である、N頂点の根付き木がある。根は頂点0。また葉がM個あり、i番目の葉の頂点番号をBiとする。 各辺に機器を置いてゆくことを考える。このとき根0から葉Biの間の辺には機器が合計でCi個あるようにし、かつ各辺に置く機…

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