友のすなる日記というものを、我もしてみむとてするなり。
はじめまして。大阪大学で物理やらなんやらをやってるあじゃじゃです。
趣味は競技プログラミングで、AtCoder、Codeforces、Codechefの三つをjutenという名前でプレイしています。
これから毎日、飽きるまで日記を書きます。
飽きたら週記にする予定です。
なぜ日記を書くのか
なんか学科で流行ってると友達から聞いたからです。ほんとかは知りません。
何を書くのか
競技プログラミングの精進の記録とお勉強の話が主になると思います。時々友達と外出するのでその時はその話をするかもしれません。
2024年11月13日(水)
今日は毎週水曜恒例激重レポートの提出日だったので前日の20:00くらいから仮眠を二時間ほどとってレポートに取り組んだ。幸い今週は最初の問題を乗り越えてしまえばあとは簡単な線形代数の証明と計算だったので二時間ほどで終わらせることができた。
しかし徹夜するつもりで仮眠を妙な時間をとったせいで、課題が終わって暇を持て余しているにもかかわらず寝ることができないまま朝を迎え、そのままだらだらとテスト勉強をしたりシャワーを浴びたりしていたらあっという間に午後の大学の講義の時間になっていたため歩いて登校した。
最初の講義は毎度激重レポートを出す講義のテスト前最終講だったのだが、レポート提出のために徹夜をするせいで講義を聞けず、余計に次のレポートが苦しくなるという悪循環からは最後まで逃れられなかったななどとウトウトしながら考えていたら気づいたら終わっていた。
その次の講義はプログラミングの演習だったが、僕が非情報系の学科で学んでるのもあってか、毎回パソコンを５分ほどカタカタしたら終わる程度のものなので人にちょっかいを出したり友達のデバッグを手伝ったりして過ごした。
家に帰って晩御飯をちゃちゃっと作って食べた後、競技プログラミングの問題を一問解いた。というわけでここから先は解いた問題の話だ。
本日の一題
解いたのはABC315-Fだ。difficultyは1674。競技プログラミングをしてない人のためにdifficultyについてちょいと説明すると、difficulty1600というのはレート1600くらいの人の五割がコンテスト中に正解したという意味なのでレートが1000くらいの僕がぼーっと考えるにはちょうどいい問題なのである。
問題を一目見るとdp[現在地][飛ばした点の数]=最小コストというテーブルを貼れば解けるように見えるのでそんなに難しいものじゃないように見える。しかし、当然レート1600というのはそんな初心者に毛が生えた程度の人間でもできるような考察ができるようになったらなれるようなものではなく、当然この問題もそれだけでは解くことができない。問題は点の数Nが最大10000個であることで、飛ばした点の数0～N-1回すべてを確認していると1億回も計算をするはめになってしまい、制限時間をオーバーをしてしまう。
じゃあどこの計算回数を減らせるか考えなければならないわけだが、ここで注目すべきは点を飛ばした時のペナルティがとっても重いことだ。
問題文のペナルティについての記述だけ下に抜粋する。
ただし、通らなかったチェックポイントの個数を Cとして、以下の通りペナルティが課せられます。
・C>0なら2^(C-1)
・C=0なら0
通常のコストが点同士のユークリッド距離の和であるのに対して、ペナルティが指数オーダーで増えるならば、通らないチェックポイントの数は10000個も調べる必要はない。そんなに飛ばすくらいなら、全部ちゃんと通ったほうが早いに決まってるからだ。
ほんとに？と思う方もいるかもしれないがユークリッド距離の最大は問題の制約から雑に見積もっても最大で10万くらい。距離10万のぺあが1億対あろうが当然2の1万乗よりはるかに少ない数になる。なんなら2の60乗くらいで十分だ。なので飛ばす点の数を最大60個に絞り計算回数を60万回程度に抑えれば低速な言語でかなり雑に書いても正しい答えを求めることができる。
実装含めて大体50分かかった。(提出はこれ)
この問題は僕がとても苦手としてる動的計画法の問題なのに、割とスッと解くことができてうれしかったので今日の一問とさせてもらった。
この調子で、毎日一問から二問は問題を解いていきたい。
長くダラダラとした文章になってしまいましたが、読んでくれた人はありがとうございました。また明日。