JOI2023/2024 一次予選～本選 参加記
一次予選
一回目に出たはいいものの、二回目と三回目は見事に絶起してしまった。そんな…
二次予選
予選前
去年も本選に進出していたので今年もさすがに通るだろと思ったが、さすがに怖かったので少し精進をした。
本番
Aを見る。問題文に書かれている通りにやるとACが出る。(1:26)
Bを見る。難化しすぎでは？と思ったが、方針自体は二分探索+累積和なので実装をするとこれもAC。(10:50)
Cを見る。問題文にdpをしてくださいと書いてあるのでdpを書いて提出するが、最後の小課題が合わない。(33:21)
よく考えるとINFの値を小さくしすぎていたので、修正すると見事にACが出る。(40:32)
とりあえずDとEをみて今後の戦略を立てる。特に何もなかったのでDを先に考えることにした。
とりあえず小課題3までは分かったので、後の小課題を考える。
明らかにインパクトが強すぎる小課題4/5を考えたが何もわからなかったので、満点解法を考えると、小課題3の解法を改善すればいいだけだとわかった。(斜めの差分を考えれば二次元累積和+二分探索が使える)
しかしあまりにも実装が面倒なのと、間に合わない気がしたので楽な方法を考える。ここで、この状況や求めたいものが明らかにこの問題に似ていることを考えれば、同様の解法で解けそうだと思ったので実装をすると一発ACが出る。(1:22:42)
Eを考える。パスの場合を考えると、絶対値の和の最小化になり、これは中央値を見ればいい。この考察があっているかどうかの確認として小課題3だけ解けるコードを提出してACを得る。(1:43:41)
一般のグラフの場合を考えると、パスの長さが重要であることが分かるので、拡張ダイクストラを書くが、バグが起きたのか小課題1/2しか取れなかった。(2:24:37)
バグを修正したが、小課題1/2/4しか通らない。(2:41:55)
通り方からしてNが大きいときにWAが出ているので、どうせまたINFの値の設定ミスかオーバーフローだと思い修正すると最後の小課題以外が取れる。(2:42:30)
よく考えると、実はダイクストラはいらないことがわかり、急いでdpを書く。すると無事に満点が取れた。危ない…(2:59:05)
終了後
満点をとれたので喜んでいたが、TLを見ると満点が続出していてそんな…になってしまう。
Pakenの中二は自分含め4人が本選に出場できることになった。
本選進出者が発表されたが、地区賞を取れていない。最高点を取った人の中から2人ランダムに選ばれるらしい(そんな…)
本選
本選前に何回かバチャを走った。ある回では満点を取れたので、かなり自信がついたはいいものの、その後あまり精進をせず、JOI本選の日が来てしまった…
Day1
自己紹介動画を見る。先輩が猫耳を付けていてびっくり。
そして交流会だが、去年や2年前は比較的ヒューリスティックに近いものが出たので、ことしも同じような問題が出ると予想したが、暗号解読×競プロという異色のテーマだった。
結果としては8位だったが、とても面白い内容だった。某さんが終了5分前くらいに最後の暗号が解けたらしく、人の力ってすげ～になる。
交流会終了後はGartic Phoneをした。
Day2
前日のABCで爆死してしまったが、気持ちを切り替えて本選の問題を解く。
A問題を見る。最初最大値を総和と誤読してしまい、やめてくれ…となってしまった。とりあえずコードを書いて提出すると小課題2/3しか取れない。(18:57)
またINFの値を小さくしすぎていた。さすがにこれは灰コーダーレベルのやらかし。とりあえず修正してAC(24:10)
問題文を見る。とりあえず始点と終点からダイクストラをすれば、座圧+平面走査+BITで解けるとわかる。(実は、もう少し考察をすればこれはいらないとわかる)またやめてくれ…となったが、仕方がないので実装をすると0点が出る。(1:13:00)
なんどか修正するが解けないので、とりあえず小課題2/3を解くコードを投げるが、またしても0点。ダイクストラの部分を見ると、ダイクストラの部分でオーバーフローが発生していたり、INFの値を小さくしすぎていたり、n^2の部分でオーバーフローを起こしたりしていた。とりあえず修正してACするが、かなり焦る(1:39:15)
Cを考える。とりあえず嘘っぽい貪欲が思いつくが、いったん後回しにしてDを見る。
Dを見る。必要十分条件をエスパーした結果、小課題1-4が取れる。(2:37:42)
そうすれば、小課題5も簡単に解けるので、小課題5を解くコードを書いて、小課題1-5を取る。(2:44:28)
Cに戻ったが、本当に何もわからない。とりあえずbitdpを書いて一部の小課題を通す(3:24:41)
Eを見る。小課題1/2はグラフの最短経路に帰着できるので、実装をすると小課題1/2が解ける。(3:45:15)
最後にCを見る。どうせ区間dpだろと思い、実装をするが、間に合わず…
終了後
結果は298点だった。去年は199点でギリギリBランクを逃したのだが、今回も300点に2点足りないということで、ボーダーが300点で落ちてしまうのではないか…などと思ったが、参加者の点数を見るとまだ春合宿のチャンスがあるのではと思い、希望を持った。
しかし、解説を聞いたところ、Cのbitdpより先の部分をとっている人が多く、また不安になってしまう。とりあえずARCもあるので、気持ちを切り替えて準備をする。
結果としては春合宿に進出できることができたが、Bでかなり時間を使ってしまったこと、Cで後半の小課題を全く取れなかったことは反省すべきであり、とても悔しい。
春合宿はオンサイトなのでかなり楽しみではあるのだが、春合宿最下位、などになってしまっては嫌なので、今後も精進を継続していきたいところ。（最近、オンサイトコンテストが増えてきていて非常に嬉しい）
この記事が気に入ったらサポートをしてみませんか？