SRM 328 div1 level 1

どんどん解いちゃうな。ヤバイ。

Nが40までならごり押しでいける。全点を全時間で、隣接するライトがOFFなら色をつけて・・・を繰り返す。全点が怖かったので、ちょっと工夫して

• 色の数の要素数でArrayList[]を作成して、そこに点灯したライトの座標int[]を入れていく
  毎回、ArrayListを引っ張り出してfor(int i=array.size()-1;i>=0;i--)でループすれば
  このArrayListに要素を追加しても最初の終了条件のままループできる（最後に追加するので）
  
• ライトを点灯したらcount++して、count＜n*n*nの間、whileでループするようにする
• boolean[][][] memを用意して、点灯したらtrueにすることで点灯したことを判別

として高速化した。

しかし、解説にあるSnapDragonのsolution、すごいな。

• ある点の最終的な色は、色のスタート地点からのマンハッタン距離（格子上の距離）が最も近い色となる
• 各点において各色からのマンハッタン距離（abs(x0-x)+abs(y0-y)+abs(z0-z))を計算して最小の色に＋１

以上。これをマンハッタン距離の最短距離問題にして考えるとは、さすが。4重ループ（全点＋全色）で一発終了。

SRM 330 div1 level 3

思ったより難しかった。明日がSRMなので最後の調整。

解説（soul-netの解説は好きな方なんだけど）でも良くわからなくて苦労した。

ここでは、「相手のターンでこのコイン数だったら勝てる」をtoWin（Wとする）、そうでなければtoLose（Lとする）とする。調べたいコイン数nにおいて、n - moves[i] = toWin[j]となるi,jの組が一つでもあればnはtoLose入り、そうでなければtoWin入り。movesでループして引き算の結果がtoWinに含まれているか調べればよい（toWinをArrayListにしておけばcontainsで調べられる）。これを繰り返せばO(maxN*moves.length)だが、解説にもあるとおり多すぎ。しかし、これがtoWin, toLoseを調べる基本。toWinの初期値はmovesがソートさえているとして0～moves[0]（最も小さい数）で、moves[0]+1から順に調べていけばいい。

n - moves[i] = toWin[j]を調べるのだから、nを調べるのに参照する数字はn-moves[0]～n-moves[moves.length-1]。実はそれ以外の数は必要ではない。だから、何とかすればどこかから繰り返しになるはずなのだが、その繰り返しを見つける方法が分からなかった。

解説にあるように、nから最も離れていてnのチェックに使う数字はn-moves[moves.length-1]。これをn-lenとする。ここで、まじめに考えるとチェックに使う数字は連続でなくてmoves.length個しかないのだが、敢えて連続したlen個の数字に着目するのがミソ。toWinに含まれていたらW、でなければLというステータスをn-len ～ n-1の数字で調べると以下のようになる。

WLWWWLWWLLW？
n-len.....................n-1 n

全ての i において n - moves[i] が全てLのときｎにWステータスがつくわけで、movesの間の数は関係ないのだが敢えて調べておく。今回nはWだったとすると、今後"WLWWWLWWLLW"と続いたら次は必ずWとなる。するとn+1はWLWWWLWWLLWW？でしらべ、これがLだとすると、今度は"LWWWLWWLLWW"が続いたら次は必ずLなわけである。こうしてキャタピラのように進んでいって、同じ長さlenのWLの組み合わせが1度でも登場すれば、そこから先は全て繰り返しな訳である。

だから、上記のW/Lチェックと同時にn-len～n-1のW/Lステータスをビットで表現（maskとする）して、mem[mask]に今のnを入れておく。もし、mem[mask]に既に数字Nが入っていたら、N～n-1がmaxNまで繰り返されると思えばよい。

あとは、0を含めた0～maxNの数字のループ内・ループ外を計算すばよくて、loop = N-nとすると(maxN+1-N)/loopがループの数で、同時に調べていたtoWinにこのループ内の数字がいくつ入っていたか調べれば（countとする）、ループ内の対象数はcount*((int)(maxN+1-N)/loop)。あとはループの前後を丁寧に数える。0～N-1でtoWinに入っている数を数えて足し、loop*((int)(maxN+1-N)/loop)～maxNの数JでJ-loop*((int)(maxN+1-N)/loop)がtoWinに入っている数を足し、最後に０を除外（０は必ず入っているので素直に1引く）すれば答え。

