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

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest 129 C - Typical Stairs
Difficulty: 795

前編のテーマは、フィボナッチ

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 さん、コメントありがとうございました。

階段の上がり方は、上記の通りですが、勘のいい方は フィボナッチ数 であることに気付くと思います。

そこで、連続した階段数を求め例.#.#...->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 では実数扱いとなり、小数点以下の誤差により WA となり嵌りましたますので、お気を付けください。

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 を使用しないと RE になるのは、お約束です。

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

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

別解へ続く

まとめ

• ABC 129 C を苦労して解いた
• Ruby に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった