kmjp's blog

競技プログラミング参加記です

TopCoder SRM 747 Div1 Easy, Div2 Hard MostFrequentLastDigit

またMedium落としてごっそりレート引かれた。
https://community.topcoder.com/stat?c=problem_statement&pm=15286

問題

正整数Nと、1桁の整数dが指定される。
以下を満たす数列を構築せよ。

  • 素数Nであり、全要素互いに異なる。
  • 1の位はいずれも非0
  • 2つの要素の対N*(N-1)/2通りにおいて和の1の位の最大多数はdである。

解法

10の位以上を徐々に上げれば、要素が異なるという条件は余裕でクリアできる。
あとは要素の半分を1の位を1、残りをd-1にすればよい。
d=1の場合は後者の1の位が0になってしまうので、代わりに2と9等にすればよい。

class MostFrequentLastDigit {
	public:
	vector <int> generate(int n, int d) {
		vector<int> V;
		int i,C[2]={};
		if(d==1) C[0]=2;
		else C[0]=1;
		C[1]=(d+10-C[0])%10;
		FOR(i,n) V.push_back(i*10+C[i%2]);
		
		return V;
	}
}

まとめ

本番もうちょいややこしいやりかたしたけどまぁ通った。