PKU 3272 Cow Traffic

PKU
問題概要

N頂点のDAGが与えられる(多重辺アリ).入次数0のノードからN番目のノードまでの全てのパスを考える.
それらのなかに最も多く含まれている辺の、含まれている回数を求めよ


辺a->bが含まれる回数は(始点からaまでのパスの総数)*(bから終点までのパスの総数)ということに気づけば終わり。各頂点からのパスの総数はDAGなのでdpですぐ求まる。


始点が複数個あって邪魔なので新たな始点の頂点0を用意してそこから各始点に辺張ってます。


まぁ7で妥当なところかなぁと思います

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
vector<int> g[5050],rev[5050];
int dp[5050],dp2[5050],e[5050];
int N,M;
int main()
{
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);
		e[b]++;
		g[a].pb(b);
		rev[b].pb(a);
	}
	for(int i=1;i<=N;i++)if(e[i]==0)
	{
		g[0].pb(i);
		rev[i].pb(0);
	}
	dp[0]=1;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<rev[i].size();j++)dp[i]+=dp[rev[i][j]];
	}
	dp2[N]=1;
	for(int i=N-1;i>=0;i--)
	{
		for(int j=0;j<g[i].size();j++)dp2[i]+=dp2[g[i][j]];
	}
	int ans = 0;
	for(int i=1;i<=N;i++)
	{
		for(int j=0;j<g[i].size();j++)ans = max(ans,dp[i]*dp2[g[i][j]]);
	}
	printf("%d\n",ans);
	return 0;
}

PKU 3252 Round Numbers

PKU
問題概要

[Start,Finish]で、二進数で表記した時に0の数が1の数以上になるような数の個数を求めよ

桁DP。やるだけ。なんでこれが8なんだろう(この前8のad-hocが自力で解けなかった)
dp[i][j][k][l]:=今上からi桁目で、0の個数-1の個数がjでkはずっと上限できてるか、lはずっと0か

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
vector<int> v;
const int geta = 40;
int dp[40][100][2][2];
int rec(int x,int d,bool f,bool f2)
{
	if(x==v.size())
	{
		if(d>=0&&!f2)return 1;
		else return 0;
	}
	if(dp[x][d+geta][f][f2]!=-1)return dp[x][d+geta][f][f2];
	int res = 0;
	if(f)
	{
		for(int i=0;i<=v[x];i++)
		{
			int nd = d;
			bool nf,nf2;
			if(!f2&&i==0)nd++;
			else if(i!=0)nd--;
			if(i==v[x])nf=true;
			else nf = false;
			if(f2&&i==0)nf2=true;
			else nf2=false;
			res += rec(x+1,nd,nf,nf2);
		}
	}
	else
	{
		for(int i=0;i<=1;i++)
		{
			int nd = d;
			bool nf2;
			if(!f2&&i==0)nd++;
			else if(i!=0)nd--;
			if(f2&&i==0)nf2=true;
			else nf2=false;
			res += rec(x+1,nd,false,nf2);
		}

	}
	return dp[x][d+geta][f][f2]=res;
}
int solve(int x)
{
	v.clear();
	while(x)
	{
		v.pb(x%2);
		x/=2;
	}
	memset(dp,-1,sizeof(dp));
	reverse(v.begin(),v.end());
	return rec(0,0,true,true);
}
int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	printf("%d\n",solve(b)-solve(a-1));
	return 0;
}

Codeforces Round #284 B Name That Tune

CodeForces
問題概要

N種類の曲があり、それらを順番に流す。聞いている側が曲名が分かり次第流す側に伝える。
流す側は伝えられたらすぐに次の曲を流す。
各曲には認知度p[i]があり毎秒ごとにp[i]%の確率で、そこから1秒で曲名がわかる。
また、各曲の歌詞には曲名がはいっているので始めのt[i]秒聞けばすぐに曲名はわかる
最後に曲名を答えたのがT秒後となるような時のそれまでに答えた曲数の期待値を求めよ

