こんにちは、天下一プログラマーコンテスト実行委員の inada-n です。 第三回Web予選に参加してくださった方、ありがとうございました&お疲れ様でした。 予選通過者には近日中に連絡が行くはずなので、もうしばらくお待ち下さい。 さて、天下一プログラマーコンテストでは、言語の性能が戦力の決定的な差にならないように、 時間がかかりそうな問題でもC++やJavaを使わずに解いてみて難易度の調整をしています。 ですが、今回の予選の第三問では私の調整ミスで、深さ優先探索+簡単な枝刈りを 使った場合、 C++では数秒〜数分で答えが出るのに PHP/Ruby/Python では数時間 かかってしまう事があり、言語によるハンディキャップが大きくなってしまいました。 投稿されたプログラムに関しては、回答が最善解でないもの、プログラムのみの 回答になっているものを含めて全て目を通しているのですが、もしきちんとプログラムが 出来ていたのに計算が終わる前に時間切れになって投稿できなかった方がおられたら 申し訳ありません。 お詫び(?)に今回の第三問問題文と、私の作った回答プログラムを紹介します。 利用した 言語はPythonで普通に実行した場合20分以下、PsycoというJITコンパイラを利用した場合 5分以下で最適解が見つかります。 問題文
30m × 30m のフロアがあります。 このフロアに、後述する売り場を敷き詰めてください。 ただし、以下の条件を満たしてください。 1) 各売り場区画は矩形をしています。配置するときには 指定されたサイズを90度回転させてもかまいません。 斜めには配置しないでください。 2) 各売り場には売上高が決められています。売り場すべては 敷き詰めることが出来ないので、売上高が一番高くなる ように敷き詰める売り場を選んでください。ひとつの売り場を 2回以上配置することは出来ません。 敷き詰め方と売り上げを回答してください。 敷き詰め方は下の例と同じフォーマットで回答してください。 (追記) 完全な最適解が見つからない場合、計算出来る範囲で準最適解を 求めて回答してください。 売り場一覧:: 名前,大きさ ,売上高 a, 9x13, 69 b, 9x24, 24 c, 23x15, 59 d, 6x26, 50 e, 7x9, 80 f, 16x8, 42 g, 7x23, 33 h, 6x17, 67 i, 11x6, 42 j, 13x11, 51 k, 26x14, 31 l, 13x26, 22 m, 11x7, 60 n, 24x10, 76 o, 7x17, 54 p, 13x14, 44 q, 13x22, 61 r, 13x20, 29 s, 11x11, 62 t, 22x11, 48 敷き詰め例:: 次のように敷き詰めた場合、選んだ売り場は a, b, f, h, j, m なので、売り上げは 69+24+42+67+51+60 = 342 になります。 _: 空きスペース a-t: 売り場 aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb aaaaaaaaa_jjjjjjjjjjjbbbbbbbbb hhhhhh_______________bbbbbbbbb hhhhhh_______ffffffffbbbbbbbbb hhhhhh_______ffffffffbbbbbbbbb hhhhhh_______ffffffffbbbbbbbbb hhhhhh_______ffffffffbbbbbbbbb hhhhhh_______ffffffffbbbbbbbbb hhhhhhmmmmmmmffffffffbbbbbbbbb hhhhhhmmmmmmmffffffffbbbbbbbbb hhhhhhmmmmmmmffffffffbbbbbbbbb hhhhhhmmmmmmmffffffffbbbbbbbbb hhhhhhmmmmmmmffffffffbbbbbbbbb hhhhhhmmmmmmmffffffff_________ hhhhhhmmmmmmmffffffff_________ hhhhhhmmmmmmmffffffff_________ hhhhhhmmmmmmmffffffff_________ hhhhhhmmmmmmmffffffff_________ hhhhhhmmmmmmmffffffff_________
解答プログラム
import csv
import itertools
from collections import defaultdict

try:
    import psyco
    psyco.full()
