ECR150-F Monocarp and a Strategic Game

問題

https://codeforces.com/contest/1841/problem/F (diff: 2700)

街には人間、オーク、エルフ、ドワーフの 4つの種族が住む予定だ。始め街には誰もいない。

N個の移住プランが与えられる。 i個目の移住プランは人間、オーク、エルフ、ドワーフがそれぞれ a_{i}, b_{i}, c_{i}, d_{i}人移住しようとしている。あなたはこの人達を全員受け入れるか拒否するかを決定する。

街の幸福度を (人間の数 - オークの数)^{2} + (エルフの数 - ドワーフの数)^{2}とする。幸福度としてありうる最大値を求めよ。

制約

  • 1\ \le\ n\ \le\ 3\times 10^{5}
  • 1\ \le\ a_{i}\ \le\ 10^{9} (他も同様)
  • TL1秒
続きを読む

ECR150-E Fill the Matrix

問題

https://codeforces.com/contest/1841/problem/E (diff: 2200)

n行 n列の行列がある。始め i列目の 1行目から a_{i}行目のマスは黒く、 a_{i + 1}行目から n行目のマスは白く塗られている。各マスには値が決められていない。

あなたは、この行列から m個の白マスを選んで 1から mの値を割り当てる。

(i, j)に kが、 (i, j + 1)に k + 1が割り当てられるような kの数は最大で何個になり得るか求めよ

制約

  • 1\ \le\ n\ \le\ 2\times 10^{5}
  • mは白マスの数を超えない
続きを読む

ECR150-D Pairs of Segments

問題

Problem - D - Codeforces (diff: 2000)

区間の列 ( (L_{1}, R_{1}), (L_{2}, R_{2}), \dots, (L_{n}, R_{n}) )は次の条件を満たすとき、またそのときに限り「良い列」と呼ぶことにする。

  • nが偶数
  • 共通区間を持つ要素同士に辺を張ったグラフを考えると、これが各連結成分のサイズが 2の \frac{n}{2}個の連結成分になる

n個の区間を与える。最小何個の区間を消去すれば良い列にすることが可能か求めよ

制約

  • 2\ \le\ n\ \le 2000
  • 0\ \le L\ \le\ R\ \le\ 10^{9}
続きを読む

ECR151-E Boxes and Balls

問題

https://codeforces.com/contest/1845/problem/E (diff: 2500)

N個の箱が横一列に並んでおり、各箱は空 a_{i} = 0またはボールが一個入っている a_{i} = 1。あなたは以下の操作を丁度 K回行う。

操作: ボールが入っている箱と空箱を一つ選ぶ。これらは隣接している必要がある。選んだ箱に入っているボールを空箱に移す。

操作後の箱の状態についてあり得る通り数 \mod 1000000007を求めよ。

制約

  • 2\ \le\ N\ \le\ 1500
  • 1\ \le\ K\ \le\ 1500
続きを読む

ECR152-F XOR Partition

問題

https://codeforces.com/contest/1849/problem/F (diff 2700)

非負整数の集合 Sに対して、 Sのスコアを Sの相異なる二要素のxorとしてあり得る最小値とする。ただし、 |S| = 1の場合スコアは 2^{30}とする。

相異なる N個の整数 a_{1}, a_{2}, \dots, a_{N}を与える。二つの空集合 S, Tを用意し、各 a_{i}をどちらか片方に挿入する。 \min(Sのスコア, Tのスコア)としてあり得る最大値を達成する操作方法を一つ求めよ

制約

  • 2\ \le\ N\ \le\ 2\times 10^{5}
  • 0\ \le\ a_{i}\ \lt\ 2^{30}
  • TL7.5秒
続きを読む

ECR152-E Max to the Right of Min

問題

https://codeforces.com/contest/1849/problem/E (diff 2300)

長さ nの順列 pが与えられます。以下の条件を満たす pの連続部分列の数を求めてください

  • 最小値を取る場所が最大値を取る場所より真に左にある

制約

  • 1\ \le\ n\ \le\ 10^{6}
続きを読む