読者です 読者をやめる 読者になる 読者になる

SRM 633

Hardはどうせ2-SATなので解いてもここに載せる気が起きない。

250:危険なアレ
Medium openなので難しいということを事前にわかって開けた。難しいと分かっているのでゆっくりやれた。2通りに場合わけするだけ。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;

class PeriodicJumping {
	public:
	int minimalTime(int x, vector <int> a) {
		int n=a.size();
		x=abs(x);
		long long L=x;
		long long R=x;
		long long D=0;
		if(x==0)return 0;
		for(int i=0;i<n;i++){
			D+=a[i];
			if(R-a[i]>=0)L=max(0LL,L-a[i]);
			else L=-(R-a[i]);
			R+=a[i];
			if(L==0)return i+1;
		}
		if(D<x){
			int ret=n*(x/D);
			x%=D;
			long long t=0;
			for(int i=0;i<n;i++){
				if(x<=t)break;
				ret++;
				t+=a[i];
			}
			return ret;
		}
		for(int i=0;i<n;i++){
			if(R-a[i]>=0)L=max(0LL,L-a[i]);
			else L=-(R-a[i]);
			if(L==0)return n+i+1;
		}
		return -1;
	}
};

600:木 木
根を決める。各頂点から根までたどって条件ふやす→最小カット
600が解けたのは相当久しぶりだと思う。

// I like wolves!!
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <string.h>
#include <complex>
using namespace std;
const int D_MAX_V=1000;
const int D_v_size=1000;
struct D_wolf{
	int t,c,r;
	D_wolf(){t=c=r=0;}
	D_wolf(int t1,int c1,int r1){
		t=t1;c=c1;r=r1;
	}
};
vector<D_wolf>D_G[D_MAX_V];
int D_level[D_MAX_V];
int D_iter[D_MAX_V];

void add_edge(int from,int to,int cap){
	D_G[from].push_back(D_wolf(to,cap,D_G[to].size()));
	D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1));
}
void D_bfs(int s){
	for(int i=0;i<D_v_size;i++)D_level[i]=-1;
	queue<int> Q;
	D_level[s]=0;
	Q.push(s);
	while(Q.size()){
		int v=Q.front();
		Q.pop();
		for(int i=0;i<D_G[v].size();i++){
			if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){
				D_level[D_G[v][i].t]=D_level[v]+1;
				Q.push(D_G[v][i].t);
			}
		}
	}
}
int D_dfs(int v,int t,int f){
	if(v==t)return f;
	for(;D_iter[v]<D_G[v].size();D_iter[v]++){
		int i=D_iter[v];
		if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){
			int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c));
			if(d>0){
				D_G[v][i].c-=d;
				D_G[D_G[v][i].t][D_G[v][i].r].c+=d;
				return d;
			}
		}
	}
	return 0;
}
int max_flow(int s,int t){
	int flow=0;
	for(;;){
		D_bfs(s);
		if(D_level[t]<0)return flow;
		for(int i=0;i<D_v_size;i++)D_iter[i]=0;
		int f;
		while((f=D_dfs(s,t,99999999))>0){flow+=f;}
	}
	return 0;
}
class DoubleTree {
	public:
	vector<int>ga[60];
	vector<int>gb[60];
	int reva[60];
	int revb[60];
	int use[60][60];
	void dfsa(int a,int b){
		for(int i=0;i<ga[a].size();i++){
			if(ga[a][i]==b)continue;
			reva[ga[a][i]]=(a);
			dfsa(ga[a][i],a);
		}
	}
	void dfsb(int a,int b){
		for(int i=0;i<gb[a].size();i++){
			if(gb[a][i]==b)continue;
			revb[gb[a][i]]=(a);
			dfsb(gb[a][i],a);
		}
	}
	int maximalScore(vector <int> a, vector <int> b, vector <int> c, vector <int> d, vector <int> score) {
		int n=a.size()+1;
		int ret=0;
		int INF=99999999;
		int val=0;
		for(int i=0;i<n-1;i++){
			ga[a[i]].push_back(b[i]);
			ga[b[i]].push_back(a[i]);
			gb[c[i]].push_back(d[i]);
			gb[d[i]].push_back(c[i]);
		}
		for(int i=0;i<n;i++)if(score[i]>0)val+=score[i];
		for(int i=0;i<n;i++){
			for(int j=0;j<1000;j++){
				D_G[j].clear();
				D_iter[j]=D_level[j]=0;
			}
			for(int j=0;j<n;j++)for(int k=0;k<n;k++)use[j][k]=0;
		//	for(int j=0;j<n;j++)for(int k=0;k<n;k++)
			int s=n*2;
			int t=n*2+1;
			for(int j=0;j<n;j++){
				add_edge(s,j,max(0,score[j]));
				add_edge(j,j+n,INF);
				add_edge(j+n,t,max(0,-score[j]));
			}
			for(int j=0;j<n;j++){
				reva[j]=revb[j]=0;
			}
			dfsa(i,-1);
			dfsb(i,-1);
		//	for(int j=0;j<n;j++)printf("%d: %d\n",j,reva[j]);
		//	for(int j=0;j<n;j++)printf("%d: %d\n",j,revb[j]);
			
			for(int j=0;j<n;j++){
				int at=j;
				while(at!=i){
					at=reva[at];
					use[j][at]=1;
				}
			}
			for(int j=0;j<n;j++){
				int at=j;
				while(at!=i){
					at=revb[at];
					use[j][at]=1;
				}
			}
			for(int j=0;j<n;j++)for(int k=0;k<n;k++)if(use[j][k])add_edge(j+n,k,INF);
			ret=max(ret,val-max_flow(s,t));
		}
		return ret;
	}
};

1000:SAT SAT
2-SATでmin(a,b)=eってどう式にするんだろうね~という気分になった

Challenge:
どうせたくさん落ちるんだろうけど問題が問題なのでコードがみな汚くて読めない。無理。

2236 -> 2366 (+130)

ようやく相応レーティングになってきた。