はまやんはまやんはまやん

hamayanhamayan's blog

写真の回転 [パソコン甲子園2019 予選 E]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0432

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0432/review/5788072/hamayanhamayan/C++14

若干の高速化は含まれるが、大体は実装問題である。
盤面の回転処理を実装する必要があるので、そこが大変ポイントだろう。

問題を簡単化していく

回転処理をどうするかという課題がすぐに見えるが、そこの解決をちょっと後回しにしておいて、
問題そのものを良い感じに解釈できないか考えてみよう。

クエリとして最大20万回回転させた後、最終的な結果を問う問題。
毎回クエリで要求されていることを実施して回転処理を行う方針がまず考えられるが、20万回回転させるのはちょっと大変そう。
しかも1で時計回りに回転して、その後-1で反時計回りで回転させると元に戻ってしまう。
そして、どのように回転させても最終的には0度回転、90度回転、180度回転、270度回転のどれかになるということを考慮すると、
全部の回転を考慮したときに最終的に最初から何度回転すればOKかが分かれば回転処理はその分だけやればいいので
かなり高速化できそうな雰囲気がある。
この方針で進めてみよう。

操作をまとめる

今回は必須ではないが、操作をまとめることができるので、それをやってみよう。
色々な操作があるとその分処理を場合分けする必要が出てきてしまう、今回で言うと時計回りと反時計回りを区別しているせいで
場合分けが存在してしまうのはあまりうれしくない。
反時計回り1回というのは時計回りで考えると3回に相当する。
そのため、操作をすべて時計回りに考えてしまって、1は時計回りに1回、-1は時計回りに3回回転させるような感じでカウントしていく。

こうすると時計回りに14回回転とか、34回回転とかというのが最終的に集計されてくるわけだが、4回回転させると元に戻るので、
4で割った余りの回数が簡単化した場合に必要な回数となる。
これで最後に残った要求事項は、0~3回与えられた盤面を時計回りに回転させるという操作になる。

時計回りに回転

ややバグりやすいのでモジュール化(関数化)して単体でテストしながら実装していくのもいいだろう。
自分はrotateClockwise関数として実装しているので、実装例として見てみてほしい。
回転させた場合に(x,y)がどこに移動するかをいくつか列挙してパターンを見つければ実装が行える。
x座標もy座標も0から始まる(0-indexed)であるとすると、(x,y)が(n - y - 1,x)となるのでこれで変換する。
実装時の注意点としては新しく配列を作らずに同じ配列でやった場合は、変換後の値で変換してしまうみたいな事態が発生したり
するので、自分のように別の配列を用意するか、何かしらうまくやる必要がある。

int N;
vector<string> row;
int Q, r[201010];
//---------------------------------------------------------------------------------------------------
vector<string> rotateClockwise(vector<string> g) {
    int n = g.size();
    int m = g[0].size();
    vector<string> res(m, string(n, '#'));
    rep(i, 0, n) rep(j, 0, m) res[j][n - i - 1] = g[i][j];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    row.resize(N);
    rep(i, 0, N) cin >> row[i];
    cin >> Q;
    rep(i, 0, Q) cin >> r[i];

    int cnt = 0;
    rep(i, 0, Q) {
        if (0 < r[i]) cnt++;
        else cnt += 3;
    }
    cnt %= 4;
    
    rep(i, 0, cnt) row = rotateClockwise(row);

    rep(i, 0, N) cout << row[i] << endl;
}