except:
    pass

_FIELD_SIZE = 30
_INITIAL_FIELD = bytearray("_") * _FIELD_SIZE **2
_MINIMUM_LENGTH = 0

class Field(object):
    __slots__ = "_field _space _deadspace _minimum_line".split()

    def __init__(self, f=_INITIAL_FIELD, space=_FIELD_SIZE**2, deadspace=0, minimum_y=0):
        self._field = f
        self._space = space
        self._deadspace = deadspace
        self._minimum_line = minimum_y

    def put(self, pos, size, chr):
        """try put size to pos.

        Return new Field if can."""
        x,y = pos
        w,h = size
        F = _FIELD_SIZE
        if x + w > F or y + h > F:
            return None

        field = self._field
        t = b'_' * w
        for offs in xrange(F * y + x, F * (y+h), F):
            if field[offs:offs+w] != t:
                return None

        new_field = bytearray(field)
        t = chr * w
        for offs in xrange(F * y + x, F * (y+h), F):
             new_field[offs:offs+w] = t

        ret = Field(new_field, self._space - w*h, self._deadspace, self._minimum_line)
        ret._fill_dead_space()
        ret.calc_minimum_line()
        return ret

    def _fill_dead_space(self):
        F = _FIELD_SIZE
        M = _MINIMUM_LENGTH
        field = self._field
        _s = ord('_')
        _d = ord('#')

        for yoff in xrange(self._minimum_line * F, F*F, F):
            end = yoff + F
            pos = field.find('_', yoff, end)

            while 0 <= pos < end:
                pp = pos+1
                while pp < end and field[pp] == _s:
                    pp += 1
                count = pp - pos
                if count < M:
                    field[pos:pp] = '#' * count
                    self._space -= count
                    self._deadspace += count
                pos = field.find('_', pp, end)

        for x in xrange(F):
            vline = field[x:F*F:F]
            pos = vline.find('_')
            while 0 <= pos < F:
                pp = pos+1
                while pp < F and vline[pp] == _s:
                    pp += 1
                count = pp - pos
                if count < M:
                    field[x + F*pos : x + F*pp : F] = '#' * count
                    self._space -= count
                    self._deadspace += count
                pos = vline.find('_', pp)

    def calc_minimum_line(self):
        pos = self._field.find('_')
        if pos < 0:
            self._minimum_line = _FIELD_SIZE
        else:
            self._minimum_line = pos // _FIELD_SIZE

    def __str__(self):
        return '\n'.join(str(self._field[i:i+_FIELD_SIZE]) for i in xrange(0, _FIELD_SIZE**2, _FIELD_SIZE))

def read_stores():
    reader = csv.reader(open('depart_data.csv'))
    d = {}
    for row in reader:
        c, s, m = [x.strip() for x in row]
        w,h = map(int, s.split('x'))
        m = int(m)
        d[c] = (w, h, m)
    return d

