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

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の要素の…

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) = …

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を出力し、そのよ…