2015-08-27

AOJ 2256 Divide the Cake

AOJ

ケーキの端にイチゴが乗ってる時(sample1)の対処をメモ。
len(Y)は片方を(0,Y)に固定したときに等分できる右側の部分の長さを返す関数。
ただ、(0,Y)にイチゴがあると色々面倒なので+eps,-epsの２つに分けて処理した。
誤差怖かったけど通ったので良かった(小並感)

int W,H,N;
int x[210],y[210];
double len(double Y)
{
    vector<double> v;
    for(int i=0;i<2*N;i++)v.pb(atan2(y[i]-Y,x[i]));
    sort(all(v));
    double low = tan(v[N-1])*(double)W + Y;
    double high = tan(v[N])*(double)W + Y;
    low = max(low,0.0);
    low = min(low,(double)H);
    high = max(high,0.0);
    high = min(high,(double)H);
    return high-low;
}
int main()
{
    while(1)
    {
        scanf("%d %d %d",&W,&H,&N);
        if(W==0&&H==0&&N==0)break;
        for(int i=0;i<N*2;i++)scanf("%d %d",&x[i],&y[i]);
        vector<P> v;
        for(int i=0;i<N*2;i++)v.pb(P(x[i],y[i]));
        v.pb(P(W,0));v.pb(P(W,H));
        vector<double> border;
        for(int i=0;i<v.size();i++)
        {
            for(int j=i+1;j<v.size();j++)
            {
                if(v[i].fi==v[j].fi)continue;
                double res = (double)v[i].sec-(double)v[i].fi*(double)(v[j].sec-v[i].sec)/(double)(v[j].fi-v[i].fi);
                if(0.0<=res&&res<=(double)H)border.pb(res);
            }
        }
        border.pb(0.0);border.pb(H);
        sort(all(border));
        border.erase(unique(all(border)),border.end());
        double ans = 0.0;
        for(int i=0;i<border.size()-1;i++)ans+=(len(border[i]+eps)+len(border[i+1]-eps))/2.0*(border[i+1]-border[i]);
        ans /= (double)H;
        ans /= (double)H;
        printf("%.12f\n",ans);
    }
    return 0;
}

2015-08-23

AOJ 2313 Box Witch

AOJ

個人的にハマるポイントが山ほどあったので戒めのメモ。
まず、自分のライブラリはverify済でも信用してはいけません
(まぁこれはverifyした後にちょっとわかり易くしようと書き換えた自分が悪いのでなんとも言えませんが)
(でもまさかadd_edgeが間違ってるとは…)
次に、dfsする前に絶対memset忘れないように!!
(これに大体5時間溶かしました)
そして解法のことですが、辺削除の時どっち向きに流れているか注意!!
(なぜかずっとe.cap>0なら使われててそうでなければ使われてないという判定をしていました)
自分の思考ガバガバすぎなので反省します…

