atcoder.jp 解法 絶対値を外すことができれば、(i, j)と(i', j') を分離できるので計算しやすくなる。 そこで、i ≧ i'かつ j ≧ j' という条件をつけることにする。 これで絶対値の中が必ず0以上になるため、絶対値を外して計算できるようになる。 i < i' か…

atcoder.jp 解法 都市から都市への移動を繰り返すという行為が、DPで遷移するというのに酷似しているため、DPをしたくなる。 次のようなDPを考える。 dp[i][j] ← i日目に都市jにいる旅の仕方は何通りか ただ問題文通りにK回、N個の町から通れる道を使って遷…

atcoder.jp 解法 問題を見てすぐに下のようなDPが思い浮かんだ。 dp[i][j] ← (i, j)へ行く場合の数 ただ、愚直に遷移しようとすると1つのマスにつき、H+W回ぐらいの遷移が必要になるのでこれでは間に合わない。 手を動かして、DPテーブルがどのような値をと…