高専プロコン参加記

決勝8位でした. 参加記を書きます

解法

大体パンフレットに書いてあることと同じです

愚直 $3 H W$ 解法

$bitfloor (x) ≔ 2^{⌊ \log_{2} (x) ⌋}$ とします

今回の問題は操作回数の合計を $3 H W$ 回以下に抑えて完全に修復する方法がいくつか存在します. そのうちの1つを紹介

左上のマスから1行ずつ直接正しい場所に持っていく方法を考えます

修復したいマスを $p = (p_{x}, p_{y})$ と置きます. そのマスにあるべきピースを未修復の範囲から探し出してその位置を $q = (q_{x}, q_{y})$ と置きます. 整理しておくと, 位置 $(x, y)$ について $y > p_{y}$ または $y = p_{y} \land x > p_{x}$ を満たすなら未修復で, そうでないなら修復済みです
$p = q$ なら「最初から正しいピースがあった」ということで何もせず終了します
$p_{y} = q_{y}$ なら以下を実行して終了です

もし $q_{x} - p_{x}$ が二の冪でないなら位置 $(p_{x} - q_{x} + bitfloor (q_{x} - p_{x}) + 1, p_{y})$ に十分大きな(256とかの)タイプ3の抜き型で左に寄せます
位置 $p$ で大きさ $bitfloor (q_{x} - p_{x})$ のタイプ1の抜き型を使って左に寄せると位置 $p$ に正しいピースが来ます

もし $q_{x} \neq p_{x}$ なら盤面の端でタイプ1の抜き型を横方向にずらして $q$ にあったピースを $p$ の真下に持ってきます (投げやり)
i. や ii. でやったのと同じような操作を縦方向にすれば正しい位置にピースを持ってこれます (投げやり)

最悪操作回数は $3 H W$ 回ですが, 実際にこの数字が出ることは殆ど無く, 平均的には $0.8 H W$ 回くらいになります

ビームサーチ

みんなが思いつく通りビームサーチします. ビーム幅は時間を計って残り時間と進捗から最適な幅に調整するようにしました

その他

当然盤面はビット列を使って持ちます

で, ビームサーチでの操作列の保持はリンクリストみたいにやると良い感じにできます

環境構成

3台あるPCの内2台が探索用でC++が動きます. もう1台が人間用でTypeScriptが動きます

競技サーバーは人間用PCが代表してアクセスし, 問題を取ってきたら探索用PCに送信します. 人間用PCは念のため上記の愚直 $3 H W$ 解法 (ビームサーチなし) で解いた手を送信します

競技終了数秒前くらいに探索用PCが探索を終え, 人間用PCに解を送信します. ここで手数が最も少ない操作列を競技サーバーに送信します

人間用PCについているGUIでは人間が解けるような盤面が来たときに人間が解く, ということができます. 出番はありませんでしたが

出来なかったこと

上の愚直 $3 H W$ 解法では1行ずつ修復してますが, これを複数行同時に修復すると手のバリエーションが増えるのでビームサーチが改善します. 最悪 $5 H W$ とかになりますけど平均は下がります

タイムライン

10/17 (Thu) 以前

eomさんが「 $256 \times 256$ の盤面で2万手を切った」という誤爆をしたり平気で $\frac{1}{4} H W$ を前提にするツイートをしたりしてたので八戸は相当強そうという感覚を持ってました. こちとらその時 $0.35 H W$ ですからね

eomさんは「他のチームもこれくらい行ってそう」という態度だったのでみんなそれくらい行ってるんだ... と思い込んでました. 実際は八戸だけめちゃ強かったです

10/18 (Fri)

移動部門

10/19 (Sat)

大会1日目

予行練習では「愚直 $3 H W$ 解法で解を提出した後, 5秒待ってから0.5秒毎に0手の操作列を送り続ける」をしました. 良心が勝って200回無を送信した後プログラムを止めました. なんかすいません

他チームがどれくらいのレベル感か分からないまま最初の試合に挑みます. 手の内を明かしたく無かったので愚直 $3 H W$ 解法をビームサーチしただけのやつを回して1位通過できました. 他のチームのレベル感が分からないめっちゃ怖い状況で1位通過したの褒めて欲しい

他の試合を見てみると八戸がダントツでびっくりしましたが, 解法が私たちが5月に実装したのと見た目が似ていて, 実装できると思いこの時点で徹夜が確定しました. 実装したかったので交流会に参加せずホテルにリターンしてひたすら実装します

$0.34 H W$ くらいまでは行きましたが探索したデータから手の復元をするところでバグが取れずに使えませんでした. 結局使えなかったんだから交流会いけば良かったですね

10/20 (Sun)

大会2日目. 本番

徹夜実装は3時くらいに寝落ちしてました. 逆にそこまでよく耐えた方だと思います

敗者復活戦中に2行同時修復 ( $0.38 H W$ くらい)をマルチスレッド化してそれを準決勝で使おうと思ってましたが, 謎の「最後ちょっとだけ操作が行われない」というバグに見舞われました. 敗者復活戦中ずっとバグの原因を探してましたが見つけられず, 仕方なく1回戦と同じプログラムで挑みました. 徳山には負けましたけど2位で決勝に進めます

さて, ここで八戸がまさかの通信エラーということで変な空気感が生まれます

とりあえずここまで安定的に動いている「愚直 $3 H W$ 解法」をマルチスレッド化して本番で動かそう, ということでそういう実装を間の時間にしました. $128 \times 128$ で動作確認をし, ちゃんと動いた. $256 \times 256$ でもやると... なんと全く正しく動きません. この時点で12:40 (本番まで20分) Gitに履歴があるので並列化する前のソースに戻しても結果は変わらず. 結局本番までにバグが治りませんでした. 数日前のデバッグではちゃんと動いたんですが何でなんでしょう

こうして予行練習から準決勝まで「3台のPCとルーターとごちゃごちゃしたケーブル」という構成だったのが腹を括って1台のPCだけで迎えることになりました. TypeScript側で「絶対正しい手順返すプログラム」を作っておいたので修復できない, という事態は避けられました. まぁ結果は8位ですけどね

10/21 (Mon)

こうして帰りの新幹線の中で参加記を書いて, 全然書ききらなかったので家に帰ってからも書いてるわけです

これを見ている高専プロコン競技部門erへ

実装より交流会の参加を優先しよう
なんか通信とかで不具合があったら焦らずに再起動しよう
複数の実装を用意しておいて, 1つバグで使えなくなってもリカバリできるようにしよう
ほんとに徹底的にデバッグしよう

以上です, ごきげんよう