ライブラリとか道具とか

コンテストのときに使ったりしているライブラリやらスクリプトの一部をgithubに置くことにした。
ライブラリはドキュメントの扱いを決めかねているのでしばらく放置。スクリプトまわりは、今使っているビジュアライザをもうちょっと改良してから上げる予定。それから、テストも自動化したいので頑張って今年度中にはとりあえず動くレベルのものを上げたい。

AOJ-0558 : Cheese

問題概要

W*H(W,H<1000)のボードがあり、どこかに1~Nの書かれたマスがある。1~Nまで順番に通る最短路を求める問題。解は必ず存在する。

解法

幅優先探索をN回やるので十分。もう少し賢いやり方があるかもしれない。

POJ-3181 : Dollar Dayz

問題概要

[1..K](K<100)円の硬貨が十分たくさんある。このときN(<1000)円の支払い方は何通りあるか求める問題。

解法

個数制限なしナップサックと同様にやればよい。最大ケースでは64bitでも足りないので多倍長が必要。

POJ-3176 : Cow Bowling

問題概要

パスカルの三角形風に数字が並んでいる。上から斜め下のどれかに移動できる。途中で拾った数の和を最大化する問題。

解法

典型的な動的計画法。色んな所で類題が出題されている。

POJ-2718 : Smallest Difference

問題概要

[0..9]の部分集合が与えられる。二つの集合に分けて適当に順序を変えて10進数の数字を作り差を最小化する問題。

解法

数が少ないので全探索が間に合う。桁数決め打ちで分けてnext_permutationくらいでも余裕。

POJ-3187 : Backward Digit Sums

問題概要

[1..N](N<=10)個の数字を一列に並べる。隣り合う数字の和からなる新しい数列で置き換えて一つになるまで減らし、最後の値が指定されたものになるようにしたい。そのような並べ方の辞書順最小なものを出力する問題。

解法

next_permutationで意外と早く見つかる。

POJ-2139 : Six Degrees of Cowvin Bacon

問題概要

連結グラフが与えられる。ある点を中心とした距離の近いほうN個の平均長の最小値を求める問題。

解法

真面目に幅優先で求めて十分間に合う。