JOI'22参加記

##はじめに
どうもみなさんこんにちは。高校2年生のUltimateBlackteaです。
運営さんからJOI'22参加記書きましょう！と言われたので書きます。
Qiitaはほとんど執筆しない人間なので、駄文にはなりますがご容赦ください。

##簡単に自己紹介
中学3年の冬からPythonで競技プログラミングをやっています。今年に入ってAtCoder水色になりました。去年のJOI'21は本選落ちだったのですが、今年はなんとか通ることができました。

AtCoder

##Day1
1日目の公式な行事はプラクティス(競技システムの確認など)のみでした。
自分は普段からPythonを使っている人間なので、コンパイルのシステムや挙動などの確認、環境のチェックは欠かせませんでした。

タイムスケジュールとしては、15時に開会式がスタートし、16時から18時までプラクティスという感じだったのですが、leafirbyさんがプラクティスの後にamong us会を企画されていたので、それに参加させて頂きました。僕がいた部屋はtatyamさんやひらきちさんなどすごい方々がたくさんいました...

交流会が終わった後は晩御飯を食べて、しばらくTwitterなどを見て21:30頃に床に就きました。

##Day2
2日目はいよいよ本番です。競技は9:00に始まるので、8:00前後に5本アラームを設定していました。なんとか8:30頃に起床することができ、軽く朝食をとって本選に臨みました。詳しいムーブや問題の感想は後ろに詳しく書こうと思います。

##本選競技
僕は自力で解けるのが難易度7の一部の問題までだったので、始まる前は200点程度取ることができればままあまあ上出来かな、ぐらいに思っていました。

###結果

A	B	C	D	E	Total
100	100	5	8	0	213
順位表によると80位ぐらいみたいです。
B満点取れたのは良かったけれどCDEの部分点取るべきだった。

###大体のムーブ
解いた順番としては、A->B->C->D->C->Dという感じです。
とりあえずAを30分で通して、Bを部分点に沿って考察を進めて60分ぐらいで通して、あとはCに30分、Dに90分ぐらい時間をかけました。

###A
とりあえず手元で実験してみて、それぞれの長さを2^x*y(yは奇数)の形で表したときに、yの長さのカステラが2^x個でできそうだな、と思ってオーバーフローに気を付けつつ累積和を実装、脳死lower_boundで無事満点。
解説で言及されてたけれど、実は制約でクエリが左から順番に来ることが保証されていたので、二分探索をせず愚直に追っていく解法もあったみたい。

###B
問題を読むとどう見ても「最小値の最大化」なので決め打ち二分探索を思いつきそうだけど、頭がまだ働いていなかったので一つずつ部分点を取っていくことにした。
#####小課題1
N教科についてN回勉強できるので、全て1回ずつ勉強しないと最小値が0になってしまう。となると、1科目ずつ授業を受けた場合と自習した場合のmaxを取っていって、その最小値が答え。

#####小課題2
それぞれ教科の理解度を大体同じぐらいにすれば良さそうだよな~と10分ぐらい考えて、「あ、**i教科目について理解度Xに必要な回数はX/b[i]**だな」と気付き、「あぁ、理解度決め打ちすればいいじゃん」とやっと気づく。ここでBに入って30分経過。決め打ち二分探索を実装してAC。

#####小課題3
自習した方が授業を受けるより効率がいい時は、授業を受ける必要性が無くなるので小課題2と同様にすればOK。そうでない時は、授業は最大M回まで受けることが出来て、ある授業を受けても、他の科目の授業を受けられる回数に影響しないことを考えれば、

a[i]>b[i]で、ある教科iについて理解度をXにしたいとき、
1. 授業をX/a[i]回受ける
*2. 授業をM回受けて、(X-a[i]M)/b[i]回自習する

のが最適であることが分かる。これを実装すれば満点が取れる。
なお、

• 1<=a[i],b[i]<=10^9
• 1<=M<=10^9

なので、二分探索のhighの初期値は10^18以上でないといけない(ここでオーバーフローして通せなかった人がまあまあいるみたい)
僕はunsigned long long intを使って通しました。

#####C~
自分は小課題1しか通せなかったのでまた時間があれば書きます。

##チューター企画について
実は1日目の夜に、E8さんから双子主催の非公式なチューター企画が告知されました。その時点では詳しい内容までは公表されず、僕は懇親会的なものかと思っていました。
肝心の内容は、本選競技の解説終了後、16:00頃に説明がありました。
概要は以下のようなものです。

• 3~4人でチームを組み、ヒューリスティックな問題を解く
• 各チームで問題に対する解答コードと入力ケースを作成し、提出する
• 互いの入力ケースを解き、スコアの高かった方が勝利
• 全チームでトーナメント戦を行う
• 優勝者には「アルゴリズム×数学」本が贈られる
• およそ問題の内容は、2種類に塗られたマス目について、任意の長方形の領域を選び、180度回転させる操作を繰り返し、少ない操作手数で定められた目標のパターンに近づけられたほどスコアが高くなるというもの

僕のチームは、僕に加えyutoさん(!),ryu150さんともう一人の方(IDが分からない)で構成されていました。競技開始は17:10で、最初の10分ほどはyutoさんとボイチャで考察をしました。
考えたことは主に次のようなことです。

• 長方形の対角線上にあるマスをswapさせる操作とできる
• 目標のパターンに1マスずつ近づけていくことを考える
• 最大でも2手あれば任意のマスを任意の場所に移動させられそう
• ということは入力に関わらず目標パターンに一致させられそう
• とりあえず各人この方針で実装してみる

僕は一通り考察をした後、書きなれているPythonで実装をしたのですが、**競技終了1時間前の18:00頃に、yutoさんが実装を終わらせて下さいました(速い?!)その後もランダムケースの作成、テストなど全てyutoさんがやって下さいました。(凄すぎます...)**終了10分前になって、チームメイトの皆さんが作成して下さった入力を試し、解答コードとランダムに生成した入力ケースを提出しました。最終的な作戦は以下の通りです。

• 右上の方から色を埋めていく
• 持ってくるマスの場所はランダムに選択
• これをTimeLimitの許す限り繰り返して、最も操作回数の低かったものを出力

そして対戦が始まりました。他のチームが20台の操作回数だったりバグを起こしている中、yutoさんのコードは15前後の操作回数で圧倒していました...

アルゴリズムで決定的な部分は右上から埋めていく、という単純なものなのですが、乱択を回したことで一気にまとめて移動させたり、より効率的な操作手順を見つけることができたようです。

結果的に、なんと僕のチームは優勝してしまいました。(yutoさんありがとう...)「アルゴリズム×数学」本を贈呈していただけるそうなので、大事に読ませていただこうと思います...

##振り返って
人生最初で最後のJOI本選だったのですが、めちゃくちゃ楽しく、とてもいい経験になりました。参加することが出来て、本当に嬉しいです。しばらく受験で競技プログラミングからは身を引かざるを得ないですが、大学に無事入学できた暁には、またやろうと思っています。

最後になりますが、JOI'22を運営してくださったみなさん、そして参加者のみなさん、本当にお疲れ様でした！そして、ありがとうございました！