dp[i][j]:=i番目の曲から残りj秒で答えられる曲数の期待値とすると

j < t[i]の時:
dp[i][j] = Σ(k=1,j){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}

それ以外の時:
dp[i][j] = Σ(k=1,t[i]-1){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}+(1-p[i])^(t[i]-1)*(dp[i+1][j-t[i]]+1)

となりますが愚直に計算するとO(NT^2)で間に合わないのでちょっと式変形

j < t[i]の時:
dp[i][j] = Σ(k=1,j){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}
= (dp[i+1][j-1]+1)*p[i] + Σ(k=2,j){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}
= (dp[i+1][j-1]+1)*p[i] + Σ(k=1,j-1){(dp[i+1][j-1-k]+1)*(1-p[i]^k)*p[i]}
= (dp[i+1][j-1]+1)*p[i] + dp[i][j-1]*(1-p[i])

それ以外の時:
dp[i][j]
= Σ(k=1,t[i]-1){(dp[i+1][j-k]+1)*(1-p[i]^k-1)*p[i]}+(1-p[i])^(t[i]-1)*(dp[i+1][j-t[i]]+1)
= {dp[i][j-1]-(1-p[i])^(t[i]-1)*(dp[i+1][j-1-t[i]]+1)}*(1-p[i])-(dp[i+1][j-t[i]]+1)*p[i]*(1-p[i])^(t[i]-1)+(dp[i+1][j-1]+1)*p[i]+(1-p[i])^(t[i]-1)*(dp[i+1][j-t[i]]+1)

これでO(NT)なので間に合いますね

int t[5050],N,T;
double p[5050];
double dp[5050][5050];
double r[5050];
double rec(int x,int rem)
{
	if(rem<=0||x>=N)return 0;
	if(dp[x][rem]!=-1)return dp[x][rem];
	double res = 0;
	if(rem<t[x])res += (rec(x+1,rem-1)+1)*p[x]+rec(x,rem-1)*(1-p[x]);
	else
	{
		res = rec(x,rem-1);
		if(rem!=t[x])res -= r[x]*(rec(x+1,rem-t[x]-1)+1);
		res *= (1-p[x]);
		res -= (rec(x+1,rem-t[x])+1)*r[x]*p[x];
		res += (rec(x+1,rem-1)+1)*p[x];
		res += (rec(x+1,rem-t[x])+1)*r[x];
	}
	return dp[x][rem]=res;
}
int main()
{
	cin >> N >> T;
	for(int i=0;i<N;i++)cin >> p[i] >> t[i];
	for(int i=0;i<N;i++)p[i]/=100.0;
	for(int i=0;i<N;i++)r[i]=pow(1-p[i],t[i]-1);
	for(int i=0;i<5050;i++)for(int j=0;j<5050;j++)dp[i][j]=-1;
	printf("%.12f\n",rec(0,T));
	return 0;
}

PKU 3612 Telephone Wire

PKU

クリスマスですね。

日本語の解説記事がなかったので。
まずは普通に
dp[i][j]:=i番目のポールを高さjにする時のそこまでのペナルティの合計の最小値
(不可能なときはINF)として漸化式をたててみると
dp[i][j] = min{dp[i-1][k]+abs(k-j)*C | 0<=k<=100} + (j-h[i])^2
となりますが、コレを愚直に実装するとO(N*(H_MAX)^2)で間に合いません。
そこで
dp[i][j] = min(min{dp[i-1][k]+k*C-j*C|j<=k<=100},min{dp[i-1][k]-k*C+j*C|0<=k<=j})+(j-h[i])^2
として(絶対値で場合分けしただけです)
a[i][j] = min{dp[i][k]+k*C|j<=k<=100}
b[i][j] = min{dp[i][k]+k*C|0<=k<=j}
とおくと、dp[i][j]=min(a[i-1][j]-j*C,b[i-1][j]+j*C)+(j-h[i])^2と書けます。
a[i],b[i]はdp[i]の計算が終わった後にO(H_MAX)で求められるので
全体としてO(N(H_MAX))で計算できます

