日本橋ハーフマラソン本戦B 日本橋大渋滞 解説

日本橋ハーフマラソン本戦B 日本橋大渋滞 解説

先日 RCO が主催したプログラミングコンテスト 日本橋ハーフマラソン のオープンコンテストに参加しました。 オープン参加で賞金もレートもかかっていなかったのでA問題は放棄して、 ビジュアライザが用意されていた B問題 日本橋大渋滞 を解こうとしたのですが、実装が間に合わず未提出、0点のままコンテストは終了してしまいました。
後日考えていた方針の実装を終わらせ提出したところ、かなり出来のいい点数を出せたのでその振り返りをします。
2017/03/26 時点で一位

http://rco-contest-2017-final-open.contest.atcoder.jp/submissions/1176109
入力例2 74手 46555点

 

おおよその方針は次の一連のツイートの通りですが、もうちょいと詳しく解説。

理論値云々は最悪ケースのときマンハッタン距離の最大が58なので。 このとき少なくとも58手かかる。

市松模様

  • 隣接する車があると移動可能な場所が制限されてしまう
  • 車の数は丁度マスの数の半分

ということで市松模様に車を配置すると、隣接する車が存在しない状態を維持しながら移動ができる。
偶然丁度半分ってこともないだろうから、運営の想定方針っぽい。

市松模様に配置できれば、2手1単位で考えると、他の車の位置に影響を与えずに斜め同士の車を交換できる。 これを繰り返すと任意の車同士を交換可能。 任意の市松模様を作ることが出来るとわかる。(イメージはバブルソート)

 

目的地の方も市松模様にしてやれば確実に目的地にたどり着くことが出来るので、高得点のカギはこの市松同士の遷移の手数を縮めることに集約される。

[初期位置] -> [初期市松] ----(遷移)----> [目的市松] -> [目的地]

([目的市松] -> [目的地] は、 [目的地] -> [目的市松] の遷移を計算し、逆方向に辿ればいい)

でも具体的にどうやって初期配置から市松模様に配置する?
「片側に寄せる」「両側に寄せる」「四隅に寄せる」等々色々手は考えられるけど、どれも地味に難しそう。
よく考えるとマッチングの問題なので、復元付きのフローが使えそう。 最大流だともしかすると遠くのほうにマッチングされてしまうかもしれないので、マッチング先までの距離をコストとした最小費用流でやるのが良さそう。
実際に組んでみると、5手前後で初期位置から市松模様にマッチングできた。 上々。

初期位置 -> 初期市松

 

目的市松 -> 目的地

 

最小費用流に使ったグラフは次の通り ( (x+y)%2 == 0 のマスを黒、 1 のマスを白とする )

  • Source -> 車のあるマス (cap 1, cost 0)
  • マス -> 隣接するマス (cap 1000, cost 1)
  • 黒マス -> Sink (cap 1, cost 0)

このようにすると各車が近い黒マスにマッチングするようなフローができる。 車のあるマスから隣接するマスへフローがあり、移動先のマスが使用可能な場合、その車を移動させる。
費用が 0 になるまで繰り返し グラフ構築 -> 最小費用流 -> 復元・移動 を行う。

最小費用流のアルゴリズムは蟻本のもの(Successive Shortest Path?)をベースに、最短距離計算の部分を SPFA に書き換えたもの。 dijkstra のものより高速に動いたのでこっちを採用。

