トップ > プロコン > ABC208

ABC208

プロコン

面白かった。めちゃくちゃいいABCだな。Eは桁DP部分が嫌い。

A - Rolling Dice

範囲内は全部作れる。

B - Factorial Yen Coin

かなり難しい見た目。C問題風。硬貨の額面が変わってるけど、どの2種類の硬貨を選んでも倍数の関係になっているのがポイント。普通に大きいものから使っていけばいい。なんか提出時には深く考えてなかったけど1種類の硬貨の最大使用枚数は10未満だ（倍率が2倍から10倍までなので）。10!円のが何枚使うかわからなかったのでwhileで適当に回した。

C - Fair Candy Distribution

これ好き。ここまで簡単でそこそこ楽しいじゃん、ほんと好き。floor(N/K)をまず配る。aをコピーしてソートしてN%K番目の値を使い、a_iがそれより小さかったら1枚渡す（渡す回数は0回からN-1回）。

D - Shortest Path Queries 2

これはちょっと面食らう。どんな方法で計算すればいいか色々考える。当然ワーシャルフロイドも浮かぶが、ライブラリのコードを見るとなんかこの問題に使えそうな形をしている（笑）。とりあえずサンプル合わしてから考えたけど、考えれば考えるほどこの問題文とこのコードは同じ意味だ（「s,t および番号が k 以下の都市のみ」を使っている）。よくはわかってないけど提出してAC。ド典型なのに面白くて、ワーシャルフロイド法の使い方ではなく中身を教えてくれる教育的な問題だ。これがABCか。

E - Digit Products

なんでKが小さいんだろうと思って見ていたが、なるほどDFSを書いて調べてみると桁の積としてありえる10^9以下の値は5195通りしかない。あとは桁DPみたいにする。具体的には、[1, 9], [10, 99], [100, 123] のように分けてそれぞれ数える。しかし実装が難しく、unordered_mapを使うか二分探索で5195通りのインデックスを求めるかで迷い、後者を選ぶも残り10分を切ってKを超えてから0を掛けて0になるケースの見落としに気づき死亡。せっかく面白いセットだったのに、この実装がコンテスト時間の大半を占めており非常に残念な感じに。桁DP的なやつの面白さがわからない（いつもの分け方でできるし実装が面倒だし面白くないと思う）。

（追記）


F - Cumulative Sum

手で少し計算してみてM=1でさえ（K乗の和になって）普通には解けないことに気づく。少し考えて、最低限のヤバさは感じたとしてEに専念した（Eから戻ってくることはなかった（そ、そんな））。