JOI2020 春合宿参加記
はじめに
春合宿に参加したのは今回が初めてです.
競技中の事とか,忘れない内に記録しておこうと思います.
（順次更新していきます）
Day-14〜Day0
2/27
春合宿の大幅な短縮が決定された. 講義とか,講演とかその他もろもろが中止になった.
この段階では,希望者は自宅から通うのも可能という感じだったので宿泊する気でいた.（緊張感が保たれるため）
3/13
オリセンが受け入れ中止を発表し,東京勢は自宅から通う事になった.
完全に競技単体になってしまい,悲しかった.
Day1 3/20
朝
起床成功.
NTTDATA駒場研修センター8時半集合という,完全に学校と同じだったので実家のような安心感（これだから緊張感がなくなる...）
競技
9時に競技が始まった.
取り敢えず1問目を読む.
小課題が11-100という急勾配だった上,11点が自明DPだったので簡単枠だと悟る.
満点を思いつき,O(N)の怪しいDPを書く.この時,AorBをキーで持たずに1次元DPをしたのがダメだった.このせいで相当遷移が複雑になってしまった.
バグりまくり,2時間経過.これ以上やるとヤバそうなので一旦諦めて次に進む.この時点でかなり焦っていた.
絶対に10人くらい解いているに違いないからだ.（実際,13人解いていた)
2問目の小課題がかなり分かれていて,差のつきどころかと思いきやK=1の自明しか分からない.
1問目も解けておらず,自明の2点しか取れていないので焦りはMAXに達してしまっていた.
2点のまま半分経過.
3問目を読み,得意なセグ木だと分かる. 取り敢えず小課題1,3を実装する.提出すると,0点.
なんでかなーと思ったら誤読をしていた.精神状態が悪すぎる.
適当に直し,出すと小課題1しか取れていない.40分くらい考えていたが,全く理由が思いつかなかった.
後で分かったことだが,セグ木のupdateをchmaxではなくただ単に代入するだけだったのがダメだった.
しかも,競技PCの画面がブラックアウトし,チューターさんを呼んで再起動する羽目になった.絶望的だ.
残り30分になり,まだ3点.こんなに最悪な出来のコンテストが今まであっただろうか？（鉄緑並感）
このままだとマジでヤバイので,取り敢えず1問目の自明DPだけ取った.
残り15分になり,3問目の小課題3のバグ取りをしようとしたが結局直らず,競技終了.
結果はなんと14点,17位だった.実質灰パフォ.
間違いなく,1問目で焦ってしまったのが原因である.
満点を実装しようとしたらバグって死亡という,これまで予選本選でも想定していた最悪のシチュエーションが実現されてしまった訳だ...
昼食など
予想通り周りが1問目を解いていた.
今までオンサイトで冷えたことがなかったので,かなりショックだった.
今まで暖まり続けてきたのが109倍になって返ってきた感じだ.
普通に泣きそうだった.
しかも弁当をゴミ箱に片付ける時に容器をひっくり返してしまい,今日は本当についていないと思った.つらい
帰宅後
バグった1問目の満点と3問目の小課題3を実装.
テストケースを見ながらバグの原因を見つけ,なんとか手元のジャッジで通った.
というか,割と普段からバグった時にテストケース使ってデバッグする時が多いのがダメなのでは?
デバッグが下手過ぎる...
まあ,あと3日間長いので今日の事は一旦忘れて集中して行きたい.
Day2 3/21
朝
普通に起きた.（えらい） 適当に朝食を食べ,適当にTwitterをして出かけた.
Quarantineの検温でkaageが無限にlowを出していて面白かった.
絶対壊れてるので,下手すると基準の37.5℃を上回るかも知れないと思うと怖すぎる...
控室でいつも通りいつもの人と喋っていたら緊張が解けて結構ふわふわしてきた.
これが噂の”相手の緊張を解いて点数を下げる一般的なテク"か,恐ろしい（いいえ）
ホワイトボードに「私語厳禁.『ヤッター！』,『全完！！』,『よし、グラフだ！！』など」と書かれていて面白かった.
類似の言葉に「よく分からんが,サンプル通ったのでヨシ！」があるがこれは大抵通らないので気をつけよう.
割と浮ついたまま競技会場入りした.
競技
昨日今日と4問目があるような事をチラつかせていたので,本当に4問セットなのではとビビっていたが,結局3問だった.
1問目を見ると,インタラクティブだった.
問題設定が「各カメレオンは,ちょうど1匹の,自身と性別の異なるカメレオンを好んでいる.」だったので,後でTwitterで物議を醸しそうだな〜とか思っていた.
小課題1は全員両思いという設定だったので,リア充カメレオン◯ね！くらいに思っていた.
この小課題は組み合わせを全列挙すればOKかな〜と思ったので後で適当にやるとして小課題2を考察した.
1時間半くらいうーんうーんって考えた末,両思いのカメレオン以外は,種類数が1になるのが3組あり,両思いは1組のみであり,この内のどれかに同色のカメレオンがいることが分かった.
後は3組の中から2つ選んでみたいな事をしようとしたのだが,同色以外を選んだ場合と片思い以外を選んだ場合で結果が同じになってしまう事に気づき,絶望.
よく考えれば,両思いではないのだからペアで成立するのは片方のみであり特定できるのだが,血迷って同色のものを3組の中から全探索した.
このせいで小課題3を落としていることになる.（実際,小課題2を取って小課題3を取っていないのは僕だけだった）
小課題2を実装した後で小課題1を考えると,カメレオンの数はNではなく2Nであり,実は間に合わないことに気づいた.
しかし,選んでも種類数が増えないのは1組だけなので単調性が成り立つな〜という事で適当に二分探索した.
投げたら両方通っていて安心した.ここまでで2時間.
次の問題を見ると,これはMaking Friends is Funとほとんど同じ見た目をしている.
Making Friends is Funは難易度9だったし,これも簡単かと思いきや何もわからない.
部分点の配点的にも明らかに簡単問なので,焦った.
何もわからないので30分くらい考えて次の問題に進んだ.
3問目は見た目がO(N3)のDPだが,何もわからない.
取り敢えず今までで各高さをいくつ持ったかという状態数 N*3N のDPを思いついたのだが,成立するかどうかのチェックに時間がかかるなぁになって死んでいた.
残り1時間,何もわからないので2問目に戻った.ここで1問目に戻らなかったのは間違いだっただろう.
ずっと考えていたが,何も分からなかったので自明の小課題1の1点だけ取っておいた.
何も分からず,25点で競技終了.昨日酷い点数だった上に今日25点だったので軽く絶望的だった.
昼食
周りが1桁とかでびっくりした.
順位表を見ると,25点で7位だったので相当やばいセットだったんだな〜と思った.
しかし,昨日の1問目を取れていないので総合では13位,しかも12位とはTAISA_がついていて悲しい（激ウマギャグ）.
明日あたりに難易度10くらいが出てくれれば挽回のチャンスなので出て欲しいなぁ〜
Day3 3/22
朝
いつも通りみたいな感じ,起床成功だと思う. 今日も一日頑張るぞい！をして,適当に競技会場へ向かう.
今日も今日とて渋谷でkaageに会う.（3回目）
しかし,今日はQuarantineを一発で突破していた.面白くねえな...
控室ではE%d氏が作ったCommunication Taskの問題を聞いていた.
HL分解みたいな事をしますみたいな話を聞いてへーとか思いながら,競技会場へ.
競技
また1完もしていないので,今日こそは1完をしようと意気込んでいた.
競技が開始されると,いつも通り1問目から解き始めた.
や,これは結構な簡単枠か〜？と思い考察をしていたのだが,中々解けない.
しかも周りのタイピング音が凄くて,やべぇみんな解いてるじゃん,解いてないのはお前だけという感じだった.
1時間位経過し,適当なDPを思いつく.
これは,同時に残してもいい組に辺を張るとDAGになって,DAG上でDPをするというものだがもちろん嘘だった.
開始から1時間半くらい経過し,ある事に気づく.
これは,同時に残してはいけない組に辺を張り,そのいくつかを残し,得点を最大にする問題に帰着するなぁ...おや,これは...?
†重み付き一般グラフの最大独立集合問題†だ〜！！！ﾄﾞﾝﾄﾞｺﾄﾞﾝﾄﾞｺ
二部グラフならまだしも,これは解けない事が知られているので解けませんになった.
とは言えそんな訳がないので,まあアプローチが違いそう.
という事で諦めて次の問題へ.
2問目を見ると,前の人との差がC以上なら全部取れて,未満ならダメみたいになりそうに見える.
よっしゃぁ1完！と思ったら未満でも前の人がギリギリ取れなかった場合に取れる事があるなぁになる.
しかも小課題2の制約が意味不明だったので,何も分からず3問目へ.
この時点で3時間が経過しており,まだ0点.
3問目を見るとCommunication Taskで,小課題も結構分かれていたので救済問だ〜と思った.
小課題1,2,3が自明だったので取り敢えず実装し,6点獲得.
ついでに小課題4もほとんど同じだったので,更に9点獲得.
ここでもう一度1,2問目に戻るも,何も分からず結局3問目に返ってくる.
小課題5を見ると,なんか無駄に1往復しても大丈夫そうなので適当に葉まで行って戻ってくるような実装をし,5点獲得.
昨日,採点方法がそれぞれの小課題の最大値の合計である事を知っておいて良かった.
これの実装が面倒だったのでまあまあ時間がかかった.残り45分.
もう一度1,2問に戻るがやっぱり何もわからない.
また3問目に戻り,小課題6の考察をする.ここで朝のE%dの問題を思い出す.
もしかして,HL分解...?と思ったが12以下なのでそんな訳がなかった.
そこからも問題を何度も往復したが,結局1点も変わらず20点で終了.
昼食
3問目で小課題6,7を通している人が多くてたまげた.
どうやら長さ6の特殊なビット列を使って根の方向かどうかを判定するらしいが,流石にそんな事が思いつくはずもなかった.
kaageが終了10秒前に3問目の満点を投げて結果が分からないと言っていたらThistle氏などのパ研勢が通るかどうかで賭け（？）をしていて面白かった.
順位表を見ると通っていなかったのだが,blackyukiとかが満点を取っていてやべーになった.
自分はDay1 14点 17位,Day2 25点 7位,Day3 20点 11位,総合59点 16位で未だに3桁すら到達していない.
順位表を見る限り,やはりDay1の1問目を通せなかったのが一番大きかったようだ.
Day4で大成功でもしない限り精神も壊れ、人間関係も壊れ、そして信用も失い、最終的には自殺に追い込まれるかもしれない（引用）ので頑張ろうと思う.
Day4 3/23
朝
起床全完.
電車がめっちゃ混んでいて,なんでーと思ったら今日は平日だった.テレワーク推奨.
平日なので電車の間隔が狭く,kaageとは初めて違う電車に乗った.
defineがいつもの電車にいないぞ、絶起か？
— kaage@JOI春合宿 (@ageprocpp) March 22, 2020
NTTデータ駒場研修センターについても,まだ受付がやっていなかったのでロビーにて待機（ちょっと暑かった）.
今日まで一発で突破してきたQuarantineだったが,今日は...?
「37.9℃...ちょっともう1回測って見るね...37.3℃? もう1回...37℃か,部屋が暑かったからかな」
なんと,一度基準の37.5℃を超えてしまい,マジで終わったかと思った.
まあ,この体温計は壊れていて上下2℃くらいは動くので,しょうがない.
つまり,本当に37.5℃とかあっても何回かやれば突破できてしまうと思う.
めっちゃ眠かったのでコーヒーを一気飲みしてしまった.
競技
1問目を見るとMergersにしか見えないので,HLDかなと思う.
見るからに簡単枠なので考察するが,やはり何もわからない.
パス上の種類数など1時間程色々考えたが,ダメだったので2問目を見るとOutput Only!!!!
流石にやりたくないので3問目へ.
JOI国の国民が全員ウイルスに感染し,その治療計画を立てるというものだがあまりにもホットな話題で面白かった.
全員ウイルスに感染ってどういうことだよ...
治療したものの幅が狭くなっていくというやつだが,かなり面倒そう.
4日間の疲れからか,面倒な実装を避けるようになってしまっていて本当に良くない.
小課題1を見ると適当にRでソートしてSegment Treeを使ってDPをすれば解けるっぽいので適当に実装して通す.
4点のためにセグ木を書くとは...
色々考えたが進展がないので1問目へ戻る.
なんかLCAとかUnionfindで都市をいい感じに併合していく,setはマージテクを使うで行けるかなーとか思い信じる心！で実装したが,200行くらい全部実装し終わった所で嘘に気づく.
Output Onlyに残された時間は僅か40分.
下手に低い部分点取ってないでOutput Onlyを詰めるほうが正解だっただろう.
名前が明らかにこどふぉのLegendary Grand MasterのパクリであるLegendary Dango Makerで笑ってしまった.
もう時間もないので,山登りとかではなくランダム生成の最大値でいいやと思い適当に実装,提出.
なんとか間に合って12点だった.ひえー
昼食
順位表を適当に配ると代表が分かってしまうということで,配られるのはいつもより遅かった.
みんなマラソンで高得点取ってて涙.
まあ山登りすれば結構点数は伸びるよなぁ...
完全に戦略のミスだった.
今日単体は16点,15位だった.
最終結果
Day1 11+2+1 14点 17位
Day2 24+1+0 25点 7位
Day3 0+0+20 20点 11位
Day4 0+12+4 16点 15位
Total 75点 17位
inf回言ったが,Day1の1問目を取れなかったのが一番ダメだった.
結局その89点の差を埋める事ができずに終わってしまった.
来年は極度精進をしてまともな点数を取れるように頑張ろうと思う.
JOI2020本選参加記
1日目
午前
午前中はエクスカーションを楽しむと決めていたので、あまり競技の事は考えなかった。
同期の人々と9時に秋葉原で待ち合わせ予定だったが、みんな早く来たので早く電車に乗れた。
TXには何度か乗ったことがあるが、やはり速い。スピードを上げる時の浮遊感（？）が心地よかった。
40分弱くらいでつくば駅に到着。が、目的地のJaxaまでは徒歩40分と長い。
少し早く着いたので、見学ツアーに含まれないスペースドームに行った。
月の探査機が想像よりもはるかに大きくて驚いた。小さいロボットみたいなのを想像していた。
改めて、恋アスの絵が忠実ですごいなぁと思った。
ツアーの最初は映像を見るのだが、案内の人が「（札が）水色の方どうぞ〜」と言ったらみんな笑っていた（AtCoder）。
宇宙飛行士養成施設で、ガイドさんが「宇宙飛行士に最も必要な事は協調性です。」と言ったらTK生だけ笑っていた（協調性がない）。
宇宙飛行士候補は、集団で、10日間密閉された空間で過ごすらしい。
kaageが「物理好きさんとか厳しいだろうなぁ。◯すから」とか言っていて、個人的には面白かった（最悪）。
隣りにいたおじさんが「みんな同じような顔してるねぇｗ 将来、東大行くんでしょ」とか言っていた。実際、みんなメガネ＋マスクだったので無理はないと思う。
見学が終わった後はJaxaの社員食堂で昼食を取る予定だったのだが、当日になって土曜日は社員食堂がない事に気づき、しばらくさまよった後、国際会議場近くのリンガーハットで食べた。
ちゃんぽんを食べたのは修学旅行で長崎に行った時以来だったと思う。
午後
国際会議場のホールに行ったら、TMJNさんとhairaさんに会った。hairaさんに会ったのは久しぶりだったが、やっぱりかわいいなぁ...
受付を済ませ、Practiceまでの時間は本選に来た人と色々話していた...というのは嘘で、実際はTwitterしかしていなかった。
一応電脳を3冊配ったが、結構無愛想だったかもしれない。渾身の懇親に失敗...
Practiceでは、Eclipseのプロジェクトの作り方などを確認して、後ろで人々と交流をした。
とは言っても、パ研合宿に来ていたようないつもの人としか基本喋っていなかったと思う。いや、立ち歩いているのがいつものメンバーしかいなかったという方が正しいかもしれない。
暫くして、スタッフ5人くらいに呼び出された。
席を離れる時にWin+Lで画面ロックをしておいたのだが、どうやらこれでWindowsが開かれてしまうらしく、これは不正行為になるという。
仕様だと思っていたのだが、本選では席を離れる時はパソコンを閉じるように、万が一やってしまった場合は相談するよう言われた。ひょえー
Practiceが終わると夕食会だった。食べる前に予選満点賞の表彰があるのだが、食事前に紙を渡されてもﾁｮｯﾄ困る...。
結局、グラスを間違えないためにコースターとして使うことにした。
夕食会の途中に会った自己紹介では「茨城県にある筑波大附属駒場中2年の〜」などと言い、みんな笑っていたが本当に茨城にあると思った人もいるかもしれない（？）。
夕食会が終わると、宿舎に移動した。ベッドメイキングやお風呂などを済ませ、早めに寝ようと思ったのだが、全く眠れなかった。
一番の原因は、心拍数である。明日が本選であると考えると、それだけで心拍数が上がり、これでは睡眠不足になってしまうと考え、また心拍数が上がり...を繰り返していた。
また、独房が暑かったのもあると思う。寒いよりはマシだが...
結局、目を閉じたまま深い眠りにつくことはできないままだった。最初は3:34に起き、その後は1時間おきに起きてしまった。
2日目
朝
朝食は鮭の切り身で、おいしかった。結構ご飯の量が多かったので、食べ切るのは大変だった。
この後バスで会場に移動するのだが、絶起erがいたらしくちょっと遅れた。
その間も、もうすぐ本選競技がはじまる...という緊張で心拍数がヤバかった。
本選競技
開始の合図とともに、まずは1問目を見た。
最大値の最小値...二分探索？と思ったがすぐに貪欲だと気づいた。
使わないネクタイを前から考えてしまい、分からなかったのでmultisetで殴ってしまった。
後ろから考えると、答えが単調増加になるので線形時間で解けるらしい。
提出すると、全部WA。確認すると、出力を全部改行区切りにしてたせいだった。
考察に一番時間がかかったのはこの問題だと思う。20分くらいで満点。
2問目を見ると、これも貪欲に見える。
要は、レベル K のJOI文字列を部分文字列に持つ長さの最小値を求めろということだと分かる。
J,O,Iそれぞれで i 番目までの個数を累積和して、スタートを決め打ちしてJ,O,Iの末尾を二分探索して解いた。
尺取りでもできるが、間違いなくバグるのでやめた。35分くらいで満点。
3問目の問題文を読むと、湖、制約が200ということで O(N3) の区間DPをすればいいことがすぐにわかった。
これは実家なので勝利を確信したが、割と典型なのでみんな解いてくるだろうなぁとも思った。
このタイプの問題は、実装が暫くバグるが結局ACできると知っていたので落ち着いて実装できた。
実際、初期化忘れや、簡単のための2倍処理をミスってかなり時間を溶かした。1時間半くらいで満点。
3問目を早めに通し、割と心に余裕があった状態で4問目を読んだ。何本も反転させてよいものと思っていたので、小課題1すら分からないまま20分が経過。
よく分からなかったので5問目に進んだ。5問目は、問題の見た目がセグ木で得意分野だったので嬉しかった。
小課題を見ると、意図が明らかなのでそれぞれすぐにわかった。
小課題1,3は素直にRange Max Query、小課題2は前処理をしてからなぜかRange Sum Queryを使った。なんで累積和を取らなかったのか...
小課題4は、火力が2になる時刻が分かればいいので、時系列順にBITで殴った。
小課題4のQueryのソートで、operatorにおいてQueryのタイプでbool型の比較をしており、そのせいでずっと小課題4だけREだった。
Queryのタイプをint型にしたら通った。終了45分前に20点。
5問目の小課題を全部取ったので4問目に戻り、小課題2の考察をした。
適当にdijkstraを書き、サンプルをテストするとWA。手計算でもWAだったので、問題文をよく読むと反転させるのは高々1つだった。
残り20分しかなかったので、とりあえず小課題1だけ取ることを考えた。
実装方針を間違え、終了5分前に小課題1の5点を取った。
小課題2は間に合わず、結局325点だった。多分、春合宿は通ったと思った。
解析
解析の時間、色んな人と話すとみんな三完していた。ボーダー300超えもあるかもしれないと思うレベルだった。
Kodamanにはギリギリ勝ち、blackyukiとは同点だったが、kaageは4問目の小課題2を取り、5問目の小課題4を取っていなかったので5点負けた。
多分、みんな最高パフォーマンスが出ていれば336点は取れているだろうなと思った。
どうやら、4問目で誤読をしたのは僕だけではなかったらしい。”高々一つ”は太字になっていたが、紙面の端にあったので気づかなかった。
昼食会場ではボーダー予想が行われていた。やはり、3問目が簡単だったのもあって300点前後だろうと言われていた。
3問目の解説で満点が23人と出ており、4問目の満点0、5問目の満点はhirakichiさんとQCFiumさんだけだったのでボーダーは300点以上が確定した。
300点が2人、301点が1人はいると聞いていたので、ボーダーは300か301か302の三択だろうと思った。
この時点で春合宿がほぼ確定したので、嬉しかった。
去年は予選Bランクで今まであんまり自信がなかったのだが、少しは認められる存在になったのかなと思えた（は？調子に乗るな）
しかし、中2は4人通過したと思われ、IOIに行くのは大変だなぁと思った。
帰り
つくばから守谷までは席がほとんど空いていなかった上に、誰も優先席の周りにいなかったので優先席に座っていたのだが（守谷で人が多そうなので立った）、傍から見たら社会性のかけらもないクズに見えたに違いない。
その途中でこたまねぎさん達に会ったので、かなりバツが悪かった。第一印象は最悪だったであろう。
守谷からは床にリュックサックを置いてみんなのデータ構造を読んでいたのだが、ほとんどの駅において開くドアが入れ替わり、リュックサックを持って毎回移動するのが面倒だった。
割とあっという間に秋葉原につき、家に帰った。
疲れていたので、ABCはサボった。
後日談
本選競技の翌日、JOIのホームページを見るとボーダーが301点になっていた。
5問目の小課題1の1点を取ったかどうかで運命を分けたと言えるだろう。
春合宿でも1点を大事にしようと思う。
さいごに
全体的にイキっててごめんなさい。