// 現在の車の位置 s を最小費用流で市松模様の位置に移動させる
tuple<vector<pair<int,int>>, vector<string>> make_checker(vector<pair<int,int>> s){
  const int inf = 1e8;
  vector<string> res;

  //市松になるまで繰り返す
  while(true){
    Min_Cost_Flow<int> f(H*W+2, inf);
    int source = H*W;
    int sink   = H*W + 1;

    vector<vector<int>> cell(H, vector<int>(W, -1));

    for(int i : range(K)){
      int r,c;
      tie(r,c) = s[i];
      f.add_edge( source, r*W+c, 1, 0 );
      cell[r][c] = i;
    }

    for(int r : range(H)) for(int c : range(W)){
      if( ((r+c)&1) == 0 ) f.add_edge( r*W+c, sink, 1, 0 );

      for(int k : range(4)){
        int rr = r + dy[k];
        int cc = c + dx[k];

        if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;
        f.add_edge( r*W+c, rr*W+cc, 1000, 1 );
      }
    }

    int cost = f.min_cost_flow(source, sink, K);
    if( cost == 0 ) break; // コストが 0 ならば市松模様

    string movement(K, '-');
    for(int i : range(K)){
      int r,c;
      tie(r,c) = s[i];

      for(auto e : f.G[r*W+c]){
        //逆辺、source/sinkへ向かう辺、流れていない辺は見ない
        if( e.is_rev || e.to == source || e.to == sink || e.cap == 1000 ) continue;
        int rr = e.to/W;
        int cc = e.to%W;
        if( cell[rr][cc] != -1 ) continue; // すでに車があるか、他の車が移動した後
        cell[rr][cc] = -2;

        if( rr != r ) movement[i] = rr<r ? 'U' : 'D';
        if( cc != c ) movement[i] = cc<c ? 'L' : 'R';

        s[i] = {rr,cc};
        break;
      }
    }

    res.push_back( movement );
  }

  // (移動後の市松, 移動経路)
  return make_tuple( s, res );
}

市松-市松間の遷移

3通りの遷移方法を考えた。

  1. 目的地までの距離が大きいものを優先的に動かすようなランダム遷移
    車を目的地までの 距離 + 乱数 でソートし、斜め隣の車と交換してスコア改善するならば高確率で交換、改善しないならば低確率で交換
  2. 目的地までの距離にかかわらずランダムに遷移
    1 のソートを完全なシャッフルに変えたバージョン
  3. 最小費用流で盤面全体を動かす
    この方針が一番大きくスコアを改善した。

    • Source -> 車のあるマス (cap 1, cost 0)
    • 車のあるマス -> 隣接するマス (cap 1, cost min(1, (next_score - prev_score) * prev_score) )
      市松模様なので隣接するマスに車はない。
      next_score, prev_score はそれぞれ移動先、移動前のマスに車があった場合の目的地までのマンハッタン距離
    • 車のないマス -> Sink (cap 1, cost 0)

    最小費用流のグラフを作るとき、辺の繋ぐ順番をランダムにすることが地味に重要。 費用最小になるような流し方が複数存在する時ループに陥る危険性が減る[注]
    最初はコストを (next_score - prev_score) = 1 or -1 で計算していたが、ビジュアライザを見ると遠くへ行きたい車が引っかかっているようだったので、 単純に距離で重みづけを行おうとした。 (next_score - prev_score) * prev_score
    しかし、序盤のスコア改善パフォーマンスは良いものの後半中々目的の市松模様へと収束してくれなかったため、試しに 1 と min を取ってみたところかなり収束が速くなった。

