最大長方形の面積
和田 英一
IIJ 技術研究所

wada@u-tokyo.ac.jp■ 連載の始めにこの 4 月から「プログラム・プロムナード」という連載を始めることになった.
本年 1 月に開催したプログラミング・シンポジウム報告集の前書きにも書いたのだが，最近プログラムを書く機会が少なくなっているということを耳にする．また ACM 国際大学対抗プログラミングコン
テスト，日本でのアジア地区予選では，アジア各地から参加する海外の大学に首位を奪われ続けている．これを放置しておくと，日本のプログラミングパワーはますます沈下するのではないかと懸念される.
古きよき昔はせっせとプログラムを書いたものである．そもそも各地にあった計算機はそれぞれが個性的であったから，プログラムを彼方から持ってくるということは考えもしなかった．他のセンターに欲しいプログラムがあれば，そのプログラムを調べ，自分用に書き直さなければならなかった．
左様な面倒なことをするより，自ら考え，作ってしまう方が早かったし，楽しかった.
しかし事情は一転している．最近の学生はプログラムの移植ばかりに熱心だと嘆く教授がいる．同じアーキテクチャの計算機が孫悟空の分身のように散らばっているから，どこかに使えそうなプログラムが存在する機会，確率は激増している．移植しなければ損だという気運も分からぬではない.
一方，自分で書かないのはなぜか．
• プログラムを書くのは面倒だ．
• とにかく書き方が分からぬ．
• 周囲にプログラムを書こうという雰囲気がない．
• 就職してもプログラム技能は活かされそうもない．
まだあろうか．
だが，プログラミングは情報処理の基本である．情報処理学会誌では，当然のこととして，これまでプログラミングの奨励は特にはしてこなかった．今回，これらの反省としてプログラミングも取り上げたいというのが，連載の趣旨である.
いうまでもないが，プログラムを書くことには利点も多い．
• 面白いアルゴリズムが見出せる．
• すっきりしたシステムが設計できる．
• 自らの思考の正しさが納得できる．
• 計画通りにものが動くのを見るのは楽しい．
プログラミングはものつくりの第一歩であり，こういう喜びを経験できない人は気の毒である.

IPSJ Magazine Vol.43 No.4 Apr. 2002435

この連載では，以前 Communications of the ACM 誌に連載されていた，プログラミングパールス☆ 1 を範にとり，いろいろな問題に対し，プログラムはいかに考えて書くべきかを解説することにしたい．
その問題は，前述の ACM 国際大学対抗プログラミングコンテストから借りてこよう．これらの問題は限られた時間のなかで，与えられた複数のデータを入力し，期待された出力を得るプログラムがいく
つ書けるかをみるためのもので，拙速プログラミングを奨励するようでもあり，必ずしも適切ではな
いが，コンテストとしてはやむを得まい．今回の連載には，学生諸君に ACM プログラミングコンテス
トは少しも恐くないということを知ってもらい，大勢の挑戦者が現れて欲しいという願望もこめられている.
このコンテストについてここで簡単に説明する 1），2）．ACM 国際大学対抗プログラミングコンテストは毎年開催される．チームは 3 名の学部学生で構成する．世界大会は 3 月頃に各地の予選を通過したチームを集めて開催されるが，日本国内で話題になるのは国内で開催されるアジア地区予選である．ア
ジア地区予選といってもアジアの数カ所で開催され，最近の 4 年間はその 1 カ所が日本国内にある（1998 年東京，1999 年京都，2000 年つくば，2001 年函館）．アジア地区予選に参加できるのは各地でそれぞれ 30 チーム程度であり，このうち数チームは海外から遠征してくるので，国内からは 20 チームくらいしか参加できない．そのため国内からの参加チームを選抜する国内予選がまず行われる．したがってコンテストは• 国内予選• アジア地区予選と 2 回ある．国内予選の問題は 5 題，アジア地区予選は 8 題となっているので，毎年 13 問題が新たに作成される．それを少しずつ連載で解説しよう．時にはこのコンテスト以外の問題もあるかもしれぬ（直前の函館大会の様子は http://www.fun.ac.jp/icpc/を見て欲しい．問題もそこから得られる）.
コンテストの公式言語は C，C++，Pascal，Java となっているが，この連載では主として C を使う．
ただ，アルゴリズムを明確にすべく，ANSI-C 規格に厳密には従わないかもしれぬ．その他 Lisp を使うこともあろう．プロトタイピングには Lisp が便利だからだ．周知のように Lisp には方言が多く，使うLisp も本来は決めておきたいが，方言というほどで Scheme を除いては相互にあまり違いはなく，現段階ではどの Lisp ということは決めずに出発したい.

