KLab主催 天下一プログラマー 第３回予選第３問
土曜日に参加した。３問目が時間内に解けなかったのが悔しかったので、とりあえずコードを仕上げた。使用言語はPython。psyco付きだと10秒かからない。
アルゴリズムは次の通り。タイルの敷き詰め問題っぽいので、正方形のあれはタイルって呼んでます。
- for k in 1...タイルの総数
- k個のタイルの選び方の組を全て出す
- 面積の総和が900を越える組は省く
- 組が残ってない場合、終了
- タイルの良し悪しにより、考慮しなくていい組を省く
- これが肝で、ほとんど減らせる
- 価格の総和が現在得られている最大値以下であるのも省く
- 残った組を、価格の総和が大きい順から以下の手順
- その組で敷き詰められるかを判定
-
- yes なら最大値を更新して次の k に
- no なら次の組へ
-
- その組で敷き詰められるかを判定
詳しくは以下のコードを見てください。
追記：判定関数に簡単な枝刈りを追加したら１秒くらいになった。
#! /usr/bin/env python # -*- coding: utf-8 -*- import psyco psyco.full() tiles = [ ('a', (9, 13), 69), ('b', (9, 24), 24), ('c', (15, 23), 59), ('d', (6, 26), 50), ('e', (7, 9), 80), ('f', (8, 16), 42), ('g', (7, 23), 33), ('h', (6, 17), 67), ('i', (6, 11), 42), ('j', (11, 13), 51), ('k', (14, 26), 31), ('l', (13, 26), 22), ('m', (7, 11), 60), ('n', (10, 24), 76), ('o', (7, 17), 54), ('p', (13, 14), 44), ('q', (13, 22), 61), ('r', (13, 20), 29), ('s', (11, 11), 62), ('t', (11, 22), 48), ] def print_d(a, n): d = [['_']*n for _ in xrange(n)] for i in a: fill_d(d, i[0], i[1], i[2], i[3], i[4]) print '-'*34 for r in d: print ''.join(r) print def fill_d(d, char, r0, c0, r1, c1): for r in xrange(r0, r1): for c in xrange(c0, c1): if d[r][c] != '_': d[r][c] = '*' else: d[r][c] = char def new_sealine(sealine, s, r, c, n): assert 0 <= s < len(sealine) r0, c0 = sealine[s] r1, c1 = r0+r, c0+c if not (r1<=n and c1<=n): return [] left = [] if r1<n: for i in xrange(s-1,-1,-1): R, C = sealine[i] if R==r1: left = sealine[:i+1] break elif R>r1: left = sealine[:i+1]+[(r1, sealine[i+1][1])] break else: left = [(r1, sealine[0][1])] right = [] if c1<n: for i in xrange(s+1,len(sealine)): R, C = sealine[i] if C==c1: right = sealine[i:] break elif C>c1: right = [(sealine[i-1][0], c1)]+sealine[i:] break else: right = [(sealine[-1][0], c1)] return left + right def find_fill(tiles, n): m = len(tiles) tbl = {} stack = [] #first = [] def dp(sealine, bit): if bit == (1<<m)-1: return True key = tuple(sealine+[bit]) if key in tbl: return False tbl[key] = 1 # # if first and bit&1==0 and first[0]&bit == first[0]: # return False # ある特定のタイルが貼れない need_area = 0 for i in xrange(m): if bit&(1<<i) == 0: (char, (r, c), v) = tiles[i] for r0, c0 in sealine: if ((r0+r<=n and c0+c<=n) or (r0+c<=n and c0+r<=n)): break else: return False need_area += r*c # 面積が足りない area = 0 for s in xrange(1,len(sealine)): area += (sealine[s][1]-sealine[s-1][1]) * (30-sealine[s-1][0]) area += (30-sealine[-1][1]) * (30-sealine[-1][0]) if area < need_area: return False for i in xrange(m): if bit&(1<<i) == 0: (char, (r, c), v) = tiles[i] for s in xrange(0,len(sealine)): for r, c in ((r, c), (c, r)) if bit else ((r, c),): next = new_sealine(sealine, s, r, c, n) if next: r0, c0 = sealine[s] stack.append((char, r0, c0, r0+r, c0+c)) # if not bit: # first.append((1<<m) - (1<<i)) if dp(next, bit | (1<<i)): return True # if not bit: # first.pop() stack.pop() return False r=dp([(0,0)], 0) return stack if r else None # 良いタイルと悪いタイルの比較 def tile_relation(tiles): def strict_better(a, b): return a[2] > b[2] and a[1][0] <= b[1][0] and a[1][1] <= b[1][1] m = len(tiles) better = [set() for _ in xrange(m)] weaker = [set() for _ in xrange(m)] for i in xrange(m): for j in xrange(m): if i!=j and strict_better(tiles[i], tiles[j]): better[j].add(i) weaker[i].add(j) # 推包を求める for _ in xrange(m): for i in xrange(m): s = better[i] for j in better[i]: s |= better[j] better[i] = s s = weaker[i] for j in weaker[i]: s |= weaker[j] weaker[i] = s return better, weaker # n から k 個選ぶ def pick_combination(tiles, k, better, weaker): n = len(tiles) def gen(i, t, must, must_not): if n-i+len(t) < k or k < len(t)+len(must-set(t)): return if must & must_not: return if len(t) == k: if not must - set(t): yield t return # i を含める if i not in must_not: for combi in gen(i+1, t+[i], must|better[i], must_not): yield combi # i を含めない if i not in must: for combi in gen(i+1, t, must, must_not|weaker[i]): yield combi return list(gen(0, [], set(), set())) def main(): n = 30 d = [['_']*n for _ in xrange(n)] better, weaker = tile_relation(tiles) max_alignment = [] max_value = 0 for k in xrange(1,len(tiles)): print 'Using', k, 'tiles' combis = [[tiles[i] for i in c] for c in pick_combination(tiles,k,better,weaker)] combis = [c for c in combis if sum(i[1][0]*i[1][1] for i in c) <= n*n] if not combis: print "Can't place", k, "tiles" break combis = [(sum(x[2] for x in t), t) for t in combis] combis.sort() combis.reverse() for value, combi in combis: if value <= max_value: break print 'try ...',value, combi a = find_fill(combi,n) if a: max_value = value max_alignment = a break print 'Current max value is', max_value print max_value print_d(max_alignment, n) if __name__=="__main__": main()
答え
485 aaaaaaaaaaaaahhhhhhhhhhhhhhhhh aaaaaaaaaaaaahhhhhhhhhhhhhhhhh aaaaaaaaaaaaahhhhhhhhhhhhhhhhh aaaaaaaaaaaaahhhhhhhhhhhhhhhhh aaaaaaaaaaaaahhhhhhhhhhhhhhhhh aaaaaaaaaaaaahhhhhhhhhhhhhhhhh aaaaaaaaaaaaa_____jjjjjjjjjjj_ aaaaaaaaaaaaa_____jjjjjjjjjjj_ aaaaaaaaaaaaa_____jjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ eeeeeeeee__ooooooojjjjjjjjjjj_ iiiiiiiiiiiooooooojjjjjjjjjjj_ iiiiiiiiiiiooooooojjjjjjjjjjj_ iiiiiiiiiiiooooooojjjjjjjjjjj_ iiiiiiiiiiiooooooosssssssssss_ iiiiiiiiiiiooooooosssssssssss_ iiiiiiiiiiiooooooosssssssssss_ mmmmmmmmmmmooooooosssssssssss_ mmmmmmmmmmmooooooosssssssssss_ mmmmmmmmmmmooooooosssssssssss_ mmmmmmmmmmmooooooosssssssssss_ mmmmmmmmmmm_______sssssssssss_ mmmmmmmmmmm_______sssssssssss_ mmmmmmmmmmm_______sssssssssss_ __________________sssssssssss_
Shibuya.lisp テクニカルトーク #3
http://shibuya.lisp-users.org/2009/06/13/sltt-3/
勢いで申し込んだ（聴く方ね）。最近は東京に行き過ぎな気がする。そして忙しいときに限って遊びたい。
ムカデ
今年もムカデの季節がやってきました。奴らはとっても凶悪。生命力が高く、見た目が気持ち悪く、咬まれるとめっさ痛い。奴らに比べたらゴキブリなんて友達になってもいいと思うほど凶悪。そんな奴らが部屋に忍び込むのがこの季節。PCいじってたらいきなり腕に這い上がってきたり、布団の中に入り込んだり、靴の中に入り込んだり、上から落ちてきたり。毎年最低一回は咬まれてる気がする。お子さん（１０cm以下）ならまだしも親御さん（１５cm以上）に咬まれたら死んじゃいそう。
というわけで以下注意してること。
- 部屋に帰ったら、まず息を潜めて耳を澄ませる
- 奴らの弱点は移動時に音を立てること
- 定期的に回りを見回す
- 洗濯物や本など物を持ち上げるときは覚悟を持って行う
- 寝る前に布団の中をチェック
- 靴を履く前にチェック
- 殺虫剤の常備
- 強力な奴を。今置いてるやつは「名前の分からない虫にも効く」と書いてある。
みなさんも気をつけましょう。
Ubuntu 9.04
8.10から9.04にアップグレードしました。8.04から8.10に上げた時、perl5.8がもってかれて酷い目にあったので、今回はバックアップをしてやった。結局今回は大丈夫だったんだけど。
ぱっと見あまり変わってない感じ。起動が若干速くなったかな。英字フォントが細くなった気がする。ちょっと違和感あるから戻したい。デュアルディスプレイの設定が簡単になってるのはうれしいな。
Circle of Numbers
試しに作ってみた問題その１。
問題
0からn-1のn個の数字を時計回りで輪に並べます。最初0から出発して右回りにk番目の数字を輪から外します。外した数字の次にある数字からまたk番目の数字を輪からはずします。これを繰り替えしていったとき最後に残る数字はなんでしょうか、という問題です。
例えば n=6, k=3 の場合を見ると、
0
5 1
4 2
3
0, 1, 2: 2を輪から外す
0
5 1
4 x
3
3, 4, 5: 5を輪から外す
0
x 1
4 x
3
0, 1, 3: 3を輪から外す
0
x 1
4 x
x
4, 0, 1: 1を輪から外す
0
x x
4 x
x
4, 0, 4: 4を輪から外す
0
x x
x x
xこの場合最後に残る数字は0となります。他に例を挙げると、
n = 30, k = 6 の場合 3 n = 64, k = 11 の場合 48 n = 64, k = 128 の場合 57
になります。では、以下に与えられるn、kの場合、最後に残る数字は何になるでしょうか。
n = 10^2, k = 9 n = 10^4, k = 123 n = 10^6, k = 1024 n = 10^8, k = 512 n = 10^10, k = 255
