こんにちは、天下一プログラマーコンテスト実行委員の 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ならではの最適化をする前にこっちを実装するべきでした。
私もまだまだですね。
それでは、本戦で皆様にお会いできるのを楽しみにお待ちしております。