AGC023-B Find Symmetries

ブログの運営方針としてコンテスト後に毎回、問題を取り上げて解説をしていくことになったので今回はこれ

https://beta.atcoder.jp/contests/agc023/tasks/agc023_b

問題概要は直接見てください。

まずは、愚直解から考えてみよう。\(AとB\)をすべて試しそれが条件満たすかどうか調べてその数を数えるというものがある。\(AとB\)の選び方は\(N^{2}\)通り存在し、それが満たすかどうかを調べるにはすべてのマスのペアについて調べる必要があるので\(N^{2}\)かかる。よって合計で計算量は\(O(N^{4})\)となり、\(N  < 300\)なので\(TLE\)。

ここで、この問題を数式で表してみる。一つ目の盤面で\((i,j)\)にある文字は二つ目の盤面では\((i+A,j+B)\)に移動する。良い盤面であるということは二つ目の盤面で\((i’,j’)\)と\((j’,i’)\)の文字が等しいことなので、\((i+A,j+B)\)と\((j+B,i+A)\)の文字がすべて等しいことが条件である。ここで\((j+B,i+A)\)の文字は一つ目の盤面では\((j+B-A,i+A-B)\)にあることが分かるので、結果として、条件は一つ目の盤面で\((i,j)\)と\((j+B-A,i+A-B)\)に書いてある文字が等しいことに言い換えられる。

ここで\(B-A=k\) (\(-N < k < N\))と置くと、一つ目の盤面で\((i,j)\)と\((j+k,i-k)\)の文字が等しければ良く、\(B-A=k\)となる\(A,B\)をまとめることができた。また、\(k\)で条件を満たした時\(B-A=k\)となる\(A,B\)は\(N-|k|\)通りある。\(k\)は高々\(2 N\)通りなので合計の計算量は\(O(N^{3})\)となりこれは十分間に合う。

注意としては\(j+k,i-k\)が\(N\)を以上の場合、\(N\)で剰余をとる必要がある。また\(j+k,i-k\)は負になる可能性があるので剰余をとる際に(j+k+N)%N(j+k+N)%Nの様にしておく必要がある。(こうしておくと負にならない)

これは頻出のテクニックなので覚えておきましょう。

以下は解答例となります。

#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

int N;
string s[300];

bool check(int k){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(s[i][j]!=s[(j+N+k)%N][(i+N-k)%N]) return false;
        }
    }
    return true;
}

int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> s[i];
    }
    LL ans=0;
    for(int k=-(N-1);k<N;k++){
        if(check(k)){
            ans+=N-abs(k);
        }
    }
    cout << ans << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;

int N;
string s[300];

bool check(int k){
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(s[i][j]!=s[(j+N+k)%N][(i+N-k)%N]) return false;
        }
    }
    return true;
}

int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> s[i];
    }
    LL ans=0;
    for(int k=-(N-1);k<N;k++){
        if(check(k)){
            ans+=N-abs(k);
        }
    }
    cout << ans << endl;
    return 0;
}

計算量を落とすために同じものをまとめて計算するというのは基本的な考え方で、今回の問題の様に数式で表してみると簡単になる問題は多い気がする。