AHC026 解説
AtCoder Heuristic Contest 026 で(コンテスト中は上手い方針がたたなかったため)コンテスト後に実装したことについて書いています。
最終的に延長戦順位表で1,411,088点で本番だと6位相当になる解法になります。
方針立て
コンテスト後、コンテスト上位者でよく見かけた解法として「各列をソートして$${+\alpha}$$の改善を行なった($${+\alpha}$$の詳細は書かれていないことが多い)」というものでした。
そこで、
ひとまず列をソートした解法を作成する
$${\uparrow}$$をベースに改善を加えていく
を行なうことで、ベースとなる解法から改善を加えていく練習をすることにしました。
この時の目標として本番10位以内相当の点数をとるまで改善を行うこととしました。
実装フェーズ
列をソートした解法 (1,398,496点, 本番46位相当)
今回のベースとなる解法になります。
ソート自体の説明ですが、
ソートする列を決める
その列がソートされた状態だとどういう順番になるかをメモしておく
ソートする列の上から順に見ていって、箱の番号が降順になる、最長の部分を別の列に移す
ソートする列を一通り他の列に移したら1箱ずつ降順に元の列に戻していく
ということをしています。3の処理は他の列に移した箱が降順になっていると4の処理で元の列に降順に戻す際に楽だからそのような処理をしています。
その他細かい部分として、
操作2が行える場合は行う
列をソートする順については「次に操作2が行える番号の箱がある列」をソートの対象にする
ソートの3の処理でどの列に移すかの優先度は以下の通りにして、箱を移す先を決める
すでに箱を移している列があり、移した箱の上にこれから移そうとしている箱を載せても降順が保たれるならそれを優先
$${\uparrow}$$を満たすものがない場合、1つも箱を移していない列がある場合、それを優先
$${\uparrow}$$を満たすものがない場合、列番号が大きいもの(これは順位づけしたかっただけでそう設定した理由は特にないです)
ということを行なっています。ここから改善していきます。
ソートの4の処理で元の列に戻す際、戻す必要がない場合は戻さない(1,398,880点, 本番45位相当)
列をソートしていくとソート済みの列ができてきます。
ソート済みの列の上に別の列の箱を置く際、箱を置いてもソート済みのままなら元の列に戻す必要がありません。
ソートの3の処理で上記の条件を満たすような箱の移動が行える場合、優先して行うようにします。わずかに点数が改善しました。
操作2ができる番号の箱は一括で動かす対象にしない(1,400,935点, 本番29位相当)
ベースとなる解法の箇所に書いた通り、
列をソートする順については「次に操作2が行える番号の箱がある列」をソートの対象にする
ソートする列の箱を他の列に移す方法は、ソートする列の上から順に見ていって、箱の番号が降順になる、最長の部分を別の列に移す
ということをしています。これら2つの処理が「操作2ができる番号の箱をソートの処理3で別の列に必ず移す」という余計な処理を行なっています。
ソートの処理3の際に「操作2ができる番号の箱の上には箱がない状態」を作ることでスコアを伸ばすことができました。
ソートの処理4の際、元の列以外の値でも大きい値があればそれを巻き込む(1,405,779点, 本番15位相当)
ソートの処理4の処理を進めていくと、ソートする列に箱が降順に積み重なっていきます。
その一手一手を行う際、ソートの際に別の列に移していた箱以外にも、ソートしていない列については大きな番号の箱が載っていたりします。
それを現在ソートしている列に混ぜ込んでもソートされた状態が保たれる場合、それらもソートしている列に巻き込むことで手数が減り、スコアが上がります。
ソートの処理3で箱を置く先の列の優先順位の見直し(1,408,757点, 本番11位相当)
ベースとなる解法の箇所に書いていた、優先度付けの処理で「そう設定した理由は特にないです」と書いていた箇所を修正しています。
具体的には「列の一番上に乗っている箱の番号が小さいものを優先」に変更しました。
理由ですが、ベースとなる解法の箇所に記載した「すでに箱を移している列があり、移した箱の上にこれから移そうとしている箱を載せても降順が保たれるならそれを優先」の処理がなるべく発生して欲しいので、それなら列の一番上の箱は小さい方から使っていくようにしました。割と点数が伸びています。
時間いっぱい列のソート順を変えて試す(1,411,088点, 本番6位相当)
今まで列をソートする順番は固定でしたが、これを制限時間いっぱいまでランダムに試すようにしました。スコアが改善したらその処理を残すようにしています。
点数は伸びる可能性が高く、実装も割と容易なのですが、テストケース150個を消化するだけで5分かかるので、行き詰まった時まで試すのを抑えていました。
所感
各列をソートする方針をどうすれば選択できたのか。
ソートすること自体は案としては浮かぶのですが、余計な手数を踏んでいるように見える
動かす箱を含む列・1度に動かす箱の個数・移動先の列の組み合わせを絞ってビームサーチしたくなる
みたいな感じで、自分には短期のコンテストで選択できる解法ではありませんでした(長期でも選べた気がしませんが)。
改善するのもなかなか時間がかかり、短期コンの地力がまだまだ足りていない感じがします。