プロコン小技

目指せ三日坊主越え

周期

こんな問題があったとします。

問題：

n人が集まってゲームをやっている。各人は各々1から順に番号を持っていて、ゲームは1,2,3...n,1...という風に繰り返される。k回のゲームを行い、各人は自分の番が回ってくる度にカードを引く。そして、そのカードの値を自分の持ち点としていく。人数とゲーム回数、カードの数列が与えられた時、ゲームが全て終わった時点で一番多く点を保持している人の番号を出力してください。

input

5 12 (n k)

1 2 3 4 5 1 2 3 4 5 1 2 (a1 ~ ak)

output

5

例なので、範囲に関しては考えないでください(

こういう問題だと

int a[n];

int tmp;

int count = 0;

while(k--){

cin >> tmp;

a[count] += tmp;

count = count>=n?0:count+1;

}

int maxc = 0, idx = 0;

for(int i = 0; i < n; i++){

if(maxc<a[i]){

maxc = a[i];

idx = i;

}

}

cout << idx << endl;

こんな感じになるでしょう。単純に考えたら。

無論悪いコードではないです。基本的にはこれで十分そう。

ただもうちょい綺麗にかけたりします。

こんな感じです。

int a[n];

int maxc = 0, idx = -1;

for(int i = 0; i < k; i++){

cin >> tmp;

a[i%n] += tmp;

if(maxc<a[i%n]){

maxc = a[i%n];

idx = i%n;

}

}

cout << idx << endl;

めんどくさかったので、最大を求める奴も入れてしまいましたが、入れないと

int a[n];

for(int i = 0; i < k; i++){

cin >> tmp;

a[i%n] += tmp;

}

こんな感じになります。大分綺麗になりましたね。

剰余を取る際に、割った数をnとすると必ず

0,1,2,3~n-1

という範囲で値を取ります。今回のように、渡される入力は一列だが問題としては特定の周期でループしている場合などは、一周辺りの数で剰余を取ることで、常に一定の感覚で同じ値を得られるということです。

なので、例えば1周期3で考えると、

1,4,7,10,13...

は全て剰余が1になります。

このように、数学的(算数的？)考え方を取り入れることで、ごり押しで実装するよりも美しく実装することが出来ます。

ごり押しが悪いわけではありませんが、ある一定の水準を超えた後は、コードに綺麗さを求めるのも楽しいですよ。

今日はここまで。ではまたの機会に。