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

Problem - C - Codeforces 概要 N項の数列が与えられる。この数列はもともと1からNまでの数字の順列であり、かつ任意のiに対しi番目の項はiではない。 現在この順列は一部が欠損しており、欠損部分が0となっている。この順列を復元せよ。ただし、いくつかの…

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

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 - Cell Inversion 概要 正整数Nに対し、BとWからなる長さ2 * Nの文字列が与えられる。 この文字列の異なる2文字を選び、その間の文字を反転する(B->W, W->B)操作を繰り返す。 「全ての文字を1度ずつ選んで文字列に操作を行い、操作後の文字列が全てWとなる…

概要 0, ..., N-1と番号付けられたN個のハスが横一列にならんでいる。現在ハス0にいる。 正の整数A, Bを選び、0, A, A - B, 2 * A - B, 2 * A - 2 * B, ...の順番で対応する番号のハスを行き来し、最終的にハスN-1に到達したい。ただし、同じハスに2度行くこ…

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とする。…

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