#define sq(X) ((X)*(X))
int dp[2][105],a[2][105],b[2][105];
int h[100100],N,C;
int main()
{
	scanf("%d %d",&N,&C);
	for(int i=0;i<N;i++)scanf("%d",&h[i]);
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<=100;j++)
		{
			dp[i%2][j]=INF;
			a[i%2][j]=INF;
			b[i%2][j]=INF;
		}
		for(int j=h[i];j<=100;j++)
		{
			if(i==0)dp[i%2][j]=sq(j-h[i]);
			else dp[i%2][j]=min(a[(i-1)%2][j]-j*C,b[(i-1)%2][j]+j*C)+sq(j-h[i]);
		}
		for(int j=100;j>=0;j--)
		{
			if(j==100)a[i%2][j]=dp[i%2][j]+j*C;
			else a[i%2][j]=min(a[i%2][j+1],dp[i%2][j]+j*C);
		}
		for(int j=0;j<=100;j++)
		{
			if(j==0)b[i%2][j]=dp[i%2][j]-j*C;
			else b[i%2][j]=min(b[i%2][j-1],dp[i%2][j]-j*C);
		}
	}
	int ans = INF;
	for(int i=0;i<=100;i++)ans = min(ans,dp[(N-1)%2][i]);
	printf("%d\n",ans);
	return 0;
}

JOI 2015 予選参加記

JOI

はい、というわけでもちろん今年も参加しました。
が、残念な結果に終わったので本選まで今まで以上に精進しようと思います。
適当な解説を書きます。テンプレはいつも通り省略してます

1.水道料金 (Water Rate)

やるだけ。

int A,B,C,D,p;
int main()
{
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;
	cin >> p;
	int X=0,Y=0;
	X = A*p;
	Y = B;
	if(p>C)Y += (p-C)*D;
	cout << min(X,Y) << endl;
	return 0;
}
2.クリスマスパーティー (Christmas Party)

これもやるだけ。書いてあるとおりにシミュレーション

int N,M;
int A[105],B[105][105],score[105];
int main()
{
	cin >> N;
	cin >> M;
	for(int i=0;i<M;i++)
	{
		cin >> A[i];
		A[i]--;
	}
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			cin >> B[i][j];
			B[i][j]--;
		}
	}
	for(int i=0;i<M;i++)
	{
		int cnt = 0;
		for(int j=0;j<N;j++)
		{
			if(B[i][j]==A[i])score[j]++;
			else cnt++;
		}
		score[A[i]]+=cnt;
	}
	for(int i=0;i<N;i++)cout << score[i] << endl;
	return 0;
}
3.気象予報士 (Weather Forecaster)

これもやるだけ。

char f[105][105];
int H,W;
int solve(int x,int y)
{
	int res = -1;
	for(int i=0;i<=y;i++)if(f[x][i]=='c')res = i;
	if(res == -1)return -1;
	return y-res;
}
int main()
{
	cin >> H >> W;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin >> f[i][j];
		}
	}
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			printf("%d%c",solve(i,j),((j==W-1)?'\n':' '));
		}
	}
	return 0;
}
4.シルクロード (Silk Road)

これもやるだけ。適当にDP。

int dp[1050][1050];
int N,M;
int C[1050],D[1050];
int main()
{
	for(int i=0;i<1050;i++)
	{
		for(int j=0;j<1050;j++)
		{
			dp[i][j]=INF;
		}
	}
	cin >> N >> M;
	for(int i=0;i<N;i++)cin >> D[i];
	for(int i=0;i<M;i++)cin >> C[i];
	dp[0][0]=0;
	for(int i=0;i<M;i++)
	{
		for(int j=0;j<N;j++)
		{
			if(dp[i][j]==INF)continue;
			dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+C[i]*D[j]);
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
		}
	}
	int ans = INF;
	for(int i=0;i<=M;i++)ans = min(ans,dp[i][N]);
	cout << ans << endl;
	return 0;
}
5.砂の城 (Sandcastle)

