seri::diary::competitive_programming

AtCoderで茶から赤を目指す競プロ精進日記

ABC218

1年3ヶ月ぶりにABCに出たのでブログを書くことにする.

atcoder.jp

結果

問題 ACまでに要した時間 AC WA TLE
A 2:23 1 0 0
B 2:29 1 0 0
C : 0 1 0
D : 0 0 0
E : 0 0 0
F : 0 0 0
新Rating Performance 順位
627 (-9) 553 4622

解答

C

 \mathcal{O} \left({N}^4\right) の解法しか思いつかず,そのままsubmitして見事TLEとWAも踏んだ.WAになったのは恐らく平行移動の探索範囲が甘いか何かだと思われる.

ダメ実装

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<vector<char>> S(N, vector<char>(N));
  vector<vector<char>> S90(N, vector<char>(N));
  vector<vector<char>> S180(N, vector<char>(N));
  vector<vector<char>> S270(N, vector<char>(N));
  int s_count = 0;
  REP(i, N) {
    REP(j, N) {
      cin >> S.at(i).at(j);
      S90.at(j).at(N - 1 - i) = S.at(i).at(j);
      S180.at(N - 1 - i).at(N - 1 - j) = S.at(i).at(j);
      S270.at(N - 1 - j).at(i) = S.at(i).at(j);
      if (S.at(i).at(j) == '#') {
        ++s_count;
      }
    }
  }


  vector<vector<char>> T(N, vector<char>(N));
  int t_count = 0;
  REP(i, N) {
    REP(j, N) {
      cin >> T.at(i).at(j);
      if (T.at(i).at(j) == '#') {
        ++t_count;
      }
    }
  }

  if (s_count != t_count) {
    cout << "No" << endl;
    return 0;
  }

  REP(i, N * 2 - 2) {
    REP(j, N * 2 - 2) {
      int match_count = 0;
      REP(k, i + 1) {
        REP(l, j + 1) {
          if ((0 <= (N - 1 - k) && (N - 1 - k) <= N - 1) &&
              (0 <= (N - 1 - l) && (N - 1 - l) <= N - 1) &&
              (0 <= (i - k) && (i - k) <= N - 1) &&
              (0 <= (j - l) && (j - l) <= N - 1)) {
            if (S.at(N - 1 - k).at(N - 1 - l) == '#' &&
                T.at(i - k).at(j - l) == '#') {
              ++match_count;
            }
          }
        }
      }
      if (s_count == match_count) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  // Sを90度右回転
  REP(i, N * 2 - 2) {
    REP(j, N * 2 - 2) {
      int match_count = 0;
      REP(k, i + 1) {
        REP(l, j + 1) {
          if ((0 <= (N - 1 - k) && (N - 1 - k) <= N - 1) &&
              (0 <= (N - 1 - l) && (N - 1 - l) <= N - 1) &&
              (0 <= (i - k) && (i - k) <= N - 1) &&
              (0 <= (j - l) && (j - l) <= N - 1)) {
            if (S90.at(N - 1 - k).at(N - 1 - l) == '#' &&
                T.at(i - k).at(j - l) == '#') {
              ++match_count;
            }
          }
        }
      }
      if (s_count == match_count) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  // Sを180度右回転
  REP(i, N * 2 - 2) {
    REP(j, N * 2 - 2) {
      int match_count = 0;
      REP(k, i + 1) {
        REP(l, j + 1) {
          if ((0 <= (N - 1 - k) && (N - 1 - k) <= N - 1) &&
              (0 <= (N - 1 - l) && (N - 1 - l) <= N - 1) &&
              (0 <= (i - k) && (i - k) <= N - 1) &&
              (0 <= (j - l) && (j - l) <= N - 1)) {
            if (S180.at(N - 1 - k).at(N - 1 - l) == '#' &&
                T.at(i - k).at(j - l) == '#') {
              ++match_count;
            }
          }
        }
      }
      if (s_count == match_count) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }
  // Sを270度右回転
  REP(i, N * 2 - 2) {
    REP(j, N * 2 - 2) {
      int match_count = 0;
      REP(k, i + 1) {
        REP(l, j + 1) {

          if ((0 <= (N - 1 - k) && (N - 1 - k) <= N - 1) &&
              (0 <= (N - 1 - l) && (N - 1 - l) <= N - 1) &&
              (0 <= (i - k) && (i - k) <= N - 1) &&
              (0 <= (j - l) && (j - l) <= N - 1)) {

            if (S270.at(N - 1 - k).at(N - 1 - l) == '#' &&
                T.at(i - k).at(j - l) == '#') {
              ++match_count;
            }
          }
        }
      }

      if (s_count == match_count) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;

  return 0;
}

愚直に並行移動させて一致性を確認しても解けなくはなかったようだが,その場合 # の座標だけのリストを事前に作っておいて探索対象を狭める足切りをしないと解けなかったようだ.

競プロフレンズさんの解説をもとに実装し直したやつ

#include <bits/stdc++.h>

#define REP(i, x) REPI(i, 0, x)
#define REPI(i, a, b) for (int i = int(a); i < int(b); ++i)
#define ALL(x) (x).begin(), (x).end()

typedef long long ll;
using namespace std;

pair<int, int> find_left_top(vector<vector<char>> a, int n) {
  REP(i, n) {
    REP(j, n) {
      if (a.at(i).at(j) == '#') {
        return make_pair(i, j);
      }
    }
  }

  return make_pair(-1, -1);
}

bool judge(vector<vector<char>> s, vector<vector<char>> t, int n) {
  pair<int, int> s_left_top = find_left_top(s, n);
  pair<int, int> t_left_top = find_left_top(t, n);
  int offset_i = t_left_top.first - s_left_top.first;
  int offset_j = t_left_top.second - s_left_top.second;
  // cout << offset_i << ":" << offset_j << endl;
  REP(i, n) {
    REP(j, n) {
      int ii = i + offset_i;
      int jj = j + offset_j;

      // Tにオフセットをつけてアクセスすることで,並行移動した状態でアクセスできる.賢い.
      if ((0 <= ii && ii < n) && (0 <= jj && jj < n)) {
        if (s.at(i).at(j) != t.at(ii).at(jj)) {
          return false;
        }
      } else {
        // Tの範囲外に#があったら一致する可能性がゼロになるので探索を打ち切る
        if (s.at(i).at(j) == '#') {
          return false;
        }
      }
    }
  }

  return true;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int N;
  cin >> N;
  vector<vector<char>> S(N, vector<char>(N));
  int s_count = 0;
  REP(i, N) {
    REP(j, N) {
      cin >> S.at(i).at(j);
      if (S.at(i).at(j) == '#') {
        ++s_count;
      }
    }
  }

  vector<vector<char>> T(N, vector<char>(N));
  int t_count = 0;
  REP(i, N) {
    REP(j, N) {
      cin >> T.at(i).at(j);
      if (T.at(i).at(j) == '#') {
        ++t_count;
      }
    }
  }

  if (s_count != t_count) {
    cout << "No" << endl;
    return 0;
  }

  auto rotate = [](vector<vector<char>> a) {
    long n = a.size();
    vector<vector<char>> b(n, vector<char>(n));
    REP(i, n) {
      REP(j, n) { b.at(i).at(j) = a.at(n - 1 - j).at(i); }
    }
    return b;
  };

  REP(_, 4) {
    S = rotate(S);
    if (judge(S, T, N)) {
      cout << "Yes" << endl;
      return 0;
    }
  }

  cout << "No" << endl;

  return 0;
}

ダメだった点

久々だったのでだいぶカンが鈍っている.

良かった点

CV系問題はまだ苦手だが画像の回転と一致性の確認をする方法が学べた.

おわりに

また精進して位置から出直して緑を目指す.