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

D - Digit Sum Replace 概要 ある数Xの十進表記が与えられる。次の操作をXが1桁になるまで行う。 十進表記で任意の隣り合う2数をその和で置き換える 操作可能な回数の最大値を求めよ。ただし、入力は2つのM項の整数列c1, c2, ..., cM, d1, d2, ...dMを用いて…

概要 N頂点の木が与えられる。各辺に色を付けて塗り分けることを考える。同じ頂点から出ている辺に同じ色がつかないように塗り分けることとしたとき、必要な色の種類の最小値と塗り分けの方法を1つ出力せよ。 制約 2 ≦ N ≦ 10^5 方針 色の種類の最小値は、各…

C - 広告 概要 R × Cマスのグリッドが与えられる。グリッドは . か * で構成される。 . のマスに広告を配置させることを考える。ただし、広告は他の広告と上下左右で隣接しないように配置したい。 配置できる広告の最大値を求めよ。 制約 1 ≦ R, C ≦ 40 方針…

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 …

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を使う…

F - Must Be Rectangular! 概要 2次元平面上にN個の点がプロットしてある。i番目の点の座標は(x[i], y[i])と表される。以下の操作を可能な限り繰り返す。 次のような任意の4か所(a, c), (a, d), (b, c) , (b, d)のうち、ちょうど3か所に点がプロットしてある…

B - Sorting a Segment 概要 0からN-1のN個の整数の順列Pと整数Kが与えられる。この順列を用いて下記の操作を行った後にできる数列の種類数を答えよ。 順列Pの連続するK項を昇順に並べ替える 制約 2 ≦ N ≦ 2 * 10 ^ 5 方針 昇順にするK項の最初の各項につい…

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

Problem - D - Codeforces 概要 整数集合Bが与えられる。1から始まる全ての整数をグラフの頂点と考え、|i - j| ∊ B であれば、iとjに辺を結んでいく。 このときできるグラフを2部グラフをするために、Bから要素を消去することを考える。消去すべきBの要素の…

E - Second Sum 概要 1からNまでの数字の順列Pが与えられる。1≦ L 制約 2 ≦ N ≦ 10^5 方針 各L, Rについて2番目に大きい項を逐一探しに行くと計算が間に合わない。あるP[i]が何回足されるかを考える。 P[i]が足されるときのL, i, Rの関係としては、P[L]からP…

概要 下記の制約があるNプレイヤーの総当たり対戦を考える。 各プレイヤーは1日1回しか試合できない プレイヤーiがj番目に対戦する相手はA[i][j] このとき、全ての試合が終わるまで必要な日数の最小値を求めよ。なお、制約下で総当たり対戦ができない場合は-…

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

F - Absolute Minima 概要 関数f(x)が与えられる。関数f(x)は最初f(x) = 0の定数関数である。 クエリがQ個与えられるので、それに従い操作する。クエリは下記2つ。 更新クエリ："1 a b"の形で与えられ、f(x) 求値クエリ："2" の形で与えられ、f(x)の最小値を…

F - Colorful Tree 概要 N頂点の木が与えられる。辺iは頂点ai, biを結び、色ciがついている。また辺の長さはdiである。 Q個のクエリが与えられる。クエリiではxi, yi, ui, viが与えられ、下記の問いに答えよ。 色xiの辺の長さがyiになったとき、uiからviまで…

E - 迷路 概要 N×Mのマス目が与えられる。マス目は迷路となっており、#が壁を表す。 長さKの文字列dが与えられる。この迷路はこの文字列に従って進むことが出来る。具体的には、文字列はU, D, L, Rの文字から成り、i秒後にi % K + 1文字目の命令に沿って迷路…

D - IntegerotS 概要 N項の整数列A, Bと整数Kが与えられる。数列Aiからいくつかの項を選び、それらの項すべてについてのbitwise orがK以下であるとき、対応するBiの和の最大値を求めよ。 制約 1 ≦ N ≦ 10^5 0 ≦ K 0 ≦ Ai 1 ≦ Bi ≦ 10^9 方針 Aiの全ての組み…

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

C - Successive Subtraction 概要 N項の数列Aが与えられる。これらの数列が黒板に書いてある。次の操作を繰り返し行い、最終的に黒板に書いてある数字が1つになった時の数字の最大値と、その数値を与える操作を出力せよ。 黒板の数字を2つ選び、x, yとする。…

E - Hopscotch Addict 概要 有向グラフが与えられる。始点Sから終点Tまでの経路で長さ3がの倍数のもののうち最小のものについて、その長さを3で割ったものを出力せよ。（けんけんぱで移動できるか） 制約 2 ≦ N ≦ 10^5 0 ≦ M ≦ min(10^5, N * (N - 1)) 方針 …

概要 2以上の整数Nと整数Kが与えられる。このときN頂点M辺の無向グラフで下記のものが存在するかどうかを判定せよ。もし存在するならそのグラフを出力し、存在しないなら-1を出力せよ。 グラフは単純かつ連結 グラフには最短距離が2であるような頂点対(i, j)…