【Ruby基礎】AtCoder Beginner Contest 027 B – 島と橋

INDEX

■はじめに

Rubyの基礎的な問題をたくさん解くことで基本的な考え方やメソッドの使い方を定着させたい。
基本的にはAtCoderというプログラミングコンテスト（競技プログラミング）の過去問を使う。（AtCoderは難易度が分かれており、難易度の低いA問題かB問題を解いていく）

（5/23時点の方針）
メソッドの切り分け方や値の受け渡しを練習するために、コード長の短さについては気にせずに書くことにする。

（2022/10/17時点の方針）
しばらくはB問題を小さい番号の方からやっていく。たまにA問題もやるかも。

■問題

●出典

AtCoder Beginner Contest 027のB問題
https://atcoder.jp/contests/abc027/tasks/abc027_b

●問題文

N 個の島が横一列に並んでいる。 1≦i≦N−1 について、左から i 番目の島と i+1 番目の島は隣り合っている。

はじめ、左から i (1≦i≦N) 番目の島には ai 人の住人が住んでいる。高橋君はすべての島に同じ人数の住人が住むようにしたいと考えている。

高橋君は隣り合う 2 つの島の間に橋を架けることができる。また、直接的または間接的に橋で結ばれた複数の島の間で、住人を自由に移動させることができる。

すべての島に同じ人数の住人が住むようにするために、架ける必要のある橋の本数の最小値を求めよ。

●入力

入力は以下の形式で標準入力から与えられる。

a1 a2 .. aN

1 行目には、島の個数を表す整数 N (2≦N≦100) が与えられる。
2 行目には、整数 ai (0≦ ai ≦100) が空白区切りで与えられる。これは、左から i 番目の島には ai 人の住人が住んでいることを表す。

●出力

すべての島に同じ人数の住人が住むようにするために、架ける必要のある橋の本数の最小値を 1 行に出力せよ。ただし、どのように橋を架けてもすべての島に同じ人数の住人が住むようにできないならば、代わりに -1 を出力せよ。出力の末尾には改行を入れること。

■回答

●愚直に書く

えーこれはどうやればいいんだろう…。

まずはいつも通り標準入力を取る。

n = gets.to_i
a = gets.split.map(&:to_i)

…このあとどうすれば良いのか全くわからない汗。
まず、aの合計を% nして余りが出たら-1になることはわかる。それ以外のパターンをどう出せば良いのいか…。

下記は例として書かれていたもの。

5
2 0 0 0 3
# => 3

これをちょっといじると、下記のようになる。

5
2 0 0 2 1
# => 2

5
2 0 0 1 2
# => 3

こうなるような計算式。わからない…。
今回は遺憾ながら早々にギブアップ。

●他の方の回答例

う〜ん全然わからない…。
コードの意味はかろうじて掴めても、どうしてこれで求める値になるのかがわかっていない。

コメントも入れたものが以下。

n = gets.to_i
a = gets.split.map(&:to_i)
sum = a.sum

unless sum % n == 0 # 各島に均等な人数にできなかったら自動的に`-1`で終了
  puts "-1"
  exit # ここで処理全体を終了
end

ans = 0 # はじめに変数ansに0を入れておく
ave = sum / n # sum % n == 0 なので、必ず割り切れた数になる
x = a[0] # 変数xにまず1番目の島にいる人数を入れておく
(n - 1).times {|i| # 「次の島がある状態」として繰り返すから、`n-1`回の繰り返し
  ans += 1 if x != ave * (i + 1) # a[0]が、ave*1と異なったら1を足す（＝橋をかける）
  x += a[i + 1] # xを、次の島の人数に変える
}

puts ans

ans += 1 if x != ave * (i + 1)のあたりがワカランなぁ…。
時間ばかりが過ぎていくのでギブアップ。

●出てきたメソッド等

公式リファレンスを見る訓練。

今回は無し。

■振り返りなど

結局わかっていない。
数学的アタマの足りなさを痛感した。