public class LongLongNim
{
public int numberOfWins(int maxN, int[] moves)
{
Arrays.sort(moves);
TreeSet＜Integer＞ toWin = new TreeSet＜Integer＞();
TreeSet＜Integer＞ toLose = new TreeSet＜Integer＞();
for(int i=0;i＜moves[0];i++){toWin.add(i);}
int max = moves[moves.length-1];
int[] mem = new int[1＜＜(max+1)];
Arrays.fill(mem, -1);
int start = -1; int end = -1;
for(int i=0;;i++){
boolean hit = false;
for(int j=0;j＜moves.length && i＞=moves[j] && !hit;j++){
 if(toWin.contains(i-moves[j])){
  toLose.add(i);
  hit=true;
 }
}
if(!hit){toWin.add(i);}
int mask = 0;
for(int j=1;j＜=max;j++){
 if(toWin.contains(i-j)){mask |= (1＜＜j);}
}
if(mem[mask]==-1){
 mem[mask]=i;
}else{
 start = mem[mask];
 end = i-1;
 break;
}
}
int count = 0;
for(int i=start;i＜=end;i++){if(toWin.contains(i))count++;}
int loop = end-start+1;
int d = (maxN-start+1)/loop;
int ret = d*count;
for(int i=0;i＜start;i++)if(toWin.contains(i)){ret++;}
for(int i=start+d*loop;i＜=maxN;i++) {
if(toWin.contains(i-d*loop)){ret++;}
}
return ret-1;
}
}

SRM 330 div1 level2

TrieもしくはPrefixed Treeなるものがあるらしいが。

要するに

• ある要素があるPrefix-Freeの集合体のどの要素のPrefixでもないならば、集合和もPrefix-Free
• ある要素をSubset数Sの集団に加えた時、Subset数は２Sになる（元のSubsetと新要素＋各Subsetでできる新Subsetの和だから）
• 文字列をソートすれば、PrefixとそれをPrefixにもつ全要素が連続する。
  a, ab, ac, d, ddであればab, acがaをprefixにもつ。
• 文字列をソートして、降順に「Prefix-Freeの要素数」を数えてメモライズすればよい
  　新Subset数＝旧Subset数＋新要素がPrefixとならない全旧Subset数
  なので、降順からループした時、
  　値　＝　前回の値　＋ 新要素がPrefixとならない単語まで遡った所の値
  　　　　　　　　　　　　　　　（それ以前の全要素とはPrefix-Freeとなるため）
  で求められる。

DPのmemが直接戻り値になる理論で考えれば自然にたどり着く・・・

SRM 330 div1 level1

条件分岐とテストケースの問題。こういう問題はテストケースが面倒くさい。

解説によれば、面倒くさくない！

＜、＞、＜－、＜＝、－＞、＝＞、・・・が含まれるか indexOfでチェックして一番長いのを返せばよい！
矢軸の長さを０から最大長までループすれば簡単！やられた！

以下はくそまじめにやる方法。


単純に文字を読んでいき、今読んでいる文字が矢印の一部になると想定して、現在の左端の矢尻"＜＞"と矢軸"-="をそれぞれchar tail, bodyに覚えておく（tail, bodyはない場合もあるので' 'も可）。また、今の矢軸の長さも覚えておく（bodylength）

基本的に以下のようになるが、うまくまとめるとIF文は少なくなる。
面倒くさい。

tail body now
＜ - ＞　bodylength+1で終了、bodylength=0, body=' ' tail = '＞'
＜ - ＜　bodylength+1で終了（←）、bodylength=0, body=' ' tail = '＜'
＜ - -　bodylength++
＜ - =　bodylength+1で終了（←）、bodylength=1, body='=', tail=' ',
＜ = ＞ bodylength+1で終了、bodylength=0, body=' ' tail = '＞'
＜ = ＜ bodylength+1で終了（←）、bodylength=0, body=' ' tail = '＜'
＜ = -　bodylength+1で終了（←）、bodylength=1, body='-', tail=' ',
＜ = =　bodylength++
＜ ＞　bodylength+1で終了（＜）、bodylength=0, body=' ' tail = '＞'
＜ ＜　bodylength+1で終了（＜）、bodylength=0, body=' ' tail = '＜'
＜ -　bodylength++、body='-'
＜ =　bodylength++、body='='
＞ - ＞ bodylength+1で終了（→）、bodylength=0, body=' ' tail = '＞'
＞ - ＜　bodylength=0, body=' ' tail = '＜'
＞ - -　bodylength++
＞ - =　bodylength=1, body='=', tail=' ',
＞ = ＞　bodylength+1で終了（→）、bodylength=0, body=' ' tail = '＞'
＞ = ＜　bodylength=0, body=' ' tail = '＜'
＞ = -　bodylength=1, body='-', tail=' ',
＞ = =　bodylength++
＞ ＞
＞ ＜
＞ -
＞ =
　 - ＞
　 - ＜
　 - -
　 - =
　 = ＞
　 = ＜
　 = -
　 = =
　 ＞
　 ＜
　 -
　 =

