ARC 073 F (嘘解法)

想定解法は segment tree だが、O(N^2) の DP を、隣の状態より strict に良い状態だけを残すような枝刈りしても通る。

発見した中でのワーストケースでは、
与えられる点が、
200000, 1, 100000, 50000, 75000, ...
のときに、保持する必要がある状態数が 20 近くになる。

#define N 200010
ll n, q, c, x[N];
set<P> dp[2];

int main(){
	cin>>n>>q>>x[0]>>c;
	rep(i, q) cin>>x[i+1];
	dp[0].insert(P(c, 0));
	for(int i = 1; i <= q; i++){
		int t = i%2;
		dp[t].clear();
		for(auto p: dp[!t]){
			dp[t].insert(P(x[i-1], p.snd+abs(x[i]-p.fst)));
			dp[t].insert(P(p.fst, p.snd+abs(x[i]-x[i-1])));
		}
		{
			auto it = dp[t].begin(), it2 = it; ++it2;
			while(it2!=dp[t].end()){
				while(it2!=dp[t].end() && it->snd+abs(it->fst-it2->fst)<=it2->snd){
					dp[t].erase(it2);
					it2 = it;
					++it2;
				}
				++it;
				if(it2!=dp[t].end()) ++it2;
			}
		}
		{
			auto it = dp[t].end();
			if(it!=dp[t].begin()) --it;
			auto it2 = it;
			if(it!=dp[t].begin()) --it2;
			while(it!=dp[t].begin()){
				while(it!=dp[t].begin() && it->snd+abs(it->fst-it2->fst)<=it2->snd){
					dp[t].erase(it2);
					it2 = it;
					if(it2!=dp[t].begin()) --it2;
				}
				if(it!=dp[t].begin()){
					--it;
					if(it2!=dp[t].begin()) --it2;
				}
			}
		}
	}
	ll res = 1e17;
	for(auto p: dp[q%2]) res = min(res, p.snd);
	cout<<res<<endl;
	return 0;
}

SRM 568 Div1Med EqualsSum

問題

一部の成分が指定されているN*N行列が与えられる.
が一定で全ての成分が非負整数になるような割り当ての個数を1e+7で割った余りを求める.

解法

Editorial と違う解法で解いた.

のうち、3つが既知のとき、残りの1つも一意に定まるので、その成分をあらかじめ決定しておく.

列ベクトル を考えると は一定になっている.
行ベクトルに対しても同様なので, それらの列/行を消去して, 各列/行 には高々1つの成分が指定されていないように行列を変形できる.(全ての成分は0以上であり、小さい方のベクトルが本質なので, 小さい方のベクトルを残す)
また、1つの成分も指定されていない行があるとき, 解は無限大になるから各列/行は丁度1つの成分が指定されていることが言える.
(対角成分だけ指定されていて、他は指定されていない行列が得られる)

を基準にして, 列/行の差の最小値を状態としてもつDPをすると解が求まる.

コード

#define N 55
ll mod = 1000000007;
ll dp[N][30][30];
ll z[N];

