E - ロボット掃除機 / Robot Vacuum Cleaner Editorial by admin
gpt-5.5-high概要
各ロボットについて、命令列を \(T\) ターン分そのままシミュレーションすると \(T \leq 10^{18}\) なので間に合いません。
命令列の周期性を利用し、「命令列を 1 周実行した後の位置」を関数として考え、周期検出で高速に答えます。
考察
ロボット同士は互いに影響しないため、各ロボットは独立に考えられます。
ロボットの命令列を \(S\)、長さを \(L\) とします。
\(T\) ターンは
\[ T = qL + r \]
と分解できます。
つまり、
- 命令列 \(S\) を \(q\) 回まるごと実行する
- その後、先頭 \(r\) 文字だけ実行する
と考えられます。
ここで、あるマス \(x\) から命令列 \(S\) を 1 回実行した後のマスを
\[ F_S(x) \]
とします。
すると、\(q\) 回命令列を実行した後の位置は
\[ F_S^q(x) \]
です。
これは「有限個のマス上の関数を何度も適用する」問題になります。
マス数は高々 \(NM\) 個なので、同じマスが再び現れたらそこから先は周期になります。
例えば、あるロボットの位置が
\[ x_0 \to x_1 \to x_2 \to x_3 \to x_1 \to x_2 \to \cdots \]
となった場合、\(x_1,x_2,x_3\) が周期です。
\(q\) が非常に大きくても、周期の長さで割った余りを使えば目的の位置を求められます。
また、同じ命令列を持つロボットでは関数 \(F_S\) が同じです。
そのため、命令列ごとにロボットをまとめ、\(F_S(x)\) の計算結果をキャッシュします。
素朴に各ロボットごとに毎ターン動かすと \(O(KT)\) となり不可能です。
また、各ロボットごとに毎回命令列 \(S\) を最初から計算すると重複が多くなります。
そこで、
- 命令列ごとにグループ化する
- 1 周分の遷移 \(F_S\) を必要になったマスだけ計算して保存する
- \(F_S\) の繰り返しは周期検出で飛ばす
という方針を取ります。
アルゴリズム
1. グリッドの前処理
各マスについて、上下左右に 1 マス移動できるかをビットマスクで持ちます。
また、同じ方向の命令が連続する場合に高速に処理するため、各床マスについて以下を前計算します。
- その行で、左にどこまで進めるか
- その行で、右にどこまで進めるか
- その列で、上にどこまで進めるか
- その列で、下にどこまで進めるか
例えば、ある行の床の連結区間が列 \(3\) から列 \(8\) までなら、その区間内のどのマスから右に進んでも列 \(8\) より先には行けません。
これにより、同じ方向に \(c\) 回連続で進む処理を \(O(1)\) で行えます。
2. 命令列ごとにロボットをグループ化
同じ命令列 \(S\) を持つロボットは、1 周分の遷移関数 \(F_S\) が共通です。
そのため、unordered_map を使って
\[ S \mapsto \text{その命令列を持つロボット一覧} \]
を作ります。
3. 命令列を 1 回実行する関数
命令列 \(S\) の先頭 len 文字を、あるマスから実行する関数を用意します。
コード中では applyWith がこれに対応します。
基本的には命令を順番に処理すればよいですが、実装ではさらに高速化しています。
スキップできる命令
現在のマスから見て、ある方向に移動できない場合、その命令は何も起こしません。
また、例えば R の直後に L があり、最初の R が実行できるなら、
R → L
で元のマスに戻ります。
つまり、この 2 命令はまとめて無視できます。
このような「現在位置が変わらない命令列」を飛ばすために、現在マスの移動可能方向のビットマスクごとに、次に本当に処理が必要な命令位置を前計算しています。
同じ方向の連続命令
例えば RRRRR のように同じ方向が続く場合、1 回ずつ動かす必要はありません。
前処理した左右上下の到達可能範囲を使って、
\[ \text{現在位置から右に最大 } c \text{ マス進む} \]
という処理を \(O(1)\) で行います。
4. 1 周分の遷移をキャッシュする
命令列 \(S\) に対して、
\[ F_S(x) = \text{マス } x \text{ から } S \text{ を 1 回実行した後のマス} \]
を考えます。
同じグループ内では \(F_S\) は共通なので、一度計算した \(F_S(x)\) は保存して再利用します。
コード中では getF がこれに対応します。
5. 各ロボットについて周期検出
ロボットの初期位置を \(x\) とします。
まず、
\[ q = \left\lfloor \frac{T}{L} \right\rfloor,\quad r = T \bmod L \]
を計算します。
次に、\(F_S\) を \(q\) 回適用します。
ただし \(q\) は非常に大きいので、訪れたマスを記録します。
- 初めて訪れたマスなら記録して次へ進む
- すでに訪れたマスなら周期が見つかったので、残り回数を周期長で割った余りだけ進める
これにより、各ロボットについて高々 \(NM\) 回の遷移を見るだけで済みます。
最後に、命令列 \(S\) の先頭 \(r\) 文字だけを実行して、答えを出します。
計算量
\(V = NM\)、相異なる命令列全体の集合を \(\mathcal{S}\) とし、
\[ A = \sum_{S \in \mathcal{S}} |S| \]
とします。
各命令列 \(S\) について、\(F_S(x)\) は各マス \(x\) ごとに高々 1 回だけ計算されます。
1 回の計算には高々 \(O(|S|)\) かかるため、全体で
\[ O(VA) \]
です。
また、周期検出では各ロボットについて高々 \(V\) 回状態を見るので、
\[ O(VK) \]
です。
したがって全体の計算量は
- 時間計算量: \(O(NM(A+K) + \sum_i L_i)\)
- 空間計算量: \(O(NM + K + \sum_i L_i)\)
です。
制約で
\[ NM(A+K) \leq 2 \times 10^7 \]
が保証されているため、十分高速に動作します。
実装のポイント
入力は 1-indexed ですが、内部では 0-indexed に直して扱います。
\(T\) は最大 \(10^{18}\) なので、
long long型で扱います。命令列が同じロボットをまとめて処理することで、同じ遷移計算を再利用します。
配列を毎回初期化すると重いので、
seenStampやfStampのような「スタンプ配列」を使って、初期化を省略しています。最後に出力するときは、行番号・列番号を 1-indexed に戻します。
ソースコード
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, M, K;
long long T;
cin >> N >> M >> K >> T;
vector<string> g(N);
for (int i = 0; i < N; i++) cin >> g[i];
const int V = N * M;
const int MAXL = 1000;
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};
const int opp[4] = {1, 0, 3, 2};
auto id = [&](int r, int c) -> int {
return r * M + c;
};
vector<array<int, 4>> go(V);
vector<unsigned char> avail(V, 0);
for (int r = 0; r < N; r++) {
for (int c = 0; c < M; c++) {
int v = id(r, c);
for (int d = 0; d < 4; d++) go[v][d] = v;
if (g[r][c] == '#') continue;
unsigned char msk = 0;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (0 <= nr && nr < N && 0 <= nc && nc < M && g[nr][nc] == '.') {
go[v][d] = id(nr, nc);
msk |= (1u << d);
}
}
avail[v] = msk;
}
}
vector<int> leftB(V), rightB(V), topB(V), bottomB(V);
for (int r = 0; r < N; r++) {
int c = 0;
while (c < M) {
if (g[r][c] == '#') {
int v = id(r, c);
leftB[v] = rightB[v] = c;
c++;
} else {
int s = c;
while (c < M && g[r][c] == '.') c++;
int e = c - 1;
for (int x = s; x <= e; x++) {
int v = id(r, x);
leftB[v] = s;
rightB[v] = e;
}
}
}
}
for (int c = 0; c < M; c++) {
int r = 0;
while (r < N) {
if (g[r][c] == '#') {
int v = id(r, c);
topB[v] = bottomB[v] = r;
r++;
} else {
int s = r;
while (r < N && g[r][c] == '.') r++;
int e = r - 1;
for (int x = s; x <= e; x++) {
int v = id(x, c);
topB[v] = s;
bottomB[v] = e;
}
}
}
}
auto moveMany = [&](int v, int d, int cnt) -> int {
int r = v / M;
int c = v % M;
if (d == 0) {
r = max(r - cnt, topB[v]);
} else if (d == 1) {
r = min(r + cnt, bottomB[v]);
} else if (d == 2) {
c = max(c - cnt, leftB[v]);
} else {
c = min(c + cnt, rightB[v]);
}
return id(r, c);
};
vector<int> start(K);
unordered_map<string, vector<int>> groups;
groups.reserve(K * 2);
for (int i = 0; i < K; i++) {
int R, C, L;
string S;
cin >> R >> C >> L >> S;
--R;
--C;
start[i] = id(R, C);
groups[S].push_back(i);
}
vector<pair<int, int>> ans(K);
vector<int> seenStamp(V, 0), seenIdx(V, 0);
vector<int> fStamp(V, 0), fVal(V, 0);
int robotStamp = 1;
int groupStamp = 1;
auto charDir = [](char ch) -> int {
if (ch == 'U') return 0;
if (ch == 'D') return 1;
if (ch == 'L') return 2;
return 3;
};
for (auto &entry : groups) {
const string &S = entry.first;
const vector<int> &members = entry.second;
int L = (int)S.size();
long long q = T / L;
int rem = (int)(T % L);
vector<int> dirs(L);
for (int i = 0; i < L; i++) dirs[i] = charDir(S[i]);
vector<int> sameRun(L);
for (int i = L - 1; i >= 0; i--) {
if (i + 1 < L && dirs[i + 1] == dirs[i]) sameRun[i] = sameRun[i + 1] + 1;
else sameRun[i] = 1;
}
int effFull[16][MAXL + 2];
int effRem[16][MAXL + 2];
auto buildEff = [&](int len, auto &eff) {
for (int m = 0; m < 16; m++) {
eff[m][len] = len;
for (int p = len - 1; p >= 0; p--) {
int d = dirs[p];
if ((m & (1 << d)) == 0) {
eff[m][p] = eff[m][p + 1];
} else if (p + 1 < len && dirs[p + 1] == opp[d]) {
eff[m][p] = eff[m][p + 2];
} else {
eff[m][p] = p;
}
}
}
};
buildEff(L, effFull);
buildEff(rem, effRem);
auto applyWith = [&](int st, int len, auto &eff) -> int {
int cur = st;
int pos = 0;
while (pos < len) {
int m = avail[cur];
int j = eff[m][pos];
if (j >= len) break;
int d = dirs[j];
int run = sameRun[j];
if (run > len - j) run = len - j;
cur = moveMany(cur, d, run);
pos = j + run;
}
return cur;
};
int gs = groupStamp++;
auto getF = [&](int x) -> int {
if (fStamp[x] == gs) return fVal[x];
int y = applyWith(x, L, effFull);
fStamp[x] = gs;
fVal[x] = y;
return y;
};
for (int idxRobot : members) {
int cur = start[idxRobot];
long long step = 0;
int rs = robotStamp++;
vector<int> orbit;
orbit.reserve((size_t)min<long long>(q, V));
while (step < q) {
if (seenStamp[cur] == rs) {
long long a = seenIdx[cur];
long long cyc = step - a;
long long target = a + (q - a) % cyc;
cur = orbit[(size_t)target];
break;
}
seenStamp[cur] = rs;
seenIdx[cur] = (int)step;
orbit.push_back(cur);
cur = getF(cur);
step++;
}
cur = applyWith(cur, rem, effRem);
ans[idxRobot] = {cur / M + 1, cur % M + 1};
}
}
for (int i = 0; i < K; i++) {
cout << ans[i].first << ' ' << ans[i].second << '\n';
}
return 0;
}
この解説は gpt-5.5-high によって生成されました。
posted:
last update: