JOI2020春合宿 参加記

結果から言うと、5位で代表にはなれませんでした。
以下、日記です。(全てその日のうちに書いたもの)

Day0

朝起きると体調がよろしくない。本選の時もそうだったので情報オリンピックに呪われているんじゃないかと思う。
Library Checkerを埋めて「やがて君になる」を読んでいると夜になっている。
早めに寝付けたものの、1時ごろに目が覚めてしまう。ここ数年でこんなことは一度もなかったので不安になった。

Day1

体調はあんまり変わっていないが、とりあえず5時間はやりきれそうなので出発。
控室が同校率80%とかで面白かった。競技会場に入るとさすがに緊張してきたが、今までの5時間バチャの戦略を思い返して心を落ち着けた。

競技

最初に全部ざっと問題文を読んだ。構築-構築-クエリゲーで、嫌な気持ちになった。
1問目の見た目が明らかに簡単枠なので、絶対に解くという気持ちで考える。
一瞬で判定の方法(未証明)が思いついたが、証明していないので当然構築できない。
緊張もあって1時間ほど進展がなかったので、とりあえず判定が正しいか確認した。"-1"を提出した場合と同じケースがACしていたので、正しいと分かる。(最悪)
これが正しいなら絶対にみんな通すはずだと思い、一度トイレに行って頭を切り替えると、普通に構築できることが分かる。
1時間半で満点。2回目の春合宿にして初めて満点が取れて嬉しくなった。

2問目が不可能枠、3問目が難易度11くらいに見えたので、3問目を考えると、小課題3まで分かる。
どうせデータ構造に強い人間が小課題4を解くだろうと思い、小課題4を1時間ほど考えるが、分からない。
後は部分点回収をしただけだが、3問目の小課題3がWAになり、1時間以上原因が分からなくて焦った。
原因は、二分探索のokの初期値を便宜上0にしていたが、実際は0でOKかどうかは確認しないと分からないというミスだった。こういう時は-1にして、判定関数内で場合分けするようにしたい。
2問目は、K=1の時は遅延セグ木で解けるのでそれで2点を得たが、実際はもっと楽にできるらしく煽られた。

結果・反省

結果は100+2+12=124点で4位タイ。やるべきことをやれたかなという感じ。難易度は10-12-12だと思った。
2:30くらいから部分点回収しかしていないのは、単に「とりあえず取っておこう」で書き始めたものが無限にバグったせいで、後半の時間はほぼ考察ができていない。
おそらくインタラクティブが出た時にも同じようになるので、最初の2時間の考察の集中力を上げていきたい。

Day2

よく休んだら体調がかなり良くなって安心した。代わりに花粉がつらくなり、ティッシュを買いに行ったらなかったので、ラムネを買った。(英断)
ラムネを体に詰め込んでから競技開始。

競技

全部読むと、インタラクティブ-グラフ-数え上げ というセットだった。どれもそれなりに点数が見込めるので、時間配分に迷った。
直感で、2->3->1の順に見ていくことにした。(敗因)
2問目の見た目が過去問と似ており、途中まで似たような考察ができたので、簡単枠だと思って考察をする。
10分ほどで解法(嘘)が思いついたので実装する。実装をサボってまず1点を取りにいった。しかしWA。
実装ミスだと思い、色々書き直したりしていると1時間半ほど経っている。ここで落ち着いて図を書くと、1回の追加で2つ以上マージされる場合があることに気づく。この場合でも17点が取れる正解法がすぐにわかったが、面倒さに比べて点数が少ないと思ったのでやめる。
3問目を見ると、意味不明な数え上げをDPでやれと書いてある。図を書いて観察すると、状態数3^N*NのDPが分かるが、6点しか取れない上に実装が重い。そして多項式時間に落とせそうもない。
この時点で3時間ほど経っていて、まだ1点も取れていないことからかなり焦っていた。そのため、2問目がやっぱり簡単枠なんじゃないかと不安になって何度も2問目と3問目を行き来していた。
結局、2問目も3問目も不可能枠だと信じ込むことにして、それなりの点数を得やすいインタラクティブに行くことにした。

小課題1すら分からないが、先に小課題2,3を考えてみることにすると、嘘考察を交えながらも何とか思いつく。一瞬で実装でき、40点。ここまで3時間半。少し精神に余裕ができる。
小課題4を考えてみる。制約が二分探索をしろと言っているので考えると少し変えるだけだと分かるが、バグらせる。それでも30分ほどで通る。冷静な心を取り戻す。
2問目の17点を実装するか、1問目の満点を考えるかで迷ったが、他の人間が3桁点取っていると思っていたので、代表争いを考えて1問目の満点に行く。
しかし、疲れからか、嘘解法に突っ走ってしまう。結局解けなかったが、その嘘が小課題1に偶然適用できたので、使うと4点が取れる。そしてコンテスト終了。

結果・反省

結果は64+0+0=64点で、Day2/累積ともに3位。順位的には申し分ないが、6位と24点、13位と88点差と、全く安心できない。他の人の失敗に救われた感じはある。
最後の1時間で、2問目の17点を取りに行くべきだった。そこは戦略ミス。
また、最初に2問目の嘘解法の実装に時間を溶かしたのがとても痛い。競技の最初で失敗すると後に響くので、実装は慎重にしていきたい。
1問目を解いているときに、何度も諦めて2問目をやろうかと思ったが、解法に近づいているという感覚を信じられたおかげで耐えられた。大事。
難易度は11-11-12だと思った。もう少し差がつくセットを出してほしい気もするが、抜かされるのは嫌という...。