const int MAX_V=100100;
struct edge
{
    int to,cap,rev;
    edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){}
};
vector<edge> G[MAX_V];
bool used[MAX_V];
void add_edge(int from,int to,int cap)
{
    edge new_edge1(to,cap,G[to].size());
    G[from].pb(new_edge1);
    edge new_edge2(from,cap,G[from].size()-1);
    G[to].pb(new_edge2);
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    used[v]=true;
    for(int i=0;i<G[v].size();i++)
    {
        edge &e=G[v][i];
        if(!used[e.to]&&e.cap>0)
        {
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0)
            {
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int flow=0;
int N;
int max_flow(int s,int t)
{
    for(;;)
    {
        memset(used,0,sizeof(used));
        int f=dfs(s,t,INF);
        if(f==0)return flow;
        flow+=f;
    }
}
int ex[505][505];
int E,Q;
int ind(int A,int B){for(int i=0;i<G[A].size();i++)if(G[A][i].to==B)return i;}
void increase(int A,int B)
{
    int id = ind(A,B);
    edge &e = G[A][id];
    e.cap++;
}
int decrease(int A,int B)
{
    int id = ind(A,B);
    edge &e = G[A][id];
    int ret = e.cap;
    e.cap=0;
    return ret;
}
int up_query(int A,int B)
{
    increase(A,B);
    increase(B,A);
    return max_flow(0,N-1);
}
int down_query(int A,int B)
{
    int c = decrease(A,B);
    decrease(B,A);
    if(c==2)swap(A,B);
    if(c==1)return flow;
    else
    {
        memset(used,0,sizeof(used));
        if(dfs(A,B,1)>0)return flow;
        memset(used,0,sizeof(used));
        dfs(N-1,B,1);
        memset(used,0,sizeof(used));
        dfs(A,0,1);
        flow--;
        return flow;
    }
}
int main()
{
    scanf("%d %d %d",&N,&E,&Q);
    for(int i=0;i<E;i++)
    {
        int F,T;
        scanf("%d %d",&F,&T);
        F--;T--;
        ex[F][T]=1;
        ex[T][F]=1;
    }
    for(int i=0;i<N;i++)
    {
        for(int j=i+1;j<N;j++)
        {
            add_edge(i,j,ex[i][j]);
        }
    }
    max_flow(0,N-1);
    for(int i=0;i<Q;i++)
    {
        int M,A,B;
        scanf("%d %d %d",&M,&A,&B);
        A--;B--;
        if(M==1)printf("%d\n",up_query(A,B));
        else printf("%d\n",down_query(A,B));
    }
}

2015-08-21

AOJ 2439 Hakone

AOJ

良問DPとして有名な箱根駅伝。結構考えましたがわからず解説を読んでしまいました。
JAGの解説が少しわかりにくかったのでここにまとめておきます。
順位表の'-'は確定するので無視します。
現在の中継地点の順位表を1位から順に見ていって、前の中継地点での順位表を上から埋めていく感じです。
DP[i][j]:=(i位まででj個未確定で放置)の場合の数
というテーブルを考えます。
初期化はdp[0][0]=1で求める値はdp[n][0]です
dp[i][j]からの状態遷移は、

(i)i+1位が'D'の時
1~iで開いてる所(すなわちj個)にi+1位のやつを入れるのでj通り。dp[i+1][j]+=dp[i][j]*j
上とあわせてi+1位のところに放置してたやつ(すなわちj個)を入れるのでj通り。dp[i+1][j-1]+=dp[i][j]*j*j

(ii)i+1位が'U'の時
i+1位のところに放置してたやつ(すなわちj個)を入れるのでj通り。dp[i+1][j]+=dp[i][j]*j
完全に放置。dp[i+1][j+1]+=dp[i][j]

O(N^2)ですが、想定解は未確定の数と放置してたやつ(両者は常に等しい)を分けてO(N^3)のようです

このDPが本当に重複なく数えられているかはdp[0][0]からdp[n][0]までのパスと一対一に対応してることを考えるとわかると思います。

典型と言われるのもわかるような気がします。これの類題は絶対落とさないようにしていく所存です

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll dp[300][300];
int n;
char c[300];
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)cin >> c[i];
	dp[0][0]=1ll;
	for(int i=0;i<n;i++)
	{
		if(c[i]=='-')for(int j=0;j<=n;j++)dp[i+1][j]=dp[i][j];
		if(c[i]=='D')
		{
			for(int j=0;j<=i;j++)
			{
				if(j>0)dp[i+1][j-1] = (dp[i+1][j-1]+(((dp[i][j]*j)%MOD)*j%MOD))%MOD;
				dp[i+1][j] = (dp[i+1][j]+((dp[i][j]*j)%MOD))%MOD;
			}
		}
		if(c[i]=='U')
		{
			for(int j=0;j<=i;j++)
			{
				dp[i+1][j+1] = (dp[i+1][j+1]+dp[i][j])%MOD;
				dp[i+1][j] = (dp[i+1][j]+((dp[i][j]*j)%MOD))%MOD;
			}
		}
	}
	printf("%lld\n",dp[n][0]);
	return 0;
}

2015-07-30

閉路の偶奇

CodeForces

グラフの閉路を検出するのはDFSなりベルマンフォードなりで適当に出来ますよね。
今日奇数長の閉路の検出が出来ずに困ってしまったのでメモ。
全然今まで気付かなかったのですが
「偶数長の閉路しかない⇔2部グラフ」
です。あとはこれより、2部グラフかどうかさえ判定できればいいです。
これは簡単ですね。
(追記)多重辺、ループのない時です

Problem - 557D - Codeforces

2015-07-20

Counting Sort

CodeForces

ちょいちょい勉強したことでも書き留めておこうと思います。
Counting Sortというのを知りました。
sortなんてquick sortとmerge sortだけ知ってりゃ十分やとか思ってたんやけど、CFでこれを使う問題が解けんくて悔しかったから書いときます。
この方法は数列とかのソートより、アルファベットみたいに種類に限りがあるものに対するソートに向いてるみたいです。
abracadabraをソートする時はa,b,c,d,rの数を数えて、それぞれ5,2,1,1,2なのでaaaaabbcdrrとするという感じです。
要するに数えたら後は並べるだけ。ってことです。
数える部分もsortする部分も(連続区間なので)segtreeを使って高速化できる場合があります。

使う問題

Problem - E - Codeforces

2015-03-18

JOI 春合宿 2010 Day 3

JOI

何日か前にやったのに書くの忘れてた

本選会場

うまいこと待ってやれば、最小全域木のコスト分しかかからない。K個まで分割することが許されるので、全域木に含まれる辺からコストの大きい順にK-1個とって木をK個に分割してやればいい。

int N,M,K;
struct edge
{
	int from,to,cost;
	edge(int from,int to,int cost):from(from),to(to),cost(cost){}
	bool operator < (const edge& a) const
	{
		return cost < a.cost;
	}
};
struct UnionFind
{
	int par[100100],rank[100100];
	void init(){rep(i,100100)par[i]=i;}
	int find(int x)
	{
		if(par[x]==x)return x;
		return par[x]=find(par[x]);
	}
	void unite(int a,int b)
	{
		a = find(a);
		b = find(b);
		if(a==b)return;
		if(rank[a]<rank[b])par[a]=b;
		else
		{
			par[b]=a;
			if(rank[a]==rank[b])rank[a]++;
		}
	}
	bool same(int a,int b)
	{
		return find(a)==find(b);
	}
}uf;
vector<edge> es;
int main()
{
	scanf("%d %d %d",&N,&M,&K);
	rep(i,M)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		es.pb(edge(a,b,c));
	}
	sort(all(es));
	uf.init();
	int cnt = 0,ans = 0;
	rep(i,es.size())
	{
		if(cnt==N-K)break;
		if(uf.same(es[i].from,es[i].to))continue;
		uf.unite(es[i].from,es[i].to);
		cnt++;
		ans += es[i].cost;
	}
	printf("%d\n",ans);
	return 0;
}

かくれんぼ

よくある感じのsegtreeで平面走査。
すんなり書けた。
前に一度解いたことがあるらしいけど、全然覚えてなかったので初見と同じ感覚で解いた。
前解いたときは何日もつかった気がするけど今回はサクッと解けたのでなんとなく成長を感じた(?)

const int SIZE = 1<<17;
struct segtree
{
	int seg[SIZE*2],lazy[SIZE*2];
	void lazy_evaluate(int k)
	{
		seg[k]+=lazy[k];
		if(k<SIZE-1)
		{
			lazy[2*k+1]+=lazy[k];
			lazy[2*k+2]+=lazy[k];
		}
		lazy[k]=0;
	}
	void update(int a,int b,int k,int l,int r,int x)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b)
		{
			lazy[k]+=x;
			lazy_evaluate(k);
		}
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,x);
			update(a,b,k*2+2,(l+r)/2,r,x);
			seg[k] = max(seg[k*2+1],seg[k*2+2]);
			return;
		}
	}
	int query(int a,int b,int k,int l,int r)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return 0;
		if(a<=l&&r<=b)return seg[k];
		else
		{
			int lch = query(a,b,k*2+1,l,(l+r)/2);
			int rch = query(a,b,k*2+2,(l+r)/2,r);
			seg[k] = max(seg[k*2+1],seg[k*2+2]);
			return max(lch,rch);
		}
	}
	int value(int v){return seg[v]+lazy[v];}
	int get_index(int x)
	{
		int p=0;
		while(p<SIZE-1)
		{
			lazy_evaluate(p);
			if(value(2*p+1)>=x)p = p*2+1;
			else p = p*2+2;
		}
		return p-(SIZE-1);
	}
}seg;
int N,M;
struct obstacle
{
	int x,y,w;
	obstacle(int x,int y,int w):x(x),y(y),w(w){}
	bool operator < (const obstacle a) const
	{
		if(y!=a.y)return y < a.y;
		return x < a.x;
	}
};
int a[100100],ans_x[100100],ans_y[100100];
vector<int> weapon;
vector<obstacle> obs;
int main()
{
	scanf("%d %d",&N,&M);
	rep(i,N)
	{
		int x,y,w;
		scanf("%d %d %d",&x,&y,&w);
		obs.pb(obstacle(x,y,w));
	}
	sort(all(obs));
	rep(i,M)
	{
		scanf("%d",&a[i]);
		weapon.pb(a[i]);
	}
	sort(all(weapon));
	weapon.erase(unique(all(weapon)),weapon.end());
	memset(ans_x,-1,sizeof(ans_x));
	memset(ans_y,-1,sizeof(ans_y));
	int id = 0;
	rep(i,obs.size())
	{
		seg.update(obs[i].x,obs[i].x+obs[i].w,0,0,SIZE,1);
		int max_val = seg.query(0,SIZE,0,0,SIZE);
		while(id<M&&weapon[id]<max_val)
		{
			ans_y[id] = obs[i].y;
			ans_x[id] = seg.get_index(weapon[id]+1);
			id++;
		}
	}
	rep(i,M)
	{
		int k = lower_bound(all(weapon),a[i])-weapon.begin();
		printf("%d %d\n",ans_x[k],ans_y[k]);
	}
	return 0;
}

