388.1
500
N人の人がいて、一人の人が高々一つのグループに所属するようにグループを分ける。それぞれの人にはできる技能が与えられているので、グループのメンバーで全部の技能を網羅するようにしたい。このとき、最大で何グループが全部の技能を網羅できるか答えよ、という問題。
取り敢えず2^N通りのグループについて全部の技能を網羅できるかを求める。後は既にグループになっている人を状態にしてDPしていく。愚直にやると4^N通り計算することになって終わらないので、グループになっていない人についてのみグループを考える。これで3^N通り計算することになる。(要は既にグループになっている人のビットが立たないようにビット演算してやる。)
1000
7桁の16進数について、桁ごとに比較したときにK箇所違うように次の番号を振るときのN番目の数を答えよ、という問題。
連動して動くことを利用して、適当にやるとダメそう。(それで通る実装ゲーならやる価値ないし...。)