523.1

解けないと判断したときに踏ん切りがつかないのをどうにかしましょうね、というお話。

250

a+b*xとc*d^yという式で表現されるN以下の数はいくつあるか答えよ、という問題。

前者は圧倒的に数が多いので、取り敢えず除算でいくつあるかカウントする。後者は指数なので総数が少ないので、全部テストする。

500

1x1xKのブロックを積み上げることを考える。ブロックの下に空洞がないように積む方法は何通りあるか答えよ、という問題。

二段階のDPをやる。ある列に長さAの範囲で詰んだ場合、その上には幅Aで高さが1小さい分の詰み方を考える。このようなAのパターンはDPで全探索する。

900

文字列の二次元マップが与えられるので、すべての文字を一度ずつ含むように隣接するマスから一文字ずつ選ぶ方法は何通りあるか答えよ、という問題。

文字数の指数でくるので、指数の肩が小さくなるように、真ん中から考える。真ん中が決まると、上下左右に移動しつつ(基本的に戻ることはしないので(3^長さ)通り全探索するだけで良い)各文字列がいくつできるかをカウントしていく。後はある文字列と、それに含まれていない文字からなる文字列の数をかけるだけ。