結果
問題 | No.314 ケンケンパ |
ユーザー |
|
提出日時 | 2015-12-08 06:15:22 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 235 ms / 1,000 ms |
コード長 | 1,395 bytes |
コンパイル時間 | 460 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 20,096 KB |
最終ジャッジ日時 | 2024-09-14 19:31:59 |
合計ジャッジ時間 | 6,696 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
コンパイルメッセージ
Syntax OK
ソースコード
#! ruby# yukicoder My Practice# author: Leonardone @ NEETSDKASU# 解説読後# http://yukicoder.me/problems/882/editorial=beginゴルファーたちのコードを見てたら気付いたhttp://yukicoder.me/submissions/63762この考察が甘かったことにA[N + 1] = B[N] + C[N]B[N + 1] = A[N]C[N + 1] = B[N]これはさらに書き直せてA[N + 1] = B[N] + C[N] = A[N - 1] + B[N - 1] = A[N - 1] + A[N - 2]B[N + 1] = A[N]C[N + 1] = B[N] = A[N - 1]となるつまり A だけで関係式を表せるA[N + 1] = A[N - 1] + A[N - 2]A[1] = A[-1] + A[-2]A[2] = A[0] + A[-1]A[3] = A[1] + A[0]A[4] = A[2] + A[1]という感じになるからA[1]とA[2]とA[3]は事前に定義をしておくとかしたらいいのかなA[1] は 「ケン」のみで 1A[2] は 「ケンケン」と「ケンパ」で 2A[3] は 「ケンケンパ」「ケンパケン」で 2でよいのかな?A[N + 1] = A[N - 1] + A[N - 2]N だと分かりにくいので i で表すとA[i + 1] = A[i - 1] + A[i - 2]A[i + 1]をA[i]に直すとA[i] = A[i - 2] + A[i - 3]これでコードにしやすい表現になったあとは mod 1000000007 を忘れずにA[i] = (A[i - 2] + A[i - 3]) mod 1000000007=endMD = (10 ** 9) + 7a = [0] * ((10 ** 6) + 1)a[1] = 1a[2] = 2a[3] = 24.upto(10 ** 6) do |i|a[i] = (a[i - 2] + a[i - 3]) % MDendn = gets.to_ip a[n]