これもやるだけ。8近傍を適当に探索。ここまで45分

int H,W;
char a[1050][1050];
int f[1050][1050];
int num[1050][1050];
int dx[8]={-1,-1,-1,0,0,1,1,1};
int dy[8]={1,0,-1,1,-1,1,0,-1};
vector<P> cur,tmp,next;
int update()
{
	int col = 0;
	for(int i=0;i<cur.size();i++)
	{
		int x = cur[i].fi,y = cur[i].sec;
		if(f[x][y]!=0&&f[x][y]<=num[x][y])
		{
			tmp.pb(P(x,y));
			col++;
		}
	}
	for(int i=0;i<col;i++)
	{
		int x=tmp[i].fi,y=tmp[i].sec;
		f[x][y]=0;
		for(int j=0;j<8;j++)
		{
			int nx=x+dx[j],ny=y+dy[j];
			num[nx][ny]++;
		}
	}
	for(int i=0;i<tmp.size();i++)
	{
		int x = tmp[i].fi,y = tmp[i].sec;
		for(int j=0;j<8;j++)
		{
			int nx = x+dx[j],ny=y+dy[j];
			if(nx<0||nx>=H||ny<0||ny>=W)continue;
			if(f[nx][ny]!=0)next.pb(P(nx,ny));
		}
	}
	sort(next.begin(),next.end());
	next.erase(unique(next.begin(),next.end()),next.end());
	tmp.clear();
	cur.clear();
	cur=next;
	next.clear();
	return col;
}
int main()
{
	cin >> H >> W;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			cin >> a[i][j];
			if(a[i][j]!='.')f[i][j]=a[i][j]-'0';
		}
	}
	for(int i=1;i<H-1;i++)
	{
		for(int j=1;j<W-1;j++)
		{
			cur.pb(P(i,j));
			int cnt = 0;
			for(int k=0;k<8;k++)
			{
				int nx=i+dx[k],ny=j+dy[k];
				if(f[nx][ny]==0)cnt++;
			}
			num[i][j]=cnt;
		}
	}
	int ans = 0;
	while(1)
	{
		int n = update();
		if(n==0)break;
		ans++;
	}
	cout << ans << endl;
	return 0;
}
6.財宝 (Treasures)

これもやるだけ。半分全列挙+座標圧縮+SegmentTree

typedef long long ll;
typedef pair<ll,ll> P;
const int SIZE = 1<<24;
int N;
ll D,end,ind;
ll X[40],Y[40];
int l[SIZE],r[SIZE];
vector<P> v[2];
void rec(int x,ll s,ll k)
{
	if(x==end)
	{
		v[ind].pb(P(s,k));
		return;
	}
	rec(x+1,s+X[x],k-Y[x]);
	rec(x+1,s-X[x],k+Y[x]);
	rec(x+1,s,k);
}
struct segtree
{
	ll seg[SIZE*2];
	segtree()
	{
		for(int i=0;i<SIZE*2;i++)seg[i]=-LLINF;
	}
	void update(int k,ll x)
	{
		k += SIZE-1;
		seg[k]=x;
		while(k>0)
		{
			k = (k-1)/2;
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
		}
	}
	ll query(int a,int b,int k,int l,int r)
	{
		if(r<=a||b<=l)return -LLINF;
		else if(a<=l&&r<=b)return seg[k];
		else return max(query(a,b,k*2+1,l,(l+r)/2),query(a,b,k*2+2,(l+r)/2,r));
	}
}seg;
int main()
{
	cin >> N >> D;
	for(int i=0;i<N;i++)cin >> X[i] >> Y[i];
	ll ans = 0ll;
	int half = N/2;
	int rem = N - half;
	ind = 0,end = half;
	rec(0,0ll,0ll);
	ind = 1,end = N;
	rec(half,0ll,0ll);
	sort(v[1].begin(),v[1].end());
	for(int i=0;i<v[0].size();i++)
	{
		l[i] = lower_bound(v[1].begin(),v[1].end(),P(-D-v[0][i].fi,-LLINF))-v[1].begin();
		r[i] = upper_bound(v[1].begin(),v[1].end(),P(D-v[0][i].fi,LLINF))-v[1].begin();
	}
	for(int i=0;i<v[1].size();i++)seg.update(i,v[1][i].sec);
	for(int i=0;i<v[0].size();i++)ans = max(ans,v[0][i].sec + seg.query(l[i],r[i],0,0,SIZE));
	cout << ans << endl;
	return 0;
}
総括