class EqualSums {
public:
	int count( vector <string> g) {
		int n = g.size();
		vector<vector<int> > v(n, vector<int>(n, -1));
		rep(i, n) rep(j, n) if(g[i][j]!='-') v[i][j] = g[i][j]-'0';
		rep(_, n) rep(i, n) rep(j, n){
			if(v[i][j]<0) continue;
			rep(k, n) rep(l, n){
				if(v[k][l]<0) continue;
				int a = v[i][j]+v[k][l];
				if(v[i][l]>=0){
					int b = a-v[i][l];
					if(b<0 || v[k][j]>=0 && v[k][j]!=b) return 0;
					v[k][j] = b;
				} else if(v[k][j]>=0){
					int b = a-v[k][j];
					if(b<0 || v[i][l]>=0 && v[i][l]!=b) return 0;
					v[i][l] = b;
				}
			}
		}
		int m = n;
		rep(i, m) rep(j, i) rep(k, n){
			if(v[i][k]>=0 && v[j][k]>=0){
				if(v[i][k]<v[j][k]) swap(v[i], v[j]);
				swap(v[i], v[m-1]);
				m--;
				i--; j = n; break;
			}
		}
		int m2 = n;
		rep(i, m2) rep(j, i) rep(k, m){
			if(v[k][i]>=0 && v[k][j]>=0){
				if(v[k][i]<v[k][j]) rep(l, m) swap(v[l][i], v[l][j]);
				rep(l, m) swap(v[l][i], v[l][m2-1]);
				m2--;
				i--; j = n; break;
			}
		}
		n = m;
		rep(i, n){
			if(v[i][i]>=0) continue;
			for(ll j = i; j < n; j++) for(ll k = i; k < n; k++){
				if(v[j][k]>=0){
					if(i!=j) swap(v[i], v[j]);
					if(i!=k) for(ll l = i; l < n; l++) swap(v[l][i], v[l][k]);
					j = k = n; break;
				}
			}
		}
		int V = v[0][0];
		rep(i, n-1) z[i] = v[i+1][i+1]-V;
		mset(dp, 0);
		dp[0][0][0] = 1;
		rep(i, n-1){
			rep(j, V+1) rep(k, V+1){
				for(ll l = -V; z[i]-l >= -V; l++){
					(dp[i+1][max(j, -l)][max(k, -(z[i]-l))]+=dp[i][j][k])%=mod;
				}
			}
		}
		ll res = 0;
		rep(i, V+1) rep(j, i+1) (res+=dp[n-1][j][i-j])%=mod;
		return res;
	}
};

AOJ 0563: Walking Santa

問題

を満たすx, y, v を求める

解法

maxの項が存在しない場合は、各軸で考えて、中央値を選べば良く、Nが偶数のときは、中央の2つの値の間の値であればどれでもよい。Nが奇数のときは一意に定まる。
maxの項が存在する場合の解は、上の問題の解のどれかであり、端点だけ調べれば良い。
計算量は、O(NlogN) (O(N)にもできる)

