読者です 読者をやめる 読者になる 読者になる

methaneのブログ

このブログに乗せているサンプルコードはすべてNYSLです。

PKU1050番

program

http://acm.pku.edu.cn/JudgeOnline/problem?id=1050
http://d.hatena.ne.jp/fkm/20060511/p1
http://d.hatena.ne.jp/fkm/20060508/p1

fkm氏にコメントしたヒントは問題をよく見ないで適当に思いついたモノを超抽象的に書いたもので、fkm氏が解けたのは完全にfkm氏の実力です。
せっかくなのでちゃんと考えて、その考え方を紹介。自分で考える人は考えた後に比べてみて、「オレの方が頭が良い」と思ったらコメント下さい。

  1. 2次元パズルはまず1次元の問題に置き換えるのが基本。上下と左右に直交性があるパズルではそのまま2次元に適用できるし、完全に直交していなくてもヒントにはなる。
  2. 1次元の長さNの配列で、合計が最大になる範囲を求めてみる。配列のindexが大きい側を右と呼ぶ。
    1. [開始点,終了点]という概念を導入する。終了点は開始地点と同じか、開始地点より右にある。
    2. 開始点が取り得る位置はN個。終了点が取り得る位置の平均はN/2個。組み合わせの計算量はO(N^2)。全探索は現実的なオーダーだが、2次元に拡張するとちょっと重い。
    3. まず開始点と終了点を0として、合計値が正の間終了点を右にずらしていき、その最大値を記憶する。合計値が負になった時点で終了点の移動を打ち切る。このとき、終了点の値は必ず負であり、解は終了点の左側の最大値(すでに求めたもの)か、終了点の右側の最大値(まだ求めていないもの)である。終了点を含む範囲に最大値が存在しえないのがミソ。
    4. (まだ求めていないもの)を求める。これは先ほどと同じ方法で求まる。終了点がNになった時点で終了する。
    5. これで、計算量はO(N)になる。さすがにO(1)やO(logN)のアルゴリズムは直感的に無さそうなので、ここで思考打ち切り。
// 一次元版の解法。眠いので検証してない。

#define MAX(a,b) ((a) < (b)) ? (b) : (a)

int arr_maxsum( int *arr, int N ){
   int e, sum=0, max=0;
   for (e = 0; e < N; ++e) {
      sum += arr[e];
      if(sum < 0) {
         int rmax = arr_maxsum( arr + e + 1, N - e - 1 );
         max = MAX(max, rmax);
         break;
      }
      max = MAX(max, sum);
   }
   return max;
}
  1. 1次元のアルゴリズムを2次元に拡張できるか考えてみる。つまり、開始点を左上端として、終了点を任意の位置にしたとき、その矩形の合計が負なら、解となる矩形は終了点を含まないと言えるか?残念ながら答えは否である。終了点の右側も終了点の下側も共に大きいとき、負の矩形を使ってでも右と下をくっつける事でより大きくなる場合があり得る。これは条件付きなのでまだ考えれば突破口があるかもしれないが、とりあえず保留。
  2. 最初に考えたとおり、1次元を全探索する計算量はO(N^2)である。X軸を全探索でO(N^2)、Y軸をO(N)のアルゴリズムでで組み合わせると、計算量はO(N^3)で、十分実用に耐える。面倒なのでO(N^2)のアルゴリズムの検討はパスする。
// 二次元版の解法。眠いので検証してない。

#define MAX(a,b) ((a) < (b)) ? (b) : (a)

// 二次元配列の内で、左と右が決まっているときに、
// 一次元配列の時と同じ方法で下に拡張していった最大値を求める。
int arr_maxsum( int *arr, int N, int M ){
   int e, sum=0, max=0;
   for (e = 0; e < N; ++e) {
      int hsum = 0, i;
      for (i = 0; i < M; ++i) {
         hsum += arr[M*e+i];
      }
      sum += hsum;
      if(sum < 0) {
         int rmax = arr_maxsum( arr + e + 1, N - e - 1 );
         max = MAX(max, rmax);
         break;
      }
      max = MAX(max, sum);
   }
   return max;
}

// 2次元配列の中の矩形合計の最大値を計算する。
int rect_maxsum( int *arr, int N, int M ){
   int xs,width;
   int max = 0;
   for (xs = 0; xs < N; ++xs) {
      for (width = 1; width < (M - xs); ++width) {
         int nmax = arr_maxsum( arr + xs, N, width );
         max = MAX( max, nmax );
      }
   }
   return max;
}

P.S.
arr_maxsum()が再帰になってるけど、僕の頭の中のイメージが再帰だっただけです。

for (s=0;s<N;++s) { for (e=s;e<N;++e) { ... } }

の方がきれいで速いけど、修正が面倒なので放置します。