2012年コンピュータフェスティバル競技部門におけるアルゴリズムの解説

 情報交換会とかで説明する時間がなかったので書きます.

 実は徳山の解法は久留米高専劣化コピーを少し改良したもので,まだ久留米高専の解を超える解を出したことはありません;

 プロコンの決勝後に司会,解説の方の質問に久留米高専の学生が答えていましたが,猛威を振るった久留米高専の戦略は

  1. 1xn(nは20程度)のビット列の全ビットパターンについて幅優先探索で最短の修復手順を求める
  2. 上記で求めた修復手順を1xnのビット列にそのまま当てはめるのは効率が悪い(あとで説明)ので,動的計画法を用いて当てはめるパターンを決定する

というものだったそうです.また,スタンプを修復しなくてもよい広い領域がある場合はその領域を避けるようにしてスタンプを適用していく解も作成し,もっともよいものを提出するという手段をとったそうです.

 実は久留米高専の戦略って久留米の学生のブログに書かれていたのですよ...

基本的なところ

分析をすればわかると思うのですが,今回の問題では

  • 同じスタンプを同じ位置に2回以上押す必要はなく,スタンプを適用する順番に意味はない
  • 効率が悪くても解は簡単に見つけられる(1x1で値が1のスタンプがなくても...)

という特徴があります.
また,1セルごとに変数を保持するとXORをとるときなどに計算に時間がかかるので,数ビット(32とか64とか)まとめて保存しておくと結構速度上がります.

スタンプを押す順番に意味がないということは,一定の方向に計算していってもいいわけです.
そこで,画像の左上から順番に画像を操作していきながら解を求めることにします.
プログラムで書くと,

for(int y = 0; y < h; ++y)for(int x = 0; x < w; ++x) { ... }

という感じです.
スタンプを押す時に現在調べているy座標より小さい位置,現在調べているy座標と同じで,x座標は現在調べているx座標より小さい位置に影響を与えないようにすればいいわけです.

ステップ1 幅優先探索(BFS)

1x[1..n]のビット列に対するもっとも手数が短い解法を計算します.このとき,ビット列より上側,左側には影響が出ないようにします.
探索にはBFS用います.

  1. スタンプの中に含まれる値が1で最も左上の位置にあるセルの位置情報を計算します.(念のため)
  2. その位置を基準に右方向へn列のビット列を作成する(スタンプからはみ出たら0にする)
  3. 1xk列について初期状態をすべて0のビット列としBFSで手順と長さを計算します(kは2〜n).

このステップが結構時間食います.ライブラリ化したコードを含めたとしても100行に満たないコードだというのに.(パレートの法則だって僕の先輩は喜ぶかもしれません)

宇部や津山の解法はこれかなーと思いましたが,プロコンの決勝の解を計算してもハノイ宇部の解よりも結構悪い解が出るので違ったのかなーとか思い始めました.(スタンプの選び方とかで解が変わるので何とも言えませんが.)
コンフェス当日にもっと単純な方法使っているんじゃないかと思いプログラム組んでみようと思ったのですが,前日の無意味な徹夜を理由に断念しました.

ステップ2 動的計画法(DP)

BFSで求めた最短手順を1xnのブロックにどんどん当てはめて行っても結構効率は悪いです.
たとえば長さn+1の列があったとして,左側n列に求めた最短手順を適用してから残り1列に最短手順を適用するのと,左側1ビットに最短手順を適用してから残りn列に最短手順を適用するのでは合計の手順が異なります.もしかすると2列のブロックとn-1列のブロックに分けて最短手順を適用したほうが短くなるかもしれません.このようなことを考慮するために1行ごとにDPを行います.

ins[j],bit[j]をその行の[0,j)の範囲を修復数する修復手順と,修復した後のその行の状態と定義します.
ins[0]は何もしない修復手順,bit[0]はいまから計算する行のフィールドで初期化します.
jは1〜w(スタンプの幅)まで増加させます.

  1. ins[j],bit[j]をnullにでもしておきます.
  2. bwを1〜min(j, n)の範囲で増加させます
    1. bit[j - bw]について,[j, j+bw)のビット列を作成しbとします.
    2. lをins[j - bw]の長さとbを修復する最短手順の長さの和にします.
    3. ins[j]がnullかlがins[j]の長さより短い場合は,ins[j]はins[j-bw]にbを修復する最短手順を連結したものに,bit[j]はbit[j-bw]にbを修復する手順を適用したものにします

ins[w]をその行の修復手順とします.
ins[w]をフィールドに適用して次の行へ移ります.

このように工夫をすることで大きい問題(決勝の問題とか)だと数千手改善します.

ステップ3 徳山がやった工夫その1

左側から右側へ修復していったのでは面白味にかけるので,左右からBFS,DPやってより短くなった方を選んでいきます.
これでプロコン決勝とかで数百手改善します.

ステップ4 徳山がやった工夫その2

左右任意の方向に修復できるようになったんだったら数行先まで先読みしちゃえってことで,深さ優先探索(DFS)やります.
大きい問題でも時間があれば8行先とかまで計算できます.
問題によりけりですがある程度は改善します.
コンフェスの決勝で徳山の学生(僕)が残り時間20秒ぐらいまで頑張って計算させてたのはこれです.

大体こんなところです.あとは上から下へやっていたのを右から左とか方向を変えるぐらいです.(フィールドやスタンプを回転させるようにするとそれだけで済みます.)

解答が提出できないと論外なので,2台のPCでn=15,n=19にして計算させました.15ぐらいだと大きい問題でも1分かからずに終わります.

久留米はすごい頑張って高速化とかをやった結果1x22〜26程度のビット列に対するBFSができるようになったらしいですが,僕の腕では18〜21ぐらいまでしかできませんでした.それなので,プロコンの決勝の問題とか解かせてみても,数百手久留米に及びません.優勝校は伊達じゃない.ぱ()ない.

本当は高速化もやりたかったんですが,時間ないので断念しました.あと,C++で組んだりしたいです.並列化もしっかりしたいです.


1行ずつ修復するだけじゃなくて,複数行同時とかもやってみたかったんですが,時間ないので断念しました.スタンプの適用位置をいじったり縦方向にDPとかすると改善すると思います.
また,途中まで1行目を修復,同じ列まで次の行を修復,次を2行同時・・・とかも考えましたが面倒なのでやめました.


実はステップ2でDPした結果って1xnまでの最短手を駆使してその行を修復する最短の手数ではないのです.
ステップ3,4を適用しても傾向として解が向上するだけで,悪化してしまう可能性も0ではないです.
特にステップ4なんかは先読みする行を増やして解が悪化してしまったということもありました.
そう考えるとやっぱりこういう問題は奥が深いです.