AtCoder Beginner Contest 057

2017年3月26日のAtCoderの記録。言語はRubyです。

問題はこちら：[AtCoder Beginner Contest 057](http://abc057.contest.atcoder.jp/)
私の回答一覧はこちら：[自分の結果](http://abc057.contest.atcoder.jp/submissions/all?user_screen_name=Linus)
67分で全問完答。

#A問題
特に言うことなし。問題文そのまま。

#B問題
特に計算量を減らす工夫もせず、片っ端からマンハッタン距離を計算すれば良い。
速く解けてた人の回答から学べることを2点挙げる。[これ](http://abc057.contest.atcoder.jp/submissions/1181711)とか[これ](http://abc057.contest.atcoder.jp/submissions/1181256)とか見てた。

**1点目。**自分は入力値を配列に入れていくところを

```ruby
N.times do
	a, b = gets.split(" ").map{|v|
		v.to_i
	}
	student << [a, b]
end
```
と書いていたけど、mapの結果が配列で返ってくるのだから

```ruby
N.times do
	a_b = gets.split(" ").map{|v|
		v.to_i
	}
	student << a_b
end
```
で良かった。もちろん変数a_bを削除して、いきなり配列に追加でも良い。

**2点目。**それぞれのチェックポイントまでの距離を求める部分。
C言語的な考え方をすると「最小値を保持しておいて、新たに出した値が最小値より小さいなら値を更新」となる。コードで書くと、こう。

```ruby
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を使って最小値を取る添え字を出せば完了。[模範回答](http://abc057.contest.atcoder.jp/submissions/1181711)。
[こっち](http://abc057.contest.atcoder.jp/submissions/1181256)はよく分からなかった。```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}$までループを回せばよいので時間が足りる。

```ruby
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で書き直したからだ。

二項係数に使う階乗を求めるところを

```ruby
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)```をしようとしてエラーになる。

```ruby
def fac(i)
	return (1 .. i).inject(1) { |sum, j| sum * j }
end
```
これが正解。**咄嗟にinjectが正しく書けるようにならないと余計な時間を食う**ので、練習せねば。

以上。レートが1187になりました。