SRM269 Div1 Level 2 SecurityBunker

SRM269 Div1 Level 2 SecurityBunker

これはなかなか面白い問題でした。いわゆるボンバーマンですね。ただ、私も問題を誤認して一からコーディングをやり直し、結局時間切れになりましたが、他の人々も英語の解釈で問題があったようです。そこさえ抑えれば、グラフ問題のとてもよい勉強材料になると思います。

問題

NxMの格子上に爆弾”*”と未確認障害物”?”と空白”.”がマップされている。爆弾は距離Dよりも大きくない範囲の爆弾を誘爆する。マップ上の全ての”?”を爆破したい。任意のどれか１つの爆弾を爆発させただけで全ての未確認障害物を爆破するための爆破レンジDの最小値を求めよ。

条件

• N,Mは1～50の値をとる


• 爆弾と未確認障害物はそれぞれ１～100個存在する

考え方

まずは問題を正しく解釈する必要がある。any one bombは、どの爆弾を１つ選んでも、という意味らしい。よって、全ての爆弾を起爆爆弾として確認しつつ、Dを1e-9の精度で求めなければならない。最大100個の爆弾をそれぞれ起爆爆弾としながらマップ上の最大2500点を確認し続けると、連鎖の確認で100x100=10000、そのたびマップを調べると25000000回であっという間に時間切れとなる。

模範解答は、グラフアルゴリズムを用いるものだ。最短経路問題の応用となる。経路は爆弾とそのほかの全ての対象物の間に作り、その距離を重みとする。全ての爆弾は全未確認障害物への経路を持っていなければならない。各爆弾－未確認障害物の経路の最小コストを求め、全経路で最大値を求めれば、それが求めるDである。

Floyd-Warshall algorithmは各経路のコストの最小値を求めるアルゴリズムで、O(n^3)で解決する。このアルゴリズムはどの経路が最短であるかを求めない。しかし、この問題の場合はどの経路を利用するかを応える必要が無いので利用する事ができる。このアルゴリズムは、全ての経路に対してそれ以外の1点を経由した場合とコストを比較し、小さい方のコストでその経路のコストを置き換える。これを全経路全経由点（n^3）で行うことで、全ての経路は最小のコストに置き換えられている。この問題の場合、この時点で全爆弾－未確認障害物経路の中で最大のものを選べば、それがDとなる。

Prim algorithmは全ての点を回るためのコストを最小にする経路を探索するアルゴリズムである。常に既に回った点から最もコストの低い経路を選んで回り、結果その経路はコスト最小となる。Prim algorismを使う場合、全爆弾を誘爆せずとも全未確認障害物を爆破できる場合の扱いが難しい。例えばテストケース３が問題となる。

B	B	B	B	B
	S		S
		S
	S		S
B	B	B	B	B

この場合のDの最大値は３である。上段の爆弾はD=3で全てのSに届き、下段のBまで届く必要は無い。下段の爆弾もD=3で全てのSに届き、上段のBまで届く必要は無い。結果、黄色のマスのB同士が誘縛する必要は無く、D=4ではなくD=3でどのBからも全てのSを爆破できる。Prim algorismで全ての爆弾－爆弾or未確認障害物を繋げると、ピンクのマスのS経由の経路で上下段の爆弾が誘爆され、D=2の答えが出てしまう。これを避けて経路をB⇒SorBにのみ限定してS⇒Bを禁止する（方向性のある重みをつける）と、ピンクのますの経路は遮断されるが黄色いマスの経路で爆弾同士の経路がカウントされ、D=4の答えが出る。

結局このようになる。まずはやはり経路をB⇒SorBにのみ限定して方向性のある重みをつける。そして任意のBから始めたPrim algorismサーチを全てのSを爆破した時点で一旦終了する。この時爆破しそこなったBから再びPrim algorismサーチをやり直して全てのSを爆破する（前回爆破した爆弾はリセットする）。トータルで全ての爆弾を爆破した時点でサーチを終了し、最も大きなDを答えとして返す。

解答例（Floyd-Warshall algorism）

