AOJ0091 Blur
問題リンク Blur
- 解法
DFS+枝刈りで解きました。
f(i, j, k, drop): 既にk滴使っている状態でマス(i, j)に大きさdropの滴を落とす
という関数を作っておいて、左上から右下のマスへこの関数を再帰させます。
問題が与えている座標系は(x, y)座標ですが、自分は癖で行列(i, j)で座標を扱ってます。
このままだとTLEするっぽいので、枝刈りを入れます。
f()を左上から右下へ動かすので、(i, j)に大きさ3の滴を落としても届かない上部のマスは、これ以降絶対に滴を落とせません。なので、その部分に染料の量が合っていないマスが存在したら、目標の模様は作れないと決定するので枝を刈ります。
- ソース
AOJ0119 Taro's Obsession
問題リンク Taro's Obsession
- 解法
容疑者を頂点にした有向グラフで考え、Y->Xという証言を辺にします。頂点の出次数が0の頂点はもう出力してしまってよく、その頂点をグラフから取り除きます。これを繰り返せばOKです。
- ソース
AOJ0260 Salary for a Plumber
問題リンク Salary for a Plumber
- 解法
ジョイントを1つ使うと、使ったジョイントの長さだけパイプの長さの総和が伸び、パイプの本数が1つ減ります。残ってるジョイントの内、最も長いものを使えば、N-1本における給料が最大になります。ジョイントを使って繋げる2本のパイプは何だって構いません。
- ソース
AOJ0259 All Numbers Lead to 6174
問題リンク All Numbers Lead to 6174
- 解法
数NをソートすればSになり、SをreverseすればLになります。
入力された数値が1111の倍数なら"NA"です
- ソース