Day3

行く途中は緊張していたが、競技会場に入ると3日目なだけあって落ち着いた。

競技

最適化-グラフ+データ構造-コミュニケーション というセット。
1問目がとっつきやすそうなので見ると、ちょくちょく良い性質が見つかるが、スルーしてしまう。小課題がDPだと主張しているが、順序付けを色々考えてもうまくいかない。不安だったが難問枠だと信じ、1時間ほどで飛ばす。
2問目は、勘違いをしていて15分ほどで嘘解法を思いつく。幸いすぐ気づいたが、正しい考察をすると、実装量が異常であることが分かる。本質部分が2つに分けられるが、簡単な方のパートの時点で既にヤバいので、最後にやることにする。

3問目を読み始めたのは開始2時間後くらい。すぐに15点解法(嘘)が思いついたが、提出しても4点しか取れない。ただ、15点と85点で完全に問題が分かれているので、一旦飛ばした。
小課題5はすぐにわかったが、面倒なので実装しなかった。
小課題6は、本質的な考察は30分ほどでできたが、実装を始めると、枝分かれで詰むことが分かる。考察ミスだと思って30分ほど考えても分からなかったので、問題文をもう一度読み直すと、見落としていた情報に気づく。
これを利用すると満点が取れることが分かったが、この時点で4時間経っていた上に場合分けが多く、ミスを埋めこんでいた時点で詰むと思った。だが、1,2問目はこの状態からまともな点数を取れる気がしなかったので、これに賭けることにした。
実装しながら場合分けを考えていたので、書き上がったのは残り30分のとき。しかし提出すると0点である。WAケースを探そうと手作りのケースを色々試すと、運良く見つかる。それが合うように直して祈ると、85点が帰ってきて安堵した。
この時点で残り18分で、絶対100点を取るという気持ちで残り11点の考察をする。すると5分ででき、手を震えさせながら提出すると、合計100点になる。安心したので後はお祈りをしていた。

結果・反省

結果は0+0+100=100点で、Day3/累積ともに5位。2人に抜かされた形だが、4位との点差は絶望的なわけではない。
1問目で小課題1すら取れなかったのは完全に実力不足。2問目は3人に解かれているが、正直実装コストを考えると手を出さなくて正解だった。
3問目は、問題文の見落としが痛かった。明日は絶対にないようにしたい。また、場合分けは実装前に詰めておくべきだった。立ち回り自体は悪くなかったと思う。
難易度は12-11-11だと思った。
明日の今頃は代表が決まり、自分のJOI人生も終わると思うと感慨深い。Day4は悔いのないようにしたい。代表目指し頑張りましょう。

Day4

二度寝をしてしまったせいで、競技開始前にあくびがたくさん出た。こういう時にやったバチャは大体失敗しているので、不安になりながら競技開始。

競技

木-Output only-最適化 というセット。
1問目を見ると木の問題で、得意だと思っていたので嬉しくなる。小課題1,2を考えるといくつか嘘を思いつくので実装すると、0点。少し考えてもうまくいきそうにないので小課題3を考える。
すると、また嘘を思いついてしまう。ちゃんと考察すれば満点に繋がる解法だったが、適当すぎたせいで実装しながら頭を壊してしまった。
1時間半くらいで、一度諦めて3問目へ。小課題2までは一瞬で分かるが、小課題3以降は人間に不可能そうな雰囲気が漂っている。
この感じだと1,3問目が不可能枠で、Output onlyで点数を稼がないと代表になれないと思ったので、2問目でまともな点数を取りにいく。

少し考えると、焼きなましが効きそうだと思ったので、山登りのようなものを一旦書く。しかし、多く回すとWAになってしまう。この原因究明に1時間ほど掛けてしまった。提出すると37点。少し改善すると39点になった。
この時点でもう冷静に戦略を考える頭は残っていないので、そのまま2問目を伸ばしに行くが、全く伸びない。
そこで、とりあえず自明な3問目の小課題1を実装しながらプログラムを回すことにしたが、3問目は0点で、2問目は回数を増やしても全くスコアが伸びない。3問目のWAは意味不明だったので2問目と心中することにする。
実は「山登りのようなもの」は山登りになっていないことに残り30分ほどで気づく。しかし、もう自分の頭には肥大化したプログラムをどう変えれば山登りになるのか分からず、気がついたらコンテストが終わっていた。

結果・反省

0+42+0=42点、Day4で9位、累積5位。代表ボーダーとの点差は100点以上開いた。
もうガチでOIをやることはないので特に書くことはないが、受験生となる身としては、大事な日には二度寝をしないようにしたい。

供養

JOI過去問埋め
f:id:TA1SA:20200323172839p:plain
海外OIなど(oj.uz)
f:id:TA1SA:20200323172359p:plain

ポエム

くやしい
受験勉強頑張ります
日本代表を応援しています
PCKはいい成績とれるといいな(誰と組むんだろう)