JOI23/24の参加記です。春合宿です。雑です。躊躇なくネタバレします。
また、記憶の捏造があるかもしれません*1
春合宿前
特段特殊な精進はしてなかったはずです。難易度10を少し埋めたり遅延セグ木の空書きとかはしました。
というので、本選前よりは精進してないと思います。
Day0
交流会
いろんな人と話しました。楽しかった。
紙でタワーを作る大会がありました。この積み方で思ってた数億倍安定してて笑いました。*2
JOI交流会にて pic.twitter.com/hSmAkExcod
— Yuk. (@Yuk3u) 2024年3月20日
プラクティス
実機を触る練習をしました。一応しっかり書き留めておきます。
1問目
入出力高速化をするだけです。scanfとprintfは嫌なのでios::sync_with_stdio(false);cin.tie(nullptr)でどうにかしました。
2問目
愚直にやっても間に合うという話はどこかで聞いたのですが、なんか80点しか取れんかった。
周り全員ちゃんと満点かと思いきや、80点の仲間が少しいて安心しました。*3
3問目
恥ずかしい話をすると、解けませんでした。馬鹿かな？
スタックに積む、よく考えたらそれはそうで泣く
周りに煽られまくりました*4
4問目
コミュニケーションの練習をするだけです。
知らなくていいC++: std::minmax_element #ゆっくり解説 - YouTube をやります。
5問目
コミュニケーション(ry
長さ16以下の01文字列は217-1個あるので、AliceとBobで同じ方法で生成して、数字を対応させればいいです。
6問目
どうみても巡回セールスマン問題です。適当な山登りで88点。これ以降はめんどくてやってません。
Day1
コンテスト中
開始し、適当に問題を流し読む。fish3とspy3の題意は理解したが、ski2は訳が分からなかった。fish3は自明部分点の64点がとれるめどが立つ。
VSCodeの設定をするが、F5キーの設定ができない。20分くらい格闘したが無理で、諦めて手打ちでなんとかすることにする。
fish3を実装する。当初の予定通り64点を手に入れる。ただ、その先はわからずspy3を考える。
とりあえずすべての辺の重みを送る8点解法は自明。各クエリごとに各辺を使うか使わないかを送るのを考えたができる気がせず*5、仮にできたとしても20点程度でコスパが悪い。というわけで、ski2に戻ってみる。
考えると、4乗っぽいDPが浮かぶ。各地点の標高をたかだか1mしか上げないことを仮定すると3乗になったため試しに実装したが、サンプル1の時点で嘘だった。
そうなると、高さを保留する必要があることに気付いて、そうすると3乗か怪しくなってしまう。いったんは実装して提出するが、答えが全く合わない。いろいろ試すが、真相はINFが大きすぎてオーバーフローしていただけだった。直すと最後の小課題以外は取れる。しかし、最後の小課題はセグフォっていた。
4乗になりそうだったが軽いことは確信したので、いろいろ調整する。そして、満点を獲得した。
fish3の満点が思い浮かぶ気がしなかったので、いったんspy3の8点を確保する。しかし、その後の成果はなかった。
64-8-100、合計172点で終わり。
コンテスト後
順位表が配られました。5位(!?)でびっくりしました。適当に緩く楽しむつもりだったのに、真面目にやらないといけなくなってしまいました。
ただ、fish3の満点が取れなかったことが悔しかったです。意外と簡単だった…
Day2
コンテスト中
とりあえず問題を流し読む。昨日と違ってどれも可能な見た目でない。とりあえず天才ゲーっぽいtricolorを考える。
F5キーで実行できるようにするのはあきらめて、それ以外を設定した。compile.shがただコピペするだけのものに見えていたが、それをたたくとコンパイルできることに気付いてびっくりした。
暫く考えて、隣り合う2つのライトをうまく光らせれば0,1,2のどれも表せることに気付いた。左端が奇数か偶数かわかれば解けそうだったが、その方法がわからず諦める。
boardgameを少し考えたが17点しか取れるめどが立たない。まだしっかり考えてないvegetables5を考える。
とりあえず愚直を書いて、ソート順にマッチングしていいことを確信する。小課題4について考えると、答えで二分探索すればその中で二分探索して行けそうであることに気付く。なんなら満点も取れそうだったが、実装が破滅しそうだったのと、大きさが相違なる制約がないのがめんどくさそうで諦めた。
小課題4を1時間くらいかけて書く。恐ろしいほど実装が重かったが、何とか書き上げて提出。しかしTLEが出る。
中で4回二分探索していたのだが、それを半分にすると間に合う。答えを合わせるために、1回の二分探索で2つの条件について調べることにした。すると何とか通った。
とりあえず、boardgameの10点を取ろうとした。しかし、3点しかもらえない。原因を探したが見つからない。諦めてtricolorに逃げた。しかしtricolorもわからず、適当な15点くらいの解法を投げるが1点も入らず終わってしまった。
3-0-67、合計70点というかなりお粗末な点数となってしまった。
コンテスト後
だいぶ絶望してたのですが、なぜか順位は1つ上がって4位(!??)、なんと代表圏内に入ってしまいました。
ごはんが一番おいしい日でした。*6
Day3
コンテスト中
いつも通り問題を流し読む。どれも絶妙に解ける見た目をしていて困る。
とりあえずcollectionを考える。しばらく考えて、各数を「目標の数」「それより大きい」「それより小さい」とまとめることでO(N3)の区間DPが思いつくが、そんな小課題はなくて困る。いったん飛ばすことにした。
towerを考える。A=1,B=Dをとりあえず解くことを考えると、頭が壊れそうだが前から順番に更新できそうだった。いったん書いてみて、答えを合わせる。しかし1ケースだけ通らなかった。表示の場所的にそれは小課題1だと考え、小課題1を書くとなんと通ってしまった。
joitourを考えてみると、いかにも愚直を書いてくださいと言わんばかりの小課題たちが待っている。とりあえず書いて20点。
そしてパスグラフはセグメント木に乗せるだけなことに気付いた。頑張って空書きして通す。
もう時間がなかったので、collectionのN<=20を通す。towerの嘘解法を書いて無事0点が帰ったところで終わり。
11-36-30、78点。昨日よりはいい点数だったので、まあ大丈夫だろうと思っていた。
コンテスト後
順位表が配られました。すると、6位に落ちてしまっていました。それだけならまだしも、5位と50点程度の差がついてしまい、逆転できるわけないと絶望しました。fish3の36点とboardgameの14点を悔やみ始めました。
自分もほかの人たちも、上位5人の争いになると考えていたと思います。
双子たちが最終日で100点差が覆った話をしていました。ただ、実力差がありすぎて自分がそれをできるとは思っていなかったです。
いろんなボードゲームをしました。楽しかった。
Day4
コンテスト中
なんとかして50点以上の差をつけないといけなくて絶望するが、とりあえず問題を読む。すると、なんか全部解けそう。
とりあえず、islandを考える、3Nまでは思いつきそうだったが、確信が持てない。いったんescape2を見てみる。すると、どう考えてもダブリング。左から行くだけだと計算量にMがかかってまずいが、両方からやってメモ化するとルートが付きそうで、満点をとれるめどがたった。
とりあえず左からだけやって、想定通り54点を得た。大変だったが、右からも書いて満点。
islandを書く。すると、N2までしか取れなかった。それを適当に枝狩りすると、3Nに落ちてくれた。しかし、2Nをかけるめどは立たなかった。
tabletennisを考えるが、きれいな性質が思いつかない。上界もわからない。しかし、山登りすればなんかN<=20とかは行けそうな気がしてきた。
そこそこバグらせたが、N<=20を通した。すると、結果を見るとN<=150が通せそうだったので、いろいろ調整して150まで通した。
そのあとは何の成果もなし。
100-72-62、234点。ワンチャンは見えた。
コンテスト後
順位表を見る前に、周りの人にネタバレされました。3位だったので、解析の時間にひっくり返らなければ勝ちでした。めっちゃびっくりしました。
解析でひっくり返ることもなかったので、代表が確定してしまいました。うれしい。
ところで
非負整数*7真面目にやります。を
進法で表したときの各桁の数字の和を
とします。
- 田園都市線、平日の朝だと怖いくらい混むぞ
- 準急は論外としても、各停ですらだいぶ混んでるよね…
- 満員電車だし池尻大橋駅で誰も降りないし運悪くドアと反対側にいたしで降りるのが間に合わないかもしれなかった、なんとか降りれたが…
- 流星コネクト ver2023 by Losstime Life - YouTubeって神曲ですよね、ずっと脳内で流れてた
- ピュレグミ美味しい
- ラムネグミのシート、食べれるんだね
- SET セットカードゲーム | ANALOG GAME INDEXっていうボードゲームをとあるチューターの方が持ってきてたんですが、めっちゃ楽しかった*8
おわりに
楽しかったです。IOIもがんばります。
