実数\(a_1, \ldots, a_n\)がすべて同じである必要十分条件は

\[ n\sum_{i=1}^n a_i^2=\left( \sum_{i=1}^n a_i\right)^2. \]

これはコーシー＝シュワルツの不等式で証明できます。

この事実を用いると、各英小文字をそれぞれのASCIIコードに置き換え、各行・各列の要素の和と二乗和を管理すれば、evimaの解法と同じ\(O((H+W)^2)\)の時間で解けます。

C++コード (44ms, 3840KB)

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
ll square(ll x){
    return x*x;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    //以上為輸入輸出流速度優化
    int H, W;
    cin >> H >> W;
    vector<pair<ll, ll>> row_sum(H, {0, 0});
    vector<pair<ll, ll>> column_sum(W, {0, 0});
    for(int i=0;i<H;i++){
        string s;
        cin >> s;
        for(int j=0;j<W;j++){
            int ind=s[j]-'a';
            row_sum[i].first+=ind;
            row_sum[i].second+=ind*ind;
            column_sum[j].first+=ind;
            column_sum[j].second+=ind*ind;
        }
    }
    pair<ll, ll> row_sum_delta={0, 0};
    pair<ll, ll> column_sum_delta={0, 0};
    while(true){
        vector<int> index_rowToDelete;
        vector<int> index_columnToDelete;
        ll column_sum_delta1=0;
        ll column_sum_delta2=0;
        if(W>1){
            for(int i=0;i<H;i++){
                if((row_sum[i].second-row_sum_delta.second)*W==square(row_sum[i].first-row_sum_delta.first)){
                    index_rowToDelete.push_back(i);
                    int ind=(row_sum[i].first-row_sum_delta.first)/W;
                    column_sum_delta1+=ind;
                    column_sum_delta2+=square(ind);
                }
            }
        }
        if(H>1){
            for(int i=0;i<W;i++){
                if((column_sum[i].second-column_sum_delta.second)*H==square(column_sum[i].first-column_sum_delta.first)){
                    index_columnToDelete.push_back(i);
                    int ind=(column_sum[i].first-column_sum_delta.first)/H;
                    row_sum_delta.first+=ind;
                    row_sum_delta.second+=square(ind);
                }
            }
        }
        if(index_rowToDelete.empty() && index_columnToDelete.empty()){
            cout << H*W;
            return 0;
        }
        //改H, W, row_sum, column_sum
        column_sum_delta.first+=column_sum_delta1;
        column_sum_delta.second+=column_sum_delta2;
        vector<pair<ll, ll>> new_row_sum;
        vector<pair<ll, ll>> new_column_sum;
        for(int i=0, ind=0;i<H; i++){
            if(ind<index_rowToDelete.size() && i==index_rowToDelete[ind]){
                ind++;
            }
            else{
                new_row_sum.push_back(row_sum[i]);
            }
        }
        for(int j=0, ind=0;j<W;j++){
            if(ind<index_columnToDelete.size() && j==index_columnToDelete[ind]){
                ind++;
            }
            else{
                new_column_sum.push_back(column_sum[j]);
            }
        }
        row_sum=new_row_sum;
        column_sum=new_column_sum;
        H=row_sum.size();
        W=column_sum.size();
    }
    return 0;
}