C - Belt Conveyor Editorial by Nyaan
この問題は答えが -1
になる条件を導き出すのが少し難しいです。
そこで、とりあえず答えが -1
でない場合に答えを求められるアルゴリズムを構成してみましょう。
これは、次のようなシミュレーションによって解くことができます。
- はじめ \((i, j) = (1, 1)\) とする。
- 次の処理を繰り返す。
- \((i, j)\) から移動できるマスを \((i_n, j_n)\) として、\(i\) を \(i_n\) に、\(j\) を \(j_n\) に更新する。ただし、\((i,j)\) から移動できるマスが存在しない場合は、繰り返しを終了する。
- \((i, j)\) を答えとして出力する。
さて、答えが -1
になる条件を考えてみましょう。
以下でははじめにいるマス \((1, 1)\) を「\(1\) 回目に通るマス」、その次に通るマスを 「\(2\) 回目に通るマス」…という風に順序付けて呼びます。
答えが -1
になる場合、あなたは無限に動き続けます。このとき、「\(1\) 回目に通るマス」「\(2\) 回目に通るマス」\(\dots\) 「\(HW+1\) 回目に通るマス」を並べてみましょう。すると、マスは全部で \(HW\) マスしかないので、この中に \(2\) 回登場しているようなマスが少なくとも \(1\) 個必ず存在します。(砕けた表現に言い換えると、「\(2\) 回以上通るようなマスが存在する」ということです。)
よって、
- (答えが
-1
になる) ならば (\(2\) 回以上通るようなマスが存在する)
ということが証明できました。また、逆に、
- (\(2\) 回以上通るようなマスが存在する) ならば (答えが
-1
になる)
ということも証明できます。
マス \((i, j)\) を \(2\) 回以上通るとして、そのうち早い方から \(2\) 回は \(t\) 回目と \(t + d\) 回目に通るとします。 このとき、詳細は略しますが、マス目 \((i,j)\) に止まるのは \(t + 2d\) 回目, \(t + 3d\) 回目, \(t + 4d\) 回目, \(\dots\) と周期的に際限無く通り続けることが示せます。(しっくりこないという方は実際にマス目を用意してコマを動かしてみると理解できると思います。)
よって、以上の \(2\) つの事実を合わせて
- 「答えが
-1
になる」ための必要十分条件は 「\(2\) 回以上通るようなマスが存在する」ことである。
ということが言えました。(この辺りの議論に自信を持てない方は高校数学の「集合と論理」を復習してみるとよいかもしれません。)
以上より、この問題は「\(2\) 回以上通るようなマスが存在するか?」を管理しながらシミュレーションを行えばよいです。これは先ほどのアルゴリズムを少し改良した以下のアルゴリズムでシミュレーションすることができます。
- はじめ \((i, j) = (1, 1)\) とする。
- また、訪問済みを管理するフラグとして \(H \times W\) の \(2\) 次元配列
vis
を用意する。vis
の要素はfalse
で初期化されている。 - 次の処理を繰り返す。
- はじめに 訪問済みフラグ
vis[i][j]
を更新する。vis[i][j]
がtrue
の場合、同じマスを \(2\) 回経由したことになるので、-1
を出力してプログラムを終了する。vis[i][j]
がfalse
の場合、vis[i][j] = true
に更新する。
- 次に移動を行う。\((i, j)\) から移動できるマスを \((i_n, j_n)\) として、\(i\) を \(i_n\) に、\(j\) を \(j_n\) に更新する。ただし、\((i,j)\) から移動できるマスが存在しない場合は、繰り返しを終了する。
- はじめに 訪問済みフラグ
- \((i, j)\) を答えとして出力する。
計算量は \(\mathrm{O}(HW)\) です。これはループ処理が最大で \(HW + 1\) 回しか発生しないことから証明できます。
- 実装例(C++)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int H, W;
cin >> H >> W;
vector<string> g(H);
for (auto& s : g) cin >> s;
vector vis(H, vector<int>(W, false));
int i = 0, j = 0;
while (1) {
if (vis[i][j] == true) {
cout << -1 << endl;
exit(0);
}
vis[i][j] = true;
if (g[i][j] == 'U' and i != 0) {
--i;
} else if (g[i][j] == 'D' and i != H - 1) {
++i;
} else if (g[i][j] == 'L' and j != 0) {
--j;
} else if (g[i][j] == 'R' and j != W - 1) {
++j;
} else {
break;
}
}
cout << i + 1 << " " << j + 1 << endl;
}
posted:
last update: