ABC084 C - Special Trains

問題ページ
C - Special Trains

考えたこと

• 乗れる電車のうち一番はやい電車に貪欲に乗っていけばよさそう
• t秒目に駅に来た時 s + k*f >= t を満たす最小のkの電車に乗ればいい
• 変形すると k >= (t-s)/f
• k = max(0, ceil*1と決定できるのであとは貪欲にえい

割り算をdoubleに変換しないアホミスで1WA出してア

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int c[505], s[505], f[505];
signed main(void)
{
  int n;
  cin >> n;
  REP(i, n-1) cin >> c[i] >> s[i] >> f[i];

  // 駅i→駅i+1 c[i]秒かかる s[i] + k*f[i] 秒目に発車 s[i]%f[i]==0
  REP(i, n) {
    int t = 0;
    FOR(j, i, n-1) {
      // jからj+1に移動
      // t以上で最も早く到達する電車に乗る
      // t >= s[j] && t%f[j] == 0
      int k = max(0.0, ceil((double)(t-s[j])/f[j]));
      t = s[j] + k*f[j];
      t += c[j];
    }
    cout << t << endl;
  }

  return 0;
}

*1:t-s)/f

AtCoder Regular Contest 007 C - 節約生活

問題ページ
C: 節約生活 - AtCoder Regular Contest 007 | AtCoder

考えたこと

• 愚直に全探索するとO(N^N)になりそう
• 多少枝刈りできそうだし10^10なら通るのでは？と思って投げるとTLEじゃなくてWA
• 全てのテレビが付くまでは視聴できない時間が合ってもいいところの実装を間違えていたので直して投げると通った

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

string t;
int dfs(string s) {
  // sで最初のxのところ
  int idx = -1;
  REP(i, s.size()) {
    if(s[i] == 'x') {
      idx = i;
      break;
    }
  }
  // 全部oなら 最初に一つテレビを使ってるので0じゃなくて1
  if(idx == -1) return 1;

  string init = s;
  int ret = INF;
  // tのi文字目からをsのidx文字目に合わせる
  REP(i, t.size()) if(t[i] == 'o') {
    for(int j=idx; j<s.size() && i+j-idx<t.size(); ++j) if(t[i+j-idx] == 'o') {
      s[j] = 'o';
    }
    chmin(ret, dfs(s)+1);
    s = init;
  }

  return ret;
}

signed main(void)
{
  cin >> t;

  int ret = INF;
  REP(i, t.size()) {
    chmin(ret, dfs(t.substr(i) + t.substr(0, i)));
  }
  cout << ret << endl;

  return 0;
}

ARC005 C - 器物損壊！高橋君

問題ページ
C - 器物損壊！高橋君

考えたこと

• N回見た拡張dijkstra
• d[y][x][何回壊したか] = (最短距離) でdijkstraをする

#include <bits/stdc++.h>

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

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define IN(a, b, x) (a<=x&&x<b)
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

string s[505];
int d[505][505][3];
signed main(void)
{
  int h, w;
  cin >> h >> w;
  REP(i, h) cin >> s[i];

  int sy, sx, gy, gx;
  REP(i, h) REP(j, w) {
    if(s[i][j] == 's') sx = j, sy = i, s[i][j] = '.';
    if(s[i][j] == 'g') gx = j, gy = i, s[i][j] = '.';
  }

  priority_queue<VI, VVI, greater<VI>> que;
  que.push({0, sy, sx, 2});
  REP(i, h) REP(j, w) d[i][j][0] = d[i][j][1] = d[i][j][2] = INF;
  d[sy][sx][2] = 0;

  while(que.size()) {
    VI v = que.top(); que.pop();
    int x = v[2], y = v[1], num = v[3];
    if(x == gx && y == gy) break;
    // 上下左右の4方向を試す
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      // 盤面の範囲内ならば
      if(IN(0, w, nx) && IN(0, h, ny)) {
        // 普通に移動
        if(s[ny][nx] == '.' && d[ny][nx][num] > d[y][x][num] + 1) {
          d[ny][nx][num] = d[y][x][num] + 1;
          que.push({d[ny][nx][num], ny, nx, num});
        }
        // 塀を破壊
        if(s[ny][nx] == '#' && num >= 1 && d[ny][nx][num-1] > d[y][x][num] + 1) {
          d[ny][nx][num-1] = d[y][x][num] + 1;
          que.push({d[ny][nx][num-1], ny, nx, num-1});
        }
      }
    }
  }

  // goal にたどり着けるか
  if(d[gy][gx][0] != INF || d[gy][gx][1] != INF || d[gy][gx][2] != INF) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }

  return 0;
}

