PKU演習問メモ - simezi

今日はTopCoderのSRMだ！2問解けるといいなあ。
恒例の今日通したPKUの問題メモ。

3094 Quicksum: 与えられた文字列の"Quicksum"という方式のチェックサムを計算する問題。
3062 Celebrity jeopardy: 与えられた解を持つ最も簡単な方程式を出力せよという問題。要するに入力の文字列を鸚鵡返しで出力するプログラムを書けという問題。
3085 Quick Change: おつりを25セント、10セント、5セント、1セント硬貨を使って枚数を最小にする支払い方を出力せよという問題。グリーディ。
3086 Triangular Sums: n番目の三角数をT(n)とするとき、Σ[1≦i≦n]n*T(n+1)を求めよという問題。long longを使えというアレ。
3077 Rounders: 与えられた整数nについて1の位について丸め、（その結果が10より大きかったら）もっとも近い10の倍数について丸め、（その結果が100より大きかったら）最も近い100の倍数について丸め……というのを繰り返せという問題。丸めとは四捨五入をさす。
3096 Surprising Strings: ある文字列がD-uniqueであるとは、文字列のうちD（D>0）離れた文字のペアが全て異なることである。ある文字列が全てのDについてD-uniqueであるときその文字列はSurprisingであるという。与えられた文字列がSurprisingかどうか判定せよ、という問題。O(n^2)の解法で間に合う。
3032 Card Trick: スペードの1からnまでで構成された山札がある。山札の一番からカードを一枚とって一番下に入れるという操作を一回行い、山札の次の一枚をめくるとスペードのAである。次にそのカードを取り除き、山札の一番上からカードを一枚とって一番下に入れてという操作を二回行い山札の次の一枚をめくるとスペードの2である。次に……ということを繰り返すと1からnまでのカードが順に現れる。このような山札の並び順を出力せよという問題。O(n^2)で通るんだけどSTLのrotateを（無理に）使ったら実装がちょっとややこしかったので下にソース添付。
3090 Visible Lattice Points: 座標平面の[0,N]×[0,N]の領域の格子点について、原点からその直線までに他の格子点が存在しないような点の数を求めよという問題。要するに分母がN以下の既約分数の個数が求める点の数の半分（引く1/2）なので、Eulerのphi関数を1からnまで足して二倍して1足せばおｋ.
1598 Excuses, Excuses!: 与えられたキーワード群が、文字列の中に一番多く入っている文字列を出力する問題。ちょっとジャッジデータが陰険（問題文に入ってない#などの記号が入っている）。

317問。正解数で1000位以内に入ったらしい。５月半ばまでに500問solvedを目指してみよう。

↓ソースとか。

3077 Rounders

int main()
{
	int pw[10]; pw[0]=1;
	rep(i,9)pw[i+1]=pw[i]*10;
	
	int cs; cin>>cs;
	while(cs--)
	{
		int n; cin>>n;
		
		for(int i=0;pw[i]<n;i++)
		{
			double d=1.0*n/pw[i];
			n=int(d+0.5)*pw[i];
		}
		
		cout<<n<<endl;
	}
	return 0;
}

3032 Card Trick

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		int n,cd[13]; cin>>n;
		for(int i=n;i>0;i--)
		{
			rotate(cd,cd+n-i,cd+n-i+1);
			cd[0]=i;
			rotate(cd,cd+((n-i+1)*n-i)%(n-i+1),cd+n-i+1);
		}
		rep(i,n)cout<<cd[i]<<(i==n-1?"\n":" ");
	}
	return 0;
}

考え方は以下の通り。

山札を逆から（nの数字のカードから）構成することを考える。

めくったカードはnの数字なので山札の最初にnのカードを入れる

以下iのカードを入れるときのことを考える。

このとき残りのカード（n-i+1枚）は一つずつ下にずれる
n回山札の上から下にカードを移す操作があったので、逆に下から上にn回カードを移す
山札の枚数だけその操作を繰り返す、と山札が元に戻る（0回操作したのと同じことになる）ので、要するにこれはn%(n-i+1)枚のカードを下から上に移す操作に同値
すなわちカードの(-i)%(n-i+1)枚目が次の山の最初に来る
余りを正にするために(n-i+1)*n（これは必ずiより大きいことに注意）を足す