UTPC 2014 - ヘクトのメモ

今年もUTPCに個人で参加してきました．
結果は46位でした．

コンテスト中の状況を簡単に書きます．

0:00 Start!

A問題に取り組む．文字列除去なので，検索をして消せなくなるまで消せばよい．
ただ，String::nposとか忘れて辛かった．実装して提出．1WAを重ねる．
"not not note"で落ちることに気づく．マッチングの方法に穴があった．
他にも"not not not "が"not not not"にマッチングしないなどのバグで
2WAを重ねる．修正して提出．

0:33 A AC

次に，Bに取り掛かる．小数を1000倍して整数に直すparseを書く．
出力フォーマットが整数であることに気づかずに，小数で出力するミスをする．
いろいろ勘違いがあり，ドツボにはまり4WA...

1:30経過

さすがに，ひどいということで同じ100点のC問題を見る．
最小カットと最大カットというワードを見て，どうするんだろうと思っていたら，
n頂点n辺の連結グラフだから，木に1本辺が追加されたグラフだ．
ということで，最大カットはn-1+(偶数長の閉路ならば1，奇数長の閉路ならば0)
最小カットはグラフの最小次数で求められる．
ここで最小カットが常に1だと思い，1WA

1:57 C AC

ここからいろいろ問題を見ていき，Kの部分点が回すだけなので回す

2:33 K WA (30pt)

改めて，B問題を見る．小数部分の変化量を見て，1000倍すれば整数でもうまく計算できる．
余りの計算で負になっていることに気づかず、1WA

3:02 B AC

とりあえず，100点問題を全完したので，どの問題に取り組むか考える．

F問題にとりかかる．
元の数字と隣接した2数を交換したの数字Aと隣接した2数を交換したの数字Bが別の値になると勘違いする．
ここで，3桁の数字の時だけうまく行く例を投げる25点
そして，順位表を眺めながら200点多いなと思いながら考える．
バブルソートの交換回数でパリティを取ればよいことに気づく．

4:08 F AC

E問題に取り掛かる．
うまく伝搬させたいデータの流れをグラフで書いてみる．→ Trie木だ!
気づけば，すんなり書けて，サンプルチェックして提出 1WA
問題文にClarが飛んでいないかと調べると， i!=jならば ai!=ajとは限らないことに気づく．
修正する．

4:30 E AC

最後にD問題に取り掛かるけど，方針が迷走して終了でした．

5:00 Finish!

ソースコード

string s;

int main(void){
	getline(cin,s);
	int n=s.size();
	rep(loop,1000){
		int cur=0;
		while(s.find("not not ",cur)!=string::npos){
			int index=s.find("not not ",cur);
			if(s.substr(index,11)!="not not not"||(index+11<n&&s.substr(index,12)!="not not not ")){
				string t=s.substr(0,index)+s.substr(index+8);
				s=t;
				cur=index;
			}else
				cur+=4;
		}
	}
	cout << s << endl;
	return 0;
}

int parse(string in){
	int res=0;
	int n=in.size();
	rep(i,n){
		if(in[i]=='.'||in[i]=='-') continue;
		res=res*10+(in[i]-'0');
	}
	if(in[0]=='-') res*=-1;
	return res;
}

int main(void){
	string xx,yy;
	cin >> xx >> yy;
	int x=parse(xx);
	int y=parse(yy);
	int dx=x%1000;
	int dy=y%1000;
	int dy2=(1000-dy)%1000;
	if(dx<=0) dx+=1000;
	if(dy<=0) dy+=1000;
	if(dy2<=0) dy2+=1000;

	int ax=(x-dx)/1000;
	int ay=(y-dy)/1000;
	int ay2=(y+dy2)/1000;
	cout << ax << " " << ay << " " << ax-dx << " " << ay-dy << endl;
	cout << ax << " " << ay2 << " " << ax-dx << " " << ay2+dy2 << endl;
	return 0;
}

vi graph[100010];
int visited[100010];
int parity=-1;

void dfs(int v,int p=-1,int c=0){
	if(visited[v]==-1)
		visited[v]=c;
	else{
		parity=(visited[v]==c);
		return;
	}
	for(auto &v2:graph[v])
		if(v2!=p)
			dfs(v2,v,c^1);
}
int main(void){
	int n;
	cin >> n;
	rep(i,n){
		int a,b;
		cin >> a >> b;
		a--,b--;
		graph[a].pb(b);
		graph[b].pb(a);
	}
	rep(i,n) visited[i]=-1;
	dfs(0);
	int cmin=inf;
	rep(i,n) cmin=min(cmin,(int)graph[i].size());
	cout << cmin << " " << n-1+parity << endl;
	return 0;
}

int nexts=1;
ll x[1000010][10];
ll v[1000010];
ll s[1000010];

void insert(int num,ll value,int cur=0){
	if(num==0)
		v[cur]+=value;
	else{
		if(x[cur][num%10]==-1) x[cur][num%10]=nexts++;
		insert(num/10,value,x[cur][num%10]);
	}
	s[cur]=0LL;
	rep(i,10) if(x[cur][i]!=-1) s[cur]=max(s[cur],s[x[cur][i]]);
	s[cur]+=v[cur];
}

int main(void){
	int n;
	cin >> n;
	clr(x,-1);
	rep(i,n){
		int a; ll b;
		cin >> a >> b;
		insert(a,b);
		cout << s[0] << endl;
	}
	return 0;
}

int func(string a){
	int n=a.size();
	int cur=0;
	rep(i,n){
		for(int j=0;j<n-1;++j){
			if(a[j]>a[j+1]){
				cur++;
				swap(a[j],a[j+1]);
			}
		}
	}
	return cur%2;
}

int main(void){
	int t;
	cin >> t;
	rep(loop,t){
		string in;
		cin >> in;
		cout << func(in) << endl;
	}
	return 0;
}

感想
今年も面白い問題が多かった．K問題はぜひ復習しておきたい．
打ち上げも行って，いろいろ面白い話を聞けた．
(chokudaiさんに懐かしいイタズラをされたり，2次会もいろいろ)
さて，UTPCは年度末コンテストになっていくのだろうか?