ARC004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

問題ページ
C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

考えたこと

• 数式を書いてみると X/Y = (N(N+1)/2 - M) / N
• N = Y/2, M = (Y^2+2Y-4X)/8
• N,Mが整数かつN < Mの条件を満たすような(X, Y)の組を探す
• N<Mの条件を満たす間(X, Y) (2X, 2Y) (3X, 3Y) … について探索していく
• これで出すとTLEしたのでMがマイナスになる部分を枝刈りする
• (kY)^2 + 2kY - 4kX > 0 を満たすように整数kを選ぶ
• k = 0, (4X - 2Y)/Y^2 になったのでMがマイナスだったら (4X - 2Y)/Y^2 をX, Yに掛けてから探索を始めることにして投げたら通った

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  int x, y;
  char c;
  cin >> x >> c >> y;

  int g = __gcd(x, y);
  x /= g, y /= g;
  if(y%2) x *= 2, y *= 2;

  vector<PII> v;
  int xx = x, yy = y;
  if(yy*yy+2*yy < 4*xx) {
    int k = (4*xx - 2*yy)/(y*y);
    k = max(1LL, k-3);
    // cout << k << endl;
    xx *= k, yy *= k;
  }

  while(true) {
    // cout << xx << " " << yy << " " << yy/2 << " " << (yy*yy+2*yy-4*xx)/8 << endl;
    if(yy/2 < (yy*yy+2*yy-4*xx)/8) {
      break;
    }
    if(yy%2 != 0) {
      xx += x, yy += y;
      continue;
    }
    if((yy*yy+2*yy-4*xx)%8 != 0) {
      xx += x, yy += y;
      continue;
    }
    if(yy/2 <= 0 || (yy*yy+2*yy-4*xx)/8 <= 0) {
      xx += x, yy += y;
      continue;
    }
    v.PB({yy/2, (yy*yy+2*yy-4*xx)/8});
    xx += x, yy += y;
  }

  if(v.size() == 0) cout << "Impossible" << endl;
  else {
    for(auto i: v) cout << i.first << " " << i.second << endl;
  }

  return 0;
}

ARC 003 C - 暗闇帰り道

問題ページ
C: 暗闇帰り道 - AtCoder Regular Contest 003 | AtCoder

考えたこと

• 最小の最大化なので2分探索をする
• 経路の明るさvを達成できるかどうかをO(HW)くらいで判定できればよさそう
• d[y][x] = (座標(y,x)に到達できる最短の時刻t) としてdijkstraをすると判定ができる
• 投げたら通った

解法

経路の明るさvを達成できるような経路が存在するかどうか？というような問題について考える。2次元グリッド上でdijkstraを行う。隣接する地点が移動できる地点であって到達する時刻が縮むのならばその地点に進む。これでこの問題にはO(HWlog(HW)) (多分)で解ける。
(1/2)⁴⁰ <= 1e-12 より40回程度二分探索をすれば精度は問題ない。したがってこの問題は解けた。
注意点としてpow(0.99, t) をその都度計算するとTLEするので前計算しておくべき。

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int h, w, sx, sy, gx, gy;
string s[505];
int d[505][505];
double po[250010];

bool check(double mid) {
  priority_queue<VI, VVI, greater<VI>> que;
  que.push({0, sy, sx});
  REP(i, h) REP(j, w) d[i][j] = INF;
  d[sy][sx] = 0;

  while(que.size()) {
    VI v = que.top(); que.pop();
    int y = v[1], x = v[2];
    if(x == gx && y == gy) break;
    if(v[0] > d[y][x]) continue;
    REP(i, 4) {
      int nx = x + dx[i], ny = y + dy[i];
      if(IN(0, w, nx) && IN(0, h, ny) && s[ny][nx] != '#' && d[ny][nx] > d[y][x] + 1) {
        if(s[ny][nx] == 'g') {
          d[ny][nx] = d[y][x] + 1;
          que.push({d[ny][nx], ny, nx});
        } else {
          double val = (s[ny][nx]-'0')*po[v[0]+1];
          if(val >= mid) {
            d[ny][nx] = d[y][x] + 1;
            que.push({d[ny][nx], ny, nx});
          }
        }
      }
    }
  }

  if(d[gy][gx] == INF) return false;
  return true;
}

