559.1

じっくりやったら遅かった。リハビリ中につき、通す方が大事。

250

X軸方向にAマスかつY軸方向にBマスまたはその逆の8通り移動できるコマがあるとする。盤面の大きさが与えられるので、移動可能な場所がK通りあるマスの数を答えよ、という問題。

左端からAマスまたはBマスで左方向への移動可否が変更し得る。右端からも上端からも下端からも同様。なので、こうして分割された25個の領域について、それぞれ何通りの移動ができるかを考えてやって、K通りになる領域の大きさの合計値を返してやれば良い。Kで分岐してもいいらしいけれど、考えるのめんどくさすぎる。

500

木の親子関係に相当するものが与えられる。どちらが親であっても構わないので、二分木かつ、根からの距離がもっとも遠い点以外はすべて埋まっていて、根から一番遠い点はなるべく左に全部寄っているようにしたい。このような木は何通り作ることができるか答えよ、という問題。

取り敢えずDPすることを考える。根から遠いものから順に組んでいく。状態としては自分は誰か、自分の親が誰なのか、根からの距離はどれくらいか、根から一番遠い子を何人抱えているか(それ以外の子は常に埋まっているはずなので考慮する必要ない)であるが、最後は一意に決まるので、何らかの方法で別途持つ。

状態遷移としては、自分が決まれば、親子関係にある可能性のある点が全部分かるので、根でなければ親が必須で、それ以外には子は二人までしか持てず、根から一番遠いなら子はいないし、その一個上なら子は2個以下の全パターンがあり得る。左右に子を持つ場合は、どちらも子がいない場合は左右反転可能だし、どちらも子がいっぱいでも同様。片方が子がいないならそれは右側でないと困るし、片方が子がいっぱいならそれは左側でないと困る。それ以外の子持ちは左側にどうやっても寄せられないので失敗。というのを書き上げるだけの面倒系DPでした。

900

見てない。