Codeforces Round #643 (Div. 2) - ferinの競プロ帳

A

15:30
証明が全然できないけどみんなめっちゃ通していく
仕方がないのでK回普通に漸化式を計算して0が含まれたら終了にした
未証明

B

30:41
全員どこかしらに入らないといけないんだと思って1ペナ
あと普通に実装が下手なので強い人のをあとで見る

下のが一番簡単かなあ

sort(ALL(a));  
ll l = 0, ans = 0;  
REP(i, n) if(a[i] <= i+1-l) ++ans, l=i+1;  
cout << ans << endl;

C(1回目)

$x+y \gt z$ になる組を数えるのと同じ
$z$ を固定 → $x$ を大きくすると取れる $y$ が1ずつ増えていく
等差数列の和なので算数するとサンプルすらあわない

D

1:01:20
解かれてるのでDに移動
明らかにYESをつくれるパターンとして 1 1 … 1 (残り) で残りがnより大きければ k=(残り)-1 とする

s < 2n のときを考える
1がいっぱい出てくる
どう頑張ってもNOのパターンをつくれない

未証明で投げた
提出

1 2 2 … 2 みたいなのを考えると $n$ に対して $s$ が最小でNOのパターン
これ以上2を分割しても $s \leq 2n-1$

C(2回目)

1:36:02
もうちょっとちゃんと整理する
$z$ を固定して、 $x$ を変化させたときの取れる $y$ の個数を考える

$x$ が小さい → $x$ が大きいに移動するにつれて、 $y$ の個数は以下のように変化する
$0, 0, \ldots, 0, 1, 2, \ldots, c-b+1, c-b+1, \ldots, c-b+1$
この列の $x=a$ から $x=b$ の部分の和を高速に求めたい

$f(p) = ($ この列で $p$ 以下の部分 $)$ の和が求まればよい
$1$ がでてくる位置と $c-b+1$ がはじめて出てくる位置を計算する
3分割された区間のうちどこに $p$ が存在するか？で場合分けして、「0の部分」「等差数列の部分」「 $c-b+1$ の部分」それぞれを計算する

提出

$z$ 固定じゃなくて $x+y$ を固定すると簡単
$\text{imos} \lbrack i \rbrack = (x+y=i$ となるような $x,y$ の組が何個あるか $)$ を計算する
これは $a \leq x \leq b$ について区間 $\lbrack x+b, x+c \rbrack$ に+1すればできる
あとは各 $x+y=i$ について $i \gt z, c \leq z \leq d$ となるような区間の共通部分を求めて足せばよい

E

$A+R \lt M$ だったらmoveをする必要はない、逆に $A+R \geq M$ だったらmoveできる限りするべき

揃える高さ $X$ を固定したときのコストを考える
$X \gt h_i$ となる $h_i$ について $v_0 = \sum (X-h_i)$ の分ブロックを足す必要がある
$X \geq h_i$ となる $h_i$ について $v_1 = \sum (h_i-X)$ の分ブロックを削る必要がある
$\min(v_0, v_1)$ の分moveして、それでも揃ってない分をaddかremoveをする

問題は $X$ の候補が多いことでどうにかして減らしたい
時間がなかったので $X=h_i$ に限定できるのかと思って試すけどサンプルが通らない
$|v_0-v_1|$ が小さいところが答えじゃね？と思って三分探索を書いたけど落ちる

冷静に考えて変なことしなくても $X$ とコストについて凸性がありそうだしもっとシンプルっぽい
残り30秒なので終了です

三分探索の初期値のinfがでかくてオーバーフローしてたのが原因で1行直したら通った…
積がある場合は $10^9$ 以上の値がそこに入らないように気をつける！
提出
 整理して書き直した提出

全体的に実装方針が悪かったり、誤読してたり、証明できなくて悩んでたりかなり微妙…

F

小さい方の素数を何個保持しているか？をクエリで特定する
大きい方の素数に関してはわからないが、誤差の条件から2個程度素数を見逃していたとしても問題がない

まず含んでいる素数の集合を特定する。これは $10^18$ 以下でできるだけ多くの素数をかけ合わせた数をクエリとして投げることで実現できる。次に含んでいる素数 $p$ に対して、 $p^k \leq 10^9$ となる最大のものをクエリとして投げることで、素数 $p$ を何個含んでいるか特定することができる。

ここまでで紹介したクエリの投げ方で677以下の素数に関しては特定できた
これで誤差の条件に当てはまる答えを必ず出力できることを確認する

特定した部分の約数の個数が1個
677よりも大きい素数は高々3個しか掛け合わせられないので、特定していない部分は1個～8個のいずれかになる。4を出力しておけば絶対誤差の制約を満たす。
特定した部分の約数の個数が2個
同様に、特定していない部分は1個～8個なので9を出力する。
それ以外の場合
特定した部分は4以上となる。このとき、特定しない部分は1個～4個のいずれかとなるので2倍した値を出力しておくと、相対誤差の制約を満たす。

以下のような流れで考察すると早いのかなあという想像

小さい方の素数の特定に気づく
素数の特定方法として効率のいいものが上のパターンであることに気づく
前半・後半でクエリの個数の分配を考える
$10^9$ 以下の数は素因数を高々9個しか持たないので、クエリの後半パートは5個クエリを使えば足りる。前半は17個クエリを使える。
特定できる素数の大きさから誤差の条件を満たす解を出力できることを確認する