はじめに
以前、*厳選！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関数 - ハッシュのキーの存在確認