LiveArchive4035

4035 - Undetectable Tour

どういう場合に到達不可能になるのかを考える。

センサーのカバーしている領域だけを通って
"領域の上から領域の下まで移動できる"
"領域の上から領域の右まで移動できる"
"領域の左から領域の下まで移動できる"
"領域の左から領域の右まで移動できる"
の4つの条件のうち1つでも満たせば到達不可能になる。

全てのセンサーの位置と各センサー(x, y)から最短で行ける領域の端(x, 0), (0, y), (x, N-1), (N-1, y)の位置を頂点とする様なグラフを作る。
(始点と終点の扱いには注意すること。領域の端を全て頂点にしてしまうとTLEする。)
このグラフ上で4つの条件のどれかを満たす様なパスの最大の辺の重みの最小値がセンサーに捕捉されずに到達可能な距離の上限になる。

やりかたは色々あるだろうけど、条件を満たすまで辺の重み順にUnionFindした。

LiveArchive5848

分割統治。

領域を縦と横に2分割して、4つの領域に分ける。
縦は2種類の点を分ける様なX軸に垂直な直線で分割し、横はそれっぽい直線で分割する。

横方向に隣合う領域同士の近い点か、斜めの領域同士の点から最近点を探す。
互いに斜めな領域同士の点の移動は、分割に使った縦と横の線の交点を通る様な移動を考える。

あとは、点の数が少なくなるまで横の分割を繰り返す。

LiveArchive3153

LiveArchiveにログインできない・・・。アカウントを作り直して挑戦。

答えの上限を大まかに見積もっておく。上限の値が出たら、終了。
入力によっては、少しも早くならない気がする・・・。
というか、ACが出たことに驚いた。
実行速度ランキング6位。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
const int TIME = 420;

int cost[N];
int g[N][N];

int result;
int lim;

void rec(int pos, int vis, int time, int size, int depth)
{
  if( TIME < time )return ;

  result = max( result, depth );
  if( result == lim )return ;

  for(int i=0; i<size; ++i){
    if( vis & (1 << i) ) continue;

    int spend = g[pos][i] + cost[i];
    rec(i, vis | (1 << i), time + spend, size, depth + 1);

    if( result == lim ) return ;
  }
  return ;
}

void wf(int size)
{
  for(int k=0; k<size; ++k){
    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        g[i][j] = min( g[i][j], g[i][k] + g[k][j] );
      }
    }
  }
  return ;
}

int main(void)
{
  int n;
  while( cin >> n && n ){

    for(int i=0; i<n; ++i){
      cin >> cost[i];
    }

    for(int i=0; i<n; ++i){
      for(int j=0; j<n; ++j){
        cin >> g[i][j];
      }
    }

    wf(n);
    
    static int c[N];
    copy( cost, cost + n, c );
    
    int mx = 0;
    for(int i=0; i<n; ++i){
      int mn = 1 << 24;
      for(int j=0; j<n; ++j){
        if( i != j ) mn = min(mn, g[i][j]);
      }
      mx = max(mx, mn);
      c[i] += mn;
    }

    sort( c, c + n );
    lim = 0;
    for(int i=0, sum = -mx; i < n && sum + c[i] <= TIME; lim = ++i){
      sum += c[i];
    }

    result = 0;
    for(int i=0; i<n; ++i){
      rec(i, (1 << i), cost[i], n, 1);
    }
    cout << result << endl;
  }
  return 0;
}