PKU300問！！ - simezi

半月前に立てた目標の「今月中にPKU300問」何とか達成できた。

2608 Soundex: 文字列を規則にしたがって変換する問題。
2853 Sequence Sum Possibilities: 与えられた整数n（n＜2^31）が、何通りの連続する自然数の和で表すことが出来るか求める問題。項数をiとしてiを2から（i*(i+1)/2がn以下の間）順に調べていけばいい。
2876 Cantoring Along: カントール集合を出力する問題。シェルピンスキーのカーペットを先にやってたので楽だった……
2894 Ancient Keyboard: キーボードのような入力デバイスをシミュレートする問題。ただし各キーにはLEDランプがついていて、そのキーを押すとランプの明滅が変化して、1秒ごとについているランプの数番目のアルファベットが出力される。
3511 Fermat's Christmas Theorem: l以上u以下の、二つの平方数で表すことのできる素数の数を求める問題。pが奇素数ならば4n+1の形をしていることと二つの平方数で表されることは同値であることを使ってよい。エラトステネスの篩書いて求めればいいのだけど、ジャッジデータがいっぱいあるっぽいので表を作らないとTLE.それからl,uが負の場合があって、対策しないとREが出る模様。

さて明後日CodeforcesのRound#7、日曜にはSRMがある。
才能ないのはわかってるが赤になりたい。どういう練習したらいいのかなー。

2876 Cantoring Along

int pw[13];
char ans[531442];

void rec(int d,int c)
{
	if(d==0)return;
	
	rep(i,pw[d-1])ans[i+c+pw[d-1]]=' ';
	rep(i,3)if(i!=1)rec(d-1,c+pw[d-1]*i);
}

int main()
{
	pw[0]=1;
	rep(i,12)pw[i+1]=pw[i]*3;
	
	fill(ans,ans+531442,'-');
	rec(12,0);
	
	int n;
	while(cin>>n)
	{
		char c=ans[pw[n]];
		ans[pw[n]]='\0';
		
		cout<<ans<<endl;
		
		ans[pw[n]]=c;
	}
	
	return 0;
}

今回は消去してく形にしてみた。

2894 Ancient Keyboard

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		int n; cin>>n;
		int l[1000]={0};
		rep(i,n)
		{
			char c; int a,b; cin>>c>>a>>b;
			for(int i=a;i<b;i++)l[i]++;
		}
		string ans;
		rep(i,1000)if(l[i])ans.pb(l[i]+'A'-1);
		cout<<ans<<endl;
	}
	return 0;
}

押したキーは関係ないっていう。