プログラミングコンテスト

一週間くらい前にプログラミングコンテストがあったらしい. ツィッター のキーワードHHKBを見たら, コンテストの話題が沢山あった.

私はプログラムを急いで書くコンテストは嫌いだ. プログラムはゆっくり と考えながら書くものとDijkstraは主張する. 私もまったく同感で, ずい ぶん前に大学対抗プログラミングコンテスト(ICPC)のオフィシャルを2年 ほど引き受けたが, プログラムをあわてて書き, テストの入力データに対 して正しい数値だけ得られれば完成で, 完成までの時間の短いのを上位 とする風潮に賛成できず, オフィシャルを辞退した.

しかし世の中ではどんな問題でコンテストをやっているかとつい問題を覗いたのが 運の尽き. 解いてみたくなり, プログラムに取り憑かれた.

やったのはsquareで, 二次元空間の整数値の格子点に角を持ち, x, y軸に 平行な辺を持つ正方形の入れ子問題である. すなわち, 一辺の長さnの正方形N の内部に, 一辺の長さがそれぞれaとbの正方形AとBを重さならないように置く 置き方が何通りあるかを計算する.

取り敢えず例題にあった n=4, a=2, b=2で考える. aもbも2でややこしい が, まぁよかろう.

n×nの正方形Nの中に, 2×2の正方形Bの置き方は, 下の図のよう に3×3で9通りある. Bの左の線はNの左端から, Nの右端からBの幅bを 引いたところまで置けて, 両端を含めるから n-b+1個. 今の数値では 4-2+1=3で, これが横方向も縦方向もあるので9通りになる.


縦, 横をそれぞれl₀, l₁とする長方形内のBの置き方は,
bs(l₀,l₁)=(l₀-b+1)×(l₁-b+1)
だから, 全体に置くのはbs(n,n), 今はbs(4,4)=9である. 今後この値をtで表す.

2×2の正方形Aの置き方も, 下の図の実線の枠が示すようにで9通りである. その各の位置で, Bの一部でも隠す勢力範囲は, 灰色の部分で, この勢力範囲内の Bの数をt, つまり9から引くと, そのAの場合の数が得られる. これをすべての Aの場所で計算すれば答が得られる.


ところで, 横方向だけ考えて, 勢力範囲の左右の幅は, Aの左端の, Nの左端からの距離をxとすると, 次の下左図の太い縦線のようになる. この下限をy₀, 上限をy₁とすると, 赤線の範囲になる. 右は一般の場合の図だ.


この図から分るように

y0(x) = max (x-b+1, 0),
y1(x) = min (x+a-(b+1), n)

だから, Aの左下の座標を(x₀, x₁)とすれば, 勢力範囲は 横がy₁(x₀)-y₀(x₀), 縦がy₁(x₁)-y₀(x₁)で, この中に入るBの数をtから引くことになる. つまり t-s(y₁(x₀)-y₀(x₀),y₁(x₁)-y₀(x₁)).

私は通常, Lispの一方言のSchemeでプログラムを書くので

(define (square n a b)
 (define (y0 x) (max (- x (- b 1)) 0))
 (define (y1 x) (min (+ x a (- b 1)) n))
 (define (bs l0 l1) (* (- l0 b -1) (- l1 b -1)))
 (let ((t (bs n n)))
  (do ((x0 0 (+ x0 1)) (sum 0)) ((> x0 (- n a)) sum)
   (do ((x1 0 (+ x1 1))) ((> x1 (- n a)))
    (set! sum (+ sum
     (- t (bs (- (y1 x0) (y0 x0)) (- (y1 x1) (y0 x1)))
))))))

実行すると

(square 4 2 2) => 32
(square 3 1 2) => 20

となる. Schemeが苦手な人のためにPythonのプログラムを示すと

def square (n, a, b):
    def y0 (x):
        return max(x-(b-1),0)
    def y1 (x):
        return min(x+a+(b-1),n)
    def bs (l0,l1):
        return (l0-b+1)*(l1-b+1)
    t=bs(n,n)
    sum=0
    for x0 in range(0,n-a+1):
        for x1 in range(0,n-a+1):
            sum = sum + \
                  t - bs (y1(x0)-y0(x0), y1(x1)-y0(x1))
    return sum
print (square(3,1,2))
print (square(3,2,1))
print (square(4,2,2))

実行すると

20
20
32

プログラムは一旦うまく動くようになると, 改良の糸口が見えだすものだ. 仮に勢力範囲の図で, 灰色の部分の面積を足すとすると, 灰色の横の長さを足し合わせ, 縦の長さも足し合わせて, 和どうしを掛ければよいようだ. いちいちtから引く代わりに, Aの置き方の数にtを掛けたものから, 勢力範囲の 総面積を引けばよい.

勢力範囲の幅は, 図のy₀, y₁の間の縦の太線を足せばよい. 両端は 少し短いが, 破線の部分も入れてしまえば, 標準の縦の長さ a+2b-2に太線の本数 n-a+1を 掛ければよい. 破線の部分は0からb-1までの和で, 左下と右上の2箇所にあるから, (b-1)b である.

そうそう, 勢力範囲lに入るBの数がl-b+1だったように, 太線の長さからもb+1を 引く必要がある. (プログラムの(* s (- b 1)) のところ.)

下のプログラムで, tは前述の通り, sは太線の数, pが太線の総延長である.

(define (square n a b)
  (let* ((t (* (- n b -1) (- n b -1)))
         (s (- n a -1))
	 (p (- (* (+ a b b -2) s) (* b (- b 1)) (* s (- b 1)))))
    (modulo (- (* t s s) (* p p)) 1000000007)))

(square 331895368 154715807 13941326) => 409369707

Python版は

def square(n, a, b):
    t = (n-b+1) ** 2
    s = n - a + 1
    p = (a+2*b-2)*s - b*(b-1) - s*(b-1)
    return (t*s*s - p*p) % 1000000007

print (square(331895368,154715807,13941326))

実行結果は

409369707

まずまず楽しんだ.