SRM 386 250pt: CandidateKeys

問題概要

DBの表がある。各列の組み合わせを抽出したものが各行に対してユニークに定まるのであれば、その組み合わせを主キーと呼ぶことにする。極小な主キーの組み合わせとして、最大の数と最小の数を求める問題。行数Rは50以下、列数Cは10以下。

考えたこと

• 問題がよく分からない。
• しばらく経ってようやく問題を理解した。で、どうするか。
• 主キーの組み合わせを列挙するのはO(2^C * C * R)でいける。
• 極小の判定どうしよう。グラフ構成するのとか面倒だからやりたくない。
• いやいや、グラフ構成する位なら候補数Nに対してO(N^2)でいけるじゃないか。
• 後は書くだけ。サンプル通った。投げた。WA。
• ビット回す範囲が2^Rまでになってた。2^Cに修正して無事AC。本番でこの間違いしたら悔しいだろうなあ。

SRM 386 500pt: PolygonCover

問題概要

凸多角形(頂点数N<=15)が与えられる。この頂点を複数個選んでできる多角形を集めて頂点を被覆したい。面積の和を最小化する問題。ただし面積が重複している部分は複数回カウントする。

考えたこと

• サイズからしてビットDP？
• 多角形で覆うとか言ってるけど三角形に分割できるので三角形だと思っていい。
• 更新するのは三角形全部作ればいい。
• 三角形の数の大さがちょっと気になる。電卓でcombination(15,3) * 2^15を計算。ちょっと大きいけどギリギリ間に合いそう。
• この計算、実は全部整数でできるので少し大きいくらいなら間に合うだろう。
• メモ化再帰で書こうとしたけど上手くかけなかった。仕方ないので配るDPをループで書く。
  • スーパーセットに配るタイプのビットDPなのでビットの回し方は単純。
• 一発コンパイルで無事通った。
• おまけ：これ結局メモ化再帰で自然に書く方法はあるんだろうか？