Ruby と Perl で解くAtCoder ABC 161 D 幅優先探索

はじめに

AtCoder の AtCoder Beginner Contest 161 の D問題が解けなかったので、復習を兼ねて投稿しました。

お礼

オフィシャルの解説やネット上の解説・解答を参照して理解を進めております。
AtCoder さん、競技プロプレイヤーさん、ありがとうございます。

なぜTLE

ループを三重にしていることもありますが、Perl では、最小公倍数を求める関数が準備されていないことも要因に挙げられます。

幅優先探索

幅優先探索といえば、次のようなマップ・迷路問題で使用されます。

# ...#.#
..#...#
.#..#..

所謂、ある地点での上下左右において、. だったらキューに追加、# だったらキューに追加しない、というふうな解法を行います。

今回の D問題はそれを応用させ、末尾の数字 (仮に 3とします) のルンルン数 (2, 3, 4) をキューに追加することにより解いていきます。

また、マップ・迷路問題ではゴールにたどり着いた時点もしくは、全マップを探索した時点でループを終了しますが、今回は K番目に到達した時点でループを終了します。

今回のD問題
AtCoder Beginner Contest D - Lunlun Number

Ruby

Ruby.rb

k = gets.chomp.to_i
cnt = 0
que = []
(1..9).each do |i|
  que.push(i)
  cnt += 1
  if cnt == k
    puts i
    exit
  end
end
while que.size > 0 do
  n = que.shift
  if n % 10 == 0
    cnt += 1
    if cnt == k
      puts n * 10
      exit
    end
    que.push(n * 10)
    cnt += 1
    if cnt == k
      puts n * 10 + 1
      exit
    end
    que.push(n * 10 + 1)
  end
  if n % 10 != 0 && n % 10 != 9
    cnt += 1
    if cnt == k
      puts n * 10 + n % 10 - 1
      exit
    end
    que.push(n * 10 + n % 10 - 1)
    cnt += 1
    if cnt == k
      puts n * 10 + n % 10
      exit
    end
    que.push(n * 10 + n % 10)
    cnt += 1
    if cnt == k
      puts n * 10 + n % 10 + 1
      exit
    end
    que.push(n * 10 + n % 10 + 1)
  end
  if n % 10 == 9
    cnt += 1
    if cnt == k
      puts n * 10 + 8
      exit
    end
    que.push(n * 10 + 8)
    cnt += 1
    if cnt == k
      puts n * 10 + 9
      exit
    end
    que.push(n * 10 + 9)
  end
end

キューに push して while で回して shift で取り出す要領で、幅優先探索を実行します。

Perl

Perl.pl

use v5.18; # strict say state
use warnings;
use List::Util qw(reduce first max min sum0);

chomp (my $k = <STDIN>);
my @que;
my $cnt;
for my $i (1..9) {
  push @que, $i;
  $cnt++;
  if ($cnt == $k) {
    say $i;
    exit;
  }
}
while (@que) {
  my $i = shift @que;
  if ($i % 10 == 0) {
    $cnt++;
    if ($cnt == $k) {
      say $i.'0';
      exit;
    }
    push @que, $i.'0';
    $cnt++;
    if ($cnt == $k) {
      say $i.'1';
      exit;
    }
    push @que, $i.'1';
  } elsif ($i % 10 != 0 && $i % 10 != 9) {
    $cnt++;
    if ($cnt == $k) {
      say $i.($i % 10 - 1);
      exit;
    }
    push @que, $i.($i % 10 - 1);
    $cnt++;
    if ($cnt == $k) {
      say $i.($i % 10);
      exit;
    }
    push @que, $i.($i % 10);
    $cnt++;
    if ($cnt == $k) {
      say $i.($i % 10 + 1);
      exit;
    }
    push @que, $i.($i % 10 + 1);
  } else {
    $cnt++;
    if ($cnt == $k) {
      say $i.'8';
      exit;
    }
    push @que, $i.'8';
    $cnt++;
    if ($cnt == $k) {
      say $i.'9';
      exit;
    }
    push @que, $i.'9';
  }
}

Perl の方は、数字を文字としても扱う様なコーディングにしています。

	Perl(文字)	Perl(数字)	Ruby
実行時間	56 ms	42 ms	25 ms
ここでは、Ruby が速い結果となりました。

まとめ

• ABC 162 C を解いた
• メモ化の応用ができるようになった

参照したサイト
Rubyの配列で使えるメソッド、二次元配列の使い方