B - Two Contests 概要 Ｎ個の区間[Li, Ri]が与えられる。この区間を2つのグループに分け、それぞれのグループごとの区間の共通部分の長さの和の最大値を求めよ。 制約 2 ≦ N ≦ 10^5 1 ≦ Li ≦ Ri ≦ 10^9 方針 maspyさんのブログを参考に考察を進めたい…ので…

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

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

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

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

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

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

令和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] と…

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

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