2014-03-28から1日間の記事一覧
解法 BFS (or Warshall-Floyd) BFSではノードの接続を隣接行列でなくて連結リストにして解いたけどその必要はあったのだろうか。 因みにnは100以下なので、コストを1に定めて Warshall-Floyd しても解ける。この方が実装が短いし、一度最短路を求めればクエ…
解法 蟻本の反転の考え方を使う。最上部を踏むか踏まないか2^10で決め打ちし、2段目からはマスの一つ上が 1 であるなら 0 に埋めることを 9*10回 繰り返す。反転のオーダーは O(M*N*2^N)蛇足 Emacsのゲームにある 5x5 で遊んだらイメージがしっかり掴めて実…
解法 典型の配るDP。ジャンプ後の位置に障害物がある場合を見逃さないようにする。 あと問題文に書かれているけれど、ジャンプ台に乗って Y を超えるようなケースも注意。 自分は斜めからスキー台に侵入する場合分けが面倒になりそうだと思ったので直進を0, …