■ 問題: 最大長方形の面積
2001 年度国内予選の問題 A は，5 × 5 の桝目のそれぞれに 1 か 0 が書いてあり，その中から 1 だけでできている最大の長方形の面積を答える.

-1なら 4，-2なら 3 が正解となる．

力づくで書くと☆ 1 Jon Bentley: Programming Pearls（Addison-Wesley 1986, 野下浩平 訳:「プログラム設計の着想」近代科学社）.

436

43巻4号 情報処理 2002年4月

となろう．これは for ループが 6 重になっているので，O(n6) アルゴリズムという．5 × 5 のデータ処理の時間に対し，10 × 10 の処理時間は 64倍になるわけだ．

■ ダイナミックプログラミングによるもの
通常，この種の問題はまずダイナミックプログラミングで解けないかと考える．つまり（2 次元の問
題なら）左上から右下へ個々の要素を順次に辿り，上隣と左隣の解の情報から，注目中の要素の解の情報を構成する．いいかえれば，ダイナミックプログラミングは配列の各要素につき，隣まで解けていたとして，その結果から注目している要素について解く．この方法については学会誌 2002 年 1 月号で阿久津君が DNA 配列の比較の話題で述べている 3）が，DNA 以前にそのアルゴリズムをテキストエディタで使っていた例 4）がある.
多少天降り的だが，図-1 に対しては，-3のような図を作りながら計算が進行するとする.

左上隅の(1 1)は，ここにできる最大の長方形は，x（左）方向に長さ 1，y（上）方向にも長さ 1 であることを示す．その右の要素の (2 1) は，最大の長方形は，x 方向に長さ 2，y 方向に長さ 1 である；
さらに下へいくと(1 2)で，これは x 方向が 1，y 方向が 2 の長方形ができるの意である．この要素から右へ 2 進むと(1 2)(3 1)とあり，図-1と見比べると，確かに上に長さ 2 の長方形(1 2)と，左に長さ3 のもの(3 1)ができるらしい．この最後の例のように，要素によっては複数の可能性を持つものがあり，その後の処理にどの長方形が利用されるか未定なため，すべての可能性の情報を持ち歩くことになる．
したがってこの情報はリストの形で保持する.
上隣と左隣の情報から自分の情報をどう作るかがこのアルゴリズムの中心だが，まずIPSJ Magazine Vol.43 No.4 Apr. 2002437

• 注目点が0 ならなにもしない．
• 注目点が1 なら上隣と左隣の情報を見る．
- 両隣がともに 0なら自分だけで長方形を作るより仕方ないので(1 1)とする.
- 上隣が 0で左隣が1 なら，上にはもう発展できないが，左に伸びられるから，（左方に続く 1の個数 1）とする.
- 左隣が 0で上隣が1 なら，左にはもう発展できないが，上に伸びられるから，（1 上方に続く 1 の個数）とする.
- 左隣も上隣も 1 なら，両隣の候補のリストを参考にして新しい候補のリストを作る．それには-4を見て考えよう．
いま右下の 1 と書いてある要素を処理しているとする．左隣は((1 5)(2 4)(3 3))上隣は((3 3)(42)(5 1))である．左隣は横に伸びたので x の値をそれぞれ 1 増やす；しかし上方は 0 で押さえられるから，y の値は上方に 1 の続く個数，ここでは 4 を最大値にする．したがって((2 4)(3 4)(4 3))になる．
同様に上隣のは y の値を 1 増やし，x の値は左方に 1 の続く個数，ここでは 4 を最大値にするから((34)(4 3)(4 2))となる． この両方をマージすると注目点の長方形候補のリスト((2 4)(3 4)(4 3)(42))ができる．