コード

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int main(){
	ll h, w, n;
	scanf("%ld%ld%ld",&h,&w,&n);
	vector<ll> x(n),y(n);
	vector<P> p(n);
	for(int i = 0; i < n; i++){
		scanf("%ld%ld",&x[i],&y[i]);
		p[i] = P(x[i], y[i]);
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	ll rx, ry, rv = -1;
	for(int i = 0; i < 4; i++){
		ll ax = x[(n-1+i/2)/2], ay = y[(n-1+i%2)/2];
		ll mx = 0;
		for(int j = 0; j < n; j++)
			mx = max(mx, abs(ax-p[j].first)+abs(ay-p[j].second));
		if(rv<mx){
			rx = ax;
			ry = ay;
			rv = mx;
		}
	}
	ll res = -rv;
	for(int i = 0; i < n; i++)
		res += 2*(abs(rx-x[i])+abs(ry-y[i]));
	printf("%ld\n%ld %ld\n", res, rx, ry);
	return 0;
}

AOJ 2554 : encode/decode

解法

固有値が2の時の固有ベクトルを求めて、適当にグラフを作ると、後ろから辿ることで状態を復元できる

#include <iostream>
#include <string>
#include <map>
#include <algorithm>
using namespace std;
typedef pair<char, int> State;
 
map<pair<State, int>, State> f;
map<pair<State, char>, pair<State, int> > g;
#define M 9
int deg[M] = {3, 6, 4, 2, 5, 4, 3, 2, 1};
 
void next(State &s, int a){
    char &c = s.first;
    int &p = s.second;
    if(c == 'A'){
        c = 'B';
        p = 2 * p + a;
    } else if(c == 'B'){
        if(p < 2){
            c = 'C';
            p = 2 * p + a;
        } else {
            p = 2 * (p-2) + a;
            if(p < 3) c = 'A';
            else {
                c = 'E';
                p -= 3;
            }
        }
    } else if(c == 'C'){
        if(p == 3){
            c = 'D';
            p = a;
        } else {
            c = 'B';
            p = 2 * p + a;
        }
    } else if(c == 'D'){
        c = 'C';
        p = 2 * p + a;
    } else if(c == 'E'){
        if(p < 4){
            c = !a?'B':'F';
        } else {
            c = 'B';
            p = p + a;
        }
    } else if(c == 'F'){
        if(p < 3){
            c = !a?'E':'G';
        } else {
            c = 'E';
            p = p + a;
        }
    } else if(c == 'G'){
        if(p < 2){
            c = !a?'F':'H';
        } else {
            c = 'F';
            p = p + a;
        }
    } else if(c == 'H'){
        if(p < 1){
            c = !a?'G':'I';
        } else {
            c = 'G';
            p = p + a;
        }
    } else {
        c = 'H';
        p = a;
    }
}
 
int main(){
    for(int i = 0; i < M; i++){
        for(int j = 0; j < deg[i]; j++){
            State a = State('A'+i, j);
            for(int k = 0; k < 2; k++){
                State b(a);
                next(b, k);
                f[make_pair(a, k)] = b;
                g[make_pair(b, 'A'+i)] = make_pair(a, k);
                //cerr<<"f("<<a.first<<","<<a.second<<","<<k<<") = "<<b.first<<","<<b.second<<endl;
            }
        }
    }
    string query, s, t;
    int n;
    cin>>query>>n>>s;
    if(query == "encode"){
        t = s[0]=='0'?"A":"B";
        State a('A'+s[0]-'0', 0);
        //cerr<<a.first<<" "<<a.second<<endl;
        for(int i = 1; i < n; i++){
            a = f[make_pair(a, s[i]-'0')];
            //cerr<<a.first<<" "<<a.second<<endl;
            t += a.first;
        }
        //cerr<<endl;
        for(int i = 0; i < 10; i++){
            a = f[make_pair(a, 1)];
            t += a.first;
            //cerr<<a.first<<" "<<a.second<<endl;
        }
        cout<<t<<endl;
    } else {
        State a;
        for(int j = deg[s[n-1]-'A']-1; j >= 0; j--){
            a = State(s[n-1], j);
            //cerr<<a.first<<" "<<a.second<<endl;
            for(int i = 1; i <= 10; i++){
                pair<State, char> q(make_pair(a, s[n-i-1]));
                if(g.count(q) == 0) break;
                a = g[q].first;
            //cerr<<a.first<<" "<<a.second<<endl;
                if(g[q].second == 0) break;
                if(i==10){
                    j = 0;
                }
            }
        }
        //cerr<<a.first<<" "<<a.second<<endl;
        for(int i = 11; i < n; i++){
            pair<State, char> q(make_pair(a, s[n-i-1]));
            pair<State, int> o = g[q];
            a = o.first;
            t += '0'+o.second;
            //cerr<<a.first<<" "<<a.second<<endl;
        }
        t += s[0]=='A'?'0':'1';
        reverse(t.begin(), t.end());
        cout<<t<<endl;
    }
    return 0;
}

AOJ 2230: How to Create a Good Game

LPであることと、フローっぽいことはなんとなく分かるけど、最小費用流のLP双対の形にするのが少し難しいので、1100妥当だと思う。

解法

最小費用流の双対なので、変形してから流す。
ネットワークが少し特殊な形をしてるけど、蟻本とかで調べるとやり方が書いてある。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<long, long> P;
#define V 10010
long INF2 = 400000, INF = 1e9;

struct edge {
  long to, cap, cost, rev;

};
typedef vector<edge> vertex;
typedef vector<vertex> graph;
long dist[V];
long h[V];
long prevv[V], preve[V];

vertex g[V];

void add_edge(int from, int to, int cap, int cost){
	//cout<<from<<" "<<to<<" "<<cap<<" "<<cost<<endl;
	g[from].push_back((edge){to, cap, cost, (int)g[to].size()});
	g[to].push_back((edge){from, 0, -cost, (int)g[from].size()-1});
}

long min_cost_flow(int s, int t, long f){
	long res = 0;
	fill(h, h+V, 0);
	for(int i = 0; i < V; i++){
		for(int j = 0; j < g[i].size(); j++){
			edge &e = g[i][j];
			if(e.cap == 0) continue;
			int u = e.to;
			h[u] = min(h[u], h[i]+e.cost);
		}
	}
	while(f>0){
		priority_queue<P, vector<P>, greater<P> > q;
		fill(dist, dist+V, INF);
		dist[s] = 0;
		q.push(P(0,s));
		while(!q.empty()){
			P p = q.top(); q.pop();
			int v = p.second;
			if(dist[v] < p.first) continue;
			for(int i = 0; i < g[v].size(); i++){
				edge &e = g[v][i];
				if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
					dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
					prevv[e.to] = v;
					preve[e.to] = i;
					q.push(P(dist[e.to],e.to));
				}
			}
		}
		for(int v = 0; v < V; v++)h[v] += dist[v];

		long d = f;
		for(int v = t; v != s; v = prevv[v]){
			d = min(d, g[prevv[v]][preve[v]].cap);
		}
		f -= d;
		res += d*h[t];
		for(int v = t; v != s; v = prevv[v]){
			edge &e = g[prevv[v]][preve[v]];
			e.cap -= d;
			g[v][e.rev].cap += d;
		}
	}
	return res;
}

