KLab若手エンジニアの これなぁに？

こんにちは、天下一プログラマーコンテスト実行委員の inada-n です。

第三回Web予選に参加してくださった方、ありがとうございました＆お疲れ様でした。
予選通過者には近日中に連絡が行くはずなので、もうしばらくお待ち下さい。

さて、天下一プログラマーコンテストでは、言語の性能が戦力の決定的な差にならないように、
時間がかかりそうな問題でもC++やJavaを使わずに解いてみて難易度の調整をしています。

ですが、今回の予選の第三問では私の調整ミスで、深さ優先探索+簡単な枝刈りを
使った場合、 C++では数秒〜数分で答えが出るのに PHP/Ruby/Python では数時間
かかってしまう事があり、言語によるハンディキャップが大きくなってしまいました。

投稿されたプログラムに関しては、回答が最善解でないもの、プログラムのみの
回答になっているものを含めて全て目を通しているのですが、もしきちんとプログラムが
出来ていたのに計算が終わる前に時間切れになって投稿できなかった方がおられたら
申し訳ありません。

お詫び(?)に今回の第三問問題文と、私の作った回答プログラムを紹介します。 利用した
言語はPythonで普通に実行した場合20分以下、PsycoというJITコンパイラを利用した場合
5分以下で最適解が見つかります。

問題文

解答プログラム

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

解説

それでは、本戦で皆様にお会いできるのを楽しみにお待ちしております。

こんばんは amo-k です。

Web予選第３回が無事完了しましたが、
御陰さまで天下一プログラマは大盛況となっております！

予想を大幅に上回る投稿数で嬉しい限りなのですが、採点サイドはテンテコ舞いとなっております 汗。

未だWeb予選第２回の解説を公開していないのですが、
実行委員inada-nが、第３回の３問目の解説をまとめたそうですので取り急ぎ実況してもらう事にします。

（順序がとか言わないでね！

追ってその他の問題やWeb予選第２回目の解説も公開しますのでお楽しみに〜

では、inada-n よろしくです！

Web予選第３回の曜日が間違えていましたので更新しました。７月２５日土曜日です。
suztomoさんありがとう！（Fri Jul 24 15:25:54 JST 2009）

こんにちはamo-kです！

天下一プログラマWeb予選２回目が無事完了しました！

なんと２回目も大反響で、４６組が合計１２９の解答を投稿してくれました〜
※ １回目は５４組が１７３解答を投稿
またまた採点が大変だーーー　

１回目の不手際を反省／学習しつつ２回目の開催に挑みましたが、、、改善の余地がまだまだいっぱいありますね　汗
しかし！　前回／今回の経験を活かすと共に、参加してくれた学生達やブログ／twitterなどの声を参考に、より魅力的なコンテストとしていきますのでよろしくです！！

Web予選第３回を７月２５日（土）に開催するので応募してね！
（天下一プログラマ２００９の予選としてはラストチャンスだよ！！

また、概況は追って公開しますのでお楽しみにｗ

問題と解答が無い状態で更新しておりましたので追記しました。（Thu Jul 9 11:39:17 JST 2009）

どうも、天下一プログラマーコンテスト実行委員会の isono です。
告知よりも、少し遅れましたが天下一プログラマーコンテスト Web 予選 第１回の概況をお伝えします。予想をはるかに上回る回答数につき集計システムを改修しながらお送りしています。

まずは問題の開示と機械集計の結果から。

※のべ回答数なので複数回答いただいている分も含んでいます
※回答時間は審査基準ではありませんので参考までに

第２問の回答数が最も多く、第１問と第３問が僅差という興味深い結果となっています。両方ループで解決してしまいそうな問題だからでしょうか？

３問とも回答いただいて、３問とも正解をにたどり着いている方が想定数を大幅に上回っています。コードの査読の結果は未だ全容は出ていませんので、ここでは詳しい結果には触れていませんが、内容を加味して工夫されている方に加点して差をつけるしかありません。

現在審査員が全力で審査を行っています。缶詰審査中に上がったつぶやきの中からいくつか抜粋しておきますので雰囲気だけでも。

第１回の結果はレベルも競争率も想定以上になってしまっています。正解と工夫した点のアピールの掛け算が攻略ポイントとなるでしょう。あえてLLを選択して工夫を最大限アピールしてみる作戦もありかもしれません。

全体として問題は決して簡単すぎることは無いと思うのですが、2回目以降の問題レベルはもう少し引き上げるかもしれません。

第2回は来週 7/15 に開催します。第１回目に参加された方も、されなかった方もふるってご参加ください。新規エントリーは 7/14 18:00 まで受け付けます。

なお、既にエントリー済みの方（第１回目参加者を含む）は改めてエントリーしなくてもそのまま２回目以降参加いただけます。

Web予選は24時間ですが本戦では限られた時間で競っていただきますので結果がどのように変化するのかも注目です。

最後にお詫びとお礼を。
Web予選第１回ではメールの不達などご迷惑をおかけしました。開催時間が１時間程遅れた方考慮して終了時間を１時間延長しました。（延長に関しては特に大きな影響は無かったようですが…）
参加者の熱き闘志に応える為、我々は努力を惜しみません。
今後とも稚拙な部分はあるかと思いますがご了承ください。
本大会はイベント開催になれた人材ではなく運営も採点もKLab技術者が手探りお送りしております。（この方法がプログラマーの気持ちを一番理解できる最善の方法であると信じています）

本戦で皆様にお会いできる事を楽しみにしております。

こんばんはamo-kです！

この度、天下一プログラマ第一回予選に参加してくれた学生達、
ありがとーーーーー！

一回目ということでﾄﾞｷﾄﾞｷだったんだけど
なんと５４組が合計１７３の解答を投稿したという大反響でした〜
採点が大変だっ　汗（嬉しい悲鳴ｗ
以降の動きは随時ここから発信していきますー

運営不手際のお詫び

こんにちは、amo-kです。

天下一プログラマ応募Webページを更新しました。
若干解りづらい部分や説明が不足していた部分等を補足した内容になっております。
詳しくはWebを参照してほしいのですが、更新概要は以下の通りです。

学生諸君！　まだまだ応募できるので是非応募してね！！
コード書こうぜ！！