0000000001
図 -401
図 -5しかし，(2 4)は(3 4)に含まれるからこれは消す．(4 2)も同様．したがって((3 4)(4 3))ができる（-5）.

このようにして，右下まで辿り，途中長方形の面積の最大値（これは(x y)の x と y の値の積）を更新していく．Lisp（UtiLisp）で書いたプログラムは次の通り.

438

43巻4号 情報処理 2002年4月

関数 selec はリストb を貰い, リストの先頭の(x y)と後方の(x' y')で x≤ x' Λ y ≤ y'のものがあれば，先頭の要素を捨てる.

■ ナノピコ教室流
プログラミングコンテストに出題する審判団も気がつかなかったようだが，この問題は bit のナノピ
コ教室に出題されていた 5），6）．出題と解答は農工大（当時はもちろん東大の院生）の斎藤隆文君.
そこに辻さんという方の O(n2)のプログラムが示してあり，なかなかよくできていると思うので，（元は BASICだが）C に書き直して説明したい.
データが n × n の配列のとき，プログラムを簡単にするため，周囲を 0 で囲む．そのため，配列board は(n+2) × (n+2)に用意する. また作業用に長さ n+2の 1 次元配列a, b も使う.

IPSJ Magazine Vol.43 No.4 Apr. 2002439

図-4 のデータでやってみよう．配列 board は-6 のようになる．周囲の 0 は省いた．太線の壁はあとで説明する.

こうしておいて y を 1 から n，x を 0 から n まで繰り返す（したがって y = 0 の行は不要であった）．これ
で y = 5，x = 5 でプログラムの注目点まで来た時，配列 a，b はである.

440

43巻4号 情報処理 2002年4月-7 のようになっており，x1 = 6，xa = 5

配列 a，b の内容を調べてみよう．
a[i](0 ≤ i ≤ x + 1) には (i，y) から上で最も下の 0 の y 座標が入っている．ただし，a[0]は特別で最初から n+1にしてある.
また b[i](0 ≤ i ≤ x + 1)は a[i]から左に眺め，初めて a[i]を超える a[j] の j が入っている．つまり i の左で 1の柱がどんと低くなるのはどこかという情報である．調べてみると，b[5] = 2 なのは a[5] = 1 の左で初めてこの 1 を超える a は a[2] = 2 であり，b[4] = 3 は a[3] = 0 の左で初めてこの 0 を超える a は a[3] = 1 だという意味で，確かにそうなっている．これは x = 3，y = 2 にある 1 は横幅 3 の長方形の左の辺の候補になり得るし，x = 2，y = 3 にある 1 も横幅 4 の長方形の左辺の候補になり得るということである.
xa は y + 1 の行の，i ≤ x で最も右の 0 の x 座標である．y + 1 は今は最下行，どこも 0 なので，xa = x = 5.
プログラムは上述の関係が成立するようにできている．
さて，「長方形を見つけた」のところだが，a[xa] < a[x1]は x1 の左に 1 の長方形の壁が聳えているということである．図-6 でいうと縦壁 0 を見つけたのだ．a[xa]は x = xa の列の上の 0 の位置を示すから，横壁 2 も知れた．さらに b[xa]は xa の左で a の値が初めて a[xa]を超えた，つまり低い位置に 0 がある列の場所を示すから，縦壁 3 が分かる．これで長方形が 1 つ求まった．縦壁 3 の隣に横壁 4 があり，これは次の長方形の候補になり得る．そこでこの列を新たに xa とし，a[xa] < a[x1]を確認し，b[xa]から縦壁5 を知り，次の長方形が求まる．その次の xa は 1 だが，この列の横壁は 6 で，a[xa] = a[x1]で低過ぎるから，xa = b[xa]による bのリスト辿りはここで終了する．リストを辿るのにxa を使ってしまったので，while ループが済むと，xa を元に戻す．これは実によくできたプログラムである.