シムロード

実は始めてのOutput onlyだった。
シュタイナー木やんこれ、ってなって適当にdijkstraで貪欲チックにやったら96.3点も帰ってきて
驚愕。snukeさんどうやって解いてるんだろう…

string s[105];
int d[105][105];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int W,H;
P village[10010];
P prev[10010];
int sx,sy;
void dijkstra()
{
	rep(i,H)rep(j,W)d[i][j]=INF;
	rep(i,H)rep(j,W)prev[i*W+j]=P(-1,-1);
	d[sx][sy]=0;
	priority_queue<T,vector<T>,greater<T> > q;
	q.push(T(0,P(sx,sy)));
	while(!q.empty())
	{
		T a = q.top();
		q.pop();
		rep(i,4)
		{
			int nx=a.sec.fi+dx[i],ny=a.sec.sec+dy[i];
			if(nx<0||nx>=H||ny<0||ny>=W)continue;
			int ne = a.fi;
			if(s[nx][ny]=='w')ne++;
			if(d[nx][ny]>ne)
			{
				d[nx][ny]=ne;
				prev[nx*W+ny]=a.sec;
				q.push(T(ne,P(nx,ny)));
			}
		}
	}
}
void cut(int v)
{
	P cur = village[v];
	while(1)
	{
		cur = prev[cur.fi*W+cur.sec];
		if(cur==village[0])break;
		if(s[cur.fi][cur.sec]=='w')s[cur.fi][cur.sec]='.';
	}
	return;
}
int main()
{
	scanf("%d %d",&W,&H);
	rep(i,H)cin >> s[i];
	int num = 0;
	rep(i,H)rep(j,W)if(s[i][j]=='@')village[num++]=P(i,j);
	sx = village[0].fi,sy = village[0].sec;
	while(1)
	{
		dijkstra();
		int mv,mn=INF;
		rep(i,num)
		{
			if(d[village[i].fi][village[i].sec]<=0)continue;
			if(mn>d[village[i].fi][village[i].sec])
			{
				mn = d[village[i].fi][village[i].sec];
				mv = i;
			}
		}
		if(mn==INF)break;
		cut(mv);
	}
	rep(i,H)cout << s[i] << endl;
	return 0;
}