import java.util.*; 
public class SecurityBunker{
 public double chooseBomb(String[] field){
  int[][] o = new int[200][2]; // 全対象物の位置
  boolean[] bomb = new boolean[200]; // 対象物が爆弾ならtrue
  int no = 0; // 対象物の数
  int n = field.length;
  int m = field[0].length();
  // 全対象物の位置をスキャン 
  for(int i=0;i<n;i++){
   for(int j=0;j<m;j++){
    char c = field[i].charAt(j);
    if(c=='*' || c=='?'){
     o[no]=new int[]{i,j};
     if(c=='*')bomb[no]=true;
     no++;
    }
   }
  }
  int[][] dist = new int[no][no]; // 対象物間の距離の二乗
  // 対象物間の距離の二乗を求める。ただし、必要なのは爆弾からの距離だけ。
  for(int j=0;j<no;j++){
   if(!bomb[j]) continue;
   for(int k=0;k<no;k++){
    dist[j][k]=
     (o[j][0]-o[k][0])*(o[j][0]-o[k][0])+(o[j][1]-o[k][1])*(o[j][1]-o[k][1]);
   }
  }
  // 全ての爆弾を経由点とする全爆弾―対象物のコストを最小化する。
  // i: 経由点（爆弾のみ）　j: 起点（爆弾のみ）k: 終点（全対象物）
  for(int i=0;i<no;i++){
   if(!bomb[i])continue;
   for(int j=0;j<no;j++){
    if(!bomb[j])continue;
    for(int k=0;k<no;k++){
     // 起点⇒経由点と経由点⇒終点のうち遠い方が必要な距離の２乗（コスト）
     // この起点⇒終点の経路で最もコストの小さいものを格納
     dist[j][k] = Math.min(dist[j][k], Math.max(dist[j][i], dist[i][k]));
    }
   }
  }
  // 全ての爆弾―未知障害物のコストのうち、最大のものが必要な距離の２乗。
  int max = 0;
  for(int j=0;j<no;j++){
   if(!bomb[j]) continue;
   for(int k=0;k<no;k++){
    if(bomb[k]) continue;
    max = Math.max(max,dist[j][k]);
   }
  }
  // 平方根を取って距離に換算して返す
  return Math.sqrt(max);
 }
}

解答例（Prime algorism）

import java.util.*;
public class SecurityBunker{
public double chooseBomb(String[] field){
  int[][] b = new int[100][2]; // 爆弾位置
  int[][] s = new int[100][2]; // 未確認障害物位置
  int nb = 0; // 爆弾個数
  int ns = 0; // 未確認障害物個数
  int n = field.length;
  int m = field[0].length();
  // フィールドをスキャンして位置を格納、個数をカウント
  for(int i=0;i<n;i++)
   for(int j=0;j<m;j++){
    if(field[i].charAt(j)=='*')
     {b[nb][0]=i;b[nb][1]=j;nb++;}
    if(field[i].charAt(j)=='?')
     {s[ns][0]=i;s[ns][1]=j;ns++;}
   }
  // dist[i][j]はiからjのコスト。
  // i,jの添え字は0からnb-1までが爆弾、nbからnb+ns-1までが未確認障害物
  int[][] dist = new int[nb+ns][nb+ns];
  for(int i=0;i<nb+ns;i++)
   Arrays.fill(dist[i], Integer.MAX_VALUE);
  // 距離を計算して格納。爆弾⇒爆弾or未確認障害物の距離の2乗を測定。
  // 他は∞として方向性を付ける。
  for(int i=0;i<nb;i++){ 
   for(int j=0;j<nb;j++){
    dist[i][j] = 
     (b[i][0]-b[j][0])*(b[i][0]-b[j][0])+(b[i][1]-b[j][1])*(b[i][1]-b[j][1]);
   }
   for(int j=0;j<ns;j++){
    dist[i][nb+j] = 
     (b[i][0]-s[j][0])*(b[i][0]-s[j][0])+(b[i][1]-s[j][1])*(b[i][1]-s[j][1]);
   }
  }
  
  // サーチをまたいで爆破した爆弾を記憶する配列
  boolean[] totaldone = new boolean[nb];
  int nbd = 0; // 爆破した爆弾数
  int max = 0; // Dの最大値
  while(nbd<nb){// 全部爆破するまでループ
   boolean[] done = new boolean[nb+ns]; // 本サーチで爆破した対象物を記憶する配列
   int nsd = 0; // 爆破した未確認障害物の数
   // まだ爆破した事が無い爆弾を探して、そこからスタート
   for(int i=0;i<nb;i++)
    if(!totaldone[i]){totaldone[i]=true;nbd++;done[i]=true;break;}
   while(nsd<ns){// 本サーチで全ての未確認障害物を爆破するまでループ
    int min = Integer.MAX_VALUE; //爆破した事のある対象物からのコストの最小値
    int point = -1;
    for(int i=0;i<nb;i++){ // 全ての爆弾において
     if(!done[i])continue; // 既に爆発した爆弾から
     for(int j=0;j<nb+ns;j++){ // 爆発していない対象物までのコストで
      if(done[j])continue;
      if(min>dist[i][j]){min=dist[i][j];point=j;}// 最小のもの
     }
    }
    done[point]=true; // このターンで最小のコストのものを爆破決定
    if(point >= nb)nsd++; //それが未確認障害物ならカウント
    if(point<nb && !totaldone[point])nbd++; // それが爆弾でまだ爆破していないなら
    if(point<nb) totaldone[point]=true; // とにかく爆破した事を記憶
    if(max<min)max=min; // 全てのDの最大値を取る
   }
  }
  return Math.sqrt(max); // 距離の2乗をコストにしていたのでルートを取る
 }
}