soraie's blog

趣味の話

JOI2022/2023 本戦参加記

はじめに

2/12にあったJOI2022/2023本選に参加して、春合宿に進出することができた。まだ春合宿があるが、自分の中で一つ目標としていた本選通過ができたので、ここまでのJOI参加記と少し過去の振り返りを書く。

過去

3年前に人に勧められて競プロを始める。コロナ禍だったのでやりこむ。

2年前、始めてJOIに参加する

soraie.hatenablog.com

本選は罠を踏んだり点数がかなり低くて散々だったが、初めての参加で本選まで進出できたことでかなり調子に乗っていることがブログからも分かる。

1年前、黄コーダーとして迎えた去年の本選、本選落ち黄コーダーという言葉があり、少し心配していたが、まあ春合宿はいけるだろと思っていた。しかし、結果は黄コーダー最低点で当然本選も落ちた。かなりショックで、去年は参加記を書かなかった。

そんなわけでJOI本選にはかなりトラウマがあった。

予選

一次予選

覚えてないが一回目が文化祭と被っていて二回目に参加した気がする。

二次予選

4完はしてEが勝負だろうと思っていたのですがDが難しく、通らなかったため辛かった。部分点もあまり取れず黄コーダー最低点。本選に対する不安が募る。

本選

2/5(開会式など)

自己紹介動画はやっぱり楽しい

ロシアンたこ焼きおもろかった

チューター企画はチームメイトが手動で作った解がめっちゃ強くてそこからチームメイトが焼いて総合2位!俺は何もしてない

2/6~2/11

憂鬱な気持ちでJOIの問題を埋めていた

2/12(競技当日)

7:30くらいに起きて朝ごはん食べた後にギターを弾いて、昼ご飯を食べてその後クッソ寒い中20分ほど走った。汗をかいた。おやつを用意して競技をスタートした。

競技パート

1問目

13:11 同じ色が連続するところがあるから圧縮して管理しておけば良さそうだと感じたのでそれを実装すると通る。

2問目

13:50 絶対値が出てきたの外して条件を眺めてみる。分からない。割と焦ったがとりあえず愚直を書いて69点を取る。

14:14 Eの降順で貪欲に取っていけばいいということは分かっていた。ここで「AがBに影響を及ぼしていて、BがCに影響を及ぼしているのならばAはCに影響を及ぼしている」ので、ある人が献本されたかはその人から近い今までに献本された人を考えれば判定できると気付く。実装してACを取る。

解けて少し安心したが、ボーダーはどうせ3完くらいあるのでそのままCを見る。

3問目

14:31 01-bfsをして壁の時は時は周りを見て一番コストが低いところから遷移、を書いて27点を取る。

14:51 二次元セグ木を使えば一番コストが低いところが高速に分かるので実装して86点を取る。

その後何度か定数倍高速化をして頑張るが一向にスコアが上がらないので、ここで一度4問目を見る。

4問目

15:32 $N\leq 5000$ のパスグラフは区間DPをすれば通るので提出して21点を取る。

この先を考えても分からなかったので5問目を見る。

5問目

15:43 とりあえず愚直を提出して3点を取る。

何回か操作をするとRR...RRBB...BBのような形になることは分かったが、そこから先が何も分からず。

その後も3問目の定数倍高速化をしてみるが通らず、4問目でDPを提出してみるがWAで競技終了。

終了後

結果は 100-100-86-21-3 で合計が310点。 3問目の定数倍高速化に固執しすぎたため4問目をあまり考察できていなかった。定数倍高速化は終盤でやるものであり、中盤は他の問題を考察するべきだったと反省。

3問目であっさり86点が取れてしまったの、「今回は簡単だったからボーダーが350点くらいあるのでは?」と思い焦る。点数情報を見ると自分よりも点数の高い人間が大勢いる。しかし、スプレッドシートを見てみると30位以内には入っていそうだったので少し安心する。相変わらず筑駒と灘は強いなあと思いながら点数を見ていた。

同期の点数を聞くとsouta_1326が2問目69点なのに合計で323点を獲得していてビビる。2問目捨てて3問目を取るの精神が強すぎて尊敬。to_omoT222が100-100-100-0-0で3問目を終了3分前に通すという異常ムーブをしたらしく精神が強すぎて尊敬。

解説を聞いて、2,3問目が自分の方針と割と違っていてびっくりした。45度回転は思いつかなかったし、区間に辺を貼るテクニックが賢すぎて感動していた。4問目が簡単らしくて泣いていた。5問目は解説を聞いている途中で分からなくなったのでご飯を食べながら聞いていた。

