AtCoder ABC123 参戦記 - cplusplusonly's memo

AtCoder の ABC123

に参戦しました。

過去にないほどさくさくと解けていき順位は 89 位! パフォーマンス 1600 で水色になりました。
AtCoder 始めるときに「自分はたぶん水色やろうな」と思っていて到達できたのでうれしいです。これからも精進して青色目指します。(次の ARC でへぐって緑色に叩き落されそうですが...)

f:id:y_r:20190406230440p:plain

感想

A 問題

問題文が長い。「隣り合うアンテナが通信できないとき」と誤読していて WA 叩き出しかけた。危ない...

B 問題

$sum(xi/10*10) - 10 + min(xi(mod 10))$ で楽勝だろ! と思ったら手元で WA 出した。実際は時間が 10 の倍数になっている料理は最後に注文してはいけないのです。危ない...しかし...

C 問題

明らかに律速するのは一番キャパシティーが少ない工程だから $max(n/xi)+ 5$ で楽勝...と思いきや WA。よく考えると割り切れるときは次の便を出さなくてよい。
これは B 問題で出したバグと同じ原因だった...

D 問題

最初は A, B, C についてソートして大きい数からとっていけばよい？と思っていたが明らかにめんどくさい。というか机上ですらよくわからない。
方針を変更して (A+B+C) を全部用意して大きいほうからとっていくことにする。これは最大 $10^9$ 通りだが、 (A + B) をとったところで大きいほうから K 個以外は捨ててよいので最大計算量は (A + B) : $1000*1000$ , (A+B+C) : $1000*1000 + 3000*1000$ で間に合うはず。
実装中いくらかバグを埋め込んでデバッグに追われたがこの方針で AC。
類題はけんちょんさんの AtCoder 版！蟻本 (初級編) - Qiita 冒頭にあった JOI 本線 C ダーツ。これを解いてなかったら (自力では LTE が取れなかったので解説 AC) 発想できなかったと思う。

解説を見ると解法がいろいろある模様。(自分の解法は一番計算量が多い)。ひとつひとつについて理解しておきたい。

結論

割り算とか、剰余を取るときは割り切れるときがコーナーケースになりやすい。仕事でも何回かこれでバグ出している。