全て自分の精進不足が招いた結果だと思うので本選まで問題を解きまくっていこうと思う

PCK 2014 本選 参加記

PCK

先日、PCK2014にチーム「三上」として参加してました。
色々あったので、箇条書きでつらつら書いておきます。
こんなにどうでもいいことをだらだら書いているのは、自分が読み返した時にいろいろ思い出せるようにするためです。冗長でごめんなさい。

Day 0
  • 学校の遠足で京都に行く
  • 京都駅の荷物預かり所にPCK用の荷物を預ける
  • 東福寺に10時集合で10時30秒に着いただけでなぜかめっちゃ注意される
  • 東福寺の散策をしたあと、ハイアットリージェンシー京都でテーブルマナー講習。
  • パンとかを食べまくる。(マナー講習とはなんだったのか)
  • 遠足が終わった後「和馬」のpotetisenseiと合流する。
  • 流れでなぜかゲーセンに行く
  • しばらく人々が遊んでいるのを眺めてた
  • 最後に全員でmaimaiしないかと誘われて、人生で初めてゲーセンで金を使う。
  • 京都駅にもどって荷物をとって、satashunさんとeyさんと合流する
  • 新幹線に乗る。satashunさんとpotetisenseiが即刻寝ていた
  • eyさんとねこま2みたいな問題出たら怖いよね〜とか話しているとeyさんがじゃあ解くか、と行って解き始める
  • 自分はほかの問題を考えたりする、しばらくして東京に着く
  • 人生で初めて東北新幹線に乗った。やまびこをE4系だと思っていたらE2系が来てなんとなく残念な気持ちになる(2階建てにのってみたかった)
  • お弁当を食べたり色々していると郡山に着いた
  • eyさんがねこま2を通す。プロ。
  • 在来線の時刻表を見てみると想像どおり1時間に一本くらいしか出ていなかった
  • 乗り換えるも、座れなくて辛くなる
  • PCの電源も切れてしまったので携帯でまだ解いていない過去問をみたりする
  • satashunさんとpotetisenseiが終始マリカしていて楽しそうだった(DSを持っていくという発想はなかった)
  • 会津若松に着く。寒い。potetisenseiがずっと「僻地」と言っていた
  • 少し歩いて会津ワシントンホテルに到着。少し問題問いたりして12:30くらいに就寝。