#define N 1100
long f[N][N];
long d[N];

int main(){
	int n, m;
	scanf("%d%d",&n,&m);
	int s = 0, t = n-1, t2 = n;
	for(int i = 0; i < n; i++) fill(f[i], f[i]+N, INF);
	for(int i = 0; i < m; i++){
		int x, y, c;
		scanf("%d%d%d",&x,&y,&c);
		c *= -1;
		f[x][y] = c;
		add_edge(x, y, INF, c);
		add_edge(x, y, 1, c-INF2);
	}
	for(int k = 0; k < n; k++)
		for(int i = 0; i < n; i++)
			for(int j = 0; j < n; j++)
				f[i][j] = min(f[i][j], f[i][k]+f[k][j]);
	add_edge(t, t2, INF, -f[0][n-1]);
	long res = min_cost_flow(s, t2, INF2);
	res += INF2*m;
	printf("%ld\n", res);
	return 0;
}

AOJ 2453 : Presentation

解法

木のサイズに関する自明な枝刈りをすると計算量が落ちるから、頑張って実装する。
木を作ったり判定したりするのが大変なので工夫すると比較的楽に実装できる。
判定するときは、queueを3つくらい使うと綺麗に実装できる。

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
#define N 500000
int h[N], t[N], c[N][2], d[N];

int main(){
	memset(c, -1, sizeof(c));
	string s;
	cin>>s;
	int n = s.size();
	int m = (n-2)/4;
	int L = 1, R = n-1, mx = 0;
	for(int i = L; i <= R; i++){
		h[i] = h[i-1]+(s[i]=='('?1:-1);
		if(s[i]=='('){
			c[t[h[i]-1]][s[i-1]!='('] = i;
			t[h[i]] = i;
			mx = max(mx, h[i]);
		}
	}
	int p2 = t[mx], p1 = p2-3, p3 = p2+1;
	d[1] = 1;
	while(p1>1){
		int ht = h[p3];
		p1--; p3++;
		if(h[p1-1]>h[p1]){
			p1--;
			while(h[p1]>=ht) p1--;
		}
		else {
			p3++;
			while(h[p3]>=ht) p3++;
		}
		int sz = (p3-p1)/4;
		if(m%sz == 0){
			queue<int> q1, q2, q3;
			q3.push(0);
			bool ok = true;
			while(!q3.empty() && ok){
				q1.push(q3.front()); q3.pop();
				q2.push(p1);
				while(!q1.empty()){
					int r1 = q1.front(); q1.pop();
					int r2 = q2.front(); q2.pop();
					int c10 = c[r1][0], c11 = c[r1][1];
					int c20 = c[r2][0], c21 = c[r2][1];
					if(c10<0&&c20>=0 || c11<0&&c21>=0){
						ok = false;
						break;
					}
					if(c10>=0&&c20<0&&c11>=0&&c21<0) q3.push(r1);
					if(c20>=0){
						q1.push(c10);
						q2.push(c20);
					}
					if(c21>=0){
						q1.push(c11);
						q2.push(c21);
					}
				}
			}
			if(ok){
				d[sz] = m;
				for(int i = 1; i <= sz; i++){
					if(sz%i || !d[i]) continue;
					d[sz] = min(d[sz], d[i]+sz/i-1);
				}
			}
		}
	}
	
	int res = N;
	for(int i = 1; i <= m; i++){
		if(m%i || !d[i]) continue;
		res = min(res, d[i]+m/i-1);
	}
	cout<<res-1<<endl;

	return 0;
}

AOJ 2231 : Cruel Bingo

