AOJ 2731 Shifting a Matrix

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2731

解説

シフト操作 F について，F[i][j] := i 行目 j 列目の要素がどこに移るか と表現すれば，あとはこれらを結合するだけです．操作 F, G に対し，これらをこの順に結合した操作 H は H[i][j] = F[G[i][j].first][G[i][j].second] と計算できます．
操作回数が大きいので，行列のシフト操作は繰り返し二乗法っぽく計算します．
変に解説するよりコードを読んでもらったほうが早いと思います．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int N;

vector<vector<pii>> make_initial() {
    vector<vector<pii>> res(N, vector<pii>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            res[i][j] = make_pair(i, j);
        }
    }
    return res;
}

vector<vector<pii>> eval(vector<vector<pii>> const& A, vector<vector<pii>> const& x) {
    auto res = A;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            res[i][j] = A[x[i][j].first][x[i][j].second];
        }
    }
    return res;
}

vector<vector<pii>> sequence(string const& s, int& p);
vector<vector<pii>> repetition(string const& s, int& p);
vector<vector<pii>> operation(string const& s, int& p);
int number(string const& s, int& p);

vector<vector<pii>> sequence(string const& s, int& p) {
    auto res = make_initial();
    while(p < s.size() && (s[p] == '(' || isalpha(s[p]))) {
        vector<vector<pii>> f;
        if(s[p] == '(') {
            f = repetition(s, p);
        } else if(isalpha(s[p])) {
            f = operation(s, p);
        } else {
            cout << "error pos: " << p << endl;
            assert(false); // error
        }
        res = eval(res, f);
    }
    return res;
}

vector<vector<pii>> repetition(string const& s, int& p) {
    auto x = sequence(s, ++p);
    ++p;
    assert(isdigit(s[p]));
    int n = number(s, p);
    auto res = make_initial();
    while(n > 0) {
        if(n & 1) {
            res = eval(res, x);
        }
        x = eval(x, x);
        n >>= 1;
    }
    return res;
}

vector<vector<pii>> operation(string const& s, int& p) {
    auto res = make_initial();
    char op = s[p++];
    int i = number(s, p) - 1;
    if(op == 'L') {
        for(int j = 0; j < N; ++j) {
            res[i][j].second = (j + 1) % N;
        }
    } else if(op == 'R') {
        for(int j = 0; j < N; ++j) {
            res[i][j].second = (j - 1 + N) % N;
        }
    } else if(op == 'U') {
        for(int j = 0; j < N; ++j) {
            res[j][i].first = (j + 1) % N;
        }
    } else if(op == 'D') {
        for(int j = 0; j < N; ++j) {
            res[j][i].first = (j - 1 + N) % N;
        }
    } else {
        assert(false);
    }
    return res;
}

int number(string const& s, int& p) {
    int res = 0;
    while(isdigit(s[p])) {
        res *= 10;
        res += (s[p++] - '0');
    }
    return res;
}

int main() {
    int L;
    string S;
    cin >> N >> L >> S;
    int p = 0;
    auto ans = sequence(S, p);
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            cout << (ans[i][j].first * N + ans[i][j].second + 1) << " \n"[j + 1 == N];
        }
    }
}

感想

構文解析，アルゴリズムの知識，実装パートのそれぞれが良いパランスで要求されている教育的良問だと思う．難易度もあまり高くない．
写像の表現は pair でやったけど，(i, j) -> i * N + j と一次元に直したほうが楽かもしれない．