Day 1
  • 6:30ごろに自分もeyさんも起きたので朝食を食べにいった。おいしかった。
  • satashunさんとpotetisenseiは朝食を解いていた。
  • PCKから送られて来た予定表を持ってくるのを忘れたため何時に会津大学に向かえばいいかわからずTwitterをしたりしながら過ごす。
  • joisinoさんに大学集合時間を教えていただく。
  • 駅前のバス停に向かうとPCK専用のバスがあったのでそれに乗る
  • しばらく待っているとHIRさん,yokozunaさん,DEGwerさん,namonakiさんなどのプロが現れる。
  • ハ　ラ　ス　メ　ン　ト　の　嵐
  • 会津大学に着く。パンフとかをもらって食堂に向かう。
  • 筑駒が顧問宛の大事そうな書類を落としていたので拾って届ける
  • 飯を食って会場にもどる。potetisenseiがポテトチップスをマスコットとして持って入れず処理に困っていた(本人は嫌いらしい)
  • 開会式を終えて、競技開始まで待つ。だんだん緊張してくる
  • DEGwerさんに「プロプロプロプロプロ」といわれたので「趣味趣味〜」と返す
  • 競技開始。
  • 1を見る。図を見た感じめんどくさそう。2を見る。
  • 全探索で間に合うのですぐ書く。AC。
  • 2を解き終わると、eyさんに「4は閉路見つけるやるだけだからやる。3難しいから考えといて」と言われる。
  • PCを渡して、3を読む。適当にシミュレートしながら数え上げたら良さそう。難しいと言われたのでなんとなく怖いなぁと思ったけど自信を持とうとする(自己暗示)。
  • 5を見る。これも適当に再帰しながら数えれば良さそう。
  • 1を見る。問題文が冗長なだけでさすがにやるだけだった。
  • 6を見る。これもやるだけ?と一瞬思ったけどO(N^4)じゃあかんやん、ってなる
  • とりあえず8を読む、にぶたんしたら良さそう。N<=15だったので適当にbitDPしたら良さそうだな〜とか思う。
  • この時点でeyさんにPCを渡してから45分くらいたっていたがまだ4が解けていないみたいでeyさんがバグで苦しんでいた。急かすのもあれなので6番のオーダーの下げ方を考える。
  • この時点でのStandings。激冷え。二人共かなり焦ってた。f:id:okuraofvegetable:20141112014019j:plain
  • まわりのチームにたくさん風船が上がっているなかで自分たちが1つしかなくて精神的にやばかった。でも1,3,4,5,8の解法はわかっていたのでまだマシだったと思う
  • eyさんが時始めてから1時間くらいで「閉路の検出をするだけなのにバグるから頼む」と言われるのでやる。
  • すべての辺に負のコストをつけてベルマンフォードする。5,6分くらいでAC。
  • 1を解く、すぐにAC。
  • 3を解く。適当に書く。Sample通る。投げる。WA。
  • ファッ!?
  • 印刷してすぐにPCをeyさんに渡す。
  • eyさんが5を解いている間に印刷したソースを眺める。1文字間違ってただけだった。そこを直して再提出。AC。
  • eyさんに「6,8はもうわかってるから7,9,10頼む」と言われたので7を読む。
  • 幾何(puke)(handshake)
  • 9を見る。色々考察してると、oとxが同数の時{(ox)or(xo)}*Nセット以外無理で、oがxより多い時は常に可能っぽいなぁとわかる。左端と右端のoxで場合分けして、サイズを落としていけば解けそうだなぁと思って考えてみる。
  • 10は木の個数とかを数え上げないといけないけどどうすりゃええねんってなってた
  • そうこうしてるうちにeyさんが6,8を通す。プロ。
  • この時点でIsだけが9を解いて単独トップの状態でランキングの更新が止まる
  • 9を実装するも間に合わず。
  • 7完 + 1WA
  • 前日に最低8完はしよう、とeyさんと話していただけあってつらくなる。
  • 1,2位は-273.15℃,Isで確定っぽいのであとは3位争い。賞金がもらえるかどうかがかかっているのでとてもどきどきする
  • ホテルにもどって懇親会。料理が豪華。ケーキも豪華。お腹いっぱいたべた。
  • shioshiotaさんなどの方とお話する。
  • いろいろ交流とかする。
  • ホテルの部屋に戻る
  • HIRさんとyokozunaさんの部屋に遊びに行ったりする。
  • Is,三上、和馬、炒めスズランの風船がすべて集まって凄いことになってた
  • 部屋に帰ってpotetisenseiと風船バレーをやった、めっちゃ楽しかったけどこの楽しさを言葉で伝えるのは難しい。
  • その後2時くらいに風呂に入って2時半くらいに就寝。
