AtCoder Beginner Contest 231 反省

なんか解ける問題ばかりが現れてうまくいった。

結果を鑑みて

2600 83:20

54位。rated内では4位。青落ち黄色だからrated内4位と言ってもそんなでもないかも。最近研究関連でごたごたばっかりだったのでメンタルがぐちゃぐちゃだったけどなんとか精神統一できた。

A - Water Pressure

やる。ひっかけがないかびくびくしながら提出した。

B - Election

なんか既視感がある。試験管difficultyの頃の問題で出てたかも。Counterでやるだけ。

C - Counting 2

身長の同じ生徒がサンプルにないのがちょっとこわい。bisect_leftを使う。

このあたりで順位は400位ちょっとくらいだった。ひとつひとつ確認しながら解いていたが、なんとなく今回は速解き回だったりしないだろうか？と思ったりした。そうなるとちんたら解いてたら危ない。

D - Neighbors

閉路があるとまずいと思った。一瞬、二部グラフかな？とか考えたけど閉路だけが問題らしかった。

サンプル２を見ると、次数の制約に気付く。これでたぶん必要十分だろうと思ったが、順位表でペナっている人を見つけてちょっと念入りに確認してから出した。

この時点で100位ちょっとだった気がする。

E - Minimal payments

わっかんね〜こんな問題があったかもしれないなと一瞬思ったけど思いはどこかへ飛んで行った。

上から貪欲にやっていくタイプか？とか考えたけどお釣りがどうにも扱いづらい。

結局F→G→Eで最後に解いた。

ある硬貨で支払った時に残り支払う金額がマイナスになったら、マイナスになった分はおつりになる、ということに気付いた。「おつり　桁dp」とかでぐぐってABC155-Paymentにたどり着いた。

Paymentは上の桁から見ていってギリギリの金額で支払うか、ちょっとだけ多めに支払うのが最適という戦略らしかった。

今回の問題で、硬貨の金額をxとして、X-xが負になるなら、-(X-x)<Xの時に限りお釣りをとったとして（すでにお釣りで考えているなら本来支払うべき金額として）遷移することにした。

計算量に自信はなかったが、剰余を取りながらXを小さくしていっているのでお釣りはよくわからないが計算回数は60回くらいで済みそうだった。

出してなんとか通った。ふう〜

F - Jealous Two

EがわからずFにきた。

問題文がちょっと読み取りづらいが、(a, -b)について二次元ソートしてあげると、i≦jなるindex i, jを使って、a[i]≦a[j]が成り立つからその中でb[i]≧b[j]が成り立てば良いことに気付いた。これは転倒数そのもの。

しかし、サンプル2でa,bペアの値がそれぞれ等しいやつがあると数え漏れが出ることに気付いた。後からこれを補填してAC

この時点で２桁順位だったはず。

G - Balls in Boxes

積の和典型。しかもNの値から、DPでやるタイプだとわかった。

白いボール、黒いボールがあって、箱1個につき黒いボールが1個割り当てられると考える。

O(N^2)が許されているが、dpに何を持たせるか？と考えた時、既に i 個の箱には黒いボールが割り当てられていると考えるのが妥当そうだった。

そこまでいくと、dpである必要はなくて、既に i 個の箱に黒いボールがあるなら N - i 個の箱にそれぞれ黒ボールを割り当てるため、K個のボールのうち N - i 個を黒ボールにして箱にあてることにする。順列の計算は前計算できそうだけどしなくても間に合う。

通すと30位くらいだった　どひゃ〜

H - Minimum Coloring

MCFっぽいけどフローが分かれちゃったりしてうまくいかなかった。

分流してしまってまずいときは双対とって分圧にする　みたいのがあった気がするけど思い出せなかったしそもそも正しいのかわからず。

総括

Fがすぐわかって、Gも積の和だったからよかった。Eで詰まってもじっくり考えれば解ける問題だったし、ABCでは解ける問題を探しに行くのが本質な気がしてきた。

積の和はいままで「積の和だ！」とわかっても解けなかったからうまくいってよかった。フロー も「フローだ！」とわかったら解けるようになりたいね。