第1回swapコン 【ABC271 F問題の覚書き】

第1回swapコンの振り返り【ABC271】

みなさん、こんにちは。第1回swapコンの振り返りを投稿します。
swapコンの詳細はこちら: https://qiita.com/swapman/items/62e9fedc2a3e39b9d28c
結果としては、A-Eまではノーペナで行けたので、復習できているかなと感じました！(A-Eの解説はこちら: )
この記事では、自分が解けなかったF問題の解説を覚書として残したいと思います。それではいきましょう！

ABC271のリンク: https://atcoder.jp/contests/abc271

解説を見る前の僕の考察

問題を見ると、良さそうな性質とかは全く使えなそうなことがわかりますね。bit演算の基本として、桁ごとに独立に考えるというテーマはよく出るので、これにフォーカスして考えたところ次のような考えが浮かびました。各A[i][j]の値の制約を見ると、たかだか30桁しかないので、各桁ごとに、マス(i,j)にいる時、1の立っている個数(mod2)がkとなるような経路数を数えようと考えました。すなわちまとめると以下のようなdpを考えました。

dp[shift][i][j][k]: 各A[i][j]をshift桁右にシフトして、マス(i,j)に今いる時、1の立っている個数(mod2)がkとなるような経路数
しかし、実装がうまくいかず時間切れ...

解説を拝見

みなさんご存知かもしれませんが、snukeさんの解説も素晴らしいですが、かつっぱさんの解説も素晴らしいです。今回はかつっぱさんの実装を参考にした背景がありますので、私の説明がわかりにくい場合は、以下の動画をご覧になってください！

ABCC271のかつっぱさんの解説リンク： https://www.youtube.com/watch?v=CbJKcqNMIDI

考察

本題に立ち返ると、やはりこの問題に良さそうな性質は存在しないので全探索的なことをする必要があります。しかし考えられる手数は38 choose 19くらいになり、確実に間に合わないです。ここで大事な考え方になるのが、半分全列挙という考え方です。
今回の問題では、どのような経路をたどっても必ず対角線状のマスのいずれかを通ることになります。ここに注目して対角線でグリッドを半分に分割します。この時、スタート地点から対角線までの経路の全列挙を考えると、雑に見積もっても20 choose 10くらいになるので、前列挙することが可能です。これに加えて対角線を境に全く同じ構造を有していることから、数え上げる際は処理を共通化させることができそうなところも嬉しいです。このような観点から、この問題を半分全列挙で解きたくなります。

実装

ここまでわかればあとは実装です。かつっぱさんの実装を参考にして再帰関数で実装しました。

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using mint = modint998244353;
using C = complex<double>;
const int mod = 998244353;
const long long LINF = 1001002003004005006;
const int INF = 1001001001;
const double PI = acos(-1);
const double EPS = 1e-10;
const int di[4] = {-1,0,1,0};
const int dj[4] = {0,-1,0,1};
const int dx[8] = {1,1,1,0,0,-1,-1,-1};
const int dy[8] = {1,0,-1,1,-1,1,0,-1};
# define sz(x) (int)(x).size()
# define rsz(x,n) x.resize(n)
# define yes {puts("Yes"); return;}
# define no {puts("No"); return;}
# define dame {puts("-1"); return;}
# define yn {puts('Yes');} else{puts('No');}
# define ret(x) {cout << (x) << endl; return 0;}
# define ll long long
# define fi first
# define se second
# define vi vector<int>
# define vl vector<long long>
# define vs vector<string>
# define vb vector<bool>
# define vvi vector<vector<int>>
# define vvl vector<vector<long long>>
# define vvb vector<vector<bool>>
# define vpi vector<pair<int, int>>
# define vpl vector<pair<ll, ll>>
# define pb push_back
# define ps push
# define eb emplace_back
# define em emplace
# define pob pop_back
# define rep(i,n) for(int i = 0; i < n; i++)
# define srep(i, a, b) for(int i = a; i <= b; ++i)
# define all(obj) (obj).begin(), (obj).end()
# define rall(obj) (obj).rbegin(), (obj).rend()
# define _GLIBCXX_DEBUG
# define Pll pair<ll, ll>
# define P pair<int,int>
# define bit(x,i) (((x) >> (i)) & 1)
# define equals(a, b) (fabs((a) - (b)) < EPS) // 誤差を考慮した同値判定
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
template<typename T>istream& operator>>(istream&i,vector<T>&v){rep(j,v.size())i>>v[j];return i;}
template<typename T>string join(vector<T>&v){stringstream s;rep(i,v.size())s<<' '<<v[i];return s.str().substr(1);}
template<typename T>ostream& operator<<(ostream&o,vector<T>&v){if(v.size())o<<join(v);return o;}
template<typename T>ostream& operator<<(ostream&o,vector<vector<T>>&vv){if(vv.size())o<<join(vv);return o;}
using T = pair<P,ll>;

map<T,ll> mp;
map<T,ll> rmp;
int n;
vector<vector<ll>> a;
 
void dfs(int i, int j, ll XOR, ll cnt) {
    XOR ^= a[i][j];
    if(cnt == 0) {
        mp[{{i,j},XOR}]++;
        return;
    }
    if(i+1 < n) dfs(i+1,j,XOR,cnt-1);
    if(j+1 < n) dfs(i,j+1,XOR,cnt-1);
}

void rdfs(int i, int j, ll XOR, ll cnt) {
    XOR ^= a[i][j];
    if(cnt == 0) {
        rmp[{{i,j},XOR}]++;
        return;
    }
    if(i-1 >= 0) rdfs(i-1,j,XOR,cnt-1);
    if(j-1 >= 0) rdfs(i,j-1,XOR,cnt-1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    a.resize(n);
    rep(i,n) rep(j,n) {
        a[i].resize(n);
        cin >> a[i][j];
    }
    dfs(0,0,0,n-1);
    rdfs(n-1,n-1,0,n-1);
    ll ans = 0;
    for(auto [t,cnt] : mp) {
        auto [ij, x] = t;
        auto [i,j] = ij;
        ans += cnt * rmp[{{i,j},x ^ a[i][j]}];
    }
    cout << ans << endl;
}

この時、気をつけたいのが対角線上は二重に数えてしまっているので、対角線状の値で再び排他的論理和を取り直す必要があります。実験してみればわかりますが、A^B^A = Bです。これ僕は知りませんでした。(bit演算強くなりたい...)
dfsの部分がスタートから対角線まで、rdfsがゴールから対角線までの処理をそれぞれになっています。
やっていることとしてはシンプルで、マス(i,j)にXORという値が書き込まれていることをメモしていき、ゴールから対角線まで辿った時に全く同じ値が書かれている部分同士をペアにしていけば良いです。これの合計値を出力すれば答えです。

終わりに

今回この問題が解けなかったのは、半分全列挙を知らなかったからに尽きると思います。でも、全探索をしたい気持ちや桁ごとに独立であることから考察を始められるようになったのは、大きな成長だと思います。次見た時は、見抜いてやりたいです！！！
ってことで、今回は終わりにします。これからもこんな感じで、解けた部分の解説と、解けなかった部分の解説を分けて記事にしていきますので、僕がわかっていなさそうな部分とか怪しい部分があったら教えてください！それでは。