Day 2
  • この日は7時30くらいに起きて朝食に行った。namonakiさんやjoisinoさんが先にいた
  • ご飯をぎりぎりまで食べて部屋に戻って急いでバスに向かった(この状況でもpotetisenseiは帰ってからシャワーを浴びていた)
  • 会津大学到着後、しばらく前の列について歩いていくと、あるところで止まって、ここからは自由時間ですと言われ野放しにされた
  • HIRさんとND勢4人で15分くらい歩いてゲーセンに向かった
  • 開店時間10時(到着したとき9時)
  • 入らなくてもできるところで太鼓やダンエボをした(satashunさんとpotetiがダンエボをする写真が面白すぎる)
  • 10時になったので中に入る。
  • HIRさんが弐寺を、satashunさんと自分はjubeatを、eyさんとpotetiはDDRをした。
  • ゲーセンでお金を使った(人生で2回目)
  • 今思い出したからここに書くけど、関東と関西で弐寺のアクセントが違って驚いた
  • jubeatむずかしい
  • 気がついたらDEGwerさんとyokozunaさんがいた
  • 開店時間を把握していたらしい(プロ)
  • なんだかんだでみんな音ゲーしまくっていた
  • ゲーセンをでて飯を探す
  • 幸楽苑に行こうとしたが、どうせなら喜多方ラーメンを食べようということで検索する
  • 「車で1分」のところの来夢というところに行く(これが大きな判断ミス)
  • 20分くらい歩いて、到着。定番っぽい喜多方ラーメンを食べる
  • 美味しい。そんなことを行ってる場合ではない。記念撮影まであと10分もない。
  • みんなでラーメンを食った直後に走る。走る。走る。
  • 予定時刻に7分遅れる。
  • たくさんの人が待っていた。本当にすいませんでした。
  • 記念撮影後、控え室にいってRailroadを解く。(iとjが一箇所間違っていて無駄に時間がかかる)
  • HIRさんが終始息を荒げながらjubeatをしていた。凄い集中力だった
  • 時間がきて表彰式に向かう。
  • 3位だった。正直他の7完のチームのWA数を把握していなかったのでかなり怖かった。
  • 色々写真をとったりしたあと、審査員の話。長すぎるねん。はよせぇ。
  • HIR氏はやはり爆睡していた。DEGwerさんも終始眠そうだった
  • 表彰式のあとは会津若松駅にバスでいって、関東の方々とはお別れ。
  • とりあえずホテルに戻った。eyさんの提案で鶴ケ城が今限定でライトアップされてるらしいので見に行く。会津の名産(?)の喜多方ラーメンとソースカツ丼は食べておきたいなぁと思っていたので帰りに寄るソースカツ丼の店も決めておいた
  • 町中周遊バスにのって鶴ケ城へ。綺麗だったんだけど綺麗すぎてレゴブロックでつくったみたい、っていうのが感想。
  • 帰りにソースカツ丼屋に行って定番っぽいソースカツ丼を頼む
  • もの凄い大きな器が出てきて全員(デデ丼)って感じになる
  • 開けてみると、かなりボリュームはあるがまぁ食べれるであろう量が入っていた。
  • 美味しい。ソースカツ丼最高。
  • ホテルに戻って風船バレーを試みるも、potetiがreverseしそう、とのことだったので途中でやめて、部屋でsatashunさんの横で競プロをする
  • potetiが寝てしまってsatashunさんがキー閉じ込めに合うも眠くて意識朦朧としてらっしゃったのでロビーに行って鍵を開けてもらった。
  • satashunさんは部屋に入ると一瞬で寝ていた。
  • 自分は風呂に入ってすぐ寝た
