アルゴリズム

ABC147 E Balanced Pathでbitset高速化を完全に理解する

本番で通せなかったABC147のE問題『Balanced Path』について、反省していきたいと思います。 問題概要 H*Wのグリッドの各マスに数が2つ書かれている。グリッド上を(0,0)->(H,W)にy+1orx+1で移動するとき、経路上の各マスについて、いずれかを選び、「その合…

0-1ナップサック問題入門(if文とfor文と配列を前提とする)

この記事ではナップサック問題を解くプログラムをPythonで実装します。 再帰関数も動的計画法も使わず、if文とfor文と配列を使って解くことを目指します。 ナップサック問題とは ナップサック問題とは次のような問題です。 いくつかのアイテムと1つのナップ…

2次元の凸包を求めるアルゴリズムと応用について

2次元の凸包(convex hull)を求めるアルゴリズムについてまとめました。また、凸包の応用先を列挙し、凸包を使って解ける競プロ問題を集めました。ギフト包装法(Gift wrapping algorithm),QuickHull,グラハムスキャン(Graham's scan),Monotone Chain,Chan's a…

n-ominoの列挙(Redelmeier's algorithm)

n-ominoとはn個の正方形で構成されるポリオミノ(Wikipedia)。 n-ominoの列挙を行うRedelmeier's algorithmをPythonで実装した。 速度検証 反転・回転を考慮しないn-ominoを列挙し、個数を数えた。所要時間は下記の通りだった。 n n-omino elapsed[s] 1 1 0.0…

ポリオミノの敷き詰め問題をDancing LinksとKnuth's Algorithm Xを使って解く

ポリオミノの敷き詰め問題を解くプログラムを書いた。効率的に解くためにDancing Linksというデータ構造を実装し、Knuth's Algorithm Xを使用した。 ポリオミノの敷き詰め問題とは こういうパズルがAmazonで売っている。結構難しい。 Amazon | 明治ミルクチ…