442.1
変則セット。
550
タイルが敷き詰められている領域の一部を切り出すことを考える。その部分に含まれる形状を再現するのに必要なタイルの枚数を答えよ、という問題。
うまいこと部分に切るのが大事。端以外は何も考える必要なし。
950
N都市があって、二都市間の友好関係が与えられる。友好関係にある都市のうち片方にしか衛兵が派遣されていないと、問題があるとする。衛兵を配置できる場所と、配置しなくてはならない場所が与えらるので、最適な配置に更新するとき、問題の起こる場所の最小数を求めよ。
最終的に配置した場所から、配置していない点への友好関係枝数をカウントする。これを最小にするのは最小カットなので、うまいことグラフを作って最大流を流せば良い。
グラフの作り方がひどかった...。