【最大公約数】STEP: 1 規則的な数列の和 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】
【Aランクレベルアップメニュー】 > 【最大公約数】STEP: 1 規則的な数列の和 (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。
これもアルゴリズムを考えなければならない問題かな？自分にはこういう問題に対する柔軟な思考がなさそうだ(-_-;)
解答例
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
<?php $input = explode(" ",trim(fgets(STDIN))); $n = $input[0]; $k = $input[1]; $kn = $k - $n; if($n % 3 == 0){ $nn = -1; } elseif($n % 3 == 1){ $nn = 1; } elseif($n % 3 == 2){ $nn = 0; } if($kn % 3 == 0){ $kk = 0; } elseif($kn % 3 == 1){ $kk = -1; } elseif($kn % 3 == 2){ $kk = 1; } echo $nn + $kk; ?> |
解答方針
今回はpaiza解説のコピペ貼り付けで(;’∀’)
方針
- 素直に繰り返しで A の要素の足し算を行おうとすると、最大 10 ^ 12 回ループが回ることになってしまい、実行制限時間に間に合いません。そこで計算の工夫を行います。
- 数列 A の規則性に注目します。 A の連続する 3 つの要素の和は必ず 0 になります。そのため、N 項目から 3 要素ずつ区切っていき、最後に残った要素の和が答えとなります。
- 最後に残る要素は 0 要素 〜 2 要素であり、その要素は N , K を 3 で割った余りによって定まるので、N%3 , K%3 について場合分けを行うことで答えを求めることができます。
