MtSakaのブログ

競技プログラミングをします

JOI2022/2023春季トレーニング参加記

JOI2022/2023春季トレーニング(もう春合宿とは言わないらしい 悲しい...)に参加しました。その参加記です。

本選まで

mt-saka.hatenablog.com

↑の記事にある通り無事本選で優秀賞を取り春合宿進出しました。

本選後

自分は5hの経験があまりなかったから一年分のバチャは絶対にやろうと思い、去年の問題を意図的に避けてJOIの問題を解いて精進していた。
問題をとにかく解いて解ける感じの問題の感覚をつかんだり、ライブラリ類の練習に役立った。
バチャは実際に四日間かけて去年のばちゃをやりました。結構よかったので自信につながった気がする。
バチャを他にできないかなーと思ったときにoj.uzにJOI open contestの過去問があったので他のコンテストをやるよりこれをやったほうが良いだろうということで2021のバチャをした。こっちもそれなりにできて春合宿に向けて気持ちが高まっていた。

本選までのJOI精進記録
春合宿前日までの記録

表彰式(3/18)

表彰式は頑張って眠気に耐えた。
交流会では色んな人に会えてとても楽しかった。自分は羞恥心に負けてあまりツイッターを表に出さなかったため交流がそこまでできたとは言えなかったので来年は交流を頑張ります。
中高生以外だとけんちょんさんやつもいよろずさんと会えたのが結構嬉しかった。
JOI春勢は交流会を途中で抜けて筑駒の目の前にあるNTTデータセンター駒場に行った。全体の到着が少し遅れたので実機演習を15分延長してくれてありがたかった。
自分のキーボードがBluetooth接続モードのままでプラクティス中は永遠に有線接続できないと勘違いしていて、パソコン本体についてるキーボードが使いにくかったのでかなり萎えていたけど有線接続モードの存在に撤退ギリギリに気づいてなんとか使えることを確認出来て安心した。
トヨタコンのオンサイトとかぶっていてチューターらが結構いなくて個人的に面白かった。
トヨタコンの影響でABCが消えていたがその代わりにこどふぉのdiv2が生えていたので出た。途中で眠気に負けて翌日の準備だけして寝た。

Day 1 (3/19)

山手線に乗り換えるときに学校に行く感覚で逆方面に乗ってしまいそのことに気づくのに時間がかかったためかなり焦ったけど早めに家を出発していたのもあって普通に間に合った。
渋谷駅でkaageさんを見かけたけど電車で一緒になったら何を話せばいいかわからなかったので見なかったことにして別の車両に乗ってしまった。結局駅で見つけられたので色々話しながらNTTデータ 駒場研修センターまで歩いた。色々面白い話を聴けて楽しかった。歩いている途中後ろから全力疾走のsquare1001さんに追い抜かれてちょっと面白かった。

競技

ふたつの通貨 (Two Currencies)

問題文を読んですぐ並列二分探索が見えたので頑張ってオイラーツアー,BIT,Sparse Tableを書いて1時間20分くらいでACした。(オイラーツアーとRMQを組み合わせたLCAをバグらせて20分くらい失ったのがかなりもったいなかったけど)

JOI 国のお祭り事情 2 (Festivals in JOI Kingdom 2)

とりあえず自明枠10点を通してN<=30は頑張ってDPの状態を持てば5乗か6乗に落ちそうだとわかったので残り一時間とかでやることがなくなったらやろうと思いいったん次の問題に行った。(結果書かなかった)

パスポート (Passport)

とりあえずちょっと考えて最小値なのでグラフに帰着したらいけるかなと思ったら46点が簡単に取れた。そっから辺を逆にすると54点に伸ばせた。
こっから方針転換して1とNに行けるようにするという問題にうまく帰着できていい線まで行ったけどちょっとした嘘にはまって渾身の提出が1ケースだけWAだった。この1WAを解消して満点を取れると思い終了までの1時間粘着し続けたが結局通らなった。

結果:100-10-54 計164 で同率7位だった(同順位が4人いてしかも全員同学年だった。面白い)
最後の問題は本質がほぼ見えていたので通せなくて悔しかったが順位はまだ耐えていたため安心して帰宅できた。翌日もがんばろうとやる気がさらに湧いてきた。

トヨタコンのオンサイトコンテストの影響で日曜日なのにABCがあった。ABC Tournamentの対象だったので眠かったがとりあえず出た。
40分くらいで7完してExはJOIにはいらない数え上げだったので考えず寝た。

Day 2 (3/20)

この日はなんとか山手線への乗り換えに成功して早めについた。4着だった。

競技

ベルトコンベア (Belt Conveyor)

小課題1,2は一本ずつ辺を特定するだけ(15点)。小課題3の10点はmod 3かな~と思って頑張ったらとりあえず5回に収まって通すことができた。これだけに1時間くらいかかってしまい、Communicationのデバッグが苦手だと感じた。満点解法は直線を定数回でいけるからHLDしたときのlight edgeだけどうにか特定できんかな~と思いながら永遠に考えた。結局この方針の嘘にはまり最後の1時間半以上は実装していた。結局終了9秒前に出した提出は落ちてた...
想定解法と全然違っていて悲しい気持ちになった。

議会 (Council)

