2015-03-14から1日間の記事一覧

Indeedなう(予選A)D: 15パズル(幅優先探索・枝刈り)

問題 D: パズル - Indeedなう(予選A) | AtCoder 解法 あるマス(i, j)の数字が本来あるべきマスとのマンハッタン距離を計算する。本来あるべきマスまで移動するのに最低でもマンハッタン距離分だけの手数がかかるので、他の数字についてもマンハッタン距離…

yukicoder No. 165 四角で囲え! (累積和・片側全探索)

問題 No.165 四角で囲え! - yukicoder 解法 AOJ 2426の方法を使いまわして座標圧縮する。 AOJ 2426: 宝探し(2次元の累積和) - 宇宙ツイッタラーXの憂鬱かつにおける宝物の数とポイントを計算してやれば良いが、x1とx2とy1とy2を全探索するとTLEになるので…

AOJ 2426: 宝探し(2次元の累積和)

問題 Treasure Hunt | Aizu Online Judge 解法 フィールドは広いが宝物の数は高々5000なので、宝物に準拠した最大5001*5001のフィールドを作る。treasures[i][j]にかつにおける宝物の数を入れておくと、かつにおける宝物の数は、以下の式で表せるようになる…