また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; } }
まとめ
本番もうちょいややこしいやりかたしたけどまぁ通った。