F - Must Be Rectangular! 概要 2次元平面上にN個の点がプロットしてある。i番目の点の座標は(x[i], y[i])と表される。以下の操作を可能な限り繰り返す。 次のような任意の4か所(a, c), (a, d), (b, c) , (b, d)のうち、ちょうど3か所に点がプロットしてある…

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] このとき、全ての試合が終わるまで必要な日数の最小値を求めよ。なお、制約下で総当たり対戦ができない場合は-…