ま～た同校制限かよ こわれるなあ
9/12(土)のパソコン甲子園にチーム「アザミ工場」で参加してきました。今年も本校からは合計4チーム出ていて、全員黄色以上なので何とかして打ち破らねば本選へ行けません。
今年の戦略
今年は2台のPCが使えるので、若干無茶ができます。
最初に1~5は相方Thistleに任せた。そして私は6以降に目を通し、機械的に分配した。その結果私は6,9,11を、Thistleは7,8,10,12を担当することとなった。
タイムライン？
私が6で苦戦していると、Thistleが1～5を書き終えたので一通りまとめて出してもらう。その結果1でCE, 4と5でWAが返ってくる。(ペナ+3)
1と5はすぐに治ったが、4が正しいようにしか見えなかったのでdefineの悪さを疑い、私が代わりに書くとなぜか通った。その後何とか6を通し切り、9の考察を始める。
最初に幾何的考察を試みるが、どうもうまくいかない。ここで制約を見て方針転換すると、各格子点を頂点とするグラフのダイクストラ法が適用できることに気づく。 として頂点数が [tex: O(N2)] で辺数が[tex: O(N3)] なので適当に書いて出す。→TLE
真面目に計算すると頂点数は約90000で辺数は90000600で5.4107, doubleの計算もあるので間に合うわけがない。また少し考察すると、スタートとゴールのbounding boxより外へ行く移動は無駄だとわかるのでそれを適用する。→TLE
また、いったんゴールに近づいてまた離れる移動も無駄であることもわかる。→TLE
ここで定数倍高速化としてintをshortに、doubleをfloatに変えるなどあがいてみるがTLE。その間にThistleは7, 8, 10をペナルティ1で通し切っていた。このままでは4と6だけしか通してない実質マスコットになってしまうと焦る。
さらに考察をすると、スタートからゴールまで直線で行ったときに x=(整数) やy=(整数) の地点とぶつかるような点の付近で曲がるのが最適だとわかるので、交点の近傍だけを採用して辺数を減らすことにした。 近傍のパラメータを調整し続けて、終了10分くらい前にWAとTLEの間のACを無事掴み取ることができた。そこまでに要したペナルティは 13回！ これぞ執念...
結果
Thistleは結局12を通せず、10完74点で終わった。全体で見ればよい成績なのだろうが、他の3チームが11, 11, 10完だったので負けは自動的に確定する。悲しい...
感想
同校制限なんとかして(N回目)
