結果

問題 No.314 ケンケンパ
コンテスト
ユーザー Leonardone
提出日時 2015-12-08 00:52:45
言語 Ruby
(3.4.1)
結果
AC  
実行時間 274 ms / 1,000 ms
コード長 2,737 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-09-14 18:47:37
合計ジャッジ時間 3,734 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

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

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

=begin

解説がACコード読めとあったので
ACのコードをいくつか読んで

要は
ある時点で「パ」の状態で終わっているパターン数
ある時点で「ケン」の状態で終わっているパターン数
ある時点で「ケンケン」の状態で終わっているパターン数
これを動的計画法とやらでNの小さいほうから積み重ねていく感じらしい（？）
そしてこの3種のパターン数の和が求める答えとなるということらしい

初期値 N=1として
A[1] = 0 「パ」で終わっている状態
B[1] = 1 「ケン」で終わっている状態
C[1] = 0 「ケンケン」で終わっている状態

N=2では
N=1で「パ」で終わっているパターンは次は「ケン」に
N=1で「ケン」で終わっているパターンは「パ」か「ケンケン」に
N=1で「ケンケン」で終わっているパターンは「パ」に
つまり
「パ」で終わる       A[2] = B[1] + C[1] = 1 + 0 = 1
「ケン」で終わる     B[2] = A[1] = 0
「ケンケン」で終わる C[2] = B[1] = 1

N=3では同様に
N=2で「パ」で終わっているパターンは次は「ケン」に
N=2で「ケン」で終わっているパターンは「パ」か「ケンケン」に
N=2で「ケンケン」で終わっているパターンは「パ」に
つまり
「パ」で終わる       A[3] = B[2] + C[2] = 0 + 1 = 1
「ケン」で終わる     B[3] = A[2] = 1
「ケンケン」で終わる C[3] = B[2] = 0

これを繰り返していけば答えが求まるということに

一般化すると
A[N + 1] = B[N] + C[N]
B[N + 1] = A[N]
C[N + 1] = B[N]

んで答えは answer = A[N] + B[N] + C[N]

「パ」で終わる部分だけ和で求めるので桁が増えすぎないように mod 100000007 を行うと
つまり
A[N + 1] = (B[N) + C[N]) mod 100000007

当然答えもmod 100000007 しておくべき

answer = (A[N] + B[N] + C[N]) mod 100000007

=end


n = gets.to_i

MD = (10 ** 9) + 7

a = 0 # n=1で「パ」で終わるパターン数
b = 1 # n=1で「ケン」で終わるパターン数
c = 0 # n=1で「ケンケン」で終わるパターン数


2.upto(n) do
    
    # ta は A[N+1]、 aは A[N]
    # tb は B[N+1]、 bは B[N]
    # tc は C[N+1]、 cは C[N]
    
    ta = (b + c) % MD  # 次に「パ」で終わるパターン数
    tb = a             # 次に「ケン」で終わるすパターン数
    tc = b             # 次に「ケンケン」で終わるパターン数
    
    a, b, c = ta, tb, tc  # パターン数の更新
    
end

p (a + b + c) % MD
0