2021年9月11日に開催された AtCoder Beginner Contest 218（ABC218） に参加しました。

AtCoder Beginner Contest 218 – AtCoder

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

結果は以下の通りでした。

• 2完（A,B） 0WA
• 順位: 4494位
• パフォーマンス: 579
• レーティング: 720 → 707

ここではC問題について復習します。

C問題について

問題等は以下のリンクをご確認ください。

C – Shapes

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

コンテスト中に思いついた手順は、以下の通りです。

1. Sは固定して、Tを90回転、平行移動させて、SとTが一致すればいい。
2. そこでまず、Tについて 90度回転させたもの（T1）、180度回転させたもの(T2)、270度回転させたもの(T2)をつくる関数を作る。
   90度回転させる関数と、180度回転させる関数を作れば、T1,T2,T3は作れる。
3. 次に、SとT、T1、T2、T3それぞれを一致チェックする関数を作る。上下左右、グリッドの端をまだく場合に注意する。

配列を回転させる関数はなんとか作れました。しかし、Tの平行移動についてもグリッドの端を過ぎたら、はみ出た部分は反対側に出ると考えていたので、実装してもWAでした。

「グリッド内にあり」ということは、グリッドの端までしか移動できないということです。テトリスみたいな感じだと思います。すなわち、グリッドの端をまだく場合は考えなくてよかったのです。端をまたがないということは、T（T1、T2、T3）の形は変わりません。平均移動によって形が変わらないということは、形さえ一致していればよく、平均移動は考えなくてよさそうです。

以上より、考え直した手順は以下の通りです。

1. Sは固定して、Tを90回転、平行移動させて、SとTが一致すればいい。
2. Sについては「#」の外側の「.」だけの行や列はいらないのでそれらを削る関数を作る。
3. 次に、Tについて 90度回転させたもの（T1）、180度回転させたもの(T2)、270度回転させたもの(T2)をつくる関数を作る（これは上記のまま）。
4. そして、T、T1、T2、T3それぞれを2.で作った関数で「#」の外側の「.」だけの行や列を削ったものとSを比較する。

この手順をもとに実装し、ACしたコードが以下になります。
*コメントは記事作成時に追記しています。

反省してACしたコードは以下になります。

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// const int mod = 1000000007;
// const ll INF = 1LL<<60;
// const int INF = 1001001001;
int N;

// 90度回転させた配列を返す
vector<string> r1(vector<string> A) {
  vector<string> result(N);
  rep(j, N) {
    string t = "";
    rep(i, N) { t += A[N - i - 1][j]; }
    result[j] = t;
  }
  return result;
}

// 180度回転させた配列を返す
vector<string> r2(vector<string> A) {
  vector<string> result(N);
  rep(i, N) {
    string t = "";
    rep(j, N) { t += A[N - i - 1][N - j - 1]; }
    result[i] = t;
  }
  return result;
}

// #の外側の.だけの行や列を削った配列を返す
vector<string> r3(vector<string> A) {
  int minX = N;
  int minY = N;
  int maxX = 0;
  int maxY = 0;
  rep(i, N) {
    rep(j, N) {
      if(A[i][j] == '#') {
        minX = min(minX, j);
        minY = min(minY, i);
        maxX = max(maxX, j);
        maxY = max(maxY, i);
      }
    }
  }
  vector<string> result;
  for(int i = minY; i <= maxY; ++i) {
    string s_ = "";
    for(int j = minX; j <= maxX; ++j) {
      s_ += A[i][j];
    }
    result.push_back(s_);
  }
  return result;
}

int main() {
  cin >> N;

  vector<string> S(N);
  rep(i, N) { cin >> S[i]; }

  vector<string> T(N);
  rep(i, N) cin >> T[i];

　// Sから#の外側の.だけの行や列を削る
  vector<string> S2 = r3(S);

  // Tから#の外側の.だけの行や列を削る
  vector<string> T_ = r3(T);

  // 一致の確認
  if(S2 == T_) {
    cout << "Yes" << endl;
    return 0;
  }

　// Tを90度回転させる
  vector<string> T1 = r1(T);

  // T1から#の外側の.だけの行や列を削る
  T_ = r3(T1);

  // 一致の確認
  if(S2 == T_) {
    cout << "Yes" << endl;
    return 0;
  }

  // Tを180度回転させる
  vector<string> T2 = r2(T);

  // T2から#の外側の.だけの行や列を削る
  T_ = r3(T2);

  // 一致の確認
  if(S2 == T_) {
    cout << "Yes" << endl;
    return 0;
  }

  // T1を180度回転させる
  vector<string> T3 = r2(T1);

  // T3から#の外側の.だけの行や列を削る
  T_ = r3(T3);

  // 一致の確認
  if(S2 == T_) {
    cout << "Yes" << endl;
    return 0;
  }

  cout << "No" << endl;
  return 0;
}

自分にとってこの問題は、実装量が多かったかもしれませんが、よく読んで落ち着いたらコンテスト中にACしないといけない問題だったなぁと思います。

WAがなかなか取れないときは問題文をもう一度確認するというチェックを忘れないようにしよう。