概要
9月9日に開催されたパソコン甲子園2023(PCK)プログラミング部門予選に出場しました。結果は1~9問正解の9完で、ペアと合わせて計15完7ぺナの10位(順位表凍結時点)でした。
チームは同学年のamino君と組んで、名前は「Rate-Mikan」。3つ上の先輩方が使っていた名前です。敬意をこめて。
予選まで
正直競プロ全然やっていなかったです。ゲームして、情報科学の達人プログラムの講義動画見て、ちょっと勉強。競プロは週一のABCくらい。しかもABCの成績は低迷気味でそこそこに焦っていました。去年のPCK予選で8完したから、という謎の自身だけで生きていた...
それまでの高校生活ではPCKの本選に出たことがなかったので、高3である程度のことを勉強に捧げなければいけないとはいえ、PCKへの参加を決めました。あわよくば入試の総合型で使えれば～などと妄想。会津行きたい。
と、PCKの前に相方のaminoのお話。彼はものすごく数学ができて、OMC青のつよつよ。今年の数学オリンピックで予選を突破、日本代表にまでなってしまった。メディアの取材などを受けたのちに、いざ幕張メッセでIMO開始。見事銀メダルを獲って帰ってきました。すごい。(ちなみにNHKからの取材には僕もちょっとだけ出させてもらった)。競プロもしっかりできて、JOIでは予選を突破、本選ランクBを取ってます。
そういうわけで本選ランクBペア(JOI2022記事参照)でPCKに望みます。
当日
悲報。aminoのクラスで学級閉鎖発生。
クラスに半分程度しか来ていないらしく、なんと学級閉鎖に。amino含めクラスの生徒は帰宅を余儀なくされます。PCK大丈夫かどうか本当に焦った。
授業が終わって放課後。やはりaminoはいないか...と思いながら、飲み終えたペットボトルを捨てるべく廊下を歩く僕。
するとそこにはaminoが！
どうやらあの後に近くの図書館に行って自習していたらしい。ありがとう。
その後PCKを受験する教室を顧問に聞くべく職員室へ。場所を聞いて、夏の暑さでバッテリーの膨らんだ爆弾(wifi)を受け取ると、衝撃の事実を知る。なんと僕らの他に2組の高1がPCKに出場しているではないか！(ちなみに、その前に顧問から送られていたIDとパスワード諸々のメールにしっかり書いてありました)
そして教室。コンセントの位置を確認し、昼食をとってパソコンを広げる。いろいろ動いた結果、爆弾を教室の真ん中において、それをみんなで囲むようなレイアウトに落ち着きました。
それからは参加チーム一覧を眺めて面白い名前を見つけながら待機。
13時30分。予選開始。ぞい！
コンテスト
問題1 キャンディの分配
A個のキャンディをN人の友達と分けたら、何個余るか？
剰余。提出。AC。(00:01:29)
問題2 的当ての判定
座標(x,y)に当たった矢は4点(0, d),(d, 0),(0, -d),(-d, 0)で囲まれる正方形の的の中か？
マンハッタン距離。提出。
...なかなか結果が返ってこない。1000人の提出を相手取ってるので時間がかかるのは当然だと気づいて。少しだけ祈って次の問題に取り掛かる。(00:03:03)
問題3 菌の祖先
ある菌iは繫殖時2個の菌2iと2i+1を生成し、その後繁殖しない。この時、菌bを祖先を順にたどれ
2で割り続ける。提出。祈って次。(00:05:10)
問題4 正方形
与えられた平面上の4点を順に結んで閉じたら正方形になるか
ちょっと悩んだ。というのも、点をたどるにしても右回りと左回りがあるので、安易に角度は使えない。複素数チックにやるのもなんとなく面倒。
というわけでとりあえず図を書いてみる。そこで対角線を使えば良い感じに判定ができることに気づいたので、対角線の長さが等しく、直交する条件を書いて提出。祈る。他の問題を解いてから見るとWAで帰ってきた。悲しい。(00:10:08)
コーナーケースを考えると、狐のような形だと漏れてしまうことがわかった。こんなの。
というわけで角度の条件を2つくらい付け足して提出。祈ってAC。(00:40:50)
問題5 2023に似た数
整数Nは異なる素数p,qを用いてN=p×p×qと表せる数(「2023に似た数」)か？
二つ解法が考えられた。
- Nを素因数分解して考える
- 「2023に似た数」を列挙して、Nがそれに含まれるか判定する
ただ、二番目はなんとなくいやな気持ちがしたので、素直に前者で。
素因数分解した結果の素因数を配列Pに保存。その後、
- Pのサイズが3
- unique/eraseした後のP'のサイズが2
として判定。祈って次。(00:14:22)
問題6 ダンシング迷路
H行W列のH×W個の部屋で入口(1,1)から出口(H,W)まで移動したい。部屋同士は扉でつながっている。プレイヤーは手をたたきながら部屋を進み、3拍周期で開く扉が変わる。プレイヤーは手をたたくごとに部屋を1つ移動する必要があり、移動できなければゲームオーバーとなる。最小で何回の移動で出口に到達するか？
ここから教室内にPCの打鍵音が響かなくなってきた。
問題に戻ろう。これは部屋に加えて拍数を加えた頂点拡張BFS。
制約を見るとHとWが100程度で時間が十分あることを確認して、安心して計算量にlogをつける。なぜなら、適切に比較演算子を定義した構造体を用意すれば、std::mapの添え字としてそれが使えて、実装がかなり簡潔にできるからだ。
頂点を拡張する以外はいたって普通のBFSなので、そんなにかからず提出。問題4と一緒に正解して次へ(00:34:03)
問題7 ボールの並び替え
それぞれ大きさの異なる箱とボールがN個ずつある。これに対して、隣り合うボールを交換する操作のみを行ってボールを昇順にソートする。このとき、常に「ボールの大きさ≦箱の大きさ」となるようにできるか
ちょっと悩むが、ボールの入れ替えが隣同士しかないのでバブルソートを考える。すると、ボールは最初のいる位置からソート後の位置に一直線で行けばよい(一次元だけど)。つまり、その区間でボールが詰まらなければ良いわけだ。
というわけでボールを添え字込みでソート、それぞれのボールの移動経路にボールより小さい箱があるかどうかをセグ木で判定して提出。祈って次。(00:52:25)
問題8 ボールの回収
二次元平面状を動くN個のボールの位置とそれぞれの速度が与えられる。ボールの回収者は始めは原点にいて、一定の速度vで動き続ける。回収者はボール回収時のみ方向転換ができるとき、全てのボールを回収するまでにかかる最小の時間を求めよ。
問題7がボールの並び替えだったので、箱から取り出すのかなぁなどと思っていたけどどうやら違う様子。
制約を見るとNが8までなので回収する順番は全探索できそう。とここで問題が。次のボールに向かうときにかかる時間を求めるには二次方程式を解かなければならないのだ。ちょっと嫌なので他の問題を解いてからにしようと思う。
問題9 色鉛筆とキャップ
N色の色鉛筆と、MセットのN色のキャップの入った袋がある。はじめ色鉛筆にはキャップがなく、これに対して
袋から無作為に一つキャップを取り出して、そのキャップと同じ色の鉛筆にまだキャップがされていなければキャップをし、そうでなければ破棄する。
という試行をT回行う。このとき、T回の試行の後で全ての色鉛筆にキャップがついている確率をMOD998244353で答えよ
解いてて一番楽しかった問題。
最初読解に少し手間取ったが、何とかして問題を下のように簡単にできた
M個ずつN色の玉から無作為にT個取り出したとき、N色すべてそろっている確率を求めよ。
さてここで制約を見る。
1≦T×N≦100,000
ーーー神は言っている。ここでDPを使えとーーー
ご丁寧に添え字まで教えてくれたので、これは好意に応えてDPを使うのが礼儀というもの。
新しい色が引かれるとき、袋にはその色がM個入っていることに気を付ければ、
dp[i][j] := i個玉を引いて、j色そろっている確率
とすると遷移が書けるのでそれでDPを書く。
提出してACを確認。2次方程式を解く覚悟を決めて問題8に(01:16:27)
問題8再び
さて解くぞーと思っていろいろ変数を決めて二次方程式を立てて整理。
出来上がった式を見ると、どこかで見たことのある形がたくさん。ベクトルの絶対値と内積である。
ここでようやくベクトルで式を立てれば簡単になることに気づき、Vec2ライブラリを駆使して方程式の係数を計算、解の公式に投げる。AC。Vec2ライブラリはいいぞ。(01:54:05)
予選後聞いた話だと、二分探索で行けるとのこと。その手があったか...
問題10,11
問題10と11を眺めて、問題10の方を考察するも、なかなか計算量が落ちずに予選終了。無念。
考察中に順位がずるずると落ちていくのを、aminoのACで何とか持ち直す。アツい。
順位表は10位で凍結。怖すぎる！というのも、上位10位は確定で本選へ出場するものの、それ以下だと成績に加えて地域性が考慮されてしまう。3年前の先輩方はその地域性で落とされてしまったらしい(?)。
感想
凍結時順位10位で、そこから他チームのACで15位程度まで落とされてそうなので、おそらく地域制考慮枠と予想。とはいえ、今までの3回で最高順位を取れているし、去年本選に行ったペアが20位程だったので本選にはいけるでしょう。会津行ってきます。
あとは大きなぺナなどなくいけたのは良かった。
あとは本選チーム発表の9月25日を待つのみ。