CSA Round #78 - omochan's diary

https://csacademy.com/contest/round-78/summary/

A
はい
B
set
C
dp[桁][Nより小さいか][桁を始めたか]の桁dp。典型らしい。
D
結合性( (a+b)+c=a+(b+c) )が成り立てばsegtreeにできるというやつ。

例えば
https://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_d
などがある。
http://d.hatena.ne.jp/DEGwer/20131211/1386757368
DEGwerさんのこの記事も役に立ちます。

今回はnodeにV[i][j]:=iからjに行く時の最大コストのようにすればsegtreeを構成できる。

最近2のべき乗で高速化する問題解いてなかったので全く思いつきませんでしたね…。DPテーブルいじったりダブリング考えてたらコンテスト終わりました。(ダブリングは結構いい線ではあったが)

int N;

struct node {
	ll V[5][5];
	node() {
		rep(i, 0, 5)
			rep(j, 0, 5) V[i][j] = -inf;
	}
};

node merge(const node& L, const node& R) {
	node res;
	rep(i, 0, 5) {
		rep(j, 0, 5) {
			rep(k, 0, 5) {
				MAX(res.V[i][k], L.V[i][j] + R.V[j][k]);
			}
		}
	}
	return res;
}

int M, Q;
ll A[5][50010];
node segtree[100010];

node start(int at) {
	node res;
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(abs(j - i) <= 1) {
				MAX(res.V[i][j], A[i][at]);
			}
		}
	}
	return res;
}

void update(int k, const node& v) {
	k += M - 1;
	segtree[k] = v;
	while(k > 0) {
		k = (k - 1) / 2;
		segtree[k] = merge(segtree[k * 2 + 1], segtree[k * 2 + 2]);
	}
}


void solve() {
	cin >> N >> M >> Q;
	rep(i, 0, N)
		rep(j, 0, M) cin >> A[i][j];

	int m = 1;
	while(m < M) m *= 2;
	M = m;

	rep(i, 0, M) segtree[i + M - 1] = start(i);

	rer(i, M - 1, 0) {
		segtree[i] = merge(segtree[i * 2 + 1], segtree[i * 2 + 2]);
	}
	while(Q--) {
		ll a, b, c;
		cin >> a >> b >> c; a--; b--;
		A[a][b] = c;
		update(b, start(b));
		node res = segtree[0];
		ll ans = 0;
		rep(i, 0, N) {
			rep(j, 0, N) {
				MAX(ans, res.V[i][j]);
			}
		}
		cout << ans << "\n";
	}
}

べつにそんな難しくはないですね…。
行列Bにtを2^k回作用させた時得られた行列Cについて、
C[0][0]=B[0][0]^B[2^k][0]^B[0][2^k]^B[2^k][2^k]となります。なので、
K回(0<=K<2^(k+1))tを作用させた行列を求めたい時、
K>=2^kなら、Bnext[i][j]=B[i][j]^B[i][j + 2^k]^B[i+2^k][j]+B[i + 2^k][j + 2^k]として、
BnextにtをK-2^k回作用させた行列を求めればよいです。
このBnextを求めるのには2^(2*k)*4回の演算が必要ですが、
今N*M<=5*10^6であり、Bnextは一回の計算でBの半分以下になるので、K'を2^K'<=max(N,M)を満たす最大の値とすれば、
0<=i<2^(K'+1)の全ての場合について求められます。
大きいKの場合は上のbitは無視できるので、結局O(1)/queryで求められます。

int N, M, Q, K; //(1 << K) <= max(N, M)
int ans[2000100];


void pre(int k, int bit, const vector<vector<int>>& A) {
	if(k == -1) {
		ans[bit] = A[0][0];
		return;
	}
	pre(k - 1, bit, A);
	int n = sz(A), m = sz(A[0]);
	int bk = (1 << k);
	int vn = min(n, bk);
	int vm = min(m, bk);
	vector<vector<int>> vec(vn, vector<int>(vm, 0));
	rep(i, 0, vn) {
		rep(j, 0, vm) {
			vec[i][j] ^= A[i][j];
			if(i + bk < n) vec[i][j] ^= A[i + bk][j];
			if(j + bk < m) vec[i][j] ^= A[i][j + bk];
			if(i + bk < n && j + bk < m) vec[i][j] ^= A[i + bk][j + bk];
		}
	}
	pre(k - 1, (bit | (1 << k)), vec);
}

void init(const vector< vector<int> >& A) {
	K = 0;
	while((1 << (K + 1)) <= max(N, M)) K++;
	pre(K, 0, A);
}

int query(int q) {
	q %= (1 << (K + 1));
	return ans[q];
}