結果
順位 109th / 5557 パフォーマンス 2266 レーティング 1872 → 1918(+46)
全完できたのでかなりパフォーマンスが良い値になった。余計な誤答がなければ100位以内になったかもしれなかったが、F問題を解けたのも運っぽいのでこんなもんだろう。
A - 9x9
場合分けをする。よく見たら1以上という部分は制約にあるのでそこは不要だったのか。そこを省けるなら3項演算子で書く長さだったな。
B - 81
forループを書きます。
C - Walk on Multiplication Table
すぐには解法がわからなくて一瞬おや？ って思ったけど落ち着けばまで考えて約数ですねと。約数列挙特有の
の場合分けが要らなくて気分が良かった。
D - Water Bottle
もうね、頭が全然回らないのでこういう問題をサッと処理できないんですよ。入力例が親切で露骨に場合分けをしなさいというメッセージを発しているのに最初は混乱していてなんか入力例1のような場合だけを考えていて「あれ？ が角度を求めるときに必要にならないぞ？」みたいなことを考えていた。
ちゃんと場合分けを考えてからもatan2がよくわからなくて普通のatanに戻ったり、弧度法と度数法の変換で頭おかしいことをやっていたりと、かなりひどかった。
さらにプログラムの最初の方でstd::coutにstd::setprecisionを指定するときに、手癖でstd::endlも流してしまって1WA。全ケースWAという表示を見たときの驚きといったら！
E - Gluttony
まず答えは二分探索で求めそうというのはパッと思いついて、後は判定部分をどうするか。降順にソートした食べ物から見て、担当する人を二分探索で見つければ良さそうという解法を書いたが、1ケースを残してTLEという前回の悪夢が蘇る結果に。懲りないものでまたよくわからん高速化をして提出したらむしろTLEが増えて、しかし増えるということは時間制限すれすれなのだということがわかり、つまり時間制限が本当に改善でなんとかなりそうということだと判断した。
毎ループ回std::multisetを構築していたのを、外部で1回構築してループ中ではコピーして利用するようにしたら通った。解説PDFを見たら、この二分探索は不要で先頭からマッチさせていくだけで良かったのか。考察が足りなかった。
F - Fork in the Road
気持ちとして大きいコストに繋がりそうなところを塞ぎたい。塞ぐことを考えない場合はDPで単純にコストは求まって、を求めるときには「遷移確率 ×
」を足しこんでくるわけだけど、遷移確率は一定なのでこの
が一番大きいところへの遷移を塞ぎたくなった。DPテーブルを構築していくときに部屋
から進める部屋
で一番コストが大きいものを記録していって、あとでそれを除いてみてDPをやるということを
回やれば全体で
で通るという仕組み。
しかし自分でコードを書いたときはループの形が3重になるので、「あとで除いてみてDPを回」ところでかかる計算量が
になっていると思いこんでいた。「TLEだろうな〜」と思って投げてみたら通ってしまい、通った後に冷静に考えれば
だった、みたいな。TLEになると思いながら提出するのもよくわからないし、計算量の見積もりを間違っているのもアホなので怪我の功名でしかない。
