SRM404 - tsubosakaの日記

順位があまり良くなかったためRateが1880->1775へと下がった

250

三角形の下から値を決めていく．もしくは全部の要素を見ていって決定できるところがあったら決定するを繰り返して，全部埋まるまでループする．

500

長さが3000までのintの配列 A が与えられるので，長さが同じ重なりがない区間を2つとったときに区間中の数の和の絶対値の差が最小となる区間の長さとその差を求めよという問題．
今，区間の長さをkと固定してB[i]=\sum_{j=0}^{k-1} A[i+j]とAの要素をインデックスiからk個取って足したものとする．
まずあきらかにTLEの解法として

for(int j =  k ; j < A.length ; j++){
  for(int l = 0 ; l <= j - k ; l++){
    //abs(B[j]-B[l])を計算してその最小値を求める
  }
}

と取る方法でこれは区間の取り方がn/2あることを考えるとO(n^3)で3000^3だと2秒ではつらい．
そこで2番目のループでlを回す代わりにB[0]..B[j-k]の値を2分探索木などに保存しておいてB[j]に最も近い上下2つの値と比較する．これだとO(n^2 log n)で一見うまくいく．
ただC++のsetでlower_boundを使うなどだと大丈夫なようですが手元で試したところTopCoderで使えるJava 5.0のTreeSetの実装だとすこし微妙で{B[0]..B[j-k]}中のB[j]以下の値の中で最大の数を求める時には

//BSはB[0]..B[j-k]の値が入っているTreeSetであるとする
SortedSet<Long> u = BS.tailSet(B[j]);
if(!u.isEmpty()){
  return u.last();
}

とする必要があって，これだと2分木を2回たどる上に余計なサブセットまで作成しなければならず無駄が多い．6.0の場合は

Long v = BS.ceiling(B[j]);
if(v != null){
  return v;
}

と書けて、手元の測定では大きさ3000の配列に対して最初のコードは4秒ぐらいの実行時間がかかり，次のコードならば実行時間が2秒弱のため6.0だとO(n^2log n)の解法でも通るのだが5.0環境のJavaだとこの解法で進めるのは難しい．Javaで二人だけ通っているんだけど実はO(n^2)の解法が存在するらしい。

追記:O(n^2)の解法というのは嘘でよくみたらソートしていたのでO(n^2 log n)だった、ただし平衡二分木は使う必要がなくて配列だけで事が足りるので十分間に合うようです。