解法

包除原理+DP

包除原理に気づかずbitDPしようとしたら複雑すぎて無理だった(解説スライド見ても解けるとしか書いてなかった)
あと、解説スライド見ると包除原理だけで良いらしい(ちょっと読んでもよく分からなかった)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long ll;
#define N 40
#define M 8
ll ux[N], uy[N], g[N][N], dp[N][N][4], dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
ll mod = 10007;
int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	int s = n&1, t = n/2, t2 = (n-1)/2;
	for(int i = 0; i < m; i++){
		int x, y;
		scanf("%d%d",&x,&y);
		ux[x] |= 1<<i;
		uy[y] |= 1<<i;
	}
	ll res = 0;
	for(int i = 0; i < 1<<m; i++){
		int bt = __builtin_popcount(i);
		int dg = 0;
		bool ok = true;
		for(int j = 0; j < n; j++){
			if(__builtin_popcount(ux[j]&i)>1 || __builtin_popcount(uy[j]&i)>1){
				ok = false;
			}
			for(int k = 0; k < n; k++){
				g[j][k] = (ux[j]|uy[k])&i;
				if(ux[j]&uy[k]&i){
					if(j==k) dg |= 1;
					if(j==n-k-1) dg |= 2;
				}
			}
		}
		if(!ok) continue;
		memset(dp, 0, sizeof(dp));
		dp[0][bt][dg] = 1;
		if(s&&!g[t][t]) dp[0][bt+1][3] = 1;
		for(int j = 1; j <= t; j++){
			int left = t-j;
			int len = 2*j+s;
			int fr[4] = {}, fr2[4] = {};
			for(int k = 0, a = left, b = left; k < 4; k++){
				for(int l = 0; l < len-1; l++, a+=dx[k], b+=dy[k]){
					if(!g[a][b]){
						if(l==0) fr2[k] = 1;
						else fr[k]++;
					}
				}
			}
			for(int k = bt; k <= n; k++){
				int ms = k-bt;
				int fr3[4], fr4[2];
				for(int l = 0; l < 4; l++) fr3[l] = max(0, fr[l]-ms);
				fr4[0] = max(0, fr3[0]*(fr3[2]-1));
				fr4[1] = max(0, fr3[1]*(fr3[3]-1));
				for(int l = 0; l < 4; l++){
					int dd = dp[j-1][k][l];
					(dp[j][k][l]+=dd)%=mod;
					(dp[j][k+1][l]+=(fr3[0]+fr3[1]+fr3[2]+fr3[3])*dd)%=mod;
					(dp[j][k+1][l|1]+=(fr2[0]+fr2[2])*dd)%=mod;
					(dp[j][k+1][l|2]+=(fr2[1]+fr2[3])*dd)%=mod;
					(dp[j][k+2][l]+=(fr3[0]*fr3[1]+fr4[0]+fr3[0]*fr3[3]+fr3[1]*fr3[2]+fr4[1]+fr3[2]*fr3[3])*dd)%=mod;
					(dp[j][k+2][l|1]+=(fr2[0]*(fr3[1]+fr3[2])+fr2[2]*(fr3[3]+fr3[0])+fr2[0]*fr2[2])*dd)%=mod;
					(dp[j][k+2][l|2]+=(fr2[1]*(fr3[2]+fr3[3])+fr2[3]*(fr3[0]+fr3[1])+fr2[1]*fr2[3])*dd)%=mod;
					(dp[j][k+3][l]+=(fr4[0]*(fr3[1]+fr3[3])+fr4[1]*(fr3[0]+fr3[2]))*dd)%=mod;
					(dp[j][k+3][l|1]+=(fr2[0]*(fr3[1]*fr3[2])+fr2[2]*(fr3[3]*fr3[0]))*dd)%=mod;
					(dp[j][k+3][l|2]+=(fr2[1]*(fr3[2]*fr3[3])+fr2[3]*(fr3[0]*fr3[1]))*dd)%=mod;
					(dp[j][k+4][l]+=(fr4[0]*fr4[1])*dd)%=mod;
				}
			}
		}
		(res+=dp[t][n][3]*(bt&1?-1:1))%=mod;
	}
	printf("%ld\n",(res+mod)%mod);

	return 0;
}