■ もっと簡単にできないか
とりあえず解答するにはダイナミックプログラミングもよいが，5 × 5 と大きさが決まっているなら別の解法はないかと考えるのは当たり前である．鶏を割くのに牛刀を用いるようなものだった．
1 と 0 が 5 × 5 に並んでいるなら，25 ビットの情報である．それなら 1 語に収まる．一方長方形のパターンはいくつあるか考えてみると，横方向は 5 の長さのもの 1 個，4 の長さのもの 2 個, ..., 1 の長さのもの 5 個だから，15 種類．縦方向も同じだから，225 個のパターンを用意し，入力した問題のパターンで，ちょうど長方形のパターンの部分がすべて 1 のものを，面積の広い方から探すというのはうまくいきそうである．パターンを表示すると-8のようになる.

図 -8
IPSJ Magazine Vol.43 No.4 Apr. 2002441

-9 は最上段が読み込んだデータ； 2 段目と 4 段目が用意したテストパターンである．まず読み込んだデータとテストパターンのビットごと論理積をとり，パターンの 1 でない部分を切り落とす．次にパターンとビットごと排他的論理和をとり，パターンの部分がすべて 1 であったか調べる．その部分に 0のものがあれば，この演算で 1 になり，最後の零のテストに引っ掛かるのである.

101011101101010
000001111100000 ∧000001101100000
000001111100000 ⊕000000010000000
図 -9
C のプログラムを示す．配列 p には 225 個のパターンが面積の順に入る．配列 q には対応する面積の値が入る．p のパターンは面積の順に入れなければならないが，ソートするまでもない．各面積の個数が分かっているので，その先頭番地を示す配列 r に従って挿入する．r は次のように考えて作る．最後の部分和が rに逆順に入る.

442

43巻4号 情報処理 2002年4月

p と q は実際には226 個分とってある．これはデータが全部 0 の時を別扱いにせず，最後で捕まえるためのいわゆる番兵みたいなものである.
始めの 2 つのプログラムとこのプログラムの最大な違いは，このプログラムでは，最初にかなりの準備をしておくかわりに，実行速度が早いことである．これはどういう問題にでもいえそうだが，データの組が多ければ，そのそれぞれの組が短時間で処理できるように，時間をかけてもあらかじめ準備をするのは能率的だということである．プログラミングコンテストでは，多くのデータの組を処理する場合があるので，こういう解法も合理的といえよう.
いまから 30 年近く前に，オランダから（学会誌 2002 年 2 月号に「計算科学の終焉？」を寄稿した）Dijkstra氏が来日した．その折，彼が力説した「プログラミングに必要な条件」は，1．母国語のマスター，
2．Sense of Humor，3．スタミナであった．Sense of Humorはむずかしいが，問題解決の発想を切り替える度量なのであろう．

1）筧 捷彦: ACM 国際大学対抗プログラミングコンテスト'98-'99 アジア地区予選東京大会顛末記（前編）, bit, Vol.31, No.6, pp.62-67（June 1999）.
2）石畑 清: ACM 国際大学対抗プログラミングコンテスト'98-'99 アジア地区予選東京大会顛末記（後編）, bit, Vol.31, No.7, pp.50-57（July 1999）.
3）阿久津達也: ゲノム情報科学における情報科学的諸問題, 情報処理, Vol.43, No.1, pp.3-15（Jan. 2002）.
4）Gosling, J.: A Redisplay Algorithm, Sigplan Notices, Vol.16, No.6, pp.123-129（June 1981）.
5）斎藤隆文: 最大面積の空き領域, ナノピコ教室, bit, Vol.15, No.4, p.50（Apr. 1983）.
6）斎藤隆文: 最大面積の空き領域, ナノピコ教室解答, bit, Vol.15, No.7, pp.94-97（July 1983）.
（平成14 年2 月21 日受付）

IPSJ Magazine Vol.43 No.4 Apr. 2002

443