TopCoder MM96 GarlandOfLights

MMで初のratedコンテストの参加だった。

概要

ワイヤーと色が決められているタイルで構成されている2次元グリッドが与えられている。タイルを並べ替えてワイヤーが閉路を構成するようにする。ただし同じ色が隣接しないように配置する。できるだけ閉路を長く出来るように並べ替えろ。

1日目

問題をザッと読んで電車で色々と考える。ターンベースじゃないし2点swap焼きなましがパット見の印象だった。H,Wが100イカでタイルの種類も24種類しかないので嘘DPとかもあるのかなーとか思っていた。
焼きなましの近傍について2点swapとか新概念であったような辺に注目して伸びるような近傍とかを考えてた。
clock()関数はTopCoderでは遅いのでrtdscで時間計測できるようにクロックと秒数の比を確認する。ExampleTestに以下のコードを投げて標準エラー出力で確認する。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)

unsigned long long int getCycle()
{
  unsigned int low, high;
  __asm__ volatile ("rdtsc" : "=a" (low), "=d" (high));
  return ((unsigned long long int)low) | ((unsigned long long int)high << 32);
}

VI v;
class GarlandOfLights {
public:
  vector<int> create(int H, int W, vector<string> lights) {
    unsigned long long int begin_cycle = getCycle();
    int begin_clocks = clock();
    REP(j, 15) {
      REP(i, 100000000) {v.PB(i);}
      v.clear();
    }
    unsigned long long int end_cycle = getCycle();
    int end_clocks = clock();
    cerr << begin_clocks << " " << begin_cycle << endl;
    cerr << end_clocks << " " << end_cycle << endl;
    cerr << (double)(end_clocks-begin_clocks)/CLOCKS_PER_SEC << endl;
    cerr << fixed << setprecision(20) <<  ((double)(end_clocks-begin_clocks)/CLOCKS_PER_SEC)/(end_cycle-begin_cycle) << endl;
    return {};
  }
};

問題とtesterをちゃんと読んだ。タイルの配置から閉路の長さを確認するscore関数を愚直に実装するとめちゃくちゃ重い気がしたので焼きなましするなら工夫しないといけないなーと思う。というか1周閉路をつくるだけの実装でもそこそこ大変そうなので実装を頑張らないとと思ってたら1日が終わる。

2日目

ビジュアライザーをつくることにした。入力を食わせたら盤面を表示してタイルを交換したりできるようなのをつくった。(作ったあとで気がついたけど手で遊ぶような小さいサイズじゃ特殊すぎた気がした。)

ここにビジュアライザーの画像が入る

閉路を焼きなましでうまくつくる方法が思いつかない。適当によさそうなパターンを決め打って、そのパターンにしたがって色を無視して閉路をつくったあと色が問題ないように並べていくことにした。

3日目

こんなパターンをつくろうとした。

横に往復させるのと縦に往復させるのをできるだけつくっていけば良い気がしたけど冷静に考えると横のワイヤーと縦のワイヤーはそれぞれ1/6しかないしそれだけじゃそんなに埋まらないことに気がついたので角ので往復させるパターンを考えた。

まず色を無視して閉路を決める。sequence[i] = {y座標, x座標, ワイヤーの種類}となるようにタイルの列を決める。前の色と異なる色でなおかつその種類でもっとも数が多い色のタイルを置いていくとして、その列にしたがってタイルを決めていく関数をつくった。

// このブロックでsequenceが可能かどうかの判定をする
  bool check() {
    // cntの初期化
    REP(i, 6) REP(j, 4) cnt[i][j] = init_cnt[i][j], idx[i][j] = 0;
    ret = VI(H*W, -1);
    memset(used, false, sizeof(used));

    int tiletype = sequence[0][2], x = sequence[0][1], y = sequence[0][0];
    int ma = 0, maidx = -1;
    REP(j, C) {
      if(ma < cnt[tiletype][j]) {
        ma = cnt[tiletype][j];
        maidx = j;
      }
    }
    if(maidx == -1) return false;
    int prev = maidx, firstcolor = maidx;
    used[v[tiletype][maidx][idx[tiletype][maidx]]] = true;
    ret[y*W + x] = v[tiletype][maidx][idx[tiletype][maidx]++];
    cnt[tiletype][maidx]--;

    FOR(i, 1, sequence.size()) {
      int tiletype = sequence[i][2], x = sequence[i][1], y = sequence[i][0];
      if(y*W + x < 0 || W*H <= y*W+x) cerr << "fail " << i << " x:" << x << " y:" << y << endl;
      // cerr << x << " " << y << " " << tiletype << endl;
      // i番目のやつの中で指定されたワイヤーの構成の中で、prevと色が違い、数が最も多いもの
      int ma = 0, maidx = -1;
      REP(j, C) {
        if(prev == j) continue;
        if(i == (int)sequence.size()-1 && firstcolor == j) continue;
        if(ma < cnt[tiletype][j]) {
          ma = cnt[tiletype][j];
          maidx = j;
        }
      }
      if(maidx == -1) {
        if(cnt[tiletype][prev] > 0) {
          ma = cnt[tiletype][prev];
          maidx = prev;
        }
        // 不可能パターン
        return false;
      }
      // (sequence[i][0], sequence[i][1]) に ワイヤーの構成 sequence[i][2] で 色 maidx のをおく
      used[v[tiletype][maidx][idx[tiletype][maidx]]] = true;
      ret[y*W + x] = v[tiletype][maidx][idx[tiletype][maidx]++];
      cnt[tiletype][maidx]--;
      prev = maidx;
    }

    int idx = 0;
    REP(i, H*W) {
      if(ret[i] == -1) {
        while(used[idx]) idx++;
        used[idx] = true;
        ret[i] = idx;
      }
    }
    return true;
  }

1st submit

縦に往復するのと横に往復するのと角で往復するのをできるだけするような列をつくる。scoreは804328.00点だった。

2nd submit

縦、横、角の往復する数を探索するように変更した。scoreは843788.39点。

4日目

横、縦、角で余ってるのを使ってさらに往復するような列をつくることを考える。

3rd submit

とりあえず角を使った往復を余った部分でするコードを書いて提出した。scoreは879338.86点。

4th submit

余ってるのをちゃんと埋め込むパターンを考える。下から横往復を埋めたあと、右から縦往復をできるだけ埋めて、最後に下から角往復をできるだけ埋める。scoreは905643.30点。

まとめ

用事がN個入ったのでMMはここで終了。そもそも外周を一周できないパターンについてコードが書けておらず0点になってたのを直せなかったのが悔しい。あと盤面が小さいケースについて点数がかなり低めになっていたのが要考察だった。
全体的に実装がつらかった…。素数洞窟の実装をゴツくしたような感じの実装になってしまい1日中バグと格闘していた。 順位表を見ていると90万点代で戦ってるのにやっと90万点に乗せたところでおわってしまった。もうちょっと実装速度を上げたい。
終わったあとのTLを見ているとタイルを小さなブロックで区切って閉路を保ったまま焼きなましをする解法があった。うまく焼きなましができる方法が思いつかなくて捨ててしまった方針なので次からはもっと考えたい。