SRM 331 div1 level 3

私は図形系問題が苦手なので苦労したが、1000点にしては比較的易しい部類だと思う。

解説はかなり短いがポイントは多い。

手順

1. 全ての「頂点候補」を洗い出す
2. 各「頂点候補」から右・下にそれぞれ辺を伸ばせる最大値を求めておく
3. 各「頂点候補」と同じY座標で右側にある全「頂点候補」に対して、その距離Lをもって以下のチェックする。
1. 起点となる「頂点候補」から距離L以上辺が右に伸ばせるか？
2. 起点となる「頂点候補」から距離L以上辺が下に伸ばせるか？
3. 同Y座標で右側の「頂点候補」から距離L以上辺が下に伸ばせるか？
4. 起点となる「頂点候補」と同じX座標で距離Lだけ下に「頂点候補」があるか？
5. ４の「頂点候補」から距離L以上辺が右に延ばせるか？
   
4. ３の全てがOKならばそれは正方形。
   

１で頂点を気にして考えると全ての線の交点を数えなければいけない気がするが、どの道後半で辺を伸ばせるかどうかチェックするので、実は頂点である必要はない。頂点となる候補であればよい。頂点のX座標はかならずx1,x2の配列の中にある。だから２つの配列x1,x2の重複を除いた全要素がxx頂点候補のX座標。同じくyyも求めると、xx.length × yy.length個の全(xx[i], yy[j])が頂点になりうる頂点候補である。勿論、全部が頂点ではない（全然違う点のX座標とY座標かもしれないが、気にしない）。

重複を除き、後の便利でソートするためにTreeSetを使っておく。andrewzta（Java）を参考にした。

２である点から右・下に伸ばせる辺の長さの最大を求めるにはプライベートクラスを作った。C++ではpairというクラスがあるらしくてうらやましいが。単にComparableをimplementsしてcompareToを実装するだけ。静的変数をみて何でソート対象変数・方向を切り替えることができるようにもできるので、自作Comparableクラス＋Arrays.sort()は便利である。

まず、四角の数だけi,x1[i],x2[i]のペアを作り、x1[i]の要素でソートする。x1順に並ぶわけである。それはつまり各辺が以下のように開始点順に並ぶわけである。点(x,y)から右に進める最大値を求めるには、全ペアをループしながら、添え字iからy1,y2を使ってY座標を調べ、y1かy2がyである辺を探す。それらの辺もやはり開始点順に並んでいるので、x1＜=x＜lx2である辺であれば、x=x2に進める。これを繰り返すと以下のように重なっている辺を渡り歩いて一番右まで進めるわけである。一番下まで進むにはこれをyで行う。全ての点について右最大値、下最大値を配列に覚えておく。

+======x
　　　+---=======x
　　　　+--o
　　　　　　　　　+---====X
　　　　　　　　　　　　　　　　　　+----o

あとは３で全頂点候補に関して、自分の右にある頂点候補に対して順にIF文を繰り返すだけである。全条件を満たせばカウンターをインクリメントし、それが 答えになる。

