DECC2025 に参加しました。今までは DDCC という名前で開催されてきましたが、今年から DECC という名前に変更されました。
厳密には競技プログラミングの大会ではないのですが、昔から競プロer が多く参加している雰囲気があったので、参加したいなぁと去年から思っていました。しかし、予選が ICPC playoff とかぶっていたため、2024 年は不参加。今年初参加です。
予選
DECC の予選は、入力が与えられるので出力結果とコードを提出する、いわゆる MHC 方式になっています。ただし入力形式と出力形式がやや特殊なので、自分は入出力用のテンプレートを事前に用意していました。
その甲斐あってか（？）、予選は 1 位通過できました。
本戦
予選通過後のメールで、ユーザ名とランキング表示名の二つの名前を送らないといけなくて、自分はこれはどちらも違うものにしないといけないと勘違いしたため、ランキング表示名は potato167 でない名前(優勝ならかっこいい(?)名前)にしました。また、大文字も使っちゃいけないと勘違いしていましたが、大文字も使っていいぽいです。
前日は kusano さんの記事を読んだりしてました。
去年の問題を見て放物線と線分の交点の計算とかが出るのかなぁとか考えながら、事前に準備するのがだるすぎてそのまま寝てしまいました。
当日会場に9時前に着き、机の上にある紙を見ると 2021 - 2024 の問題とはまるで違う実機のイメージ図が書かれていました。T シャツのデザインや実機から予想するに、地面を傾けバウンドさせてボールを穴に入れる問題が出るのかなと予想して、頭の中でどういうコードを書くべきかを考えていました。
シュミレータ
9:55 - 11:00 の 65 分だったと思います。
問題内容はこちらから見れます。
簡単に問題を言うと以下の感じ。
- 3 次元表面上の z = 0 の平面上に輪っかが複数個あって、そこにボールを入れるのが目的。輪っかの y 座標は必ず正。
- ボールは (x, y, z) = (0, 0, 700) の場所から 21 回自由落下される。
- $k$ 回目の自由落下のタイミングでは、ボールとの反発係数が 0.9 である板が (x, y, z) = (0, 0, 20(k - 1) - 12.7) の位置にあり、あなたはこの板に対して以下の操作を順に行う。
- 板の中心を通り、 x 正方向と並行な直線を軸として、好きな角度回転させる。
- 板の中心を通り、 z 正方向と並行な直線を軸として、好きな角度回転させる。
- また、自由落下のタイミングで、どの輪っかに入れるかを宣言する。
- 宣言通りの輪っかにボールが入れば 100 点。板の傾きが大きいほど追加点。板の高さが高いほど追加点(最大 200 点くらい？)。違う輪っかに入れば 10 点で、ボーナス点はなし。
- 1 個の輪っかに複数ボールを入れたとき、最初に入れたボールの点数のみがスコアに加算される。
- テストケースは 5 個で、全てのテストケースの輪っかの数の和は 58 個
2024 年の問題では制御するものがテーブルの傾きと 4 つの棒の傾きであったのに対し、今回制御するのは板 1 枚であって、傾きも 2 種類しかないので、流石に実装し切れるだろうと思って、色々考えた後に実装する。
実装方針としては以下の通り。
- 輪っかの数が少ないときは、最初のボールはスルーする。
- 輪っかの距離が近い順に狙う。
- 板の向きのうち、 z 軸を中心として回転するものは三角関数で求め、 x 軸を中心とするものは、5.000 度から 45.000 度まで全探索し、一番近いものを採用する。
最終的にできたコードは以下の通りで、3667.75 点でした。
このコードは最後 1, 2 分で提出したもので、それまでは最大で 1000 点くらいしか得られていませんでした。
まず、コードを提出する際にシステムエラーが発生してしまうというバグがありました。これは自分のコンテスト中の調査だと同じコードを提出すると起こるもので、コード内に適当なコメントを打つと解消されました。
1000 点取る前は 100 点くらいで多分何もかも間違っていたと思います。遡って確認できた範囲で言うと、二次方程式の立式が間違っていた、二次方程式の解の公式を正しく覚えていなかった、度からラジアンへの変換やラジアンから度への変換。ここら辺は汎用的なので、ライブラリ化しといてもよかったですね。
1000 点から 3667 点まで上げた間で直したバグは反発係数の計算でした。固定面にボールが斜めにぶつかった時、反発係数が 1 でないなら入射角と反射角は異なり、反発係数は面に鉛直方向の速度ベクトルにしかかからないのですが、自分は単純に速度が 0.9 倍されるものだと考えていました。
このバグに残り 5 分くらいで気づいて 3, 4 分で修正し切って点数めっちゃ増えた瞬間は気持ちよかったですが、それでも 5800 点前後になっていないのは不思議に感じていました。
それはそうと、自分の高校数学や高校物理の実力の低下に驚いてしまいました。2019 年に受けた東工大模試と東大模試では物理の偏差値 80 は常に上回っていたんですけどね...
終わった後に人の点数を引き出そうと話していましたが、まるで点数についての話をしてくれない... 3, 4 人くらいで話しているときに 3000 点くらいだったとは言ったんですが、shinchan から「それよりは低かった」と言われたのが一番情報量が高い発言で、他の人からは何も情報が得られず。こたまねぎさんからは絶対黙秘するという意思を感じました。それはそうで、この問題をリアルに落としただけの問題を今後解くわけで、情報を言うことはディスアドバンテージになるからです。どこまで言っていいかを運営の人に聞いたんですが、特に線引きをしていないらしく、自分は話す内容に困っていました。
参加者の 62 人中 28 人が実機に進めるのですが、26 人しか通過者が発表されませんでした。多分、1 点以上取った人が 26 人しかいなかったんですかね...
このタイミングでは順位が発表されず、実機用コード提出の時間が始まりました。
実機用コード提出
競技時間は 40 分だったと思います。
ここで提出するコードの戦略としては 2 つほどあります。
- シュミレータのコードをそのまま出す。
- 何かしらの実験をする。
実験とかして何も得られないほうがやばいし、2 回しかないんだから最初から全入れ狙う気でいないとダメじゃないかと思い、シュミレータのコードのバグを探すことにしました。このフェーズで見つかったのバグは、輪っかの狙う順番についてです。今まで近い順にしてきたのですが、そうすると最後の方は輪っかにボールが届かないことがわかりました。なので、狙う順番を遠い順にしました。
実機用のコードを提出したときシュミレータのスコアが表示されるのですが、それでもスコアが少ししか伸びませんでした。でもバグが見つからないのでそのまま提出。
昼ごはん
昼ごはん中も休憩中もパソコンを触ることは禁止されています。運営の人に確認したところ、スマホで自分のコードを見ることは OK でした。結局 TUPC の順位表観戦したり人と話したりしたら時間が過ぎてしまいましたが...
休憩後、トライアルの結果が発表。1 位でした。4000 点も取れてないのにいいのかという感じですが、後で話を聞く感じほぼ間に合っていたのにバグがあってダメだった人が多そうでした。mtsd さんは板が上がる高さを間違えていて、Yu212 さんは高さの計算方法がバグっていたみたいです。
あの、本当にしょうもないバグ（高さの計算に発射回数ではなくターゲット番号を使っていた）を直すだけで7400点くらい出ます……
— Yu (@Yu_212_MC) 2025年3月23日
当時はそんなんことはあんまり知らないので、間に合ったの自分だけだったんかなぁとか思ってました。
トライアル 1 回目
競技時間は 70 分だったと思います。
自分はトップ通過だったので、競技開始の時点で機械の前にいました。
終わった直後に紙が渡され、739.859 点であることが告げられました。
板の傾きが浅いやつについて、以下のダメなポイントが挙げられます。
- 全く届いていない(誤差が大きいと判断)
- 入らなかったときに、他の穴に入るなどの邪魔になりやすい
この時点で 2 バウンドの線は完全に消えました。全部直で届くのにそんなことをするのは色々な面でリスクと考えました。
ということで、板の傾きだけ大きくしようとしました。具体的には輪っかに一番近いものを採用するのではなく、輪っかにある程度近いもののうち一番傾きが大きいものを採用するということにしました。また、入れる順番を全部入ったときのスコアが最大になるようにしました。この順番は bitDP で $O(N2^{N})$ で求まります。($N$ は輪っかの数です。)
以上のことを考えたり実装したら時間がなくなってしまいました。それでもスコアが伸びなくてよくわからないなとなっていました。
トライアル 2 回目の直前に自分に対してインタビュー的なものがありました。下記に記事の 2 ページに載っていますが、要約すると「うまくいったり、いかなかったり」と言ってるだけで、ほぼ何も喋ってないのと同じじゃねーか。
トライアル 2 回目
競技時間は 70 分だったと思います。
1664.644 点
とりあえず板の傾きを多くして、鋭い角度でボールを輪っかに狙うという作戦はうまくいっている。入らなかったのもほとんどが弾かれなので、これ以上どういう修正を加えればいいのかわからない。この時点で課題として挙げたのは以下の 2 点
- 手前の端の輪っか (1 番、7 番) は外側に大きく外ししている。
- 手前の真ん中 (4 番) が全く届いていない。
それぞれに対して修正を加えたかったが、大きく修正して本番のスコアが下回るのが怖かったので、以下のように修正を入れました。
- 端の輪っかを狙うときは、0.1 度だけ内側にする。
- 「輪っかにある程度近いもののうち傾きが一番大きいものを採用する」のある程度の値をより厳しくした。
20 分くらい残してコードを提出。
直前に手を加えてミスるというのがいつもの自分なので、20 分くらい時間を余してパソコンを閉じてしまった。
コンテスト後に nok0 や bayashiko さんが話してる内容を聞いていたところ、自分が板の z 軸の回転の計算するときに、arctan にしなければいけないところを arcsin で計算していることがわかりました。cos が大きければ誤差はほぼないのですが、角度が大きくなればなるほどこの値のズレが大きくなります。だから 1 番と 7 番のズレがデカかったんですねー。実機のせいにしていましたが、自分のせいでした。シュミレータで点数が低かったのも納得です。
mtsd さんはシュミレータのジャッジを書いていたらしくて、コンテスト中にかけるくらい楽であるなら書いたら良かったなぁと思いました。そうしたら気づけたかもしれない。
ファイナル
トークセッションを聞いた後にシュミレータの順位が低い順に競技が行われます。
最初 4 人の点数が渋かったのを見て、もしかしたら 1600 点でも優勝あるのではと緊張していましたが、 5 人目で 2900 ↑ 出て肩の力抜けました。もう勝負あり。
DECC2025 実機優勝！
— CoCo_Japan_pan (@CoCo_Japan_pan) 2025年3月23日
シミュは正の得点最小値10点で26位でした。
ノーバンで遠くから順に狙い、飛ばない分の補正は一律玉一個分にしたら想定以上に入りました。#DECC2025
自分は最終出番で、その時点で 3 位を取るには 2100 点以上は必要で、かなり無理なのではないかと思っていました。
自分の結果がこちら。
最後なのに全然盛り上がってなくて草。3000 点には行きそうにないのと、同じものを 30 回見せられているからですかね？
一応 3 位という賞金圏内に入ってホッとしました。
ボールが弾かれる回数が気持ち少なかったのと、たぶん 4 位の方が提出した出力結果が 1 行足りなくて、最後の 1 球が発射されなかったという事件があって、それが入っていれば 4 位に落ちていたはずなので、かなり運が良かったと思います。
左上の名札を見て貰えばわかるのですが、名前が書いておらず顔を知らない人に関しては誰なのかわからなかったので名前があると嬉しいですね。あの機械をわざわざ作っているのだからお金の問題はないと思うのですが...
終わりに
自分の想像していたより楽しかったです。結果が良かったからかもしれませんが... 今年は色々なイベントが重なったり、広報がちゃんとしていなくてスルーしている人も多かったので、予選の参加者も少なかったかもしれませんが、来年は歴戦の猛者が予選に参加してくるように思えるので、今回みたいにいい成績を残すのは難しいかもしれません。来年も予定が被っていなければ参加しようかなと思います。