signed main(void)
{
  cin >> h >> w;
  REP(i, h) cin >> s[i];
  REP(i, h) REP(j, w) {
    if(s[i][j] == 's') sy = i, sx = j;
    if(s[i][j] == 'g') gy = i, gx = j;
  }
  po[0] = 1;
  FOR(i, 1, h*w+1) po[i] = po[i-1]*0.99;

  double lb = 0, ub = 9;
  REP(i, 40) {
    double mid = (lb+ub)/2;
    if(check(mid)) {
      lb = mid;
    } else {
      ub = mid;
    }
  }

  if(!check(-INF)) cout << -1 << endl;
  else cout << fixed << setprecision(10) << lb << endl;

  return 0;
}

AtCoder Regular Contest 088 E - Papple Sort

問題ページ
E: Papple Sort - AtCoder Regular Contest 088 | AtCoder

解法

文字列Sに文字aが11個存在すれば左の5個は回文の左半分に属し、右の5個は回文の右半分、真ん中の1個は回分の中央に属する。同じ文字を入れ替えたとしても操作回数が減らせることはないため各文字種について見ていくことでその文字が左半分、中央、右半分のどこに属するかを決定できる。
次に左半分と右半分を回文になるように操作していくことを考える。左半分を操作することと対応する右半分を操作することは実質同じ操作であるから、右半分だけを操作するとしても最小の操作回数を達成することが出来る。したがって右半分の文字列が左半分の反転になるように操作すればよい。ある文字列S1を文字列S2に変える最小の操作回数について考える。前述したように同じ文字種を入れ替えるメリットはないことから、各文字種について前から順番に対応させいけばよい。例としてatmatからmattaにすることを考える。

atmat→matta
01234→20143

したがって、並べ替える前の文字列と並べ替えた後の回文においてどの文字をどこにもっていくべきかの1対1の対応が取れる。これはバブルソートの交換回数でありO(|S|log|S|)で計算できる。

学び

• ある列Aから列Bに隣接した要素を交換することで移しかえる最小回数はO(NlogN)で求めることができる
• 回文をつくるときは 左半分 or 右半分 のどちらかを決めれば残り半分は一意に決まるんだから片方だけについて考える
• 同じ要素を入れ替えるメリットがない→各要素ごとに前後が入れ替わることはない

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int bit[200010], n = 200010;

//0からi-1番目までの和
int sum(int i) {
  i++;
  int s = 0;
  while(i > 0) {
    s += bit[i];
    i -= i&-i;
  }
  return s;
}

//i番目(0-index)にxを加える
void add(int i, int x) {
  i++;
  while(i <= n) {
    bit[i] += x;
    i += i&-i;
  }
}

int cnt[30], idx[30], a[200010];
deque<int> idx2[30];
signed main(void)
{
  string s;
  cin >> s;
  REP(i, s.size()) cnt[s[i]-'a']++;

  int tmp = 0;
  REP(i, 26) if(cnt[i]%2) tmp++;
  if(tmp >= 2) {
    cout << -1 << endl;
    return 0;
  }

  string t1 = "", t2 = "", t3 = "";
  REP(i, s.size()) {
    if(cnt[s[i]-'a']%2) {
      if(idx[s[i]-'a'] < cnt[s[i]-'a']/2) a[i] = 0;
      else if(idx[s[i]-'a'] == cnt[s[i]-'a']/2) a[i] = 1;
      else if(idx[s[i]-'a'] > cnt[s[i]-'a']/2) a[i] = 2;
    } else {
      if(idx[s[i]-'a'] < cnt[s[i]-'a']/2) a[i] = 0;
      else a[i] = 2;
    }
    if(a[i] == 0) t1 += s[i];
    else if(a[i] == 1) t2 += s[i];
    else t3 += s[i];
    idx[s[i]-'a']++;
  }
  reverse(ALL(t1));

  // t3をt1に合わせる
  REP(i, t1.size()) idx2[t1[i]-'a'].push_front(i+s.size()/2+!!(s.size()%2));
  VI v2;
  REP(i, t3.size()) {
    v2.PB(idx2[t3[i]-'a'].back());
    idx2[t3[i]-'a'].pop_back();
  }

  // 回文にした後で移るindex
  VI v;
  int id = 0, id2 = 0;
  REP(i, s.size()) {
    if(a[i] == 0) {
      v.PB(id++);
    } else if(a[i] == 1) {
      v.PB(s.size()/2);
    } else {
      v.PB(v2[id2++]);
    }
  }

  // vの転倒数を求める
  ll ans = 0;
  REP(i, v.size()) {
    ans += i - sum(v[i]);
    add(v[i], 1);
  }
  cout << ans << endl;

  return 0;
}

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を見ているとタイルを小さなブロックで区切って閉路を保ったまま焼きなましをする解法があった。うまく焼きなましができる方法が思いつかなくて捨ててしまった方針なので次からはもっと考えたい。