2/13

学校で春合宿通過を教えてもらう。開成が6人も通ってて嬉しかった。

おわりに

去年のこともあり、かなり嬉しかった。春合宿は初めてなのでIOIに行けることは無いと思うが、できる限りいい点数を出せるように精進をしようと思った。最近は趣味ややるべきことが増えて競プロをする時間があまりなかったが、やはり競プロは楽しいと感じた。

JOI2021 参加記

JOI2021に参加し、本戦まで残ることができたのではてなブログでの初めてのブログを書くことにしました。

また、とても悲惨な体験をしたのでそれも併せてここに書いておきます。

 

一次予選

まあまあここは大丈夫ですね。C++を封印してPythonで参加しました。

舐めプしてごめんなさい。

 

二次予選

このブログは本戦終了後に書いているので具体的なムーブは忘れてしまいました!!!

なのでおおまかな流れだけをここに書いておきます。

スタート

絶対に通るぞという強い意志を持って開始しました。

A問題を解く

結構実装が面倒でした。一回オーバーフローしましたが、早めに気づき、修正してACした。

B,C問題を開く

なんか算数オリンピックとかで見たことがあるなあとか思いながら解きました。

あとで調べたら本当にありました。結構難しかったのでC問題も開き、交互に考えました。

Bの解法が分かる

前処理で条件を満たすパンケーキの並びを全部持っておいてBFSをするという解法を思いつきました。パンケーキの並び方は 3^N通りなので、計算量を考えると前処理が O(3^N)でクエリが一つ当たり O(1)なので間に合います。
C,D,Eを考える
A,Bの200点では通らないだろうと考え、さっき考えていたCとD,Eを考えました。
しかし、なかなか分からず結局Dの小課題1(めっちゃ簡単なやつ)しか取れませんでした。
終了
コンテストが終わった瞬間は正直終わったと思いましたね
しかしtwitterとかで他の人の得点を見てみるとみんな意外と点数が低く、結果的に本戦に進出することができました。
本戦
正直強い人がいすぎて通る気が全くしませんでした。まあ結局通らなかったです。
だって黄コーダー以上が30人以上くらいいるっていくらなんでも異常()でしょ。
競技前日
開会式の動画がすごかった。
みんなの顔が見れた。
とりあえずすごかった。
あもんぐあす楽しかった。
感想が小学生。
スタート
春合宿行けたら嬉しいくらいの気持ちでしたね.....
もっと気合をいれなければダメでした。
Aを解く
Aを見ます。小課題1も分かりませんでしたが実験をするとなんかいい感じに解法が降りてきました。小課題1を取った後満点解法を書いて通します。
Bを見る
まず愚直を書いて小課題1を通しました。満点解法を考えます。
風のデータをあらかじめ解析しておくと雪玉の間の幅を利用することで満点が取れると考えました。実際これは合ってたっぽいです。
しかし、実装して提出してみるとTLEが帰ってきました。コードをじっと睨んでみますがバグが見つかりません。
C,D,Eを見る
とりあえずCの小課題1を通しました。しかしそれ以降は全く分かりません。
終了
結果138点で終わりました。解説を聞いてもBのバグは分かりません。モヤモヤした気持ちで本戦を終えました。
交流
いろんな人と交流できてとても楽しかったです。やっぱりあもんぐあすは楽しいですね。

 


 
後日
ABC192に参加しました。このコンテストのE問題のダイクストラがなぜかTLEしました。このせいでパニックになってしまい、緑パフォを出し、レートが40ほど下がりました。
睨んでも分からないのでEのコードをみせたところ、
#define _GLIBCXX_DEBUG
ここの部分を指摘されました。上のコードは書くことでデバッグをしやすくしてくれるのですが、これを書くと実行が遅くなってしまうらしいのです。
 この部分を抜いて提出したところ、ACしました。
 
え、これがなんで今回のJOI本戦と関係があるのかって?
 僕はJOI本戦のB問題で計算量は間に合うはずなのにTLEをしました。そしてそのコードでは
#define _GLIBCXX_DEBUG
とlower_boundを使っていました。もう分かりますね?僕がJOIのBでTLEをしたのは多分
#define _GLIBCXX_DEBUG
のせいです。悲しくなりました。
 
おわりに
オプションをつけないと#define _GLIBCXX_DEBUG されないようにしました。
もうこんなことは絶対にあってはならないのでこれから自分のテンプレートにコードを書き足すときには十分注意したいと思います。
ここまで読んでくれてありがとうございました。またいつかブログを書くかもしれません。