100+100+96.3 = 296.3
全完出来なくて悲しいけどわりと嬉しい点数だった

2015-02-22

JOI 春合宿 2008 Day 3 Origami

JOI

問題文はちゃんと読みましょう

Origami,簡単だけど5ではないでしょ…
— おくら (@okuraofvegetabl) 2015, 2月 22

ええええええええええ辺の長さ20cm以下とか聞いてないぞおおおおお
— おくら (@okuraofvegetabl) 2015, 2月 22

mapで数えるだけの問題を2次元座圧+2次元imosでやりました。
普通にやったらMLEするので、平面走査風にやってメモリ節約しました。

int imos[10050],cnt[10050];
int a,b,n;
int p[5050],q[5050],r[5050],s[5050];
vector<int> vx,vy;
vector<T> event;
ll size(int x,int y)
{
	if(x+1>=(int)vx.size()||y+1>=(int)vy.size())return 0ll;
	return (ll)(vx[x+1]-vx[x])*(ll)(vy[y+1]-vy[y]);
}
int main()
{
	scanf("%d",&n);
	scanf("%d %d",&a,&b);
	for(int i=0;i<n;i++)
	{
		scanf("%d %d %d %d",&p[i],&q[i],&r[i],&s[i]);
		p[i]--;q[i]--;
		vx.pb(p[i]);vy.pb(q[i]);vx.pb(r[i]);vy.pb(s[i]);
	}
	sort(all(vx));
	sort(all(vy));
	vx.erase(unique(all(vx)),vx.end());
	vy.erase(unique(all(vy)),vy.end());
	for(int i=0;i<n;i++)
	{
		p[i]=lower_bound(all(vx),p[i])-vx.begin();
		q[i]=lower_bound(all(vy),q[i])-vy.begin();
		r[i]=lower_bound(all(vx),r[i])-vx.begin();
		s[i]=lower_bound(all(vy),s[i])-vy.begin();
		//printf("%d %d %d %d\n",p[i],q[i],r[i],s[i]);
		event.pb(T(P(p[i],q[i]),1));
		event.pb(T(P(p[i],s[i]),-1));
		event.pb(T(P(r[i],q[i]),-1));
		event.pb(T(P(r[i],s[i]),1));
	}
	sort(all(event));
	int SX = vx.size(),SY = vy.size();
	int id = 0;
	int ans_sz = 0;
	ll ans_num = 0ll;
	for(int i=0;i<=SX;i++)
	{
		if(!(id<event.size()))break;
		if(event[id].fi.fi!=i)continue;
		memset(cnt,0,sizeof(cnt));
		while(id<event.size()&&event[id].fi.fi==i)
		{
			cnt[event[id].fi.sec]+=event[id].sec;
			id++;
		}
		for(int j=0;j<=SY;j++)cnt[j+1]+=cnt[j];
		for(int j=0;j<=SY;j++)
		{
			imos[j]+=cnt[j];
			if(ans_sz<imos[j])
			{
				ans_sz = imos[j];
				ans_num = size(i,j);
			}
			else if(ans_sz==imos[j])
			{
				ans_num += size(i,j);
			}
		}
	}
	printf("%d\n",ans_sz);
	printf("%lld\n",ans_num);
	return 0;
}