コード
public class HiddenSquares
{
 public int count(int[] x1, int[] y1, int[] x2, int[] y2)
 {
  int n = x1.length;
  Pair[] x = new Pair[n];
  Pair[] y = new Pair[n];
  TreeSet＜Integer＞ xx = new TreeSet＜Integer＞();
  TreeSet＜Integer＞ yy = new TreeSet＜Integer＞();
  for(int i=0;i＜n;i++){
   x[i] = new Pair(i, x1[i], x2[i]);
   y[i] = new Pair(i, y1[i], y2[i]);
   xx.add(x1[i]); xx.add(x2[i]);
   yy.add(y1[i]); yy.add(y2[i]);
  }
  Arrays.sort(x); Arrays.sort(y);
  int[] X = new int[xx.size()]; 
  int[] Y = new int[yy.size()];
  int idx=0;for(int a: xx) X[idx++]=a;
  idx=0;for(int a: yy) Y[idx++]=a;
  
  int[][] maxR = new int[X.length][Y.length];
  int[][] maxD = new int[X.length][Y.length];
  
  for(int i=0;i＜X.length;i++){
   for(int j=0;j＜Y.length;j++){
    // max Right
    int tx = X[i]; int ty = Y[j]; int start = tx;
    for(int k=0;k＜x.length;k++){
     if(y1[x[k].id] != ty && y2[x[k].id] != ty) continue;
     if(x[k].first ＜= start && x[k].second ＞ start){
      start = x[k].second;
     }
    }
    maxR[i][j] = start;
    // max Down
    start = ty;
    for(int k=0;k＜y.length;k++){
     if(x1[y[k].id] != tx && x2[y[k].id] != tx) continue;
     if(y[k].first ＜= start && y[k].second ＞ start) {
      start = y[k].second;
     }
    }
    maxD[i][j] = start;
   }
  }
  int count = 0;
  for(int i=0;i＜X.length;i++){
   for(int j=0;j＜Y.length;j++){
    int tx = X[i]; int ty = Y[j];
    for(int k=i+1;k＜X.length;k++){
     int rx = X[k];
     int L = rx-tx;
     if(maxR[i][j]-tx ＜ L) continue;
     if(maxD[i][j]-ty ＜ L) continue;
     if(maxD[k][j]-ty ＜ L) continue;
     // find bottom left corner
     int byindex = -1;
     for(int l=j+1;l＜Y.length && Y[l]＜=ty+L;l++){
      if(Y[l]==ty+L){byindex=l;break;}
     }
     if(byindex==-1) continue;
     if(maxR[i][byindex]-tx ＜ L) continue;
     count++;
    }
   }
  }
  return count;
 }
 
 class Pair implements Comparable {
  int id; int first; int second;
  public Pair(int id, int first, int second){
   this.id = id;
   this.first = first;
   this.second = second;
  }
  public int compareTo(Object o){
   Pair oo = (Pair)o;
   return this.first - oo.first;
  }
 }
}

SRM 331 div1 level2 Shopping

解説もいいけど、賢過ぎなきがする。

Sドルまでn個のコインで表現できた状態で、x<=S+1の金額のコインを持ってくるとS+xドルまでn+1個のコインで表現できる状態に飛べる、というもの。１～Ｓまでは仮定から既にＯＫで単純に０、１～Ｓのそれぞれの金額にxを足すとx、x+1～Ｓ+xまでもＯＫになる。x<=S+1だから１～Ｓとx～S+xは繋がるという仕組み。 i=１～Ｘ（Ｘ含まず）のループで、i=1の時にコインの数c=1とする。i+1以下ので最大のコインを加える。コインに1があること前提で必ず加えられるコインはある。そのコインがkだとすると、i=i+k、c++でループの頭に戻る。つまり、iまでの金額をcコインで表現できるという意味。iがＸかＸを越えた地点でのcが欲しいので、i=Xの時に加算のループをする必要はない。 基本に返って考える。ナップサック問題だと思うとどうだろうか。andrewztaの回答が基本に忠実で美しい。

1. メモライズするmemはなんであるかを考える。ナップサック問題に習うと
   int[][] mem = new int[values.length][X+1];
   (金額をそのまま添え字にするために１～Ｘを利用）
   
   
2. 答えはreturn mem[values.length-1][X]で返したい。そう思えばmemの意味は
   「mem[i][j]はコイン種類0～iまでを使って金額1～jまでを表現するのに必要なコイン数」
   となる。
   
   
3. 各コインの枚数が問題なので、金額の小さいコインから順に何枚必要かを考えていく。
   金額xを作るのに金額vのコインは０～x/v個使用出来る。
   k個使用した場合、v, 2v, ..., kvの金額は表現できるので、１～xの全てを表現するには隙間を埋めなければならない。隙間はそれぞれの間隔mv+1～mv+v-1と、kv+1～xである。これは、1～v-1と1～x-kvが既に小さい金額のコインで表現できていれば良い。大きい方で十分なので１～max（v-1, x-kv）が表現できているかを調べる。
   
   
4. すると、k=0～x/vのループでmem[i-1][max(v-1, x-kv)]が既に値を持っていればmem[i-1][max(v-1, x-kv)]+kがmem[i][x]の候補になる。
   
   
5. ただし、添え字となるmax(v-1, x-kv)が0-Xであることを保障しなければならないのでmin(max(v-1,x-kv),x)となる。１～xが表現できていれば十分である。また、i-1も0-values.lengthなので、iは１から始めて、初期条件mem[0][j]は自明であるjを代入しておく。ここではソートされたvaluesの最初の要素が1であると仮定している。1でない場合は１を表現できないので-1を返して終了できるのでこの仮定は成り立つ。
   
   
6. mem[values.length-1][X]が答え。
   

public class Shopping {
public int minNumber(int X, int[] values) {
 Arrays.sort(values);
 int n = values.length;
 int[][] a = new int[X + 1][n + 1];
 for (int i = 1; i <= X; i++) {a[i][0] = -1;}
 for (int j = 1; j <= n; j++) {      
  for (int i = 1; i <= X; i++) {
   a[i][j] = -1;
   int v = values[j - 1];
   for (int k = 0; k <= X / v; k++) {
    int z = Math.max(i - k * v, v - 1);
    z = Math.min(z, X);
    if (a[z][j - 1] == -1) {continue;}
    if (a[i][j] == -1 || a[i][j] > a[z][j - 1] + k) {
     a[i][j] = a[z][j - 1] + k;
    }
   }
  }
 }
 return a[X][n];
}
}

SRM 331 div1 level1 CarolsSinging

どんどん遡って練習してます。

スピード問題。Javaで最速の人を参考。

public int choose(String[] lyrics) {
       int res = 1000;
       int[] masks = new int[lyrics.length];
       int carols = lyrics[0].length();
       for (int i = 0; i < lyrics.length; i++)
           masks[i] = Integer.parseInt(
  lyrics[i].replace('Y', '1')
   .replace('N', '0'), 2);
       for (int m = 0; m < 1 << carols; m++) {
           boolean ok = true;
           for (int i = 0; i < masks.length; i++)
               if ((masks[i] & m) == 0) ok = false;
           if (ok && Integer.bitCount(m) < res)
  res = Integer.bitCount(m);
       }
       return res;
   }

• 文字列 "YYNNNY"をビット110001に変換
  

  Integer.parseInt(lyrics[i].replace('Y', '1')
   .replace('N','0'),2)

• 
  


• int の立っているビットを数える
  

  Integer.bitCount(m)



• ビットなんてものは後で何でもできるから、まずビット化し方法を採用してあとはループ。
  この場合、人毎にintを作って人ビットを作った方が早い。
  Carolsの組み合わせビットを使ってチェックするには
  一人一人 Carolsビット & 人ビットを取って、一人も０にならないCarolsビットを採用
  

SRM 339 div1 level3

ポイントは、起点となるランクの人を決めた時、その人が最大金星を取れたとして、更に負けるべき人も最大金星を取れて・・・というツリー探索を、常に上位のランクの人から最大金星をつぶしていくようにすること。そしてつぶせればその人は起点となりえ、つぶせなければその人が優勝することは不可能。最上位を負かせる人から勝負していかないといけないので、常にランク順にソートしてランクの上のものからサーチしなければいけない。常に次のレベルの枝に移る時にＡｒｒａｙ．ｓｏｒｔしてみる。

なるべくランクの低い人を起点するよう調べなければいけないが、最低ランクから順に調べると2^16かかる。ソートしていることを考慮すると間に合わない。

なるべくランクの低い人を探すということは、ソートされた配列をサーチするのと同じであると気付けば、バイナリサーチすればよい。i=2^n番目から始めて、i番目の人が起点になりえれば、次はi = i | 2^(n-1)番目の人、とサーチしていけばn回の試行でよい。上記のArray.sortは全く問題なくなる。

既存の配列をサーチするときだけでなく、引数を順にインクリメントしながら関数を実行して最大／最小の引数を求める場合などでもサーチのアルゴリズムは使えることを思い出す。また、バイナリサーチの実装も覚えておく。

• 最大金星の範囲内のものが更に最大金星をとって・・・と範囲の重なりでどんどん範囲を広げていくものをinterval treeというものらしい。
• 消去法でつぶしていく時は、先からつぶしていくか手前からつぶしていくか考えないとコンフリクトする
• i = i | 2^(k-1)番目の要素と比較してバイナリサーチを実装
• 比較は単に既存のデータの比較ではなく、関数の実行結果の比較でも使える
  

SRM 339 div1 level2

最初に数学をやっておけば簡単だった。

この賭け、結局勝って次の賭けからもう一度勝つ時に儲かるチップは必ず１。

Ｓ= 1+2+4+...+2^n
2S = 2+4+8+...+2^(n+1)
S=2S-S = 2^(n+1)-1

n-1回負けてn回目に勝つと負け分は2^n-1、勝ち分は2^n、だから儲けは１。

すると、連続k回負けて次に勝つというセットがどのように組めるか数えればよいだけ。ゴールが1000だから、現在の持ち金と残りラウンド数の2次元配列でも[1000][50]だからＤＰで余裕。残りラウンドがrなら、0からr-1回連続で負けて次に勝つというセットが取れる。確率は求められるし、k回負けて次にかつなら、残りラウンドはr-k-1にして次の再起呼び出しをすればよい。

• 等差数列は解いておけ
• ＤＰはmemすること前提に。memのサイズでループ回数を概算。
• この場合は、途中で掛け金がなくなることを終了条件に含めなければならない。
  

SRM 339 div1 level1

Little Birryむかつく。

• 時間が1000以内であるので、単に毎単位時間チェックしていけばよいことに気付く
• 1ターンの順序を紙に書いていけ
• 必要な変数を書き出していけ

SRM 340 div1 level3

難しい。覚えることたくさん。

まず、囲む系の問題は範囲チェックのロジックを思い出す。「ある一方方向」に向かって端まで進むのに境界を何回越えるかを数える。奇数なら内側、偶数なら外側。

このとき、実はある一方だけでよい。2次元空間でも1つの軸だけでよい。1軸についても正か負のどちらかだけでよい。ただし、範囲が閉じていることが保障されていなければならない。なぜなら、閉じているので軸の向きに関係が無く、ある軸においては閉じた空間で切れば必ず境界は偶数ある。だから片方が偶数ならもう片方は偶数、奇数なら奇数と反対側の境界線数も決まってしまう。

チェックすべきものが最大で10なので、総当りでも2^10=1024しかないのでモノをビットで見立てて、それらの境界線数のパリティをintのビットで表しておく。また、各セグメントを通った時にそれぞれのモノの境界線のカウントに含まれるかどうかもintのビットで表しておく。 ＸＯＲを取り続けると、その結果がパリティになるので、境界線パリティのintと通ったセグメントのintをＸＯＲしていけば、その時の境界線パリティが更新され続ける。

同じ場所を通って同じ境界線パリティであれば全く同じ状態と思っていいので、int[51][51][1<<n]（nはチェックすべきモノの数）をメモライズすればよく、最小コストの枝だけを残していけばｂｓｆで～2,500,000程度のループになる。常に到達可能なセグメントを進んでいき、進むたびに境界線パリティをＸＯＲで計算して、memしてあるx,y,パリティのステップ数より小さい時だけ進んでいく。x=y=0になったら止める。ぎりぎりいける。

• 境界の内外問題は、閉じた空間であることを保障して1軸1方向に進んだ時の境界のパリティで内外を判断する（1軸1方向でよければ状態数は激減する）
• ＢＳＦなどサーチの問題のループ数はmemのサイズのオーダーだと思えばよい
• やはりＬｉｎｋｅｄＬｉｓｔを使え
• 境界を作成するループは普通にやれば無限だが、その地点にいるときの意味が同じものを除いてしまえば状態数は激減する。この場合、各モノが数える境界線パリティの状態が同じものは同じ意味を成すので、常にパリティを数えながら移動して行けばよい

SRM 340 div1 level2

久しぶりです。TopCoder Open 2007に向けて、スキルを蓄積していこうかと思います。

SRM 340 div1 level2

理論スキルと実践スキルの2次元マップだと思えば、(0,0)から(skillBound, skillBound)まで移動する最短経路問題となる。ただし、移動は(0,1), (1,0), (1,1)が可能で、授業が受けられればどれも同じコスト。マップの大きさは、授業の数が50で二回以上受けても意味がないことから、0－50の５１ｘ５１でＯＫ。よって幅優先探索でも～51x51で十分ＯＫ。各探索で授業全部をスキャンするとしても51x51x50は余裕。

理論スキル、実践スキル、時間（月）、これまで受けた授業をＱｕｅｕｅに渡してぐるぐる回して、受けられる授業があれば片っ端から受けて枝を広げる。その時、その座標でより短く若い受講数・辞書順で到達していたらその枝は止める。両スキル目標達成したら、今までの最短受講数・辞書順を比べて更新する。

授業を受けるたびにintを加えていかなければいけないが、最初から最大個数の配列を用意しておいて、受講記録用配列（最大固定）と受講数の２つのメモライズを使えば楽。その代わり、返却値を返す時はSystem.arraycopyで整えなければならない。

• LinkedListを使え（一応）
• ゴールは（skillBound, skillBound）ではない。（>=skillBound, >=skillBound）のどこかの地点。到達チェックを毎回行って、到達したら最小値チェックをして返却候補に収めてしまえばよい。
• 動的配列を無理にmemしないで、固定配列memとインデックスmemの2つを使えばよい。
• 初期条件を確認。目標値０ならば授業を受けなくていいので{}を返さなければならない。（０，０）から始めるなら、到達チェックは最初にやらなければならない。

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乗をコストにしていたのでルートを取る
 }
}

SRM269 Div1 Level 1 PatternOptimizer

SRM269 Div1 Level 1 PatternOptimizer

少し古いですがSRM269から。私は結局Level3が簡単と誤認して０問解答＆チャレンジ失敗（-25)という最悪の結果に終わり、Div2へ転落しました。実はLevel1が気づけば簡単だったことを後で認識し、かなりショックを受けました・・・

問題

正規表現 ‘?’ （任意の１文字）、’*’（任意の０文字以上の文字）を使った文字列がある。これと同じ意味（例： “*??*a” = “?*?a”）を示す最短の文字列を返せ。同じ長さの回答がある場合は辞書順（* は ? より先）。

条件

• 文字列の長さは１～５０文字


• 文字列の文字は('a'-'z','A'-'Z')

考え方

まず、問題から特定文字列を最適化された文字列に置換していく問題である事を理解しなければならない。そのパターンは例題から見つかる。

"*??*a"　-> "*??a"
"*b**a*"　-> "*b*a*"
"cla??" 　-> "cla??"
"*?*?*?*"　-> "*???"
"T***nd?*"　-> "T*nd*?"

まず、連続する”*”は１つに省略できる。”?*”のペアは”*?”と同じ意味（１文字以上の任意の文字列）となるので、辞書順から”*?”にできる。これをパターン化すると”**”を”*”と置換、”?*”を”*?”と置換、の２つを可能な限り繰り返せばよい。

順に一度のsweepで実現するためには、置換によって文字列の長さが変わって文字列を調査するindexがずれる事を考慮する必要がある。私はここで色々なテストケースを用意したりして５分ほど不要な時間をとられた。”**”と”?*”が無くなるまでsweepを繰り返すと思えば、実はJavaならばStringクラスのreplaceAll(String reg, String replace)で置換すれば早い。この手の問題はこういった工夫で１分でも時間を短縮できるようがんばる。

解答例

public class PatternOptimizer{
 public String optimize(String pattern){
  // "**"と"?*"がなくなるまで置換を繰り返す
  while(pattern.indexOf("**") != -1  pattern.indexOf("?*")!=-1){
   pattern = pattern.replaceAll("\\*\\*","*");
   pattern = pattern.replaceAll("\\?\\*","*?");
  }
  return pattern;
 }
}

はじめに

このブログは、プログラマーに競争と報酬の場を提供するTopCoderのアルゴリズムコンペティションに関して、私の勉強ノートとして各コンペの問題に関するアプローチとコーディングを記録していくものです。アルゴリズムは奥が深く、多くの人が集まれば集まるほど考え方も多様化し、その集大成として全体の技術の底上げができると考えています。もちろんTopCoderのページにも議論する場がありますが、もちろん英語ですので（問題も英語ですが・・・）、日本語で議論する事で、日本人はより活発に議論しあえるのではないかと思ったわけです。

また、このコンペはとてもよくできており、ぜひとも多くのCoderにこのすばらしいシステムを知ってもらいたく、宣伝もかねてCoderの毎日をつづって行きたいと思います。

よろしく！