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

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

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!

ソースコード

A

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;
}

B

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;
}

C

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;
}

E

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;
}

F

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は年度末コンテストになっていくのだろうか?