2017年3月26日のAtCoderの記録。言語はRubyです。
問題はこちら：AtCoder Beginner Contest 057
私の回答一覧はこちら：自分の結果
67分で全問完答。
#A問題
特に言うことなし。問題文そのまま。
#B問題
特に計算量を減らす工夫もせず、片っ端からマンハッタン距離を計算すれば良い。
速く解けてた人の回答から学べることを2点挙げる。これとかこれとか見てた。
**1点目。**自分は入力値を配列に入れていくところを
N.times do
a, b = gets.split(" ").map{|v|
v.to_i
}
student << [a, b]
end
と書いていたけど、mapの結果が配列で返ってくるのだから
N.times do
a_b = gets.split(" ").map{|v|
v.to_i
}
student << a_b
end
で良かった。もちろん変数a_bを削除して、いきなり配列に追加でも良い。
**2点目。**それぞれのチェックポイントまでの距離を求める部分。
C言語的な考え方をすると「最小値を保持しておいて、新たに出した値が最小値より小さいなら値を更新」となる。コードで書くと、こう。
student.each do |s|
min = 10 ** 9
j = 1
index = -1
cp.each do |c|
dist = (s[0]-c[0]).abs + (s[1]-c[1]).abs
if dist < min then
min = dist
index = j
end
j += 1
end
puts index
end
うーん、なんとも不格好なコードだ。
rubyじゃfor文は普通使わないよなと思ったのでcp.eachと書いたが、最小値を取ったときの添え字が必要になるから変数jを導入する必要がある。まだfor j in 0..M-1としたほうがスッキリしたか。
AtCoderの解説はC++であり、これと近い書き方である。C++ならこれでいいのだろうが、rubyではスマートでは無い。なんというか「rubyらしくない」コードである。
「各チェックポイントまでの距離」を配列にしてしまえばよかった。C言語なら1つずつ求める他無いが、rubyならmapでアッサリ書ける。
で、minとindexを使って最小値を取る添え字を出せば完了。模範回答。
こっちはよく分からなかった。M.times.min_byって何が起きているんだ?
#C問題
Nが与えられるから、2つの数A,Bの積がNとなるようにして、A,Bの桁数のうち大きい方の最小値を求めよ、という問題。素因数分解して約数を列挙かな、と始め考えたが、上手い方法がある。まずAとBが「離れる」ほど、max(A,B)は大きくなる。したがってAとBがなるべく近い数になるようにする。正確に言えば、$A\geq\sqrt{N}$となるもののうち最小のAの桁数が答えだ。
では$\sqrt{N}$からNまでループを回して、最初に約数となったのがAだから……と考えると失敗。Nが素数の場合は最後までループが回ってしまい時間オーバー。ここで発想を変えると、Aが上記の条件ならば、Bは$B\leq\sqrt{N}$となるもののうち最大の値なのだ。こちらは1から$\sqrt{N}$までループを回せばよいので時間が足りる。
N = gets.to_i
i = 1
a = 0
while true do
if N % i == 0
a = i
end
break if i * i >= N
i += 1
end
#この時のaが上記のBである
a = N / a
puts a.to_s.length
#D問題
通常の場合、A個以上B個以下の要素を選べといっても、上位からA個だけ選べばよい。それ以上選んだら平均が下がってしまう。だから選び方など1通りしかないのだ。2つ以上選び方があるのは特殊なケースであり、どんなときにそれが起きるか考える。
結局、全部で3つに場合わけをする。以下、「i個目」は「価値が大きい順からi個目」を表す。
- A個目とA+1個目が異なる場合。これは上位A個が一意に定まるので、1通り。
- A個目とA+1個目が等しく、1個目とA個目が異なる場合。(A+1)個以上取ると平均がさがるので、選ぶのはA個。例えば上位から「30,20,20,20,20,10,...」で3個選ぶならば、4つある20のうちどれを選ぶかの問題になる。答えは4C2。
- A個目とA+1個目が等しく、1個目とA個目が等しい場合。つまり上位A個までが同一。この場合に限り(A+1)個以上取ってもよい。実は更に場合分けがある。いくつまで取れるかは、Bと「同じ数の要素の個数」の小さい方になる。
- 例えば上位から「20,20,20,20,20,10,...」で選ぶのが「3個以上4個以下」選ぶならば、答えは5C3 + 5C4となる。
- 一方で選ぶのが「3個以上6個以下」ならば、6個選ぶと平均が下がってしまうので、選べるのは5個まで。5C3 + 5C4 +5C5が答え。
というところまでは良かったのだが、実装段階で手間取った。
injectの使い方を間違えて、悪戦苦闘した挙句にforで書き直したからだ。
二項係数に使う階乗を求めるところを
def fac(i)
return [1 .. i].inject(1) { |sum, j| sum * j }
end
# => ./Main.rb:123:in `*': Range can't be coerced into Fixnum (TypeError)
と書いてエラーに悩まされていた。何となく「 1,2,3,4,5 と1 ..5 が等価なんでしょ」と思ってこう書いてしまったんだと思う。
1 .. iの返り値はRangeオブジェクトであり、これはEnumerableクラスを継承したものだからinjectが使える。[1 .. i]と書いてしまうと「Rangeオブジェクトが入った配列」ができてしまう。結果、injectの中で1 * 配列の第一要素すなわち1 * (1 .. i)をしようとしてエラーになる。
def fac(i)
return (1 .. i).inject(1) { |sum, j| sum * j }
end
これが正解。咄嗟にinjectが正しく書けるようにならないと余計な時間を食うので、練習せねば。
以上。レートが1187になりました。