MtSakaのブログ

競技プログラミングをします

JOI2023/2024 春季トレーニング 参加記

参加記

JOI2023/2024春季トレーニングに参加しました。結果から言いますと四日間総合8位で代表にはなれませんでした。

本選

正直結果が良くなかった。そのせいで参加記とかを書く気が起きていなかったので書いていないしもうあんま覚えてないので言うことがない。なんとか通過はした。

春合宿まで

難易度11を中心に解いていてあとは意図的に残していた2020/21春を四日間バチャをした。結構良かった。
春前の感触としては上位6とかにいて代表争いをしているだろうというイメージでいた。そういう場合のイメージトレーニングみたいなことをしていた気もする。

Day0

practiceでN=1000のワーシャルフロイドやるだけがずっとTLEして解決せずに終わりちょっと心配だった。(が、結局本番で定数倍で死ぬことはなかったのでまあヨシ)

ここから問題のネタバレがあります




Day1

結果から言うと9-0-12 計21点 同率24位(実質下から二番目)だった。
この日は絶望の一言。まだあまり思い出したくないのでちょっと忘れたころに詳細を書くつもりです。とにかく後半2時間の記憶が全くというほどない。
家に帰って雛鶴 あいみたいに大泣きした。

結果的に、心を入れ替えてDay2以降取り組むマインドに切り替えることができた。

Day2

boardgame

小課題1~4は丁寧に状態を考えて解くことができた(この時すでに自分の中ではO(N2/K)に落ちていた)
あとはK<=100さえ解けば平方分割で解ける！と思い考察するとプレイヤー2~Kのコストは傾き1,2の半直線であることには気づくがうまく言語化ができず後半の疲労感の中考察していたのもあり、迷走してしまいちゃんと詰められなかった。(反省)
結局小課題1~4だけの36点

tricolor

全くと言っていいほど考察が出なかった。こういうパズルは一生苦手だと思う。5点しか回収できなかった。頑張ったら15点はいけたなあと思ったが40,50点を取っている人が理解できない...

vegetables5

この日問題を見て一番解けそうだと感じた問題だったので一番最初に取り組んでいた。
小課題1~3を回収した後は難しい考察をあまりせずに20分~30分で O(Nlog(N)log(A)) の満点想定を思いついた。
とにかく添え字を合わせるのが不快だが、添え字を合わせる以前にTLEが出て絶望した。結果的に他の問題を回収した後に最後に再び取り組んで、軽い O(Nlog(N)log(A))でもなんとか通せる小課題4だけ取れた。この後最後の5分とかで添え字を合わせた解が出来上がり、提出するがTLEしてかなりつらくなった。
解析で単調性を利用してlower_boundのlogを尺取りすることで落としたら満点が取れた。10分くらいしかかかってないので他の問題に割いていた時間をこれに割けば...と思ったがもう遅い。

36-5-67 計108点 Day2単体3位と割と良い結果となった。

Day3

collection

最初に見た問題で、初手の考察で O(N^{3}M)の区間DPに簡単に落ち、Nの次元を一つ落とせば一気に38点入るため頑張って区間dpの改善を考えた。考察をしたが大胆予想をするしかないと考え大胆予想をして実装するがWAで撤退した。結果的に最初の一時間をこれに浪費してしまった。

joitour

問題を真面目に考え始めた時点で時間が微妙に残っており、満点特攻するなら特攻するくらいの時間しか残っていなかった。HLDを使って根へたどっていって情報を更新すればいいことには気づいていたが、情報量が多すぎて頭の中でそれを管理する方法がうまく思い浮かばなかったため結局部分点をちまちま回収することにした。
部分点自体はそれほど難しくなく、丁寧に実装して52点を取れた。ただ、中途半端に時間が余った。

tower

この日の三問で一番解きやすそうに見えた。段数/時間のグラフを考えて非連続になる点を考えるという方針でやると区間を管理するテクだけで割と簡潔に書けた。ただこの考察にいきつくまで紆余曲折しており、実装も結構バグらせて時間がかかった。
何度も提出してなんかいつの間にか満点が取れた。ついに初の満点である。

11-52-100 計163点 Day3単体2位でDay2,3だけの成績だと1位だった。総合も8位まで舞い戻った。これでDay1で底辺にまで落ちた自信がちょっとだけ取り戻せた気がする。ボーダーとは80点以上差があったので厳しいなあと思ったがワンチャンを狙える位置ではあった。

Day4

escape2

ようやく実家が出てくれたという感覚になった。絶対に満点を取るという強い意志でダブリングを実装し、平方分割をして満点が取れた。ただ実装に無駄に時間がかかった。ちゃんと鍛えていたはずだが三日間の疲れが予想以上にあったのだろう。

island

面白いパズルで今までのどの日のcommunicationと比べても取りやすいだろうと思った。ただ、全然うまく線形回のクエリに落とせなかった。
結局クエリ数は(次数の最大値)*Nくらいしか実装できず50点。
人々の満点解法がきれいすぎてびっくりした。こういうのは解ききりたかった。

tabletennis

解の上界の評価をしてその結果をもとに3すくみの個数を頑張って山登りとかすれば解が割と高速に求まるんじゃないかと読んで実装したが評価からうまく行かず失敗してしまった。
最後20分くらいはなんとかN<=20を埋め込むでもして23点だけでも自明部分点以上を回収しようと思い、頑張ってコードを回したがそもそも間に合わなかった。

100-50-9 計159点 単体8位(多分) 総合8位(合計451)

結果的には昨年度と同じ順位まで追い上げることができた。すべてはDay1が悪いが、そこからの修正力には自信を持ちたい。
来年は代表になります。頑張ります。