ひゅ～Menの雑記帳

主にパソコン関係のことについて適当にしゃべります

JOI'20本選 敗退記

全列挙さんに脅されて、この記事を書きました。mencottonです。　

JOI'20本選に参加して244点でした。個人的にはかなり成功したと思ったのですが、3問目を23人も通しており、本選落ちです...

Day0

クエリ系の問題が出てきたときに殴れるように、一応平方分割を書いて寝た。

 

Day1

学校があったので、学校に行った。KCLCメンバーで事前に話し合った結果、別々に行動しつくばに向かうことになっていたので、昼食を中本にすることは朝から決めていた。

（本選前に普通に授業を受けるの図）

 

授業が終わったので、適当にクソツイをしながら、中本へと向かった。

 

クソツイをしてたらいつの間にか御徒町駅で降りていて、中本の前に来ていた。

実家のような蒙古タンメンを食べ、実家のように腹を壊した。（美味しかったです）

 

休憩を終え、無限人いそうなアキバへと向かったが、結局一人でグルコスして終わってしまった（社会性…）

 

グルコスを終えTXに乗ると、本選erが結構いた。

 

蟻本を見たり、ツイッターをしたりするなどし、つくばに到着。

 

割とギリギリだったので、すぐプラクティスをやった。

ところで、プラクティスで全完したあと内輪で固まって談笑するのが恒例となっていますが、内輪外からはどう思われているんでしょうね…（私は内輪側の人間なので分かりませんが…）

 

プラクティスを終え、OSSに関する講義を聞いた。業プロっぽい話を聞くのはあまりない機会だったので、興味深かった。

（なんとその後講演者の方からフォローされ、リプライを頂いた）

 

その後、夕食会場へと直行。自己紹介フェーズでは、人々のツイ垢を特定したり、tk72ersに煽られたりした。

 

バスに乗り、いつもの独房へ。人々と話すなどし、就寝。

 

Day2

絶起を回避し、いつもの朝食を食べた。

 

支度を終え、本選会場に向かうまで暇なので、人々に精神攻撃を仕掛ける。

 

そんなこんなで本選が開始する。クスリも決め、準備万端。

 

本選競技

本選中はスマホの使用が禁止されているため、本選中の行動はその場で手書きしたタイムラインによって記す。（解法のネタバレがあるので注意）

0:01:45 紙の不備が無いことを確かめ、本選開始。取り敢えず1問目「長いだけのネクタイ」に取り掛かる。

0:05:30 1問目なので、適当にソートすれば良さそうなことに気付く。単にソートして調べるだけだと、O(N^2) かかってTLEするので、GCD on Blackboard みたいに左右から累積MAXを取れば良いことに気付く。方針が立ったので、コーディング開始。

atcoder.jp

0:16:30 コーディング終了。テストケースも一発で合わせる。

0:18:15 提出し、1問目をAC。2問目「JJOOII 2」に取り掛かる。

0:21:45 2問目の考察が終了。消す文字数は固定なので、明らかに先頭と末尾の文字列をたくさん消したほうが良い。先頭をいくつ消すかを決めると、累積和を使い O(log N) で末尾をいくつ消すかが求まるので、全体として O(N log N) でできることが分かった。　実装を始める。

0:35:15 2問目の実装が終了。テストケースも一発で合わせる。

0:38:30 提出するも、TLEで13pts。Range-based-for が遅そうだったので、普通のforに直す。

0:40:45 訂正し、提出。無事AC。3問目の「スタンプラリー 3」に取り掛かる。

0:45:15 高々1回しか曲がらないギャグ問かと思い、実装する。

0:55:45 コーディング終了。テストケースが合わないので、少し直す。

1:04:30 直し終わったので、提出。WAで0pts。複数回曲がるケースの存在を確認。

1:06:45 区間DPでいけることに気付くが、その時点での経過時間も持って遷移しなければ行けないことに気付き、あと回しにしたくなる。

1:10:00 競技中1回目のトイレ。

1:13:15 トイレから帰還し、4問目の「オリンピックバス」を読み始める。

1:16:15 5ptsはやるだけだったので、実装することにする。適当な計算量解析の結果、ワーシャルフロイド法でも間に合うと思い、実装。

1:29:45 実装が終わり、テストケースも無事通ったので、提出。TLEで0ptsが帰ってくる。ダイクストラ法に変更。

1:41:30 ダイクストラ法の実装が終わり、提出。無事に5ptsを獲得。小課題2, 3を少し考えてみたが、何もわからないので5問目の「火事」を見てみる。

1:46:00 5問目の問題を読み終わり、考察に入る。

1:49:45 小課題3までは平方分割+αでできる*1ことが分かる。

1:51:00 競技中2回目のトイレ。

1:53:30 トイレから帰還し、実装を始める。

2:24:30 実装が終わり、テストケースも無事通ったので、提出。しっかりと小課題3までをACし、14pts。C問題に再度取り掛かる。

2:26:00 小課題1, 2は巡回セールスマン問題で解けることに気付く。実装を開始。

2:44:00 実装が終わり、テストケースも無事通ったので、提出。ACし、15pts。小課題3の区間DP解の詳細な考察に入る。

2:47:30 現在位置は始点からみて正の方向にいるか、負の方向にいるかだけ持っておけば良い、それによりDPの遷移もそこそこ単純に書けるとイメージできたので、実装に入る。

3:18:45 実装が終わり、テストケースも無事通ったので、提出。ACし、25pts。この時点で勝ちを確信する。

3:22:30 ここで何を狂ったか慢心し、4問目の嘘解法*2を思いついたので、実装する。

3:25:15 競技中3回目のトイレ。

3:42:30 実装が終わり、テストケースも無事通ったので、提出。WAとTLEが帰ってくる。vector<map<int, pair<long long, long long>>> という型でグラフを作ったので、TLEはある程度想定していたが、小課題1すら通らないのにビビる。適当にINFの値を調整するなどしたが、一向に通らない。

4:00:00 まごまごしている間に終了。最終結果は 3:18:45 時点と同じ、 100+100+25+5+14=244 pts。

 

解析の時間が開始する。全列挙氏から、3問目の本質*3を教えてもらう。確かになぁという感じになった。E869120氏が熱を出していたので少し心配だったが、余裕で3完+部分点を取っており、流石の貫禄。…と思っていたが、想定より3完している人が多い。

昼食中も人々の点数を観測していたが、本当にやけに3完が多い。そしてyuma氏のこのツイートを見て、私の自信は打ち砕かれた。なんと、この時点での投票者40人中、50%が3完以上だったのだ。

 

昼食を終え、解説を聞く。3問目のACコードは、なんと小課題2と3の考察を合わせることで出来ると解説された。そんな発想は全く無かったので、たまげた。

そして得点分布が開示される。やはり異常に多かった。

 

悲しくなり、square1001と一緒に高速バスで帰る。安いわりに割と速く着いたので、アド。

 

音ゲー勢とエンカするが、言及されていた通り無限人いたので撤退し、再びグルコス。

 

かなり暗くなり怖くなったので、1クレだけやり撤収。帰り際に見知らぬ人に声を掛けられ、微妙に怖くなる。適当にツイートをしながら、帰路へ。

 

ツイッターをしていたらkaage氏に煽られたので、仕返しにねぎしに行く。

ちなみに、毎回疑問に思っていた「とろろの食べ方」を、食後にヴァネロピ氏*4に伺うと、このように返ってきた。

 

食後ツイッターを開くと、このようなツイートを発見。

 

折角なので、画像を作ってみた。

f:id:mencotton0410:20200210185324p:plain

疲れていたため、帰宅後はすぐに就寝。

 

Day3

ボーダーは301となり、本選落ちが確定。square1001が銅賞であることも確定。

 

総括

　244点で十分通ったと考えていたために、春合宿に行けないのはただただ自分の精進不足だと感じました。昨年にくらべ今年のボーダーは異常に上がったので、来年のボーダーはさらに厳しくなることが予測されますが、それにも負けないぐらい精進し、次こそは通りたいと思います。

*1:セグ木でもできるが、正確に速く書く自信が無いので…

*2:各辺について最小コストと次点を記録し、指定された辺で遷移しないようにしたダイクストラ

*3:DPの添字と値を入れ替えるテク、EDPC-E みたいなの

*4:ねぎし界のtourist