Day 3
  • この日も7時30分くらいに起きて、ご飯を食べた。
  • 会津に来たのにまだ温泉に入ってない!ということでeyさんとsatashunさんと東山温泉へ(potetiは寝ることを優先していた)
  • まちなか周遊バスにのって東山温泉入り口へ。
  • まず足湯に入る。暖かい。気持ちいい。
  • 足湯beatをしたりするf:id:okuraofvegetable:20141110092140j:plain
  • 旅館の温泉に入る。最高。めっちゃ良かった。
  • ホテルに戻って急いで荷物をまとめてチェックアウトして駅に向かう。
  • 11時57分発の電車に乗ろうとするもeyさんが部屋に忘れ物をしたことに気付いて取りに戻る。
  • この次の電車が1時30分までない。
  • 自分たちだけが11時56分に駅に着く。eyさんが到着。もう11時59分だったので絶望的かと思っていたがなぜかまだ止まっていたので走って乗った。
  • 田舎すごいなぁ
  • 帰りの電車はほとんど全員寝ていた。
  • 京都で降りて、遠足のお土産を買って、帰った。
  • 疲れました

まとめ

来年こそは、優勝します。

最後に、PCKに参加するにあたって、様々な形で協力していただいたkyuridenamidaさんにはこの場で感謝申し上げます。

SRM 509 Div1 Med Palindromization

SRM
問題概要

回文をつくろう

3280 -- Cheapest Palindromeに文字をchangeする操作が加わっている。
基本的にはその問題と同じように区間DPをする。
ただしchangeが加わっているため、changeしてからerase,みたいなことができる。
まずchange操作はワーシャルフロイドしておく。
eraseは、changeしてからeraseする時のコストの最小値に更新する。一度の更新ではchangeした後のeraseの更新がまだ終わっていない可能性があるのでベルマンフォードっぽく頂点数(アルファベット数)回す。

#include <cstring>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
#define INF 10000000
class PalindromizationDiv1
{
	public:
	int add[30];
	int erase[30];
	int change[30][30];
	int dp[55][55];
	string Word;
	int rec(int l,int r)
	{
		if(l>=r)return 0;
		if(dp[l][r]!=-1)return dp[l][r];
		if(Word[l]==Word[r])return dp[l][r]=rec(l+1,r-1);
		int res=INF;
		int L = Word[l]-'a',R = Word[r]-'a';
		if(add[R]!=-1)res = min(res,rec(l,r-1)+add[R]);
		if(add[L]!=-1)res = min(res,rec(l+1,r)+add[L]);
		if(erase[R]!=-1)res = min(res,rec(l,r-1)+erase[R]);
		if(erase[L]!=-1)res = min(res,rec(l+1,r)+erase[L]);
		if(change[R][L]!=-1)res = min(res,rec(l+1,r-1)+change[R][L]);
		if(change[L][R]!=-1)res = min(res,rec(l+1,r-1)+change[L][R]);
		return dp[l][r]=res;
	}
	int getMinimumCost(string word, vector <string> operations)
	{
		Word = word;
		for(int i=0;i<30;i++)for(int j=0;j<30;j++)change[i][j]=INF;
		for(int i=0;i<30;i++)change[i][i]=0;
		for(int i=0;i<30;i++)add[i]=INF;
		for(int i=0;i<30;i++)erase[i]=INF;
		memset(dp,-1,sizeof(dp));
		for(int i=0;i<operations.size();i++)
		{
			stringstream ss;
			ss << operations[i];
			string op;
			ss >> op;
			string a,b;
			int cost;
			if(op=="add")
			{
				ss >> a >> cost;
				add[a[0]-'a']=cost;
			}
			else if(op=="erase")
			{
				ss >> a >> cost;
				erase[a[0]-'a']=cost;
			}
			else
			{
				ss >> a >> b >> cost;
				change[a[0]-'a'][b[0]-'a']=cost;
			}
		}
		for(int k=0;k<30;k++)for(int i=0;i<30;i++)for(int j=0;j<30;j++)change[i][j]=min(change[i][j],change[i][k]+change[k][j]);
		for(int k=0;k<30;k++)
		{
			for(int i=0;i<30;i++)
			{
				for(int j=0;j<30;j++)
				{
					if(change[i][j]!=INF&&erase[j]!=INF)
					{
						erase[i]=min(erase[i],change[i][j]+erase[j]);
					}
				}
			}
		}
		int ans = rec(0,(int)word.size()-1);
		if(ans>=INF)return -1;
		else return ans;
	}
};