こんにちは、ZOIと申します。高3です。1年ほど前から競プロにハマっています。
自己紹介
AtCoder: ZOIZOI
AtCoderくらいしかやっていないので... 参加時点で水コーダーです。
チーム
パソコン甲子園では、同じ学校の2名で1チームを組みます。僕の学校ではPC部がなかった(僕の代で同好会ができた)ので、あまり競プロをやる文化はないです。
高3でAtCoderをやって"いた"(過去)人はいましたが、当然受験生なので皆さん忙しそうです(お前もやれ)
同好会を下の代へ宣伝していなかったので去年までほとんど後輩がいませんでした。
メンバーのほとんどが高3になってしまうと流石に存続が危ういので急遽宣伝をしたところ、高1がたくさん入ってきてくれて、そのうちの一人が競プロに興味を持ってくれました。
ので、その人とのチームです。5月にプログラミングを始めたと思うのですが、すでに茶色です。緑パフォを出すこともよくあるので期待してます。
チーム名は「sprouts」です。
もやしみたいにひょろひょろのやつ、をすごくかっこよく読んだ感じの意味なのですが、このチーム名についてはまた後ほど色々話します。
とりあえず結果
PCKでは謎システムが採用されており、予選の結果を予選終了後すぐに見れるわけではありません。
本戦出場チームの決定は9/25、点数や順位が正確にわかるのは本選後となります。
順位表の更新停止がコンテスト30分前なので、今言及できるのは終了30分前の情報まで、ということになります。
順位表はここ(もしリンクが切れていたらWayback Machine)から見れます。
上位30チームはこんな感じです。
19位ですね。ちなみにここから残り30分でP07、P08を一つずつ通したので、19位より下がっていることは無いと思いたいです。
PCKはどうやら「Top10+地方枠30」が本戦出場数らしく、地区予選枠としては関西は2~3枠だと言われています。(僕は関西の学校です)
また、同校制限(2チーム)もありますので、(もしこの順位が最終順位だとすれば) 4位 anmisted, 7位 iron wall, 9位 Terminal が同校制限により出場できず、13位 typoの達人までがTop10枠に入るわけです。
もしこうであれば、灘・白陵・明石高専・帝塚山あたりが関西だと思うので、sproutsは地区枠では関西1位ということになり、まあまあ希望が持てそうな気もしています。
が、最後の30分というのは何が起こってもおかしくありません。この時点で1点のチームが残り30分で200点にすることも理論上可能なので、まああとは運です。
くわしく
予選以前
実は僕は、去年のパソコン甲子園に出場させていただいています。(といっても競プロではない「モバイル部門」ですが)
その際、チームメンバーの中に灘チームに知り合いがいる人がいたので、その繋がりで灘の方々と雑談する機会がありました。
それまでも、灘は競プロがすごいらしい、NPCAは競プロをめちゃくちゃやってるらしい、という話は聞いており、「灘の同級生でものすごく強い人がいる」というのは頭では理解していましたが、やっぱり会ってみるというのは全然違いますね...なんというか、一気にリアリティが出たのを覚えています。
先ほど掲載したレート変動のグラフを見てみると、去年のパソコン甲子園が終了したあたりからいきなり開始しているのがわかると思います。PCKのおかげで、灘のおかげで、競技プログラミングにハマったと言っても良いでしょう。
なお、この去年のパソコン甲子園に出場したときのチーム名が「sprouts」です。といっても、メンバーは同級生3人で、今回と違います。
(今回チーム名考えるのめんどくさくてそのまま使いました。かっこいいので気に入っています。)
参加まで
受験は最悪来年もできるけど、高校生大会は今年までしか出れないな〜という舐めた考えで出場するのを決めました。一年生の人を誘って参加登録を(結構ギリギリで先生に迷惑をかけましたが)出し、夏休みはふつうに毎週AtCoderをやったりしてました。
夏休み終わりくらいに2022の過去問を解いてみたところ、僕が40点、相方が30点でした。
(とはいっても、なんか問題に見覚えがあったので、おそらく去年に一度目を通したのだと思います)
それまでは「本選には出れないだろうけど楽しめたらいいなあ」と考えていましたが、この結果を受けていきなり本選出場の可能性が出てきました。
PCKはテンプレートの利用や、事前に作成したコードのコピーなどが禁じられており、印刷されたもののみ参照できます。
僕はその時点では蟻本と螺旋本、そして鹿本を持っていました。しかし、蟻本と螺旋本はKindle、鹿本はPCKで使うには心もとないです。
とりあえず運営に「電子書籍はOKか?」とClarを出したところだめだといわれたので、急遽鉄則本を紙で買いました。
予選当日
とりあえず気合い入れるか、と思い、昨年の文化祭で作った同好会Tシャツを着ておきました。あと、去年のPCKでもらったパソべえのフィギュアを持っていきます。
競プロの大会ではフィギュアを持っていくのがよくあるらしい(要出典)ので、近くにあったぬいぐるみを持っていきました。北海道で買ったシマエナガです。(普段はデスクトップコンピュータの中に放置されています)
昼までふつうに授業なので、
12:40に4限終了 → たまたま終礼がなかったので食堂に走る → ラーメン食べる → 13:00に会場の教室に着く、先生と相方を発見 → 13:15くらいまでゆっくり準備
というふうになってました。
(ヘッドホンは耳栓代わりです、何も繋げずただ被ってました)
相方にいくつかチョコレートをもらい(気が利く)、コンテスト開始です
コンテスト中
まずは問題を見ます。予選を見た感じだと、~5点はある程度ぱっと解ける、~10点は考える、11~は運、という感覚です。
まずは問題1を見ます。日本語をうまく読めません...
適当に解いて提出です。
異常にジャッジが遅いな〜と思いながら問題2を見ておきます。
13:33:32 キャンディの分配 不正解 13:34:53
現時点: 0(-1), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
(それぞれ 提出時刻・ジャッジ完了時刻 だと思います)
嘘でしょ...という気持ちです。
コンテスト前に、相方と「このコンテストは同点の場合はペナルティ数で判定されるらしいので、落ち着いて一発ACを取りに行こうね〜」みたいな話をしていたのですが、すでにダメそうです...
AとNを逆にして計算していたことに気がつき、再提出をします。
13:36:43 キャンディの分配 正解 13:40:40
現時点: 1(-1), 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
一応ACです。
次に問題2を見ます。あー数学でやったことあるグラフだ、などと考えながら適当にコードを書きます。
13:40:35 的当ての判定 不正解 13:46:31
現時点: 1(-1), 0(-1), 0, 0, 0, 0, 0, 0, 0, 0, 0
全然だめです。ジャッジ待ちの間に問題3に移ります。
13:43:22 菌の祖先 正解 13:50:00
現時点: 1(-1), 0(-1), 3, 0, 0, 0, 0, 0, 0, 0, 0
一応これはACです。さすがにね...
問題4に進みます。
13:49:59 正方形 不正解 13:57:04
現時点: 1(-1), 0(-1), 3, 0(-1), 0, 0, 0, 0, 0, 0, 0
いやいや、全然合いません。流石に焦りが出てきます。サンプルは何故か合います。
とりあえず問題2に戻ります。問題をよく読むと、問題文の下に答えが書いているではありませんか...
泣きながら提出します。
13:52:58 的当ての判定 正解 14:00:02
現時点: 1(-1), 2(-1), 3, 0(-1), 0, 0, 0, 0, 0, 0, 0
さて問題4に戻ります。doubleの誤差かと思って色々やります。
14:04:47 正方形 不正解 14:09:11
現時点: 1(-1), 2(-1), 3, 0(-2), 0, 0, 0, 0, 0, 0, 0
悲しいです。こんなところで詰まっているわけにはいかないので、問題5を覗きに行きます。
素因数分解が見えましたが、あまり書き慣れていません。適当に書きます。
14:17:01 2023に似た数 不正解 14:18:23
現時点: 1(-1), 2(-1), 3, 0(-2), 0(-1), 0, 0, 0, 0, 0, 0
ペナルティだけが積み重なっていきます。
さすがにまずいので問題4をACしにいきます。
14:23:12 正方形 不正解 14:23:32
現時点: 1(-1), 2(-1), 3, 0(-3), 0(-1), 0, 0, 0, 0, 0, 0
なんなんでしょうね、これ...
ここで問題をよく読むと、「与えられた順に点を線で結んで、」と書いてあるではありませんか。任意順だと思っていました。どうりでACが出ないわけです。
14:36:24 正方形 正解 14:37:10
現時点: 1(-1), 2(-1), 3, 5(-3), 0(-1), 0, 0, 0, 0, 0, 0
なんとかACです。
次に、問題5に復帰します。
よくわからないコーナーケースかと思い、適当に場合分けを少しつけるももちろんWA。
14:40:09 2023に似た数 不正解 14:42:28
現時点: 1(-1), 2(-1), 3, 5(-3), 0(-2), 0, 0, 0, 0, 0, 0
すでに1時間以上経っていることに恐怖しながら、順位表を見ます。35位で、そこまで絶望ではありません。
一度考え直します。今まで使っていた関数を全部消し、少し違うやり方で考察します。
これまでは、「Nを割り切れる最小の数pを見つける」を3回やる、みたいな方針だったのですが、おそらく何かをミスっているか見落としているのでしょう。(まだわかってません)
「$N$が$p\times p$で割り切れるような最小の数$p$」を見つけることにします。これをもとにして、$\frac{N}{p^2}$を計算し、これがpと異なる素数であるならOKです。
14:54:52 2023に似た数 正解 15:00:31
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 0, 0, 0, 0, 0, 0
やっとACです。5点問題でここまで落とすか...と悲しくなります。
次に問題6です。
迷路、というからには当然BFSですが、入力形式を見て脳が止まります。
紙に書きつつ「あーたしかに3マスでいけるなー」などと考えつつ、問題を考え始めます。
まず通常のBFSではありません。グラフの辺を時間ごとに愚直に変化させると間に合わないでしょう。去年の問題でもあったように、BFSの情報に(x,y)だけでなくtimeも入れます。
timeをグローバルでインクリメントしてWA、それを直すと次はtimeに1を足すタイミングをミスってWA、などWAを量産します。
初提出まではある程度時間がかかっているものの、その後はある程度のスピードで修正でき、一応ACです。
WAの数はもう見ないことにします。このあたりでもうWAについては諦めています。
15:08:18 ダンシング迷路 不正解 15:09:29
15:12:07 ダンシング迷路 不正解 15:12:14
15:13:25 ダンシング迷路 不正解 15:13:26
15:17:33 ダンシング迷路 正解 15:18:21
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 6(-3), 0, 0, 0, 0, 0
次に問題7を見るわけですが、なんか制限がある上でのソート可能性についての話です。もし転倒数やソートアルゴリズムについての話であった場合、僕には無理です。
リスクを感じ、問題8を見ます。問題の概要とN<=8を見て順列全探索以外は無いな、と感じます。(一応8!を手計算しました)
ただし、小数問題なので誤差には気をつけないといけないかな、とも思います。
まずは紙に書いて考えます。時刻$t_0$において、自分からみたボールの相対位置を$(\Delta x, \Delta y)$、とします。このとき、時刻$t_0+t$で衝突するとすると、衝突位置はボールの速度$\vec{v_ball} = (v_x, v_y)$を用いて、自分がはじめに居た位置から見て相対位置$(\Delta x + v_x \times t, \Delta y + v_y \times t)$となります。また、人が$t$秒移動することでこの位置へ移動したことから、人の速度$v$を用いて、$(v\times t)^2 = (\Delta x + v_x \times t)^2 + (\Delta y + v_y \times t)^2$が成立することがわかります。ここから$t$を求めたいわけなので、tについての2次方程式の形に整理し、解の公式に放り込めばいいことは明らかです。
これを適当に実装します。
15:49:29 ボールの回収 不正解 15:49:35
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 6(-3), 0(-1), 0, 0, 0, 0
なんでしょうね...いつも通りサンプルだけは合います。
とりあえずトイレに行きます。ついでに順位表を見ます。相方がめちゃくちゃ頑張ってくれているので26位です。僕がWAしか出していないせいで、同点内では最下位しか取ることができません。申し訳ない...
とりあえず、doubleの誤差のせいで==0が動いていないのではないかと考え、修正します。
16:01:39 ボールの回収 不正解 16:01:48
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 6(-3), 0, 0(-2), 0, 0, 0
残り30分を切り、順位表が凍結しました。
これ以上この問題に取り組んでいる余裕はありません。
問題7は先程飛ばしましたが、順位表を見る限りそこまで難しいわけではなさそうです。難しそうに見えるけど簡単、ということは、思い付けばめちゃくちゃ簡単にできる可能性があります。
問題7を読みます。
はじめはindexとかとごにょごにょしたら判定できるのではないかと適当なことを考え、サンプルで死にます。まず、正当性が見えません。
制限が10^5なので、せいぜい$O(N\log N)$に抑える必要があります。まずは余裕を持って$O(N)$あたりで考えてみます。DPか...?この難易度ならありえるな...と考えますが、あまり大きなDPは無理です。ここで、1次元DPではないかと気づきます。
問題は、新しい候補が1つ増えたときどうするか、です。それまでの要素の中で最大のものは、当然一番右端にあります。つまり、新しい要素とswapされるのは、それまでで最大の要素です。これを使います。
16:17:37 ボールの並べ替え 正解 16:19:32
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 6(-3), 6, 0(-2), 0, 0, 0
これはかなり大きなACです! かなり嬉しいです。
残り時間は約10分です。ここから問題9に行ったとしても実装は間に合いません。当然、サンプルACまではできている問題8のデバッグをします。
といっても自分でサンプルケースを作ったとして、答えが合っているかどうかを判定できません。小数問題でサンプルが合っているということは、どこかの遷移が間違っているとか、多分その程度の間違いです。方針は合っているはずだと考え、作業を進めます。
誤差かもな、と思いlong doubleを使ったりもしますが、結果は変わりません。
16:20:36 ボールの回収 不正解 16:23:36
16:23:44 ボールの回収 不正解 16:29:21
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 6(-3), 6, 0(-4), 0, 0, 0
残り2分となり、いよいよ大会終了の香りがしてきたところで、コードの間違いに気が付きました。本来「$t$秒時点で球がいる場所」としなければならないところを、「$\Delta t$秒時点で〜」にしていたのです。
たとえミスがこれだけではなかったとしても、少なくともここは間違っているという確信がありました。PCの時計を見ます。あと60秒。
心のなかで、気持ち早めに秒数を数えつつ、全速力でコピーして提出。
ここでコンテスト終了です。
相方と「ごめんいっぱいミス出しちゃった...」などと喋りつつ、提出一覧を眺めます。
ギリギリで提出した人が多いのか、WAのまま全く変化しません。
もうそろそろ帰ろうかな、と思ったとき、
16:29:38 ボールの回収 正解 16:38:58
現時点: 1(-1), 2(-1), 3, 5(-3), 5(-2), 6(-3), 6, 10(-4), 0, 0, 0
AC。
相方に「あ、8番ACした...え?!?!」みたいな話をしつつ、部活のDiscordに結果を書き込みに行きました。
感想
まず、WAがあまりにも多いです。しかも、ある問題に囚われた、という感じはなく、まんべんなくWAしています。また、問題を読んでいないことで発生した時間ロスやWAも、全く無視できない量となっています。
いつもプレイしているAtCoderのサンプルが強い、というのはあると思います。しかし、いつもそれに頼っていることで、自らの正確性、問題文を一字一句読む集中力などが、自分の思っていたよりもずっと劣っているということに気が付きました。
ただ、競プロを始めたころに比べて、問題文から解法を読み取る力についてはある程度上がったと感じられます。
コンテスト全体の話で言えば、配点が去年より傾斜していて驚きました。去年の..., 12, 12, 36ですらなにこれ...と思っていたのですが、今年は..., 11, 11, 40とただただ差が広がっています。
これは自分の技量不足かもしれませんが、なんか過去問を解いたときに比べて(同じ点数で比べた場合)難化しているように感じました。実際、去年のコンテストに比べ、全体として5~7割程度の点数になっているようです。
本選に関しては、なんとも言えません... はじめのほうにも書きましたが、最後の30分でどれだけ順位が変動していてもおかしくありません。できれば通っていてほしいです。
もし通っていたならばの話ですが、他の本選erと会えることが楽しみです!