【Ruby】ハミング距離を使ってABC480 B問題を解く
こんにちは、しきゆらです。
今回は、この記事の執筆時点で直近に開催されたAtCoderのABC480のB問題を解く中でハミング距離というものを知ったのでまとめます。
問題の概要
この記事を書いている直近に開催されたABC480のB問題で以下のような状況が提示されました。
Tj が名前に完全に一致している候補者がいる場合、その候補者に 1 票が入ります。 そうでなく、Tj を 1 文字書き換えて名前が一致するような候補者がちょうど 1 人いる場合、その候補者に 1 票が入ります。 そうでない場合、それは無効票となります。
候補者のリストと投票用紙の記載された文字列のリストを渡され、投票用紙に記載された文字列に対して、以下の処理をします。
- 候補者名と一致した場合、その候補者に1票加える
- 投票用紙に記載された文字列に対して、1文字置き換えて名前が一致するような候補者が1名のみいる場合、その候補者に1票加える
- そうでない場合、無効票とする
上記の番号において、処理1に関しては一致するかどうかを判定すれば良いので容易に判定可能です。
処理2に関しては、1文字置き換えて名前と一致する、というものをどう表現すれば良いかパッと思い浮かびませんでした。
先頭から一致しているかをみるしかないか、と思いますが文字数が異なる場合や該当候補者が複数名存在する場合をどうすれば良いかわかりませんでした。
調べてみると、この問題で求められている「1文字置き換えて名前が一致する」というものを求めるアルゴリズムがあることを知りました。
それが「ハミング距離」です。
ハミング距離
IT用語辞典から引用します。
ハミング距離とは、同じ長さの二つの符号列を比較した際に、対応する位置の符号が異なっている箇所の数を表す指標。
IT用語辞典では符号列となっていますが、文字列や数値を比較するときに使われるようです。
ということで、これを使えば良さそうです。
ハミング距離の実装もシンプルに以下のような感じになります。
def hamming_dist(base, target)
# 空文字列の場合、文字数が異なる場合は比較対象外
return nil if base.empty? || base.size != target.size
# 比較元の文字列に対して1文字ずつ比較し、一致しない文字数を数える
base.each_char.with_index.count { |b, index| b != target[index] }
endハミング距離を使ってABC480 B問題を解く
B問題を解くとすると、こんな感じになるかと思います。
問題の条件から、入力される候補者名や投票用紙に記載された値は文字列なのでそれを前提とした処理をしています。
# frozen_string_literal: true
def hamming_dist(base, target)
return nil if base.empty? || base.size != target.size
base.each_char.with_index.count { |b, index| b != target[index] }
end
input = $stdin.read.split("\n")
n, m = input[0].split.map(&:to_i)
names = input[1, n]
# 候補者名とその票数を保持するHashを作成
result = names.zip(Array.new(n, 0)).to_h
m.times do |num|
voted_name = input[n + num + 1]
# 投票用紙の値と候補者名が完全一致する場合
if result.key?(voted_name)
result[voted_name] += 1
else
# 候補者名と投票用紙の値のハミング距離を計算し、その値が1のもののみを抽出
candidates = names.select { |name| hamming_dist(name, voted_name) == 1 }
result[candidates.first] += 1 if candidates.size == 1
end
end
puts result.values
実装としては、候補者の名前をキーとするHashを作成し、そのHashで票数を管理しています。
記載された文字列に対して、完全一致するかどうかはHash#key?で判定し、それ以外は今回学んだハミング距離で対象稼働かを判定しています。
また、ハミング距離が1となる候補者が1人の場合のみその候補者の有効票となるためnames.selectで処理しています。
実行例
ABC480 B問題の入力例を用いて動作確認してみます。
入力例 1
$ ruby abc480/b.rb
# 入力
5 8
takahashi
aoki
sato
kato
kano
aoki
takanashi
sano
atcoder
chokudai
kato
aoki
yato出力1
1
2
0
1
0入力例2
$ ruby abc480/b.rb
# 入力
2 5
a
b
a
b
c
a
aa出力2
2
1合っていそうです。
補足
今回の問題の条件設定から候補者名や投票用紙は最大でも100枚なので上記で問題ないと思いますが
より候補者数や投票用紙数が多くなった場合はlazy.select{...}.first(2)を使うと無駄なチェックを除外できそうです。
今回の学び
今回は、2つの文字列を比較し、異なる箇所を探すアルゴリズムとして「ハミング距離」というアルゴリズムがあることを知ったのでメモしました。
2つの文字列を比較し、片方の文字列に1個の記号を挿入・削除・置換をしてもう一方へ変換するための最小操作回数を表すレーベンシュタイン距離や、2点間の距離を求めるユークリッド距離など、「〇〇距離」と呼ばれるアルゴリズムはいくつか知っていましたが、ハミング距離は今回初めて知りました。
実装自体はシンプルで理解しやすく、「ハミング距離」という名前を知らなくても実装できるようなものでした。
私は、C言語や古典的なJavaScriptでのforを使った処理が頭の中に出てきて、それをRubyぽい書き方にしようとしてごっちゃになり、どう書けば良いのか分からなくなって考えが止まってしまう場面がちらほらあるため、修行が足りないな、と思った今日この頃でした。
まとめ
今回は、AtCoderの問題を解く中でハミング距離について触れたのでまとめてみました。
そして、実際にABC480のB問題をハミング距離を使って解いてみました。
今回はC問題でなくB問題でしたが、ここ最近参加した中では見たことない形式の問題が出題されると手が止まってしまうんだな、ということがわかりました。
手が空いているときに、どんどん色々な問題に触れて、すぐに解けなくても「似た問題をやった気がする」というところまで行きたいな、と思った今日この頃でした。
今回は、ここまで。
おわり