E - ロボット掃除機 / Robot Vacuum Cleaner 解説 by admin
gpt-5.5-highOverview
For each robot, directly simulating the command sequence for \(T\) turns would not be fast enough since \(T \leq 10^{18}\).
We exploit the periodicity of the command sequence, treat “the position after executing the command sequence once” as a function, and use cycle detection to compute the answer efficiently.
Analysis
Since robots do not affect each other, each robot can be considered independently.
Let \(S\) be a robot’s command sequence and \(L\) be its length.
\(T\) turns can be decomposed as:
\[ T = qL + r \]
In other words:
- Execute the command sequence \(S\) in full \(q\) times
- Then execute only the first \(r\) characters
Here, let us define the cell reached after executing the command sequence \(S\) once starting from cell \(x\) as:
\[ F_S(x) \]
Then, the position after executing the command sequence \(q\) times is:
\[ F_S^q(x) \]
This becomes a problem of “repeatedly applying a function over a finite set of cells.”
Since there are at most \(NM\) cells, once the same cell appears again, everything after that point becomes periodic.
For example, if a robot’s position sequence is:
\[ x_0 \to x_1 \to x_2 \to x_3 \to x_1 \to x_2 \to \cdots \]
then \(x_1, x_2, x_3\) form the cycle.
Even if \(q\) is very large, we can find the target position by taking the remainder when dividing by the cycle length.
Furthermore, robots with the same command sequence share the same function \(F_S\).
Therefore, we group robots by their command sequence and cache the computation results of \(F_S(x)\).
Naively moving each robot every turn would be \(O(KT)\), which is infeasible.
Also, recomputing the command sequence \(S\) from scratch for each robot would cause a lot of redundant work.
Instead, we take the following approach:
- Group robots by command sequence
- Compute the one-cycle transition \(F_S\) only for cells that are actually needed, and store the results
- Skip repeated applications of \(F_S\) using cycle detection
Algorithm
1. Grid Preprocessing
For each cell, store a bitmask indicating whether movement is possible in each of the four directions (up, down, left, right).
Additionally, to efficiently handle consecutive commands in the same direction, precompute the following for each floor cell:
- How far left it can travel in its row
- How far right it can travel in its row
- How far up it can travel in its column
- How far down it can travel in its column
For example, if the connected floor segment in a row spans from column \(3\) to column \(8\), then starting from any cell within that segment and moving right, you cannot go beyond column \(8\).
This allows processing \(c\) consecutive moves in the same direction in \(O(1)\).
2. Group Robots by Command Sequence
Robots with the same command sequence \(S\) share the same one-cycle transition function \(F_S\).
Therefore, using an unordered_map, we create:
\[ S \mapsto \text{list of robots with that command sequence} \]
3. Function to Execute a Command Sequence Once
We prepare a function that executes the first len characters of a command sequence \(S\) starting from a given cell.
In the code, applyWith corresponds to this.
Basically, we process commands in order, but the implementation includes further optimizations.
Commands That Can Be Skipped
If movement in a certain direction is not possible from the current cell, that command has no effect.
Also, for example, if R is immediately followed by L, and the initial R can be executed:
R → L
returns to the original cell.
That is, these two commands can be ignored together.
To skip such “command subsequences that don’t change the current position,” we precompute, for each bitmask of movable directions from the current cell, the next command position that actually needs to be processed.
Consecutive Commands in the Same Direction
When the same direction continues, such as RRRRR, there is no need to move one step at a time.
Using the precomputed reachable ranges in each direction:
\[ \text{Move at most } c \text{ cells to the right from the current position} \]
can be done in \(O(1)\).
4. Cache the One-Cycle Transition
For a command sequence \(S\):
\[ F_S(x) = \text{the cell reached after executing } S \text{ once from cell } x \]
Since \(F_S\) is shared within the same group, once \(F_S(x)\) is computed, it is stored and reused.
In the code, getF corresponds to this.
5. Cycle Detection for Each Robot
Let the initial position of a robot be \(x\).
First, compute:
\[ q = \left\lfloor \frac{T}{L} \right\rfloor,\quad r = T \bmod L \]
Next, apply \(F_S\) a total of \(q\) times.
However, since \(q\) can be very large, we record the cells visited:
- If a cell is visited for the first time, record it and proceed
- If a cell has already been visited, a cycle has been found, so advance only by the remainder of the remaining steps divided by the cycle length
This ensures that for each robot, we only need to examine at most \(NM\) transitions.
Finally, execute only the first \(r\) characters of command sequence \(S\) to produce the answer.
Complexity
Let \(V = NM\), let \(\mathcal{S}\) be the set of all distinct command sequences, and define:
\[ A = \sum_{S \in \mathcal{S}} |S| \]
For each command sequence \(S\), \(F_S(x)\) is computed at most once for each cell \(x\).
Each computation takes at most \(O(|S|)\), so the total is:
\[ O(VA) \]
Additionally, in the cycle detection phase, each robot examines at most \(V\) states, giving:
\[ O(VK) \]
Therefore, the overall complexity is:
- Time complexity: \(O(NM(A+K) + \sum_i L_i)\)
- Space complexity: \(O(NM + K + \sum_i L_i)\)
Since the constraints guarantee:
\[ NM(A+K) \leq 2 \times 10^7 \]
the solution runs sufficiently fast.
Implementation Notes
The input is 1-indexed, but internally we convert to 0-indexed.
\(T\) can be up to \(10^{18}\), so it must be handled with
long longtype.By processing robots with the same command sequence together, we reuse the same transition computations.
Since reinitializing arrays every time is expensive, we use “stamp arrays” like
seenStampandfStampto avoid reinitialization.When producing the final output, convert row and column numbers back to 1-indexed.
Source Code
#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;
}
This editorial was generated by gpt-5.5-high.
投稿日時:
最終更新: