JOI 春合宿 2022
今年も情オリ代表をやらせて頂きます よろしくお願いします
— yuto (@yuto1115_cp) 2022年3月23日
各日 2-2-13-2 位、累積は 4 日連続で 2 位です 最後トップに 6 点及ばず… pic.twitter.com/raTD6LRYCm
— yuto (@yuto1115_cp) 2022年3月23日
この記事では、問題の解法に関する言及が一部含まれています。ご注意ください。
全体感想
- 非競技
楽しかった。やっぱり 30 人いると盛り上がって良い。会ったことがある人・ない人含め交流できてよかった。
- 競技
去年よりは確実にいいパフォーマンスが出せたと思う。問題は去年より易化していると感じた。 難易度 10 後半 ~ 11 前半くらいの問題が体感多くて、ここら辺をだいたい刈れたのが良かった。
- 参加者
参加者のレベル上がってないか？自分が解けなかった問題でも普通に 10 人とか満点とっているので、怖い。 難易度 10 確実に取れれば代表狙えると思っていたが、この感じだと来年以降は 11 もある程度解けないとダメそう。
中学生がここに沢山来てるだけでも凄いんですが、中 2 で 500 点超えてくるのはヤバいよ。 来年代表なれるだろと思ったが、高 2 が抜けてもあんまり嬉しくなくて、強い高 1 がまだ残ってるんですね〜〜、厳しい世界。 2, 3 年後の春合宿にチューターで参加して、彼らが無双するのを見るのが楽しみです。
~ Day 0
1 月後半から 2 月にかけて JOI 埋めをやった。3 月は忙しくてほとんどやれなかったので、前日に 1 回だけ 5h バチャをやった。
Day 1
今年は宿泊補助を得られなかったので、毎日 1 時間半かけて通った。渋谷で井の頭線に乗っていたところ、まだ席は全然空いてるのに体がぶつかるくらい近くに座ってくる人がいて、 ヤバいやつか？？と思ったら kaage だった。ここで会えたおかげで駒東から会場まで迷いませんでした。感謝。
控室で軽く交流した後、初競技に臨んだ。まず 1 問目を見る。どうせこうじゃないと解けない！と思いながら強気の未証明を投げると、ちゃんと部分点が通るので確信。 満点もいけそうなので考えると、実装がダルい解法を思いついたので書く。いきなり JOI やらされてんな〜〜と感じた。2.5h くらいで無事満点。2 問目を考えるが、こんなものが解けていいのか？という気持ちにしかならない。 とりあえず自明だけ取って次に進むと、3 問目は簡単だったので満点を書いて、通す。2 問目に戻ったが、結局追加点は取れず、1 時間椅子を温めた。ずっとマスコットを撫でていた気がする。
昼食後、配られた順位表を確認すると、1 位とは 30 点差で同率 2 位。90 点差じゃなくてよかった。
mac はファイル名の小文字と大文字を区別しないことを知った。
Day 2
寝ていたわけでも無いのに乗り換えを忘れて一敗。歩きパートでも迷うとやばかったが、昨日 kaage が連れて行ってくれた道を頑張って思い出しながら歩くと、無事到着。
Day 1 はフォーマッタの設定に失敗したが、今日はうまく行った。今年の春合宿では色んな IDE の機能の使い方を事前に頭に入れておいたので、かなり快適にコーディングができた。 1 問目、解けそうなのになかなか O(N4) から落ちない。1 時間くらいで O(N3) が思いついたので、部分点のつもりで提出すると、緑の表示。え？？となる。後でチューターとも話したが、普通に非想定っぽい。犯罪が得意で、すまん。2 問目、まるで考察が進まない。中盤は何も思いつかない辛い時間帯で、お菓子を食いまくった。ようやく思いついたが、バグに悩まされ、残り 1 時間で何とか 40 点を獲得。3 問目は 2D セグ木を使うなどして 73 点を取ったが、満点は取れなかった。すぐデータ構造に走ってしまうの、良くないね。それはそれとして、今まで書いたことのない 2D セグ木を 15 分くらいで書けたのは良かった。
順位は変わらず 2 位。トップとの差が 17 点に縮んだ。
Day 3
電車に乗っていたら、緊急停止ボタンが押されて 20 分くらい止まった。集合時間には間に合わなかったが、競技開始が遅れるほどではなかったので良かった。
1 問目、何も見えない。こういうのどうやったら解けるようになるんだろうか。2 問目、満点を取れると思ったが 83 点で止まってしまう。log を落とさないといけないんだなあと思ったが、とりあえず飛ばす。 3 問目、これまたずっと考えてもなかなか見えない。Day 2 までが簡単に感じたので、もしかして今年はずっとこんな感じ...？ と思っていたが、分からされてしまった。Hall の結婚定理自体は序盤に考えたけど、春合宿に出るわけないと思ってまともに考える前に捨ててしまった。結局合計で 100 に行かなかったので、終わった......と思ったが、周りも出来てなさそうでひとまず安心。とはいってもこの日の成績は全体 13 位で、4 日間通して 1 番の反省日です。
総合順位と、トップとの点差は変わらず。ボーダーと 100 点差をつけて安心して眠る予定だったが、無理だった。もし明日失敗したら......という不安がよぎる。 ネガティブ思考してて良いことは何もないので、どうせ大丈夫だと自分を鼓舞しながら寝た。
Day 4
最終日にして、初めて何のトラブルもなく電車移動を完遂した。すると、めちゃくちゃ速く到着してしまった。
1 問目、制約からしてどう見ても Q = NM log M で、この手の Communication の log は二分探索か分割統治なので、その路線で考えると、解ける。45 分で 100 点が取れたので、だいぶ精神的に落ち着いた。 2 問目、簡単そうに見えたが、しばらく考えると、どうも難問枠っぽい。しばらく考えた後、自明だけ取って次に進む。3 問目は自然な考察を積み重ねていくと解けて、とりあえず部分点を出してみると、緑の表示。 Day 1 の犯罪を思い出して、またやったかと思わず笑ってしまう。もっとも、後で解説を聞いて分かったが、今日のは犯罪ではなくて、非自明な計算量改善が起きていたらしい。2 問目に戻る。考察の欠片みたいなのは沢山集まったが、それが上手く纏まらずモヤモヤ。部分点解けなくはないんだけど、実装がマジでヤバい。最後の 30 分でマシな方針が思いついたので書く。サンプルに落ちたのでバグを直して、もう一度サンプルを試そうとしたところで、突如パソコンがフリーズ。急いでチューターを呼んだ。結局、競技時間延長はされないが提出だけはさせてもらえることに。とはいってもサンプルも試せてないし、期待はできないな......
順位表が配られた。なんと！最後に提出したコードがちゃんと点を獲得していた。1 位には 6 点及ばなかったが、最後まで 2 位を守れた。安心。 表彰式や写真撮影を終え、春合宿が終了した。この日は 7 時くらいまで会場に残って人と話していて、楽しかった。その後もちょっと遊んだ。
今後
今年もまた APIO, JOI open, IOI と続きますね。今年こそはインドネシア、行けるといいなあ。
JOI Open 2021
結果
100-100-10 (210)
詳細
1:48 28-0-0
2:28 28-100-0
2:58 28-100-10
3:55 100-100-10
思考
A（1 周目）
小課題 2 から考えた。区間に対する操作をしながら情報を取得するので、遅延 Segtree で解けそう。考えると、各区間に対して
を持ってやると、merge は各要素ごとの足し算、update は一致する数を「変更先の要素の数」に変更すれば良いので、遅延 Segtree に載る。初めて非再帰遅延 Segtree をソラで書いたので割と時間を食った。 小課題 3 以降は分からなかったので一旦飛ばした。
B（1 周目）
明らかに DP ぽいのでその路線で考える。まず dp[i][j] := i 個見て、一番 A が大きいのが j の時の最大値 みたいなのが思いつくが、明らかに無駄がありそう。ちょっと考えると、A の Max が更新されるところを管理するのが良さそう。dp[i] := 最後に A の Max が更新されたのが i の時の最大値 と定義すると、dp[j] ← dp[i] + 1 と遷移できる条件は
- A[i] < A[j]
- i < k < j, A[i] >= A[k] を満たす k を全部選んだ時、i から j までの間で、差が D 以上になる場所がない
と書ける。配る DP をやると、自明に O(N2) で解ける。
簡単枠ぽかったので、実装せずにそのまま満点解法を考えた。上の条件をじっと睨むと、i から遷移できるのは「ある区間内にありかつ A[i] < A[j] を満たす j」 みたいになるので、この区間を求めたい。これは、A[i] が小さい順に i を見ていって、map とかで差が D 以上になる場所を管理してやるとわかる。それさえ分かれば、同じように A の小さい順に dp の値を見ていくと、区間 Max 一点取得の操作に帰着される。もっと上手い方法があるかもしれないが、A で遅延 Segtree を作っているのでそのまま流用する。30 分で解けたのでよかった。
C（1 周目）
色々考えてみたがなんかよく分からないので、とりあえず小課題 1 を解く。これは全ての組み合わせで対戦させて、勝利数順に並べたのち、勝利数 1 同士・N-2 同士を対戦結果を元に並び替えれば良い。考察がそこから膠着したので 2 周目に行く。
A（2 周目）
交配によって作れる条件を考えたいが、なんの特徴量も掴めないので、とりあえず実験コードを書いて、色々な初期条件に対して作れる遺伝子を全列挙してみる。すると、どんな初期条件にしてみても高々 9 個しか出てこない。まさかとは思ったが、作れる遺伝子を全列挙した後に全てに対して小課題 2 と同じことをやると、満点が得られた。拍子抜けした。9 個で抑えられる証明は与えられていないです（そもそも高々 9 個なのか？）。
C（2 周目）
1 時間くらい考えて、二分探索とか色々なものに思いを馳せてみたもののよく分からず。 ここで 10 点超えられるかで上位に入れるか分かれそうだなあと感じたがやはりそうだった。
JOI 春合宿 2021 / AtCoder 橙
要約
"Hello, World!" から広義1年で AtCoder 橙 / IOI 日本代表 になるまでの記録
橙コーダーと、申します
— yuto (@yuto1115_cp) 2021年3月14日
yuto1115さんのAtCoder Regular Contest 114での成績：18位
パフォーマンス：3133相当
レーティング：2387→2488 (+101) :)
Highestを更新し、三段になりました！#AtCoder #ARC114 pic.twitter.com/DyU8WQDXdL
日本代表になりました
— yuto (@yuto1115_cp) 2021年3月23日
JOI 春合宿の問題に関する言及があります。ネタバレが始まる前にネタバレ部分を飛ばすリンクがあるので、飛ばしたい人は踏んでください。
2019/12
同じクラスだった友人の勧めで競プロを始めた。初めに使う言語として Golang を推されたので、本を借りて Golang の勉強をした。ンコソパのンの字も知らなかったので、色々と教えてもらいながら習得した。
2020/01-02
適当に ABC-A, B, C あたりを埋めたりコンテストに出たりしていた。2月中旬に茶色になった。
C++ は危険だからやめとけと言っていた友人を裏切って、APG4B を使って C++ に乗り換えた。
古いパソコンを使っていたのでかなり重く、動かなかった時にスマホコーディングで ABC に出たら冷えた。
2020/03-04
学校が休校になり、一日中競プロをしていた。今までで一番精進をしていた時期。
蟻本を買い、けんちょんさんの記事（AtCoder 版！蟻本 (初級編) - Qiita）の練習問題や参考記事を見ながら初級編を進めた。
3月上旬に緑になった。
4月上旬に水色になった。
新しいパソコンを買ってもらった。
2020/05-06
友達が家に来ていた日に ABC が重なってしまい、みんなが休憩モードになったのでこっそり部屋に戻って ABC に出ていたが、途中で呼ばれてしまったためリビングで UNO をしながら部屋で ABC に出ていた。すると、初 2400 perf. をとって青になった。
その後は ARC, AGC が続いたこともあってレートが伸びず、初めての停滞を経験した。
精進としては、蟻本の初級編と中級編をやっていた。
2020/07-08
7月くらいからコンテスト成績が上がり始め、停滞から抜け出した。
青 diff を埋めたり、EDPC を解いたりしていた。
8月末に情報オリンピックの夏季セミナーに参加した。JOI のイベントに参加するのは初めてだったので、twitter でしか知らなかった中高生競プロer達と交流できてとても楽しかった。暖色だらけでかなりビビっていた。
最終日の発表の自己紹介で、翌日に黄色になることを宣言した。黄色になった。
2020/09-11
暖色の人たちが rated 不足を嘆いているのをずっと聞いていたのでそれなりに覚悟はしていたが、いざ自分が黄色になるとすぐに ARC が増え始め、結局 rated 過疎を経験しなかった。ゆとり世代とお呼びください。
とはいってもすぐにレートが上がるわけではなく、3~4ヶ月くらい黄溜まりから抜け出せずにいた。
黄 diff に手を出したり、JOI の難易度 7~8 を埋めたりしていた。
2020/12
JOI の2次予選に参加した。本選には絶対に行く、春合宿まで行ければ大満足、というのが当初の目標だった。
結果は全完で、理事長賞を頂いた。嬉しい。
本選に向けて、JOI の難易度 9 を埋め始めた。
AGC にかなりの苦手意識があったので Good Bye rng_58 コンに出るのは怖かったが、実際に出てみると2日連続でいい結果が出せ、一気にレートが +119 した。これは1月中か2月中に橙になれるのでは？とか思っていた。
2021/01-02
ところがそううまくはいかず、橙手前までは行ったが微妙に届かなかった。
1月初めにパ研合宿に外部枠として参加した。オンサイトイベントは初だったのでとても楽しかった。2日目と始業式が被って参加できず、残念だった。
JOI 本選に参加した。メダルとはいかなかったが、春合宿への参加権を獲得した。
春合宿に向けて難易度 10 を解き始めた。難しかったが、思っていたよりは解けた。
2021/03
テスト勉強をしていたので、しばらく精進ができていなかった。その状態で AGC に出てみたところ、全く思考が回らず1問も解けなかったので撤退した。
テストが終わったので、思考能力を回復させるために精進をした。SSRS さんのバチャに参加するなどして去年の春合宿の問題を解いた。代表ボーダーには遠く及ばなかったので、今年は春合宿を経験して、来年本気で代表を目指そうと思っていた。
Day 0
科学の甲子園全国大会に参加した。情報の筆記を担当した。（筆記は優勝していたらしい。やったね！！！）
筆記が終わり、つくばからホテルのある渋谷に移動した。
渋谷駅を出てホテルまで歩いていたが、携帯の充電が1桁だったので「渋谷の路頭に迷うところだったwww」みたいなツイートを後でしようと考えていたところ、残り5％から急に電源が落ちて真顔になった。幸い iPad を持っていたので、コンビニの free Wi-Fi があるところでは地図が見れた。隣のコンビニに行く→間違っていたので戻る→他の隣のコンビニに行く→合っていたので次のステップ みたいな DFS でなんとか到着できた。事務局の方、めっちゃ遅れてすいません。
夕飯は焼肉弁当だった。美味しかった。
ここから JOI 春合宿の問題に関する言及があります。飛ばしたい方はこちら。
Day 1
絶起しなかった。さすが。起床界のt（略）。
人々と会った。すごく非日常空間だった。
持参していたキーボードを繋ごうと思ったところ、USB-C がついておらず、絶望した。去年はこの PC でしたよ〜って言ってた PC には付いてたのに...... 慣れない日本語配列での競技が確定した。
競技が始まった。1問目が Output only だったのでかなりビビったが、他の人よりはできる自信があったので取り組んだ。とりあえず 2-opt と 2点 swap で焼きなましをするのが最初に思いついたので、実装した。細かいパラメータ調節を繰り返して、50点くらいを得た。
2問目を見た。自明な5点をまず取った。シミュレーションには解説とはちょっと違うダイクストラ的なものをやった。（衝突時刻をコストとして持つ辺を張ると、ある人が感染する条件は、コストが単調増加なその人までのパスが存在すること。dp[i] = i までの単調増加パスのうち、最後の辺のコストの最小値 と定義すると、ダイクストラ風に更新できる。最短経路問題では無いが。）それ以降も考えたがわからなかったので捨てた。こういう明らかに全探索が無理そうなやつは、「実は探索する必要があるパターンは少しだけ」を疑うべきだった。反省。
3問目を見た。自明部分点とパラレルバイナリサーチによる小課題6をとった。小課題4が取れれば89点が取れたので必死に考えたが、chmax / add を合成できるという発想に至らなかった。その日の ABC-E で本質が出てかなりびっくりした。精進不足です。
1問目に戻ってきて、現在最小値をとる角のまわりが優先的に選ばれるようにしたらちょっと改善して、65点を得た。
下の方だろうな〜と思いながら結果を見ると4位だったので、かなり驚いた。
水3本と蒟蒻ゼリー1本を飲んだ。
夕飯は油淋鶏弁当だった。美味しかった。
Day 2
絶起しなかった。さすが。起床界のt（略）。
1問目を見た。一度日を跨げばそれ以降は前計算でまとめられるのは分かったが、日を跨がない移動の計算がわからず一旦飛ばした。
2問目を見た。いつもの45°回転をすると、平面走査 and 二分探索の解法がすぐに生えた。K 回二分探索をする解法で K=10 行けるかな〜と思って提出すると、K=1 しか通らない。もう少し考えると、一回だけ二分探索して上界を見つければ、あとは全列挙できることに気づく。これで K=10 解けたぜ〜と思って提出すると、まさかの100点。よく考えたら別に K=10 の必要はなかった。ただし log は二つつけているので犯罪でした。通した人全員犯罪だったけど。
3問目を見た。設定がめっちゃシンプルなので自明枠か？と思ったが、すぐに激ヤバであることに気づく。バケット法を使って10点を獲得し、それ以降は諦めた。正しい判断だった。
1問目に戻ってくると、最短経路が高々 M 回しか変化しないことに気づき、これ間に合うのか〜？とかいいながら NM 回ダイクストラする解法を書くと、最後の小課題を除いて通った。密なグラフだと prique 使った方が遅くなるの、それはそうなんだけど非自明。
この日の成績は同率1位で、合計で3位に浮上した。あまり狙っていなかった代表だったが、狙える位置にあるとなって、急に今年に代表になりたいという思いが出てきた。
水4本と蒟蒻ゼリー2本を飲んだ。
帰りに暴風雨に遭遇し、使っていた骨の1本折れた傘が、骨の2本折れた傘に進化した。
夕飯は串焼き弁当だった。美味しかった。
こっちに全競争心が向いた結果、夜に出た ARC では今までに出た AtCoder rated で一番やる気が湧かなかった。結果も酷かった。それなのにレートが上がったので、これもう冷えるビジョン見えなくない？とか言ってた。フラグにならないことを祈る。
Day 3
1問目を見た。ビット数的にどうせ貪欲だろという気持ちで眺めると、貪欲解が生える。1時間程度で70点を獲得し、次の問題に移った。
2問目を見た。最初の部分点を取るが、それ以降はわからず一旦飛ばす。
3問目を見た。木DPで20点を取るが、それ以降が全然わからない。
どれも解ける気がしなかったので迷ったが、一番チャンスがありそうな2問目に脳の資源を費やしたところ、残り1時間を切ってから45°回転を思いつき、座圧DPで28点を獲得した。時間が足りず、これで終わってしまった。48点は全探索なので解けるべきだったが、CHTはほえ〜〜〜〜って感じだった。CHT 未履修です（おい）
この日の結果は4位で、合計3位もキープしていたが、昨日までは100点以上あった5位との差が60点になっていて、かなり焦った。
水5本と蒟蒻ゼリー2本を飲んだ。
夕飯は生姜焼き弁当だった。美味しかった。
この日の夜はかなり緊張していて、足が震えたりもしていた。
かなり暇だったので Youtube を見始めたら、気づくと1時になっていた。よくない。大事なコンテストの前は早く寝ようね。
Day 4
毎日飲んでいた蒟蒻ゼリーが無かったので動揺した。かなしい。
1問目を見た。2乗解ならすぐ生やせるだろうという勘があったので考えると、生えた。何度かバグらせたが、焦らずにバグ取りをして無事部分点を獲得。トイレに行くとダブリングが思いついたので、戻ってきて実装。満点を獲得した。これでかなり緊張がほぐれた。後にわかるが、この時点で代表が確定していた。
2問目を見た。37 解は自明なので 27 解を考えた。手元で色々なお絵かきをすると、1 x 1 の市松と 2 x 2 の市松を組み合わせた模様で行けることがわかった。頑張って実装とバグ取りをして、39点を獲得。
3問目を見た。まず簡単な木DPで最初の部分点を取る。JOI の木の問題の N <= 105 はどうせマージテク（要出典）なので、なにか部分木の要素数以下であるものがないか探すと、DPの差分が該当することがわかった。頑張って実装して2番目の部分点を取った時はかなり安心した。functional graph の場合も考えると、ループ上の頂点だけ別処理を加えてうまくやるとできることに気づき、満点を獲得した。解説の木に帰着する方法、なるほどなあ。
昼食時に近くに maroon さんがいて思わず二度見してしまった。
流石にこれで代表になれなかったらキツイな、と思っていたが無事代表になっていた。この日の成績は単独1位で、合計としては2位になっていた。めっちゃ嬉しかった。
水6本とよく分からないゼリー1本を飲んだ。日に日に増えた水の量だが、最終日は2L飲んだ。
写真撮影が長かった。
（日本代表写真撮影にて）
事務局の人A「それじゃあメダルもつけて写真撮りましょうか〜〜」
事務局の人B「一人メダルないですね」
事務局の人A「あ、じゃあやっぱメダル外しましょう〜〜」
メダルを取っていない代表がいてごめんなさい。
帰りの電車で、代表になったことを twitter で報告した。1晩でフォロワーが70人増えてかなりびっくりした。橙になった時の比じゃない。
他3人は想定していたが自分は非想定だった的なコメントがちらほら見えた。その気持ちよく分かります。自分が一番驚いているので。
感想（ポエム）
一年前、自分がまだ競プロを始めたばかりの頃、twitter で本選、春合宿、そして代表と活躍する中高生の存在を知り、心から尊敬するとともに、いつか自分もその場所に立ちたいと思っていました。まさか1年後にそれを達成できるとは自分でも驚きですが、代表になった以上は、自分も他の競プロerの目標となれるような実力をつけていきたいと思います。よろしくお願いします。
今後の目標
IOI の問題とかを一問も解いていないので、IOI、APIO、JOI オープンコンテストとかのバチャをたくさんやりたい。
あと、他の代表に比べてレートがかなり貧弱なので上げないとやばい。IOI までに最低限 AtCoder 2600 には乗せたい。
来年の春合宿には赤コーダーとして参加したいです。
色変記事恒例の精進量とかを載せるやつ
こうして見ると、全然精進していなくて、涙......
