Arantium Maestum

プログラミング、囲碁、読書の話題

蟻本

ナップサック問題

蟻本から: 重さと価値が, の物体n個から、重さの総和がWを超えない部分集合の最大の価値を求める。 解法としてはメモ化か: def solve(vs, ws, W): def max_v(i, max_w, memo = {}): if i >= len(vs): return 0 if (i, w) in memo: return memo[i, max_w] i…

Fence Repair問題

POJ/蟻本から 3253 -- Fence Repair 蟻本の解説がすごく面白かった。 板を切ることを二分木の枝分かれと考えて、最終的に切られた板一片にかかったコストは板の長さX二分木における深さ。 そう考えると、長さが短い板ほど深くするのが正しいことがわかる。の…

Best Cow Line問題

POJ/蟻本から: 3617 -- Best Cow Line ある文字列の左右どちらかの端から文字を1個ずつ取って、lexical orderが最小になる文字列を作成する、という問題。 最初は舐めていたのだが、bacbなどを正しく処理するためには先読みが必要になる。 しかしbbbbbacbbb…

区間スケジューリング問題

蟻本から。 n個の作業がある。 各作業は開始時と終了時が決まっており、同時に二つの作業をすることはできない。 作業をどう選べば、完了した作業数を最大化できるか。 かなり有名な貪欲法の問題。ポイントは、開始時や長さではなく、終了時を基準に選んでい…

迷路の最短路問題

蟻本から。 スタート、ゴール、壁、通路が'S', 'G', '#', '.'で表されている二次元配列の地図で、スタートからゴールまでの最短経路(必ず存在する)の長さを返す。 ざ・BFS。 import itertools as it def solve(map_): def neighbors(i,j): dirs = ((i+i1, …

Lake Counting

蟻本&POJから水たまりを数える問題: 2386 -- Lake Counting ナイーブに書くなら: import itertools as it def solve(map_): lakes = {(i, j):set((i,j)) for i, row in enumerate(map_) for j, v in enumerate(row) if v == 'W'} def neighbors(i, j): n =…

部分和問題

プログラミングコンテストチャレンジブック、通称蟻本を読み始めてみる。 とりあえずPythonで解いていって、C++の勉強が進んである程度綺麗に書ける気がしてきたらC++でもやってみたい。 まずは部分和問題。 整数の部分集合の和が整数kと等しくなるものがあ…