PKU200問

ひたすらハイエナ作戦。
(ランキングから他の人の解いてる問題が見られるので、その中で解きやすそうな問題を解くという作戦w)


Problem Statusによる問題の難易度推測ができるようになってきた。
Submission5000以下くらいのものについてはAC数を見ることで、

3000以上
簡単な実装系
2000〜3000
簡単な数学問題
1000〜2000
有名アルゴリズムダイクストラ法、プリム法、単純な動的計画法など)
1000未満
簡単ではない

がおおよそ判別可能。さらにTLEの数を見ることで、
何か特殊なアルゴリズムを使用する必要がある、もしくはC++のStringコンテナやVectorコンテナを使用してはいけない(Cの文字列、配列を使う必要がある)ということまでも判別可能。


Submission5000以上だとまた話が変わってくるけれど。


や、凄くどうでもいいね……
面白かった問題の解説でも書こう。

2499 Binary Tree

簡単な数学問題。


無限の深さを持つ二分木があり、

  • 根は(1,1)の値を持つ
  • あるノード(a,b)は(a+b,b)と(a,a+b)の二つの子を持つ

x,y≦20億なる自然数x,yが与えられたとき、根からノード(x,y)に最短距離で移動したい。
このとき左右にそれぞれ何回移動するか。


ノード(x,y)から(1,1)まで逆に辿ることを考える。
ノード(a,b)の親はa>bの時(a-b,b)であり、(a,b)はこの親の左側の子。
グラフは木なのでこれを繰り返せば(1,1)までたどり着くことが可能。


ただしこれをナイーブに実装するとTLEになるので、
a>bの時(a-b,b)へ進むループの代わりに割り算を使って回数を出す。

int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		int a,b; cin>>a>>b;
		
		int l=0,r=0;
		while(a&&b)
		{
			if(a>b)l+=a/b,a%=b;
			else r+=b/a,b%=a;
		}
		//aまたはbが0になっている。根は(1,1)なので、
		//余分に移動した分を引く。
		if(a==0)l--;
		if(b==0)r--;
		
		cout<<"Scenario #"<<cs+1<<":"<<endl;
		cout<<l<<" "<<r<<endl<<endl;
	}
	
	return 0;
}

(main部分のみ)