【AtCoder:14回目】AtCoder Beginner Contest 137の振り返り（Ruby）

【目次】

【本題】

振り返り

今回は 8/10(土)に開催されたAtCoder Beginner Contest 137の振り返りを行います。

AtCoder Beginner Contest 137 - AtCoder

今回は３問回答出来ました

レーティング微増

A - +-x

問題文 整数 A , B があります。

A + B ,

A − B ,

A × B の中で最大の数を出力してください。

制約 入力は全て整数である。 − 100 ≤ A ,

B ≤ 100

足し算・引き算・掛け算の３パターンの中から最大値を求める問題ですが、これをif文で書こうとすると冗長です。

なので、配列内で計算し、それをmaxメソッドで抽出する方法で計算しました。

それがこちらです。

a,b = gets.split.map(&:to_i)
puts [a+b, a-b, a*b].max

B - One Clue

問題文 数直線上に 2000001 個の石が置かれています。これらの石の座標は − 1000000 , − 999999 , − 999998 , … , 999999 , 1000000 です。

これらの石のうち、ある連続する K 個の石が黒で塗られており、それ以外の石は白で塗られています。

また、座標 X にある石は黒で塗られていることが分かっています。

黒で塗られている石が置かれている可能性のある座標をすべて、小さい順に出力してください。

制約 1 ≤ K ≤ 100 0 ≤ X ≤ 100 入力中の値はすべて整数である。

これは、座標から最も左に石が塗られているパターンと、最も右に塗られているパターンの２通りだけを把握すれば、その両端の間の座標で石が塗られている可能性のあると分かります。

座標xには既に一つ石が塗られているので、最左端はx-(k-1)、最右端はx+(k-1)で求められます。

Rubyで連番の出力する場合は、範囲オブジェクトの左に*を記述すれば良いです。

[*1..10]
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

そして、範囲オブジェクトは変数で生成することも出来ます。

a = 1
b = 10

[*a..b]
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

その結果、完成させたコードがこちらです。

k,x = gets.split.map(&:to_i)
puts [*([x-k+1, -1000000].max)..([x+k-1, 1000000].min)].join(" ")

このコードですが、1≤K≤100と0≤X≤100という制約を見逃していて、座標の両端を超えてしまう可能性を考慮して、max・minメソッドを利用していました・・・

でも制約があるのでしたら、これらは不要ですね

k,x = gets.split.map(&:to_i)
puts [*(x-k+1)..(x+k-1)].join(' ')

この様にすることが可能でした。

C - Green Bin

問題文 文字列 a に含まれる文字を何らかの順序で並べることで得られる文字列を a の アナグラム と呼びます。

例えば、greenbin は beginner のアナグラムです。このように、同じ文字が複数回現れるときはその文字をちょうどその回数だけ使わなければなりません。

N 個の文字列 s 1 , s 2 , … , s N が与えられます。それぞれの文字列は長さが 10 で英小文字からなり、またこれらの文字列はすべて異なります。二つの整数 i , j

( 1 ≤ i < j ≤ N ) の組であって、 s i が s j のアナグラムであるようなものの個数を求めてください。

制約 2 ≤ N ≤ 10 5 s i は長さ 10 の文字列である。 s i の各文字は英小文字である。 s 1 , s 2 , … , s N はすべて異なる。

始めに考えたのは、一文字づつ分割して、それらをgroup_byメソッドでグループ分けします。

（アナグラムという事は、同じ文字が同じ回数だけ出現するという点は共通）

これにより、どの文字が何回出現するかをハッシュ形式で取得出来ます。以下の様な感じです。

{"a"=>["a"], "c"=>["c"], "o"=>["o"], "r"=>["r"], "n"=>["n", "n"], "i"=>["i"], "s"=>["s"], "t"=>["t", "t"]}

このバリューを文字毎に比較し、完全一致するものの数を数える方法です。

実際に書いたコードがこちらです。

n = gets.to_i
strs = []
n.times { strs << gets.chomp }
 
checks = []
strs.each do |str|
  checks << str.chars.group_by { |s| s[0].chr }.values
end
 
count = -n
checks.each do |check1|
  checks.each do |check2|
    count += 1 if check1.all? { |c1| check2.include?(c1) }
  end
end
 
puts count/2

これだとeachを二重で回している事で、既にチェック済みのパターンを見ていたり、同じ文字同士を検証していたり、かなり無駄が多いです。

現に、これだとテストケースの５以降がTLE（実行時間制限超過）で通りませんでした・・・

そこで次に試したコードはこちらです。

n = gets.to_i
strs = []
n.times { strs << gets.chomp }
 
checks = []
strs.each do |str|
  checks << str.chars.group_by { |s| s[0].chr }.values.sort
end
 
count = -n
checks.each do |check|
  count += checks.count(check)
end
 
puts count/2

eachの二重は無くなりましたが、これでもテストケースの５以降はTLEで通りません・・・

この時点で、全探索は無理だと気づいて、組み合わせを計算して割り出す方法に考え方を切り替えました。

こういったn通りの中から、２つの組み合わせを重複を除いて計算する場合の計算式は以下の通りです。

n * (n - 1) / 2

# 5通りの場合
5 * (5 - 1) / 2
# => 10

この計算式を用いて実装したコードがこちらです。

n = gets.to_i
strs = []
n.times { strs << gets.chomp }
 
checks = []
strs.each do |str|
  checks << str.chars.sort.join('')
end
 
checks = checks.group_by { |i| i }.values
 
count = 0
checks.each do |check|
  count += check.size*(check.size-1)/2
end
 
puts count

以下の、「入力例 3」を例に解説します。

5
abaaaaaaaa
oneplustwo
aaaaaaaaba
twoplusone
aaaabaaaaa

文字列を分割する部分（strs.each）は、一文字づつ分割した文字をソートして結合します。

# strs.eachを通す前
["abaaaaaaaa", "oneplustwo", "aaaaaaaaba", "twoplusone", "aaaabaaaaa"]

# strs.eachを通した後
["aaaaaaaaab", "elnoopstuw", "aaaaaaaaab", "elnoopstuw", "aaaaaaaaab"]

そしてgroup_byメソッドによって、同じ文字をグループ分け（同じ配列に格納）します。

# checks.group_by { |i| i }.valuesによって同じ文字を同じ配列に格納する
[["aaaaaaaaab", "aaaaaaaaab", "aaaaaaaaab"], ["elnoopstuw", "elnoopstuw"]]

最後は、先ほどの組み合わせの計算式をグループごとに実行して、全ての組み合わせの数を求めるだけです。

(3 * (3 - 1) / 2) + (2 * (2 - 1) / 2) = 4

繰り返しは単語数しか実行されないので、先ほどまでの処理より大幅に軽くなりました。

これで通りましたが、もっとスマートな方法がありました。

n = gets.to_i
h = {}
n.times do
  s = gets.chomp.chars.sort.join
  h[s] ||= 0
  h[s] += 1
end
puts h.each_value.map{ |i| i * (i-1) / 2 }.inject(:+)

ハッシュのキーにソートした文字列を指定して、そのバリューに1を足していく方法です。

# ループ１回目
{"aaaaaaaaab"=>1}
# ループ２回目
{"aaaaaaaaab"=>1, "elnoopstuw"=>1}
# ループ３回目
{"aaaaaaaaab"=>2, "elnoopstuw"=>1}
# ループ４回目
{"aaaaaaaaab"=>2, "elnoopstuw"=>2}
# ループ５回目
{"aaaaaaaaab"=>3, "elnoopstuw"=>2}

こっちの方が、シンプルに書けて良いですね。