|http://www.topcoder.com/stat?c=problem_statement&pm=8084方針を検討DPっぽいstartとfinishが100以下なのがポイントになりそうだとりあえず区間の昇順にソートしておく。状態を考える今考えている区間と、最後に使った区間とで状態を持つのはどうか状態遷移は、最後に使った区間(の終わり)に交わらない区間を選択していく。これだけだと複数の区間を飛び越えて選択してしまいそうだ。発想を変えてみるグラフに落としこんでみる各区間をノードとして、区間が交わっていればノードをエッジでつなぐ頂点彩色問題っぽい?効率的な解き方あったっけ時間切れ。他の人のコードを見るといろんな解き方があって面白い。午前中emacsでAOJやってたのでeclipseでのコーディングに戸惑うサンプル通る。テスト問題分を読みなおす最大の素因数がkっていうところが妙に引っかかる本当にこのやり方で合ってるのか?いや、大丈夫なはず。|http://www.topcoder.com/stat?c=problem_statement&pm=8473グラフゲーきた方針を検討ふむ。あるノードを選んだ時、それと直接つながっているノードに話が行き渡るのかノードを複数選んで、全員に話を行き渡らせる。一度使ったノードは使えないとすると、それが最大何回できるか・・ということかなんとなく最大流っぽい制約を読む。パターンを全部trueにしてみるこれで多少計算量が落ちてることを祈るさて、パターンは求まった。これ、あとはsubset同士の和の最大を取っていくだけか。いつぞやのKiwiJiceを思い出した。