//現在の車の位置 s から 目的地 target に近づくように最小費用流で移動させる
vector<string> get_next(vector<pair<int,int>>& s, vector<pair<int,int>>& target){
  const int inf = 1e8;
  vector<string> res;

  vector<int> order_s(K), order_r(H), order_c(W), order_adj(4);
  iota(order_s.begin(), order_s.end(), 0);
  iota(order_r.begin(), order_r.end(), 0);
  iota(order_c.begin(), order_c.end(), 0);
  iota(order_adj.begin(), order_adj.end(), 0);

  // 2手1セットで遷移を行うと、黒マス -> 白マス -> 黒マス のように車はいつも黒マスに存在することになって扱いやすい
  for(int t : range(2)){
    Min_Cost_Flow<int> f(H*W+2, inf);
    int source = H*W;
    int sink   = H*W + 1;

    string movement(K, '-');

    vector<vector<int>> cell(H, vector<int>(W, -1));

    //辺を作る順番をシャッフルするとループにハマりにくい
    shuffle(order_s.begin(), order_s.end(), mt);
    for(int i : order_s){
      int r,c;
      tie(r,c) = s[i];
      f.add_edge( source, r*W+c, 1, 0 );
      cell[r][c] = i;
    }

    shuffle(order_r.begin(), order_r.end(), mt);
    shuffle(order_c.begin(), order_c.end(), mt);
    for(int r : order_r) for(int c : order_c){
      if( cell[r][c] == -1){
        f.add_edge( r*W+c, sink, 1, 0 );
      }else{
        int i = cell[r][c];
        shuffle(order_adj.begin(), order_adj.end(), mt);
        for(int k : order_adj){
          int rr = r + dy[k];
          int cc = c + dx[k];

          if( rr<0 || rr>=H || cc<0 || cc>=W ) continue;

          // 目的地へのマンハッタン距離
          int prev_score = abs( r - target[i].first ) + abs( c - target[i].second ); 
          int next_score = abs( rr- target[i].first ) + abs( cc- target[i].second );

          f.add_edge( r*W+c, rr*W+cc, 1000, min(1, (next_score-prev_score)*prev_score) );
        }
      }
    }

    int cost = f.min_cost_flow(source, sink, K);
    if( cost == 0 ) break;

    //各車は必ず隣接するマスへ移動する
    for(int i : order_s){
      int r,c;
      tie(r,c) = s[i];

      for(auto e : f.G[r*W+c]){
        if( e.is_rev || e.to == source || e.to == sink || e.cap == 1000 ) continue;
        int rr = e.to/W;
        int cc = e.to%W;
        if( cell[rr][cc] != -1 ) continue;
        cell[rr][cc] = i;

        if( rr != r ) movement[i] = rr<r ? 'U' : 'D';
        if( cc != c ) movement[i] = cc<c ? 'L' : 'R';

        s[i] = {rr,cc};
        break;
      }
    }

    res.push_back( movement );
  }

  return res;
}

実際に試してみて、一番スコアを改善しやすかった3の確率を高く、しかし低確率で1,2の遷移も使うようにした。
一度目的の市松模様を生成出来たら、何手か戻ってより短い手数で生成できないか余った時間で探索する。

初期市松 -> 目的市松

 
注) ランダム性の重要性

基本的にはスコア改善する方向に動かすと良さそうだけど、単純な法則で貪欲に動かし続けるとどこかでループにハマってしまうことがある。
現在の盤面 S の次の遷移先 S` を決めるとき、 S` を S のみによって決定する方針( f(S)=S` )では、 途中にループが現れたとき同じところを回りつづけてしまう。
S_1 -> S_2 -> S_3 -> S_4 -> S_2 -> S_3 -> S_4 -> S_2 ...
なのでずっと同じ貪欲はあまり良くなくて、ある程度のランダム性は持っていた方が良い。 乱数生成器を R として、 f(S, R) = (S`, R`) といった感じで、盤面の状態と乱数で次の状態を生成するようにすると、 同じ盤面が現れても次の盤面が同じとは限らないので、いい感じに動く。

おまけ

実は最小費用流の辺を作る順番をシャッフルするアイデアがあれば、変な調整とかしなくても最小費用流だけで100手切るぐらいまで行ける。 コンテスト時間内でもこれだったら不可能ではなさそう。 http://rco-contest-2017-final-open.contest.atcoder.jp/submissions/1180485 (1ケースTLE)

最小費用流のみ

 

感想

  • ビジュアライザがあるとやっぱり面白い。 しかも最終状態だけでなくて途中経過も表示してくれるのは good
  • コンテスト中にAもやりながら目的地に車置けた人たちはすごい。 自分は実装力がなくて無理
  • グラフの形にもよるけどフローは強力。 辺シャッフルのアイデアは今後役立つ機会もありそう
  • 800手 -> 200手 -> 130手 -> 70手 と改善したけど、120手ぐらいが限界だと思ってた。 ふと思いついたコストに重みづけしつつ min 取ってみよう、というアイデアを実装して走らせたら突然 130手かかってたやつが 80手ぐらいになって何かのバグかと思いました
  • コンテスト直後はあと2週間欲しいとか言ってそうだけど、 2週間もあるとこの問題では上位は1,2手詰める勝負になりそうなのでダメですね

目的地にまっすぐ進む優秀な上のやつより、阻まれつつもなんとか辿り着こうとする下のやつの方が温かみがあって好き。 応援したくなる