ABC 028を解いた - 電波ビーチ

tomerun.github.io

これにあるやつで難易度低そうなABCの問題セットから解いていくシリーズ。界隈ではABC042以降を解けという声がありますが果敢に無視します

A - テスト評価

数値が与えられるので値で分岐して答える

n = gets.to_i
if n<=59
  puts "Bad"
elsif n<=89
  puts "Good"
elsif n<=99
  puts "Great"
else
  puts "Perfect"
end

B - 文字数カウント

文字列が与えられるからどの文字が何回出現したかを出力する。文字列はA~Fで固定なので適当に辞書でも作って数えてやる。rubyだと範囲オブジェクトがアルファベットにも対応しててクソ楽だったけどどうせFまでの6つなので手でやっても変わらん

alphabet = ("A".."F").to_a.zip(Array.new(("A".."F").to_a.size, 0)).to_h
gets.chomp.chars.each{|c| alphabet[c]+=1}
puts alphabet.values.map(&:to_s).join(' ')

C - 数を3つ選ぶマン

それぞれ1以上100以下の異なる数値が5つ与えられるから適当に3つ取った和の3番目に大きい数値を答える。....単純に考えればpermutation,あるいはそんな組み込みライブラリがなくても、それぞれせいぜい100までなので3重for文で全探索しても充分間に合う。

# 全探索する
arr = gets.chomp.split.map(&:to_i)
results = []
arr.size.times do |i|
  for j in (i+1...arr.size) do
    for k in (j+1...arr.size) do
      results << arr[i] + arr[j] + arr[k]
    end
  end
end
results = results.uniq.sort
puts results[-3]

だが、O(1)で分かる方法があり、それが解説として載っていたが、atcoderの解説は解説を読んで分かることは極稀なのでとうぜんこれもわからん。なんかしらんけど通る例はこちら。納得のいく&&理解できる解説がほしい。

# 原理がまったくわからん例
arr = gets.chomp.split.map(&:to_i).reverse
puts [arr[0]+arr[1]+arr[-1], arr[0]+arr[2]+arr[3]].max

D - 乱数生成

0~10⁶まで取り得る整数Nと、N以下の整数Kが与えられるから、Nまでの数値を（重複を許して）3つ取ったときにそれらの中央値がKになるときの確率を答える。総数ではない。

クソ丁寧に解説すると以下のようになる。この問題は（「atcoderの解説は解説を読んで分かることは極稀」としながら）珍しく中学生程度だったら解けなくても読んだら分かるって感じの解説が載っているので、以下は読んでもわからなかったキッズ向け。

中央値ってのはなんか習った気がするが完全に忘れてたのでググると、ソート済の数列の真ん中にくる値のことである。題意では3つ取ったとあるので、その3つの値をソートしたときの配列を[a, b, c](1<=a<=b<=c<=N)とする。

この配列の中央値がKということは、取った順番を無視して、取った値だけソートすると、[a, K, b]になればいいということである。まごうかたなく、真ん中の値はKになっているので。

a!=K かつ b!=Kとすると、K以外の残りのa, bの選び方の組み合わせの総数がKがひとつだけ出たときの数である。a<K かつ K<b、すなわちKが一回しか登場しない場合は、aの取り得る値はa<Kと1<=aより、K-1個であり、bの取り得る値はK<bとb<=Nより、N-K個である。そして3回の試行中、取り方は、[a, K, b], [a, b, K], [b, a, K], [b, K, a], [K, a, b], [K, b, a]の6通りある。

a==Kかつb!=K または a!=Kかつb==Kとすると、Kは二回取る。3回のうち2回がKなので題意を満たすには残り1枠は（Kは二回までなので、）Kを除くどんな数字でもいいので、残る数値をxとすると、[x,K, K], [K, x, K], [K, K, x]の3通りある。xはNまでのうちKを除く値なのでこれはN-1個の候補がある。

a==Kかつb==Kとすると、K を三回取ることを意味し、これはすべてのうちで1種類しかない。自明だが[K, K, K]の並べ方は1通りであるからだ。

以上で中央値がKになる組み合わせの総数が求まる。求めるのはその確率なので、全事象の数で割る。全事象ってのは当然、試行が独立した、取り得る値がN種類である操作、を、3回繰り返す、ってことである。

というのを落ち着いて数学脳で見ればなんとなく分かる。というか逆に愚直解ってどうするんだ...？

n, k = gets.chomp.split.map(&:to_i)
puts ((n-k)*(k-1)*6+(n-1)*3+1)/(n*n*n).to_f