#63762 (Ruby) No.314 ケンケンパ

• 問題: 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

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#! 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
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX