はじめに
Rubyおよびアルゴリズムの学習の一環として競技プログラミングに参加しています。
ここでは、学習の中で学んだことをアウトプットしています。
今回はハッシュについて。
この記事執筆のきっかけは、第三回アルゴリズム実技検定、第五問「スプリンクラー」。
この問題、ハッシュを用いるとスムーズに解答出来るような問題だったのですが、
ハッシュについての理解が浅かった僕は検定中にこの問題に解答出来ず…
という訳で今回は、
①この問題にハッシュを使って解答する
②解答をもとにハッシュの使い方を考えてみる
このような流れで、自分なりにまとめてみたいと思います。
問題
1,2,3,...,N と番号が付いたN個の頂点と、1,2,3,...,M の番号が付いた M 本の無向辺からなる無向グラフが与えられます。
辺 i は頂点 ui と vi を双方向につないでいます。
それぞれの頂点には色を塗ることが可能で、はじめ頂点 i は色 ci で塗られています。
(この問題において、色は 1 以上 10**5 以下の整数で表されます)。
それぞれの頂点にはスプリンクラーが設置されています。
頂点 i にあるスプリンクラーを起動すると、
頂点 i に隣接する全ての頂点の色がスプリンクラー起動時点の頂点 i の色で塗り替えられます。
以下の形式で与えられる Q 個のクエリ s1,s2,…,sQ を順番に処理してください。
- 頂点 x の現在の色を出力する。その後、頂点 x にあるスプリンクラーを起動する。1 x という形式で与えられる。
- 頂点 x の現在の色を出力する。その後、頂点 x の色を y で上書きする。2 x y という形式で与えられる。
制約
- 与えられる入力は全て整数
- 1≤N,Q≤200
- 0≤M≤N(N−1)/2
- 1≤ui,vi≤N
- 1≤ci≤10**5
- i は下記のいずれかの形式の文字列
- '1 x'(1≤x≤N)
- '2 x y' (1≤x≤N,1≤y≤10**5)
- 与えられるグラフに多重辺や自己ループは存在しない
入力は以下の形で与えられる。
N M Q
u1 v1
⋮
uM vM
c1 c2 ⋯ cN
s1
⋮
sQ
入力例
3 2 3
1 2
2 3
5 10 15
1 2
2 1 20
1 1
出力例
10
10
20
問題のイメージは以下のような感じです。
解答
今回、他の方の解答を参考にして解答を作らせて頂きました。
N, M, Q = gets.split(" ").map(&:to_i)
H = Hash.new{|hash, key| hash[key] = []} #①空のハッシュ作成
M.times do
u, v = gets.split(" ").map(&:to_i)
H[u].push(v) #②ハッシュへの追加
H[v].push(u) #②ハッシュへの追加
end
C = gets.split(" ").map(&:to_i)
C.insert(0, nil)
Q.times do
x,y,z = gets.split(" ").map(&:to_i)
puts C[y]
if x == 1
H[y].each{|i| C[i]=C[y] }
else
C[y] = z
end
end
この解答について、
ハッシュの作成とハッシュへのキーと値の追加について、
次回の解答で使うため、イメージを掴めるようにまとめてみます。
①空のハッシュ作成
上記の解答では、Hashクラスのnewメソッドにブロック {} を与える形で空のハッシュを準備しています。
H = Hash.new{|hash, key| hash[key] = []}
ハッシュにキーと値を追加する度に、ブロックでの評価が行われ、オブジェクトが生成されます。
上記のコードでは、空の配列を値のデフォルト値としています。
これは、今回解答する問題が、ひとつのキーに対して複数の値が存在する可能性がある問題のためです。
（キーにはひとつの頂点、値にはその頂点に隣接する（辺でつながっている）頂点が入る）
②ハッシュへの追加
標準入力から受け取ったオブジェクトをキーと値としてハッシュに追加しています。
今回の解答では、値はデフォルト値として設定された配列に要素として追加します。
u, v = gets.split(" ").map(&:to_i)
H[u].push(v) # u をキー、 v を値として
#配列への追加なので「<<」の記号を使ってもOKです。
H[u] << v
ここまでのイメージを自分なりにまとめてみました。
ちょっと散らかっちゃってますが、ようやくイメージが掴めてきた気がします。
ハッシュを使いたい時は、
①ブロックでキーと値の関係性を設定する。
②キーをハッシュに追加する度、①に従って値が用意される。
③値への追加や変更を行う場合は、デフォルト値の形に合わせて行う。
ひとまず今回の問題については、このような形で攻略出来ることが分かりました。
最後に
以上、ハッシュの作成やキー・値の追加について自分なりにまとめてみました。
ハッシュをどんどん使っていって、自分のものにしていきたいです。
リファレンスなどを読みながらまとめたつもりですが、
もし間違いなどございましたら、ご指摘いただけると嬉しいです。