終了から2日も経過してしまい，詳細に書くような暇もないので，勝負のポイントとなったと考える点を手短にまとめる．普段の競プロとはかなり毛色の異なるコンテストで，実装時間が特に短く，トライ&エラーの機会も少ないので戦略をその場で詰めるようなことはしづらい．実機では思わぬ誤差によるズレも頻発するので，そういう意味でも偶発的な事象がかなり結果に影響するコンテストだと感じた．
実装すべき課題の難易度に比べて実装時間が非常に短く，事前準備が全くないと本番で何もできないということも考えられる．勝ちに行くなら最低限過去問に目を通しておくべきだろうと思う．
なんでこんな運ゲーを本気で振り返っているかと言うと，運ゲーの割に賞金がやたらと高額だからである
今回の分も含む過去問はこちらから確認できる．(もう本戦の問題も上げられているようで助かる)
ルール概要
- 昨年と同じように長方形の盤面の一辺の中央に取りつけられた発車口から球を発射して穴に入れる競技．
- 1つの穴につき10個までの球が有効な球とみなされる．
- 発射する球は70個まで．
- 連射の際の時間間隔は0.5s．
- 制限時間が50秒で，非常に短い．すべての穴をまともに10発ずつ狙うと時間が足りなくなる．
- 得点は(有効な球の個数)*(1個以上の球が入った穴の個数) である．1個以上球が入った穴を増やすべく様々な軌道で穴を狙うことが肝要である．
- 今回追加された要素は盤面に鎮座する3本の巨大なバー．しかも発射の向きを変えるたびに面倒なルールに従って向きが変わってしまう．どこを狙うにもこれが非常に邪魔である．バーの隙間を狙う，台の傾きを利用してバーを迂回する，バーの回転の向きを調整するなどの工夫が必要．
シミュレータ実装中に考えたこと
- まずは入出力を実装する．どう見てもx座標とy座標が逆の方が計算しやすいし，回転角はなぜか時計回りに与えられるし，とにかく意地悪な問題文である．DDCCの社員の方は普段から回転角を時計回りで表記されているのだろうか．
- ひとまずはバーのことなどは忘れて，台を傾けずに各穴に直線軌道で10発ずつ打ち込むコードを書く．入力が正しく受け取れているかのチェックでもある．シミュレータで260点を得る．5ケースあるので平均すると7個中2個程度の穴に収まっているようだ．少しほっとしたがこの時点で30分ほど経過していた．
- バーへの衝突や他の穴に落下することを防ぎつつ狙った穴に入れるには迂回するような処理が必要だ． シミュレータ実装時間中にこの実装が間に合うとは思えなかったが，装置実装では必ず使う処理なので少しでも書き進めるようにした．また発車方向の傾きはどうせ計算できないので，左右方向の傾きだけを実装することにした．
- 台の各支点の高さと発車角度とx座標(問題文におけるy座標．自分のコードではここを逆にしている)を引数にとり，そこでの球でのy座標を返す関数を書いたあたりでシミュレータ実装が終了．熱烈準備勢はたぶんこの辺まで事前にやってたんだろうなあ．
会社説明を聞きながらこのあとの実装を頭で考える．デカすぎるバーのよけ方をどうしようか…
装置実装 (前半)
- 実装方針が固まってくる．
- 手前の穴から狙う．
- ランダムに台の傾きを決め．二分探索で発車角度を決める．
- 狙った穴に落ちる前に他の穴に落ちたりバーにぶつかったりしたら探索をやり直す．
- バーの角度の調整はいったん諦めて，常に真横を向いていると想定することにした．
- 終了20秒前くらいにバグが除去できて，ギリギリ提出完了．シミュレータは10点を返していた．
実機観察
- この時点では，他の人はあまり台を傾けずに直線で狙っていた気がする．みんな手前のバーで弾かれていた．手前の穴に40発くらい入れていた人もいた．
- 初手で一番奥の穴を直線で狙って入れていた人がいて，これを自分も真似することにした．
- 自分の番について．
- バーにぶつかりまくって散々だったが，まぐれで5個の穴に入った．これは意外と適当に傾ければチャンスがあるのではないかと思った．
- 110点を得て中間順位は4位となった．
- 軌道の計算がうまく行っているように見えた部分があり，手ごたえを得た(ただし，後から見返すとこれは勘違いだった．どのタイミングでどの穴を狙うのかを把握しながら観察すべきだったと反省している)．
- シミュレータ15位以降の人はそもそもまだまともなコードが完成していなさそうな人も多かった．このあたりから他の人の観察をやめて自分の録画を見返しまくって残りの30分で書くべきことを頭で考え続けていた．
装置実装(後半)
- 穴を狙う順番や探索を打ち切るかどうかの判定をより洗練させた．バグをいくつか直した．あまり覚えていないけど，優勝できるかもと思いながら書いた．
- 一番奥だけでなく右側の穴も直線で狙うつもりだったが，なぜかシミュレータ上でうまくいかなかったので仕方なく放物線を探索する方針に切り替えた．
- 2番目の穴はどういう軌道でも入らなかったので最後の10発は適当に打つことにした．
本番
- 直線で狙った奥の穴に10発中2発しか入らず真っ白になった．誤差大きすぎるやろ．それでも全部外れるよりはかなりマシだが．
- 放物軌道が若干ずれていることによる取りこぼしがかなりあった．中間実装のときに見逃していた点だったので，今見ると少しもったいない．
- バーの回避はかなり上手く，そのおかげでいくつかラッキーを拾うことができた．この点は上手かった．
- 結果は5位．あと4発入っていれば賞金圏内だったので最初の取りこぼしが悔やまれる…．
- 2番の穴には1~9位の人は1発も入れていなかった．やっぱあそこ入れるのって運に頼らないと無理なのでは？
- 多分最適は直線で狙える4つの穴に40発打ちこんでから中央の3つを台の傾きで狙うことだと思う．最初の40発で台を傾けないことにより，待機時間を0にすることができるのも大きい．また当然だが直線の方が実機特有の誤差は減る
- どうしても入らない2番の穴だが，球が転がっている最中に台を傾けるなどの戦略に賭けることになりそうだ．
次回への教訓
- 問題文にある角度や座標の記法(時計回りなど)に気をつける．単位も．
- コードはある程度準備してから行く．今回はたまたまうまく行った方だが，初見の問題だと本当に何もできずに負けることもありそう
- シミュレータの点数がどのくらい参考になるかは問題による．今回は直線軌道の確認くらいしか参考にならなかった．
- 他の参加者のお試し実装を観察してヒントを探る．
- 自分のお試し実装を眺める際にはどの動きが何を狙っているのかを把握しながら見る(良さげな動きをしていると，それが非想定のものであっても見逃しやすい)
- 誤差が少なそうな方針を考える．
- 幾何ライブラリを出しておく
- あとはお祈り
提出したコード
なんとなくライブラリ使って良いかどうかが気になって，珍しく<bits/stdc++.h>から書いてしまった．他の方は普通に自前の幾何ライブラリとか使ってたらしい．ちょっと損した．
#include <bits/stdc++.h> using namespace std; const double pi = acos(-1); #define rep(i, n) for(int i = 0; i < int(n); i++) using point = pair<double, double>; void point_in(point& p) { double x, y; cin >> x >> y; p = make_pair(y, -x); } point convert_point(point& p) { return make_pair(p.second, -p.first); } double distance(const point& p) { return sqrt(p.first * p.first + p.second * p.second); } const double speed = 500; double time_to_run(const point& p) { return distance(p) / speed; } double arg(const point& p) { return atan2(p.second, p.first); } int convert_to_theta(double angle) { double deg = angle * 180 / pi; return -int(deg * 1000); } // pi rad = 180 deg // ang rad = 180 / pi * ang double rad_to_deg(double radian) { return 180. / pi * radian; } double deg_to_rad(double deg) { return 1. / 180. * pi * deg; } bool range_chk(int value, int low, int high) { return low <= value && value <= high; } int counter = 0; void print_ans(int ch, int lh, int rh, int theta, int nu, int tm, bool is_end = false) { assert(range_chk(ch, -5000, 1000)); assert(range_chk(lh, -25000, 25000)); assert(range_chk(rh, -25000, 25000)); assert(ch * 2 >= lh + rh); assert(range_chk(theta, -45000, 45000)); assert(1 <= nu && nu <= 70); assert(range_chk(tm, 0, 60000)); cout << ch << ',' << lh << ',' << rh << ',' << theta << ',' << nu << ',' << tm; if(is_end) cout << ';'; cout << '\n'; counter++; } // unit: mm, second double theta_to_acceleration(double theta) { return 5. / 7. * sin(theta) * 9.8 * 1000; } double acceleration_to_theta(double a) { return a * 7 / 5 / 9.8 / 1000; } double calc_y(double x, double theta, double a) { const double time = x / (speed * cos(theta)); const double vy = speed * sin(theta); return vy * time + a * pow(time, 2) / 2; } double calc_theta(double x, double y, double a) { double theta_max = pi / 4; double theta_min = -pi / 4; rep(i, 100) { double theta_mid = (theta_max + theta_min) / 2; if(calc_y(x, theta_mid, a) > y) { theta_max = theta_mid; } else { theta_min = theta_mid; } } return theta_max; } void solve() { counter = 0; const int n = 7; vector<point> holes(n); rep(i, n) { point_in(holes[i]); } sort(begin(holes), holes.end()); const double bar_halflen = 100; point alpha, beta, gamma; point_in(alpha); point_in(beta); point_in(gamma); const double xmin = 0; const double xmax = 1000; const double ymin = -400; const double ymax = 400; int count_ball = 0; int time_remain = 100000; auto convert_bar_angle_to_my_plane = [&](double value) { return pi / 2 - rad_to_deg(value); }; auto alpha_angle = [&]() -> double { int div_count = 0; for(int i = 1; i < count_ball; i++) { if(count_ball % i == 0) div_count++; } // return pi / 2 - rad_to_deg(double(div_count) * 30); return convert_bar_angle_to_my_plane(double(div_count * 30)); }; auto beta_angle = [&](double ch, double lh, double rh) { return convert_bar_angle_to_my_plane((ch + lh + rh) * 100); }; auto gamma_angle = [&]() { return convert_bar_angle_to_my_plane(counter * 35); }; auto in_range = [&](double a, double low, double high) { return low <= a && a < high; }; auto calc_a = [](double lh, double rh) { const double sin_steep = (rh - lh) / 800; const double a = theta_to_acceleration(asin(sin_steep)); return a; }; const double hole_radius = 20; auto in = [&](double ch, double lh, double rh, double theta) -> int { int ret = -1; const double a = calc_a(lh, rh); rep(i, n) { const auto& hole = holes[i]; double go_y = calc_y(hole.first, theta, a); if(in_range(go_y, hole.second - 20, hole.second + 20)) { ret = i; break; } } if(ret < 0) return ret; if(abs(alpha.second - calc_y(alpha.first, theta, a)) < bar_halflen) { return -1; } if(abs(beta.second - calc_y(beta.first, theta, a)) < bar_halflen) { return -1; } if(abs(gamma.second - calc_y(gamma.first, theta, a)) < bar_halflen) { return -1; } return ret; }; const double theta_max = rad_to_deg(pi / 4); vector<int> order(n); iota(order.begin(), order.end(), 0); swap(order[0], order[1]); order = { 6, 0, 5, 3, 2, 4, 1, }; for(int i = 0; i < n; i++) { const int id = order[i]; const auto& hole = holes[id]; // cerr << id << ' ' << hole.first << ' ' << hole.second << '\n'; int ch_miq = 0; int lh_miq = 0; int rh_miq = 0; double theta = arg(hole); if(theta > theta_max) { theta = theta_max; } else if(theta < -theta_max) { theta = -theta_max; } int nu = 10; int tm = (hole.first) / (speed * cos(theta)) * 1000 + 10; if(i < 2) { ch_miq = int(rad_to_deg(pi / 2 - theta) * 10 / 3); lh_miq = ch_miq; rh_miq = ch_miq; } else { rep(loop, 100000) { ch_miq = rand() % 1500 - 1000; lh_miq = rand() % 40000 - 20000; rh_miq = ch_miq * 2 - lh_miq; double ch = double(ch_miq) / 1000.; double lh = double(lh_miq) / 1000.; double rh = double(rh_miq) / 1000.; double a = calc_a(lh, rh); // debug(ch, lh, rh, a); theta = calc_theta(hole.first, hole.second, a); // debug(theta); if(abs(theta) < theta_max) { if(in(ch, lh, rh, theta) == id) { break; } } // ch_miq = 0; // lh_miq = 0; // rh_miq = 0; // theta = arg(hole); // if(theta > theta_max) { // theta = theta_max; // } else if(theta < -theta_max) { // theta = -theta_max; // } } tm /= 2; } print_ans(ch_miq, lh_miq, rh_miq, convert_to_theta(theta), nu, tm, i == n - 1); count_ball += nu; time_remain -= tm; } } int main() { solve(); }
提出した解答
235,235,235,-19358,10,1970 300,300,300,0,10,410 -164,-13495,13167,29837,10,930 -566,10364,-11496,-28749,10,623 79,13976,-13818,6875,10,655 -990,19857,-21837,-35769,10,655 -344,-7294,6606,7039,10,505;
感想
普段書いているコードは実機で動いたりしないので，新鮮で思いの外楽しい経験だった．マラソンは経験がほとんどなくて下手なので5位だったのは想定よりかなり良かったが，入賞できなかった悔しさが残った．来年は今年の経験を生かして勝てればと思う．
