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…