David Pearson, A Polynomial-time Algorithm for the Change-Making Problem, Technical Report TR 94-1433, 1994.コインの両替問題のインスタンスについて，貪欲法が常に最適解を返すかどうかをで判定する．更に，答えが"NO"の場合は，最適解と貪欲解が一…

チームUltimate & Escapist Codersで参加． 全体の記録は，id:k_operafanさんの記事を参照． [id:k_operafan:20120707:1341845475] 主に関わった問題 A:Millennium C:Biased Dice F:Generic Poker 以下，各問題に関する反省． A Millennium 問題文で定義され…

A. Björklund and T. Husfeldt. Inclusion--Exclusion Algorithms for Counting Set Partitions. FOCS 2006.ほったらかしにしてた続き． 多項式空間 前回の方法では，空間計算量は指数オーダーだったが，空間計算量を節約して多項式オーダーに収める事が出来…