ACPCVC20200617 復習メモ - tinumu's reminder

https://kenkoooo.com/atcoder/#/contest/show/8292b88e-c34a-4b53-bf9a-396ec14abd4d
考察はゆっくりやっていたが、チーム戦で冷静にできるかな…？

A - 五目並べチェッカー

まずお互いの碁の数がおかしくなってたらダメなのでその判定をする。
不正がないと言えるのは、まだどちらも勝利条件を満たしていないか、現在のターンで勝利条件を満たしているかのどっちかである。
まとめると、「 $1$ ターン前において考えられる碁の配置において、全ての状況で勝利条件を満たしている」と、現在のターンに来ることはないので不正があると言える。
そのため、 $1$ ターン前を再現して、その全てに置いて勝利条件を満たしているかを試せば終わり。これは計算も $19^4$ よりは小さそうなので普通に間に合う。

B - 合コン大作戦

男性について要求年収が低い人から見ていく(そのようにソートしておく $i < j$ ならば $B_i \leq B_j$ のような数列にしておく)。

例えば $1$ 番要求年収が低い人は $2$ 番目の男性の要求年収より低い女性たちに対して独占できる。
ここでマッチングを見つければ、その人たちは取り除いても良さそう。

もしここでマッチングを見つけられなかったら、 $2$ 番目の男性も含ませて、 $3$ 番目の男性の要求年収より低い女性たちに対して見てみる。
これは $3$ 番目の男性以降の人には全く関係のない女性たちである。
ここでどちらかのマッチングを見つけたら、できるだけ年収の低い男性を選んでおくと、のちのち男性が選ばれやすくなるはず。

この状態では $1$ 番目の男性も $2$ 番目の男性も要求年収について無視できるし、候補の女性たちについても自分の年収については無視できるので、単純に女性が適切な男性を選んでいくだけで良い。

このようにしてここで選ばれなかった男性たちは、また次の男性を入れて、同じようなことを繰り返していくと最適であることがわかるので、
男性は要求年収で昇順にソート、女性は自分の年収で昇順にソートしながら、男性の年収を multisetで管理しながらしゃくとりのようにやっていくと、この問題を $\mathrm{O}((N+M) \log N)$ ?で解くことが出来る。

ちょっと解説の言語化が難しい(というか解説できてないよねこれ)

C - 増築王高橋君

選び方は明らかにコストが小さいものから選んでいくと最適なことはわかる。
現在選んでいるコストが大きくなれば、もちろん増築回数も増えることになるので、単調増加な性質がある。

現在選んでいるコストを $c$ にすると、建物 $i$ について、何回増築したかというと、 $\displaystyle \left\lfloor \frac{c-A_i}{D_i} \right\rfloor +1$ 回であるため、実施回数は $c$ を決め打ちすると求めることが出来る。すると、 $\mathrm{O}(N)$ で合計で何回増築したかが分かる。

そのため、 $c$ で二分探索することを考える。
$K$ をぎりぎり超える増築回数 $k$ になるコスト $ansc$ が求まると、 $K$ 回増築した場合のコストは、
$\displaystyle \mathrm{simulate}(ansc) - (k-K) \times ansc$ となりこれが答えとなる。
ここで $\mathrm{simulate}(ansc)$ とは、現在 $ansc$ までのコストを見ているときの合計の増築コストを意味していて、現在見ているコストというのがわかっていれば、それぞれの数列の和もちゃんと $\mathrm{O}(1)$ で出てくるので全ての数列に適応した $\mathrm{simulate}$ 関数は $\mathrm{O}(N)$ の計算量になる。ちゃんと $\mathrm{simulate}$ 関数を実装して、この問題を $N \log (KD_{\max})$ で解くことが出来る。

ちなみに $\mathrm{simulate}$ 関数の実装時に計算順序に気をつけないと64bit符号付き整数型でもオーバーフローするところがある。
最大の答えになるケースは多分

だと思うのだが、これ、 $K=10^8$ のために $1$ 番目の数列に $10^8$ 回適応するわけだが、
ここでの数列の和は $\displaystyle KA_1 + \frac{D_1 \times K(K-1)}{2}$ になる。

ここで、着目すると、 $D_1 \times K(K-1) = 9999999900000000000 \geq 2^{63}$ である。
だが、 $\displaystyle \frac{D_1 \times K(K-1)}{2} = 4999999950000000000 \lt 2^{63}$ であるのでできるだけ早く $2$ で割っておきたい。
考えてみると、 $K(K-1)$ は偶数になっているのですぐ割れる。ここを先に割っておけばオーバーフローせずに計算できる。
でもたぶんこれ unsigned long long で十分な気もするな

感想

あんまりこの段階で言うことじゃないかもしれないけど、問題を与えられたら、ちゃんと頭でイメージする必要がありそう