A – Grouping 2
問題
解法
「3人以上のグループを出来るだけ多く作る」なので、解は\(\lfloor N/3 \rfloor\)になる。
実装
puts gets.to_i/3
B – Grouping 2
問題
解法
「桃色、白色、緑色の3種類」or「桃色、白色、緑色、黄色の4種類」なので、黄色（Y）が1つでもあれば4種類、そうでなければ3種類となる。
実装
gets
a=gets.chomp.split(" ")
puts a.include?('Y') ? "Four" : "Three"
C – March
問題
解法
組み合わせの条件は以下の2つです。
- 全ての人の名前が M,A,R,C,H のどれかから始まっている
- 同じ文字から始まる名前を持つ人が複数いない
1つ目の条件より、入力のうちM,A,R,C,Hで始まらないものは無視して良いことがわかります。
2つ目の条件より、3人の組み合わせとして有効なのは、
（Mで始まる人、Aで始まる人、Rで始まる人）
（Mで始まる人、Aで始まる人、Cで始まる人）
：
のような組み合わせになります。
ここで、例えば（Mで始まる人、Aで始まる人、Rで始まる人）の組み合わせの数は、
Mで始まる人の人数 x Aで始まる人の人数 x Rで始まる人の人数
で求めることが出来ます。
よって、最初に以下の5つの数を計算しておき、そこから3つを取り出した時の組み合わせ毎にその積をとって、その総和を出せば解になります。
- Mで始まる人の人数
- Aで始まる人の人数
- Rで始まる人の人数
- Cで始まる人の人数
- Hで始まる人の人数
実装
rubyで組み合わせを求める場合、配列のcombinationを使うと簡単です。
N=gets.to_i h=Hash.new(0) N.times do s = gets.chomp h[s[0]] += 1 if s[0] == 'M' || s[0] == 'A' || s[0] == 'R' || s[0] == 'C' || s[0] == 'H' end ans = 0 h.values.combination(3) do |l,m,n| ans += l*m*n end puts ans
D – Practical Skill Test
問題
解法
LからRへDずつ移動した際の距離の総和を求める問題です。
L、Rは最大9万なので、距離を求めるのが1回であれば、Dずつ移動しながら移動距離の総和を出せば良いです。
しかしながら、与えられるL、Rの組み合わせの数Qは最大105なので、都度Dずつ移動しながら距離を計算するのは時間がかかりすぎます。
よって、L、Rが与えられた時に定数時間で移動距離を出す方法を考える必要があります。
考え方のポイントとしては、Dは常に一定である、という点です。
例えば入力例1のように、Aが1〜9でDが2である場合、移動パターンは以下の2種類しかありません。
- 1 → 3 → 5 → 7 → 9
- 2 → 4 → 6 → 8
よって、奇数の場合は1からの累積距離、偶数の場合は2からの累積距離、を事前に求めておくことで、任意の点間の移動距離を定数時間で求めることが出来ます。
例えば、例1の4から8の場合は、（2から8の累積距離）-（2から4の累積距離） を計算すれば、4から8への移動距離を求めることが出来ます。
実装
H,W,D=gets.chomp.split.map(&:to_i)
p = Array.new(H*W+1)
H.times do |i|
gets.chomp.split.map(&:to_i).each_with_index do |v,j|
p[v] = [i,j]
end
end
d = [0] * (D+1)
(D+1).upto(H*W) do |i|
d[i] = d[i-D] + (p[i][0] - p[i-D][0]).abs + (p[i][1] - p[i-D][1]).abs
end
Q=gets.to_i
Q.times do
l,r = gets.chomp.split.map(&:to_i)
puts d[r] - d[l]
end