最初に見た問題だった。パっと見たときM<=20の制約できっと高速ゼータ/メビウス変換とか色々がんばるんだろうと思った。
とりあえず満点とりたい気持ちになり色々条件を整理したりしたらいい感じに高速ゼータ/メビウス変換に帰着できたので実装を始めたが途中で最大値評価をミスって迷走してmodintを実装したり、帰着できていたと思っていたものが少し嘘だったりと紆余曲折あったが無事開始1時間20分で満点を取れた。

水ようかん 2 (Mizuyokan 2)

Bを読んだ後すぐ読んでいた。このときに小課題1,2の15点分がわかっていた。AとBが両方ともいったん一息ついた後に取り掛かった。小課題3以降では絶対いい性質を見つける必要があるということがわかったが谷を一個にしていいというのがなかなか思いつかなくて昼食会場で言われるまでわからんかった。

結果:25-100-15 計140 二日間で304点で暫定8位。
昨日から何も進捗がなく、ボーダーが少し離れただけだった。このままではいけない

Day 3 (3/21)

朝、渋谷駅でyuto1115さんを見つけた気がしたが自信がなかったので話しかけられなかった。結局正しかったらしく話しかければよかったな思った。

競技

ビーバーの合唱 (Chorus)

パッと問題見て40点まではAを並べ替えるという視点に立つと自明だな~と思い、どうせ二乗はMongeとか使うんだろうなと思ったが結局わからず。40点はとりあえず実装して通した。

クッキー (Cookies)

一番何も見えなかった。箱を決め打つのはそれはそうだけど大きいほうから決めていったりその他必要十分条件の列挙は頭よいなあという気持ちになった。結局自明dpをがんばるだけの小課題1,2,3だけ取って25点。

旅行 (Tourism)

C上の区間で隣同士のパスのの和集合の頂点数だなあというのは見えていたので小課題1,2はいい感じにやるだけで小課題3は区間min/maxなのでセグ木。小課題4はHL分解して遅延セグ木で区間更新/区間総和をできれば良くてそれを書いた。これで35点、方針的にはミスではなかったっぽい。最初に考えてた満点方針が完全な嘘でこれに2時間以上費やしていたので悔しい。一番解ける可能性があった問題だった。

結果:40-25-35 計100 三日間で404点で暫定8位
上位には差をつけられ代表が遠のいたただけだったうえ、一個下のCyanmondには差を詰められ2点差になっていた。個人的にはばうまくいくことがなさそうなセットだったのが唯一の救いだった。

Day 4 (3/22)

朝渋谷駅で昨日のAのMongeとかの性質を使った高速化を頑張って読みたいなと思い記事を読み始めたら降り過ごしてしまった(それはそう)。結局理解できていまま会場に行った。

競技

最後の戦い (The Last Battle)

正直8点しかまともな解法が思い浮かばなかった。この四日間で一番何も考えていない問題だと思う。考え方がかなり下手だった。2桁点数も言っていないのがかなり恥ずかしい。

警備員 (Security Guard)

問題を見てQ=0は通したいなと感じた。パスで値がすべて1,2の場合は割と単純に解けたが、値が自由の場合はかなり大胆な予想をして実装した。結果通ってかなり興奮した。この予想をもとに木にも帰着してなんとかAC。一般グラフについても拡張できるだろうということで色々考えたが終盤で思考力が落ちていたのもあって嘘にハマって通すことができなかった。解説では自分がした大胆予想をもっと定式化していて、負けたなあと感じた。

ビ太郎の旅 (Bitaro’s Travel)

問題文を読んで一番の良心枠ではあるだろうという予想はついた。小課題1,2はシミュレーションそのままだが、そこからdpを考えて単調性を発見できないか1時間以上試行錯誤したが結果何もわからなくていったん小課題1,2を実装した。実装している最中に小課題3の制約の意図を理解しこれは向きの変更回数に着目する問題であるとやっと気づくことができた。しかし、この時はここから満点解法まで思い浮かばなかった。実力がない証拠だ。
いったんこの問題から離れて他の問題を考えて戻ってきたときに、いい感じに式で向きの変更がO(log N)回であることを示せて急いで実装した。少し雑な実装をしたのでバグってるかと思ったが、サンプルも一発で通ったうえ提出も一発で通った。この四日間で一番脳内にヤバい成分が出た。この問題は正直反省点が多いが、通せた喜びは大きかった。

結果: 8-37-100 計145で順位は変わらず総合8位だった。
一個上のぷらと差を結構詰めたが追いつけなかったのは少し悔しい。
競技中にぷらがいきなりかなり大きくガッツポーズをしていたのが印象的だった。昼飯のときにチューター陣でも話題になったという話を聴いた。
昼飯中に(学校の)OBのyutaka1999様が来ていたので挨拶とがっちり握手をした。JMOの春合宿にいるという話を風の噂で聞いていたのでびっくりした。

春季トレーニングを振り返って

結論、俺は弱かった。
悔しい気持ちももちろんあるがこの結果に納得してしまっている自分がいるのがとても悲しい。単純に上位勢にわからせられただけだった。
主な反省点としては単純に知識が足りていなかったこと、5時間集中することに慣れていなかったこと、Communicationを真面目に解いたことがなかったことなどがあったと自分では思っている。
とはいえJOI春は初参加で、コンテスト中にACを取れたことや他の参加者/チューターの方々たちとの会話で色々な学びを得られたことなどの貴重な経験ができた。ありがとうございます。
来年は代表になれるようこれから一年間しっかり自分磨きをしていきたい。