【最大公約数】STEP: 1 規則的な数列の和 (paizaランク C 相当) 解答例 – PHP編【Aランクレベルアップメニュー】

Pocket

【Aランクレベルアップメニュー】 > 【最大公約数】STEP: 1 規則的な数列の和 (paizaランク C 相当)
※リンク先へ移動する為には「paiza」へのログインが必要です。

arank-menu-step7-1a

これもアルゴリズムを考えなければならない問題かな?自分にはこういう問題に対する柔軟な思考がなさそうだ(-_-;)

解答例

解答方針

今回はpaiza解説のコピペ貼り付けで(;’∀’)

方針

  • 素直に繰り返しで A の要素の足し算を行おうとすると、最大 10 ^ 12 回ループが回ることになってしまい、実行制限時間に間に合いません。そこで計算の工夫を行います。
  • 数列 A の規則性に注目します。 A の連続する 3 つの要素の和は必ず 0 になります。そのため、N 項目から 3 要素ずつ区切っていき、最後に残った要素の和が答えとなります。
  • 最後に残る要素は 0 要素 〜 2 要素であり、その要素は N , K を 3 で割った余りによって定まるので、N%3 , K%3 について場合分けを行うことで答えを求めることができます。

arank-menu-step7-1

エッグ

シェアする

コメントを残す

メールアドレスが公開されることはありません。

コメントする