Ruby と Perl と Java で解く AtCoder ABC 129 C (前編)

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Beginner Contest 129 C - Typical Stairs](https://atcoder.jp/contests/abc129/tasks/abc129_c)*
<font color="brown">Difficulty: 795</font>

前編のテーマは、フィボナッチ
# Ruby
|階段数|組合せパターン|組合せ数|
|:--:|:--|:--:|
|1|1|1|
|2|1-2|1|
|3|1-2-3/1-3|2|
|4|1-2-3-4/1-2-4/1-3-4|3|
|5|1-2-3-4-5/1-2-3-5/1-2-4-5/1-3-4-5/1-3-5|5|
**追記** 階段数 = 足元の段 ＋ 次の段 です。
@swordone さん、コメントありがとうございました。

階段の上がり方は、上記の通りですが、勘のいい方は **[フィボナッチ数](https://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A3%E3%83%9C%E3%83%8A%E3%83%83%E3%83%81%E6%95%B0)** であることに気付くと思います。

そこで、連続した階段数を求め`例.#.#...`->`1, 1, 3`、組合せ数を総乗していきます。`fib(1) * fib(1) * fib(3)`

```ruby.rb
n, m = gets.split.map(&:to_i)
a = []
1.upto(m) do |i|
  a[i] = gets.to_i
end
a[0] = -1
a.push(n + 1)
b = []
1.upto(m + 1) do |i|
  if a[i] - a[i - 1] == 1
    puts "0"
    exit
  end
  b.push(a[i] - a[i - 1] - 1)
end
fib = []
fib[1] = 1
fib[2] = 1
3.upto(n + 1) do |i|
  fib[i] = fib[i - 1] + fib[i - 2]
  fib[i] %= 1_000_000_007
end
ans = 1
0.upto(b.size - 1) do |i|
  ans *= fib[b[i]]
  ans %= 1_000_000_007
end
puts ans
```
```WA.rb
  ans %= 1_000_000_007
  ans %= 1e9 + 7
```
除数を 1e9 + 7 と記載しますと、*Ruby* では実数扱いとなり、小数点以下の誤差により <font color="orange">WA</font> となり~~嵌りました~~ますので、お気を付けください。
# Perl
```perl.pl
chomp (my ($n, $m) = split / /, <STDIN>);
my @a;
for my $i (1..$m) {
  chomp (my $in = <STDIN>);
  $a[$i] = $in;
}
$a[0] = -1;
push @a, $n + 1;
my @b;
for my $i (1..$m+1) {
  if ($i != 1 && $a[$i] - $a[$i - 1] == 1) {
    print "0\n";
    exit;
  }
  push @b, $a[$i] - $a[$i - 1] - 1;
}
my @fib;
$fib[1] = 1;
$fib[2] = 1;
for my $i (3..$n+1) {
  $fib[$i] = $fib[$i - 1] + $fib[$i - 2];
  $fib[$i] %= 1e9 + 7;
}
my $ans = 1;
for my $i (@b) {
  $ans *= $fib[$i];
  $ans %= 1e9 + 7;
}
print "$ans\n";
```
*Perl* は *Ruby* 以上に動的な型です。
# Java
```java.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int m = Integer.parseInt(sc.next());
        int a[] = new int[m + 2];
        for (int i = 1; i <= m; i++) {
            a[i] = Integer.parseInt(sc.next());
        }
        sc.close();
        a[0] = -1;
        a[m + 1] = n + 1;
        List<Integer> b = new ArrayList<>();
        for (int i = 1; i <= m + 1; i++) {
            if (a[i] - a[i - 1] == 1) {
                System.out.println(0);
                return;
            }
            b.add(a[i] - a[i - 1] - 1);
        }
        long fib[] = new long[n + 2];
        fib[1] = 1;
        fib[2] = 1;
        for (int i = 3; i <= n + 1; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
            fib[i] %= 1_000_000_007;
        }
        long ans = 1;
        for (int i = 0; i < b.size(); i++) {
            ans *= fib[b.get(i)];
            ans %= 1_000_000_007;
        }
        System.out.print(ans);
    }
}
```
long を使用しないと <font color="orange">RE</font> になるのは、お約束です。

||Ruby|Perl|Java|
|:--:|:--:|:--:|:--:|
|コード長|457 Byte|522 Byte|1106 Byte|
|実行時間|64 ms|85 ms|343 ms|
|メモリ|3836 KB|10368 KB|45652 KB|

いつもはこれにて終了なのですが、今回はコーナーケースで散々な目に会いましたので、別解を投稿します。

*[別解へ続く](https://qiita.com/superrino130/items/b9cad212d64f8bcb0eda)*
# まとめ
+ ABC 129 C を苦労して解いた
+ Ruby に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった