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点の差を埋める事ができずに終わってしまった.
来年は極度精進をしてまともな点数を取れるように頑張ろうと思う.
