はじめに

以前、厳選！Perl アルゴリズム実装に使える 25 の標準ライブラリ【前編】という記事を投稿しましたが、それが役立った話と、嵌った話です。

D - Banned K

AtCoder Beginner Contest 159 D - Banned K
ボールが N 個あり、i 番目のボールには整数 Ai が書かれています。

うまくいった話

各整数ごとの出現頻度を取得するために、以前の投稿の ハッシュの利用 が役立ちました。

hash.pl

$h{$_}++ for @list;

もう少し丁寧にすると

hash2.pl

for $_ (@list) {
  if (exists $h{$_}) { # ハッシュにキーが存在するか？
    $h{$_}++;
  } else {             # 存在しない場合
    $h{$_} = 1;
  }
}

Perl では存在しないキーのハッシュは未定義値を返しますので、未定義値に ++ 演算子を使用すると、0 + 1 => 1 の扱いとなり hash.pl の書き方でも正しく動作します。
流石 TMTOWTDI

どやっ

WA.pl

use v5.18; # strict say state
use warnings;

chomp (my $n = <STDIN>);
my @a = split / /, <STDIN>;
my (%h, %k, %g);
$h{$_}++ for @a;
my $sum = 0;
for (keys %h) {
  $sum += $k{$_} = $h{$_} * ($h{$_} - 1) / 2;
  $g{$_} = ($h{$_} - 1) * ($h{$_} - 2) / 2;
}
for (0..($n-1)) {
  say  $sum - $k{$a[$_]} + $g{$a[$_]};
}

WA

ぐぬぬ

嵌った話

後半の for ループの中の計算式をいろいろ触ってもうまくいかず、元のハッシュの中を見てみますと、

入力例1.txt

5
1 1 2 1 2

Keys	Values
1	3
2	1
2	1

あっ、2 が別れてカウントされている。
といいますか、2 の後ろに改行コード(見えない)が含まれていました。

before.pl

my @a = split / /, <STDIN>;

after.pl

chomp (my @a = split / /, <STDIN>);

他の競技者を参考にするなら

another.pl

my @a = map {$_ + 0} split (/ /, <STDIN>);

これも Perl の仕様で、

another.pl

print "2\n" + 0;                          # => 2
print "1 dollar 2 dollars" + "3 dollars"; # => 4

+ 演算子で数値と文字が混在した場合、先頭の数値部分のみを評価することを利用して、改行コードを除去しています。
やっぱり TMTOWTDI

他言語

java.java

int a = Integer.parseInt(scanner.next());

ruby.rb

a = gets.split.map(&:to_i)

後発のオブジェクト指向言語は型を指定して、スペースや改行コードをうまいことやってくれるんですよね。

まとめ

投稿した記事が役立った
新たな知見を得た
TMTOWTDI
隣の芝生は青く見える

参照したサイト
exists関数 - ハッシュのキーの存在確認

Perl AtCoder ABC 159 D で嵌った話、うまくいった話

はじめに

D - Banned K

うまくいった話

嵌った話

他の競技者を参考にするなら

他言語

まとめ