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つを使えばよい。
• 初期条件を確認。目標値０ならば授業を受けなくていいので{}を返さなければならない。（０，０）から始めるなら、到達チェックは最初にやらなければならない。