概要 長さ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}のケースを考える。このとき該当する部分列…

Problem - C - Codeforces 概要 N項の数列a, bがある。a, bに含まれる要素はあわせて2N個であるが、このうちN個は1からNまでの整数で、うちN個は全て0である。aを手札、bを山札とし、次の操作を繰り返す。 手札から1枚選び、山札の底に入れる。その後、山札…

Problem - D - Codeforces 概要 n項の数列aと整数kが与えられる。aをk個の連続する部分列に分解し、f(i)：i番目の項が属する部分列の番号とする。Σai * f(i)の最大値を答えよ。 制約 1 ≦ k ≦ n ≦ 3 * 10 ^ 5 |ai| ≦ 10^6 方針 数列の後ろからの累積和s(k) = …

概要 整数Lが与えられる。下記の条件を満たす非負整数の組(a, b)がいくつあるかを求めよ。(mod 10^9+7 して出力) a+b ≦ L a+b = a xor b 制約 1 ≦ L 方針 a + b = a xor b ⇔ a & b = 0 ⇔ a, bの2進表記でどちらも1となる桁がない（繰り上がりがない）下記の…

D - プレゼント 概要 N項の数列HとWが与えられ、N個の箱の縦の長さと横の長さを表す。箱iと箱jはHi 入れ子にすることができるか。 制約 1 ≦ N ≦ 10^5 1 ≦ H, W ≦ 10^5 方針 Hが全て異なる場合は、H・WのペアについてHを昇順に並べた後、WのLISの長さが答え。…

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

B - ABC 概要 A, B, Cからなる文字列がある。この文字列の部分文字列のうちABCの部分をBCAに変える操作を好きなだけ行う。操作が行える最大の回数を答えよ。 制約 1 ≦ |s| ≦ 200 000 方針 ①前から順に操作したいが、次の例のように後ろを走査した後に前が再…

A - Kenken Race 概要 横一列に並んだNマスがあり、マスAとマスBにはコマが置いてある。マスAのコマをマスCに、マスBのコマをマスDに移動できるかどうかを判定せよ。ただし、以下の条件がある。 コマは右に1マスもしくは2マス移動できる 移動先のマスが壁'#'…

Problem - C - Codeforces 概要 0以上m未満の整数からなるn項の数列aが与えられる。 各項にmod mで最大x回1を足すことで、aを非減少数列にすることできるとき、最小のxを答えよ。 制約 1 ≦ n, m ≦ 300 000 方針 すでに問題を言い換えている。xを決めうつこと…

Problem - B - Codeforces 概要 1以上n以下の整数(ai, bi)のペアがm個与えられる。同じペアのai, biは異なる。 整数x, yを適切に選ぶことにより、「全てのペアについて、ai, bi の少なくとも1つがxまたはyと等しい」という状態にできればYESを出力し、そのよ…

E - Roadwork 概要 数直線上の座標0にQ人の人がいる。人iは時刻Diから数直線上正の向きに毎秒1ずつ進む。 数直線上ではN回の工事が行われており、工事iでは時刻Si-0.5から時刻Ti-0.5の間、座標Xiが通行止めである。 人iは最初に通行止めにあった時点で停止す…

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 方針 行、列独立に考…

令和ABC初回。残念ながらunratedでした。F - XOR Matching 概要 整数M, Kが与えられる。長さが2^(M+1)の数列aで下記を満たす数列が構築できる場合、その数列を1つ出力せよ。できない場合-1を出力せよ。 要素に0, 0, 1, 1, ... 2^M, 2^Mをもつ a[i] = a[j] と…

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 方針 回転…

B - LRUD Game 概要 H行W列のマスにコマが1つおいてある。先手と後手はそれぞれ'L', 'R', 'U', 'D'からなる長さNの文字列をもっている。 先手と後手は交互に文字列の先頭から、文字が表す方向にコマを1マス動かすことができる。また動かさなくてもよい。 コ…

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 - へんてこ辞書 概要 N頂点N辺の有効グラフとN項の数列bが与えられる。各頂点から出る辺は1本であり、b[i]は頂点iから出ている辺を表す。 頂点aからスタートし、k回移動した後にいる頂点番号を答えよ。 制約 2 ≦ N ≦ 10^5 1 ≦ k ≦ 10^100000 共通方針 この…

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 方針① いろい…

C - GCD on Blackboard 概要 N項の数列Aが与えられる。この数列のうち1項を好きな数字に変えて数列全体のGCDを計算する（数字を変えなくてもよい。）。GCDの最大値を求めよ。 制約 1 ≦ N ≦ 2*10^5 1 ≦ A[i] ≦ 10^9 全体の方針 数字を変更する項を固定する。 …

SoundHound Inc. Programming Contest 2018 -Masters Tournament- D - Saving Snuuk(400) D - Saving Snuuk 概要 n頂点m辺の連結無向グラフが与えられ、各辺には2種類のコスト（コストA, コストBと分類）が与えられる。 頂点sから頂点tに移動するコストを考…

CODE FESTIVAL 2017 qualB C - 3 Steps(500) C - 3 Steps 概要 N頂点M辺の連結無向グラフに、「長さがちょうど3の経路をもつ2頂点間に辺を追加する」ということを繰り返す。追加できる辺の最大値を答えよ。 制約 2 ≦ N, M ≦ 10^5 方針 最終的に、奇数長の経…

D - Handstand 方針 反転する区間は0が続いている区間のみを考えてよい。 すると問題は、0が続いている区間をK区間ずつ1に反転していって、1が連続する区間が最大になるものを求めればよい。これは尺取り法でO(N+K)で求めることが出来る。 感想 下記ブログを…

B - 花束 概要 赤い花がR本、青い花がB本ある。次の2種類の花束を好きなだけ作るとき、2種類の花束の合計の個数の最大値を求めよ。 赤い花がx本、青い花が1本の花束 赤い花が1本、青い花がy本の花束 制約 1 ≦ R, B ≦ 10^18 2 ≦ x, y ≦ 10^9 方針 2分探索を使…

D - Cake 123 概要 X項の数列A、Y項の数列B、Z項の数列Cがある。 A、B、Cからそれぞれ1項ずつ取り出して和を求めるとき、その和が大きい順にK個出力せよ。 制約 1 ≦ X, Y, Z ≦ 1000 1 ≦ K ≦ min(3000, X * Y * Z) 1 ≦ Ai, Bi, Ci ≦ 10^10 方針 Ai + Bj + Ck…