結果

問題 No.314 ケンケンパ
ユーザー Leonardone
提出日時 2015-12-08 06:38:30
言語 Ruby
(3.4.1)
結果
AC  
実行時間 234 ms / 1,000 ms
コード長 1,466 bytes
コンパイル時間 194 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 20,096 KB
最終ジャッジ日時 2024-09-14 19:32:17
合計ジャッジ時間 5,752 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

#! ruby
# yukicoder My Practice
# author: Leonardone @ NEETSDKASU

# 解説読後
# http://yukicoder.me/problems/882/editorial

=begin

http://yukicoder.me/submissions/63826
これで問題の答えの考察を忘れてた

answer[N] = A[N] + B[N] + C[N] なわけで
これを直すと
answer[N] = A[N] + B[N] + C[N] = A[N] + A[N - 1] + B[N - 1] = A[N] + A[N - 1] + A[N - 2]
A[N + 1] = A[N - 1] + A[N - 2]なので
answer[N] =  A[N] + A[N - 1] + A[N - 2] = A[N] + A[N + 1]
A[N] + A[N + 1] = A[N + 1] + A[N] = A[(N + 2) - 1] + A[(N + 2) - 2] = A[(N + 2) + 1] = A[N + 3]
つまり
answer[N] = A[N + 3]
ということに

これだと答えあわない・・・！？

じゃなかった
答えあわないのは A[1], A[2], A[3] の定義が間違いだから
http://yukicoder.me/submissions/63762
でのA[1] B[1] C[1]の定義を使うべきだった
A[1] = 0
B[1] = A[1 - 1] = A[0] = 1
C[1] = B[1 - 1] = B[0] = A[0 - 1] = A[-1] = 0

rubyではインデックスにマイナスが使える
（配列後方のインデックスになるので後方に-1の分の1個余分に増やせばよい)

http://yukicoder.me/submissions/63826
で答えが合ってたのは
結果的にAのインデックスを-3個ずつずらした状態になってたからであるのであった

=end

MD = (10 ** 9) + 7
N = 10 ** 6
a = [0] * (((N + 3) + 1) + 1)

a[1] = 0
a[0] = 1
a[-1] = 0
2.upto(N + 3) do |i|
    a[i] = (a[i - 2] + a[i - 3]) % MD
end

n = gets.to_i

p a[n + 3]
0