def _solve(field, stores, remains, current, max_dead, dump=0, top=False):
    if dump > 0:
        print dump, remains, current

    b = remains[0]
    w, h, m = stores[b]
    min_wh = min(w,h)

    if dump > 0:
        print dump, "next store:", b, w, h

    next = current+m
    next_remains = remains[1:]

    pos = field._field.find('_')
    while 0 <= pos:
        x, y = pos % _FIELD_SIZE, pos // _FIELD_SIZE
        if top:
            if x > (_FIELD_SIZE - w) / 2:
                x = 0
                y += 1
                pos = y * _FIELD_SIZE
            if y > (_FIELD_SIZE - h) / 2:
                break
        if dump > 1:
            print dump, "x,y = ", x, y
        nf = field.put((x,y), (w,h), b)
        if nf is not None and nf._deadspace <= max_dead:
            if next_remains:
                res = _solve(nf, stores, next_remains, next, max_dead, dump-1)
                if res:
                    return res
            else:
                return nf
        if nf and x == 0 and field._deadspace + h > max_dead:
            pos += _MINIMUM_LENGTH
        else:
            pos += 1
        pos = field._field.find('_', pos)

    pos = field._field.find('_')
    while 0 <= pos:
        x, y = pos % _FIELD_SIZE, pos // _FIELD_SIZE
        if top:
            if x > (_FIELD_SIZE - h) / 2:
                x = 0
                y += 1
                pos = y * _FIELD_SIZE
            if y > (_FIELD_SIZE - w) / 2:
                break
        if dump > 1:
            print dump, "x,y = ", x, y
        nf = field.put((x,y), (h,w), b)
        if nf is not None and nf._deadspace <= max_dead:
            if next_remains:
                res = _solve(nf, stores, next_remains, next, max_dead, dump-1)
                if res:
                    return res
            else:
                return nf
        if x == 0 and field._deadspace + w > max_dead:
            pos += _MINIMUM_LENGTH
        else:
            pos += 1
        pos = field._field.find('_', pos)
    return False

def solve(stores, remains, area):
    remains = sorted(remains, key = lambda x: stores[x][0] * stores[x][1], reverse=True)
    field = Field()

    max_dead = _FIELD_SIZE**2 - area
    print "max_dead", max_dead

    global _MINIMUM_LENGTH
    _MINIMUM_LENGTH = min(min(stores[s][0], stores[s][1]) for s in remains)
    print "_MINIMUM_LENGTH", _MINIMUM_LENGTH

    return _solve(field, stores, remains, 0, max_dead, dump=2, top=True)

def _pre_research(stores):
    store_keys = stores.keys()
    num_store = len(store_keys)
    combis = defaultdict(list)
    while num_store > 0:
        for combi in itertools.combinations(store_keys, num_store):
            earn = 0
            area = 0
            for s in combi:
                st = stores[s]
                area += st[0]*st[1]
                earn += st[2]
            if area > _FIELD_SIZE**2: continue
            if earn < 450: continue
            combis[earn].append((combi, area))
        num_store -= 1

    print "earning, combination, area"
    for k in sorted(combis.keys(), reverse=True)[:5]:
        for v in combis[k]:
            print k,v
    return combis

if __name__ == '__main__':
    stores = read_stores()
    combis = _pre_research(stores)
    for earn in sorted(combis.keys(), reverse=True):
        print "target:", earn
        for comb, area in combis[earn]:
            field = solve(stores, comb, area)
            if field:
                print earn
                print str(field).replace('#', '_')
                break
        else:
            continue
        break
解説
基本的には、売り場を場所を少しずつずらしながら配置していく深さ優先探索になっています。 今回の問題は、どの売り場を利用するかという組み合わせによってフロアの総売上と 売り場の総面積が決まります。なので、先に売り場の組み合わせを列挙し、総面積がフロア面積以下な 組み合わせのうち総売上の高い組み合わせから優先して利用していきます。こうすることで、深さ優先 探索でも最初に見つかった解=最善解にすることができます。 そのほかには、 * 売り場のうち一番小さい幅を見つけ、その幅よりも小さい空間をデッドスペースとしてカウントし、 デッドスペース + 売り場の総面積 > フロアの面積 になった場合に枝刈りする。 * 最初の売り場の配置場所を左上に限定することで、対称な配置を探索しないようにする。 * 売り場を大きい順にソートして利用することで、探索範囲が早く収束するようにしている。 * Pythonで二次元配列でテーブルを作ってループで走査すると遅いので、bytearrayの一次元配列を 使ったりスライスを駆使したりして高速化 といった工夫をしています。 このほかにも枝刈り方法をいくつか考えていたのですが、実装する時間が足りませんでした。 後で考えてみると、Pythonならではの最適化をする前にこっちを実装するべきでした。 私もまだまだですね。
それでは、本戦で皆様にお会いできるのを楽しみにお待ちしております。