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

KLab株式会社の若手エンジニアによる技術ブログです。phpやRubyなどの汎用LLやJavaScript/actionScript等のクライアントサイドの内容、MySQL等のデータベース、その他フレームワークまで幅広く面白い情報を発信します。

2009年07月

Web予選第3回概況 - 第3問解説 -

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

天下一プログラマ2009 Web予選概況

こんばんは amo-k です。 Web予選第3回が無事完了しましたが、 御陰さまで天下一プログラマは大盛況となっております! 予想を大幅に上回る投稿数で嬉しい限りなのですが、採点サイドはテンテコ舞いとなっております 汗。 未だWeb予選第2回の解説を公開していないのですが、 実行委員inada-nが、第3回の3問目の解説をまとめたそうですので取り急ぎ実況してもらう事にします。 (順序がとか言わないでね! 追ってその他の問題やWeb予選第2回目の解説も公開しますのでお楽しみに〜 では、inada-n よろしくです!

天下一プログラマ2009 Web予選2回目終わりました!

Web予選第3回の曜日が間違えていましたので更新しました。7月25日土曜日です。
suztomoさんありがとう!(Fri Jul 24 15:25:54 JST 2009)
こんにちはamo-kです! 天下一プログラマWeb予選2回目が無事完了しました! なんと2回目も大反響で、46組が合計129の解答を投稿してくれました〜 ※ 1回目は54組が173解答を投稿 またまた採点が大変だーーー  1回目の不手際を反省/学習しつつ2回目の開催に挑みましたが、、、改善の余地がまだまだいっぱいありますね 汗 しかし! 前回/今回の経験を活かすと共に、参加してくれた学生達やブログ/twitterなどの声を参考に、より魅力的なコンテストとしていきますのでよろしくです!! Web予選第3回を7月25日(土)に開催するので応募してね! (天下一プログラマ2009の予選としてはラストチャンスだよ!! また、概況は追って公開しますのでお楽しみにw

天下一プログラマ2009 Web予選第1回概況

問題と解答が無い状態で更新しておりましたので追記しました。(Thu Jul 9 11:39:17 JST 2009) どうも、天下一プログラマーコンテスト実行委員会の isono です。 告知よりも、少し遅れましたが天下一プログラマーコンテスト Web 予選 第1回の概況をお伝えします。予想をはるかに上回る回答数につき集計システムを改修しながらお送りしています。 まずは問題の開示と機械集計の結果から。
第1問 問題:2001年1月1日から3000年12月31日までの間に日曜日は何回あるか。 うるう年については以下のルールに留意せよ。 1. 西暦年が4で割り切れる年はうるう年 2.ただし、西暦年が100で割り切れる年は平年 3. ただし、西暦年が400で割り切れる年はうるう年 なお、2001年1月1日は月曜日である。 ※日付・時刻用ライブラリの使用は減点対象とする。 答え:52177 のべ回答数:55 最速回答:2009/7/5 1:37 最終回答:2009/7/5 23:54 第2問 問題:次の10文字からなる数字列において、連続する4桁の数字を "8710", "7104", ... のように7個取り出すことができる。 8710410111 では、次の数字列から連続する4桁の数字を取り出したとき、3の倍数はいくつあるか。 87104101110321051103211610410132991111171141151013211110232104117109971103210111810111011611544321051163298101991111091011153211010199101115115971141213210211111432111110101321121011111121081013211611132100105115115111108118101321161041013211211110810511610599971083298971101001153211910410599104321049711810132991111101101019911610110032116104101109321191051161043297110111116104101114443297110100321161113297115115117109101329710911111010332116104101321121111191011141153211110232116104101321019711411610444321161041013211510111297114971161013297110100321011131179710832115116971161051111103211611132119104105991043211610410132108971191153278971161171141013297110100327897116117114101115327111110032101110116105116108101321161041011094432973210010199101110116321141011151121019911632116111321161041013211111210511010511111011532111102321099711010710511010032114101113117105114101115321161049711632116104101121321151041111171081003210010199108971141013211610410132999711711510111532119104105991043210510911210110832116104101109321161113211610410132115101112971149711610511111046 答え:402 のべ回答数:84 最速回答:2009/7/5 0:47 最終回答:2009/7/5 23:54 ※問題の表示に意図しない改行が含まれており不正解になった方は解釈の違いを加味いたします 第3問 問題:日本には、 1円、5円、10円、50円、100円、500円、1000円、2000円、5000円、10000円 の硬貨および紙幣がある。 これらをつかって10円をつくる方法は、 1. 10円 × 1 2. 5円 × 2 3. 5円 × 1 + 1円 × 5 4. 1円 × 10 の4通りある。 では、10000円をつくる方法は何通りあるか。 答え:24597373439 のべ回答数:54 最速回答:2009/7/5 1:59 最終回答:2009/7/6 0:20(終了時間を1時間延長しました)
※のべ回答数なので複数回答いただいている分も含んでいます ※回答時間は審査基準ではありませんので参考までに 第2問の回答数が最も多く、第1問と第3問が僅差という興味深い結果となっています。両方ループで解決してしまいそうな問題だからでしょうか? 3問とも回答いただいて、3問とも正解をにたどり着いている方が想定数を大幅に上回っています。コードの査読の結果は未だ全容は出ていませんので、ここでは詳しい結果には触れていませんが、内容を加味して工夫されている方に加点して差をつけるしかありません。 現在審査員が全力で審査を行っています。缶詰審査中に上がったつぶやきの中からいくつか抜粋しておきますので雰囲気だけでも。
・正解者は全員通してあげたい… ・レベル高すぎですね…採点するのがおこがましいです ・C/C++の人はやっぱり実行効率を極限まで考える傾向があるなぁ・・・ ・考え方は良いのにミスで回答が不正解の人、通したいけど全問正解チーム多いからどうしよう… ・入力がメモリに乗り切らない場合とかまで考えてる人がいるよ ・狭いところで勉強しているから足を引っ張ってる人とかもったいないなぁ… ・Perl が居ないがーん! 昔は Perl で cgi だった領域はPHPに、ゲーム作るならC/C++だし… (選択言語の集計もあとでやってみます)
第1回の結果はレベルも競争率も想定以上になってしまっています。正解と工夫した点のアピールの掛け算が攻略ポイントとなるでしょう。あえてLLを選択して工夫を最大限アピールしてみる作戦もありかもしれません。 全体として問題は決して簡単すぎることは無いと思うのですが、2回目以降の問題レベルはもう少し引き上げるかもしれません。 第2回は来週 7/15 に開催します。第1回目に参加された方も、されなかった方もふるってご参加ください。新規エントリーは 7/14 18:00 まで受け付けます。 なお、既にエントリー済みの方(第1回目参加者を含む)は改めてエントリーしなくてもそのまま2回目以降参加いただけます。 Web予選は24時間ですが本戦では限られた時間で競っていただきますので結果がどのように変化するのかも注目です。 最後にお詫びとお礼を。 Web予選第1回ではメールの不達などご迷惑をおかけしました。開催時間が1時間程遅れた方考慮して終了時間を1時間延長しました。(延長に関しては特に大きな影響は無かったようですが…) 参加者の熱き闘志に応える為、我々は努力を惜しみません。 今後とも稚拙な部分はあるかと思いますがご了承ください。 本大会はイベント開催になれた人材ではなく運営も採点もKLab技術者が手探りお送りしております。(この方法がプログラマーの気持ちを一番理解できる最善の方法であると信じています) 本戦で皆様にお会いできる事を楽しみにしております。

天下一プログラマ2009 予選1回目終わりましたー

こんばんはamo-kです! この度、天下一プログラマ第一回予選に参加してくれた学生達、 ありがとーーーーー! 一回目ということでドキドキだったんだけど なんと54組が合計173の解答を投稿したという大反響でした〜 採点が大変だっ 汗(嬉しい悲鳴w 以降の動きは随時ここから発信していきますー 運営不手際のお詫び
運営側の不手際で一部の人に告知メールが届いていなかったようです。 予選開始後、しばらくの間(約45分)ログイン情報を提示しきれていませんでした。 告知メールを受信できていなかった人達ゴメンなさい!
 KLab若手エンジニアブログのフッター