問題文 : 本棚解法 : にかいどうさんの言うとおり, 昨日解いた「House Moving」と同じ問題でした.(重さがそれぞれ違いますが, あまり関係ない) ということで, 解説は昨日のもの参照です. BITでも解けるみたいなので, あとでBITで実装してみます.コード : #in…

問題文 : 日本情報オリンピック旗解法 : 旗を4つに分解し, それぞれに何を割り振るのかが最適なのかを深さ優先探索で決めていく. ここで, 旗の大きさに対して最初から書かれている文字の個数が少ないので, 見ている範囲に文字が無い or 旗のレベルが0のとき…

問題文 : カンニング対策 (pdf注意, 3枚目)解法 : 監視する装置の範囲の最大値を求めれば良いから, すべての装置の精度を等しいものとして考える. すると, 端から貪欲的に装置を置いていける. 装置の範囲の最大値は, 二分探索で決めてやることで, O(Mlog(max…

問題文 : カードキー解法 : 包除原理のようなものをつかう.この問題は, "0 ~ 2 ^ (N - K)までの数から, すくなくとも1つ数をつかって論理積を0にする組み合わせの総数はいくつか", という問題に置き換えられる.数の選び方は, U = 2 ^ (2 ^ (N - K)) - 1 通り…