最小のスキルの固定して、|skill| 分だけ動的計画法すると O(50 * 50 * 50 * 60000) でTLE。スキルが高い順に足していくと、最後に足されたスキルが最小のスキルになる。 そのことを利用して、昇順からナップサップの動的計画法をしていく、いざ足し合わせる…

問題文各列の状態はそれぞれ独立しているので、各列ごとに状態数を求めてそれらを掛け合わせる。 列ごとの状態数については、上からコマを置いていって、「何番目のコマか」と「コマを置ける一番上の場所」で DP する。 public class FoxAndShogi { const in…

問題文アリスが移動できなくなるまで幅優先探索すればよい。 DP してもいいけれど、やっていることは結局同じになる。 public class GameInDarknessDiv2 { int[] dx = { 0, 1, 0, -1 }; int[] dy = { 1, 0, -1, 0 }; string ds = "DRUL"; struct Point { pub…

問題文メモ付き探索する場合は、Nullableの配列を使うと初期化する必要がなくなるので楽メモ配列へのアクセスに Array.SetValue/GetValue を使うようにすると、メモ化に使うパラメタに破壊的代入してもバグらなくなる。追記：ただし、非常に速度が遅いので取…