J - Leveling 概要 H×Wのグリッドが与えられる。各グリッドには非負整数A[i][j]が書かれている。 隣接するグリッドを通って左下マス⇒右下マス⇒右上マスに移動することを考える。このとき、各マスに移動する際は移動先のマスの数字分コストがかかる。ただし、…

D - Swap and Flip 概要 カードがN枚ある。i番目のカードの表面には1以上の整数A[i]が、裏面には1以上の整数B[i]がそれぞれ記載されている。 最初、全てのカードが表面を上にして置かれている。この状態から次の操作を好きなだけ繰り返し、見えているカード…

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

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 …

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となる…

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

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の全ての組み…

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

J - GCD β 概要 整数のペア(Ai, Bi)がN個ある。各ペアから1つずつ整数を選び、選んだN個の整数の最大公約数を計算することを考える。計算されうる最大公約数の最大値を求めよ。 制約 1 ≦ N ≦ 5 * 10^4 1 ≦ Ai, Bi ≦ 10^9 方針 最初のペア(A1, B1)のうちどち…

E - Enumerate Xor Sum 概要 長さNの数列Aが与えられる。i=1, …, Nについて(A1 xor X) + (A2 xor X) + … (Ai xor X)を出力せよ。ただし、X = A1 xor A2 xor … xor Aiとする。 制約 1 ≦ N ≦ 3 * 10^5 0 ≦ Ai 方針 2進けたごとにみていくとうまくいく。各2進け…

D - Decode RGB Sequence 概要 押すと押した箇所がRGBという文字列になるスタンプがある。このスタンプを好きな回数押して与えられた文字列が作れるかを判定せよ。ただし、スタンプがはみ出るような押し方はできない。 制約 3 ≦ N ≦ 10^5 方針 難しい。貪欲…

D - Two Piles 概要 A枚のコインの山とB枚のコインの山がある。次のルールで2人ゲームを行い、最後に操作した人を勝者とする。先手勝ちならYes、後手勝ちならNoを出力せよ。 2山のうちコインがある山を一つ選ぶ。その山のコインの枚数をX枚とする。 各山から…

D - DivRem Number 概要 整数Nが与えられる。このときN以下の整数mで、Nを割った時の商とあまりが等しいものはいくつあるか。 制約 1 ≦ N ≦ 10^12 方針 N以下のすべての整数を試すことはできない。 Nをxで割った時の商をr、あまりをqとすると、N = rx + qと…

Submission #5371956 - diverta 2019 Programming Contest 概要 N個の文字列sのすべてを好きな順番に連結し、連結した後の文字列から'AB'という部分文字列がいくつ含まれているかを数える。すべての連結方法を試したときに、各連結方法で含まれうる'AB'の個…

E - Exclusive OR Queries 概要 長さNの数列Aがある。Q個のクエリが与えられるので、それに解答せよ。 i番目のクエリではLi, Ri, Xiが与えられる。AのうちLi以上Ri以下のすべての項のXORを答えよ。またその後、Li以上Ri以下のすべての項をXiにする。 制約 1 …

Problem - D - Codeforces 概要 円周上に等間隔でn個の点があり、いくつかの点同士が線で結ばれており、その辺の数はm本である。 この図形が回転対称(rotationally symmetrical)であるかどうかを判定せよ。 制約 2 ≦ n ≦ 100 000 1 ≦ m ≦ 200 000 方針 回転…

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

D - Modulo Operations 概要 N項の数列Sと整数Xが与えられる。Xは黒板に書いてある。 N!通りあるSの順列のそれぞれについて、黒板に書いてある数をmod S[i] して黒板に書き直すことを繰り返してゆき、最後に黒板に残った数字を足してゆく。合計を求めよ。 (m…

C - Snuke the Wizard 概要 N個のマスが直線状に並んでいて、そのマスにはアルファベットが記載されている。また各マスの上には一体ずつゴーレムが配置されている。Q個の命令があり、命令iはマスのアルファベットに対応するアルファベットtiと、"L"（左）か"…

C - ロト2 概要 N項の数列Aと正整数Kが与えられる。 Ai * AjがKの倍数であるような(i, j) (i （以降、aがbの倍数である、すなわちbがaを割り切ることをb | aと記載する） 制約 1 ≦ N ≦ 200000 1 ≦ Ai ≦ 10^9 1 ≦ K ≦ 10^9 方針 まず考えられるのはすべての(i…

D - Deforestation 概要 竹がN本ある。スタート時の長さはすべて0であり、時間が1経過することに全ての竹の長さは1増える。 M回の伐採があり、i回目の伐採時は時間Tiに行われ、番号LiからRiの竹が伐採される。 伐採されても時間が1経過することに全ての竹の…

C - Come Together 概要 H * Wマスのすべてのマスに1個ずつコマが置いてある。そこからK個のコマを取り除く。 その後全てのコマについて、縦または横に隣接したマスに動かす操作を繰り返し、ある1マスにコマを集めることを考える。 このとき、最小の操作回数…

D - Ears 概要 長さLの数列Bを準備しておく。値はすべて0。数直線上に0, 1, 2, ..., Lの点がある。 上記点の好きな場所からスタートし、隣接した点を移動してゆく。 i-1からiに、もしくはiからi-1に移動するとB[i]が1加算される。 これを好きなだけ繰り返し…

C - When I hit my pocket... 概要 ビスケット1枚、お金0円でスタートし、以下の操作を好きな順にK回繰り返す。 ビスケット1枚増やす ビスケットA枚減らし、お金1円増やす お金1円減らし、ビスケットB枚増やす K回の操作後のビスケットの枚数の最大値を答え…

D - Restore the Tree 概要 頂点の有向根付き木がある。 この木に本の辺を追加する。ただし追加する辺をとすると、はの祖先でなければならない。 追加された辺を含む全ての辺が与えられたとき、各頂点について元の根付き木における親を出力せよ。 制約 方針 …

概要 項の数列とが与えられ、二人でゲームを行う。 先手が数字iを選ぶと全体の得点に加算され、後手が数字iを選ぶと全体の得点から減算される。 先手は全体の得点を最大化、後手は全体の得点を最小化させたい。 二人が最適に行動するとき、全体の得点の最大…