ABC293 C問題の考え方
ABC293 C - Make Takahashi Happy の考え方を書きました。
問題理解
- 格子上を移動する
- 左上がスタート、右下がゴール
- 最短経路でスタートからゴールまで移動する（下方向と右方向の移動だけでゴールへ向かう）
- マスには数字が書いてあり、通る際にそれを「踏む」
- 同じ数字は1度までしか踏めない（一度踏んだ数字 と同じ数字が書いてあるマスへは移動できない）
解き方を考えていきましょう。
再帰DFS
まずは、マスに書いてある数字のことは置いておいて、「最短ルートは何通りあるか？」を考えます。
これはDPなどで効率的に求めることができますが、後から様々な制約を適用していくことを考慮し、今回は”全ルートを数え上げる”という方式にします。
(1, 1) から出発する場合に何通りあるかを考えると、「下に進んで (2, 1) に行った場合に何通りか」と「右に進んで (1, 2) に行った場合に何通りか」の合計です。
(2, 1) まで来たとして “そこから何通りあるか” は、やっぱり「下に進んで (3, 1) に行った場合に何通りか」と「右に進んで (2, 2) に行った場合に何通りか」の合計です。
つまり、ざっくりと
def dfs(x, y): # (x, y)から出発した場合に何通りか を返す
return dfs(x+1, y) + dfs(x, y+1)
のような再帰関数を定義できれば、
ans = dfs(1, 1)
として答えを求められそうです。
この案をもとに、制約を実装に加えていきましょう。
※補足：Pythonで再帰関数を使うと、呼び出し回数が多い場合にTLEとなってしまうことがあります。今回の問題ではTLEとなりませんでしたが、注意が必要です。
制約を加えていく
再帰の終端を書いておく
このままでは、無限に再帰関数が呼ばれてしまいます。
終端（ゴールにいるとき）は再帰せずに値を返すようにします。
ややｙトリッキーなのですが、「既にゴールマスにいる場合、そこからゴールへの行き方は1通り」とし、1を返すようにします。
def dfs(x, y):
if (x, y)はゴール座標？:
return 1
return dfs(x+1, y) + dfs(x, y+1)
“マス目の外部に移動することは出来ません”
現状でも、無限に再帰関数が呼ばれてしまいます。
マス目の外部に移動できないという制約を実装に追加します。
def dfs(x, y):
if (x, y)はゴール座標？:
return 1
count = 0
if (x+1, y)は範囲内？
count += dfs(x+1, y)
if (x, y+1)は範囲内？
count += dfs(x, y+1)
return count
通ったマスに書かれた整数は全て異なる
さて、本題です。
例えば {3, 1, 4} のように通ってきたら、以降は 1 が書かれたマスへは進めない という制約です。
これは、これまでに通ってきたマスに書かれていた数字を集合として保持し、「いま進もうとしているマスの数字が、その集合に含まれているか」を判定できればよいです。
集合管理には、以下の操作を高速に行えることが要求されます。
- 集合への要素の追加
- 集合からの要素の削除
- ある値が（その時において）集合に含まれるか
この要求を満たすのは、setと呼ばれるデータ構造です。 （setそのものが標準ライブラリに存在しない言語では、Hash、Map、辞書 などと呼ばれるデータ構造で代替も可能です。）
解法説明に戻ります。
setによる通ってきたマス管理では、具体的にはdfsをしながら以下の操作をします。
- 「マスの数字が未登場（setに含まれない）の場合のみ、そこへ進める」という条件を追加
- dfsで進む（次のマスへ進む）ときに、書かれているマスの数字を set へ追加
- dfsで戻る（そのマスについての情報が返ってきたので、そのマスから抜ける）ときに、書かれているマスの数字を set から削除
def dfs(x, y, s):
if (x, y)はゴール座標？:
return 1
count = 0
if (x+1, y)は範囲内 かつ, (x+1, y) の数字は s に含まれていない？
s に (x+1, y) の数字を追加
count += dfs(x+1, y, s)
s から (x+1, y) の数字を削除
if (x, y+1)は範囲内 かつ, (x, y+1) の数字は s に含まれていない？
s に (x, y+1) の数字を追加
count += dfs(x, y+1, s)
s から (x, y+1) の数字を削除
return count
ans = dfs(1, 1, {a[1][1]})
このアルゴリズムを正しく実装すると、ACできます。