銀行員からのRailsエンジニア

銀行員からのRailsエンジニア

銀行員から転身したサービス作りが大好きなRailsエンジニアのブログです。個人で開発したサービスをいくつか運営しており、今も新しいサービスを開発しています。転職して日々感じていること、個人開発サービス運営のことなどを等身大で書いていきます。

ABC168 E「∙ (Bullet)」の解説 【AtCoder Beginner Contest】

はじめに

難しかったですね...!コンテスト中には余裕で解けませんでした...

僕が勤めている会社の競プロの集まりで、この問題を解説する機会があり、せっかくだったので噛み砕いてブログにしてみました。

問題

f:id:ysk_pro:20200523103429p:plain

問題文と制約のスクリーンショットです。
実際の問題のページはこちらです。
E - ∙ (Bullet)

考察

全探索の計算量を考えてみる

とりあえず、全探索の計算量を考えてみます。

N匹のイワシから1匹以上を選ぶ選び方なので、それぞれのイワシについて選ぶ or 選ばないの選択をしていき、最後に全てを選ばなかったケースを引けば良さそうです。

よって、O(2^N) となります。Nの制約は2 ×10^5なので圧倒的に間に合わないですね。他の方法を考えます。

解法

A_i × A_j + B_i × B_j = 0 という数式は、i と j が混ざっていて分かりにくいので、式変形をしてみます。f(j) = g(i) の形にできると考えやすくなることが多いです。

\frac{A_j}{B_j} = - \frac{B_i}{A_i} となります。一旦、簡略化のために A, B に 0 は入らないと仮定して考察を進めます。

ここで I_i = \frac{A_i}{B_i} とすると( I はもちろん Iwashi の I です)

I_j = - \frac{1}{I_j}

とすることができます。

少しまとめると、

ということが分かります。

イワシの相性は、I の値でのみ決まるので、I の値でイワシたちをグルーピングしてみましょう。

N匹のイワシ だと考えにくいので、図のような具体的な例で考えてみます。

f:id:ysk_pro:20200523095944p:plain

イワシが6匹いて、I = 2 となるのが 2匹、I = - 1/2 が 3匹、I = 3 が1匹いるとします。

仲が悪くなってしまう I をペアにすると、ペア1、ペア2と分けられます。(ペア2は相方がいませんがペアとして考えます)

f:id:ysk_pro:20200523100136p:plain

この時、何通りの選び方ができるかを考えます。

まずペア1のみに絞って考えると、それぞれのグループ(I = 2 と I = -1/2)から同時に選べないので、

(2^2 - 1) + (2^3 - 1) + 1

となります。(カッコは分かりやすくするためにつけています)

どういうことかというと、I = 2 のイワシと I = -1/2 のイワシは同時に選べないので、I = 2 のイワシのみを選ぶ場合と I = 1/2 のイワシのみを選ぶ場合で分けて考えて、最後に足すという方針で計算します。
I = 2 のイワシのみを選ぶ場合は、それぞれのイワシを選ぶ or 選ばないなので 2^2 となり、全てのイワシを選ばないとしたケースは I = 2 のイワシを選んだことにならないので最後に 1 を引いています。これで 2^2 - 1 になります。
I = -1/2 のイワシを選ぶ場合は同様に2^3 - 1 となります。
最後に +1 をしているのは、I = 2, -1/2 のイワシをどちらも選ばなくても、ペア1からの選び方として問題にはならないからです。(I = 2 のイワシと I = -1/2 のイワシが同時に選ばれなければOK)

ペア2に対しても同様に考えることができ、

(2^1 - 1) + 1

となります。

そして、ペア1 と ペア2 は互いに独立しているので、それぞれのケース数を掛け合わせ、最後に 1匹も選ばないケースを除けば(問題の条件として1匹以上選ぶ必要があるため)全ての組み合わせを求められそうですね。

一般化すると、

  • 相性が悪い I のグループ同士をペアにして、それぞれ x 匹、y 匹含まれるとすると、組み合わせの数は (2^x -1) + (2^y + 1) - 1 で求められる
  • それぞれのペアの組み合わせの数を掛け合わせると組み合わせの総数

となります。

したがって、I を全て求める → I の値でグループ化してグループに何匹ずつ含まれるか数える → グループをペアにして組み合わせの総数を求める という感じでいけそうですね。


ただ今回、そのまま I = A/B を計算してしまうと、I は小数になるので誤差がでてしまう可能性があります。例えば、I が 0.(たくさん)1 と 0.(同じたくさん)2 は違う値なので別のグループとして扱うべきところ同じグループとしてしまう、みたいなイメージです。

小数だと誤差が出てしまいそうで怖いので、I を 小数を使わない形で表現することにします。

やり方としては、I を A と B の配列で表現します。(やり方は他にも色々あると思います)
I_i = [A_i, B_i] と表現します。

小数がなくなり誤差の問題はクリアできて嬉しいのですが、注意点がいくつかあります。

  • それぞれの値を A_iB_i最大公約数で割る必要があります。例:[1, 2] と [2, 4] は同じグループとして扱いたいためです。
  • A_i が 負の場合は、A_iB_i 両方に -1 を掛けて、A_i は必ず正の値にする必要があります。例:[-1, 2] と [1, -2] は同じグループとして扱いたいためです。


ここで、ここまで無視してきた 0 の扱いについても考えます。
0 で割ることはできないので、この式で考えます。

A_i × A_j = - B_i × B_j

  • A_iB_i のどちらも 0 のケース

どんなイワシとも相性が悪くなる最悪のイワシです。(A_jB_j に何が入ったとしても式が成り立ちます。)このタイプのイワシをクーラーボックスに入れたいときは、このタイプのイワシをただ1匹だけ入れるしかありません。よって、最悪イワシは何匹いるかを数えておき、最後に匹数を足せば良さそうです。

  • A_iB_i のどちらかだけが 0 のケース

例えば、A_i が 0 だとすると、左辺は 0 になり、B_i は 0 ではないので、B_j が 0 のイワシと相性が悪くなります。つまり、A = 0 のイワシと相性が悪いのは B = 0 のイワシです。(このとき、A = B = 0 の最悪のイワシは別管理しているので考慮する必要はないです)
B = 0 のときは I = [1, 0]、A = 0 のときは I = [0, -1] とすることで、グループ化したイワシたちと同様に考えることができます。

実装

やっと、、やっと実装です!
Ruby のコードに適宜コメントを入れています。

MOD = 1000000007
N = gets.chomp.to_i

group = Hash.new(0)
worst_iwashi_count = 0 # 最悪のイワシを管理する変数

N.times do |i|
  a, b = gets.chomp.split.map(&:to_i)

  if a == 0 && b == 0 # 最悪のイワシのケース
    worst_iwashi_count += 1
    next
  end

  if a == 0 # A = 0 のイワシのケース
    group[[0, -1]] += 1
    next
  end

  if b == 0 # B = 0 のイワシのケース
    group[[1, 0]] += 1
    next
  end

  # 最大公約数でそれぞれを割る
  gcd = a.gcd(b)
  a /= gcd
  b /= gcd

  # 正負を揃える
  if a < 0
    a *= -1
    b *= -1
  end

  group[[a, b]] += 1
end

ans = 1

group.each do |(a, b), count|
  # ペアとなるグループに含まれるイワシの数を数える
  # ペアとして計算されたグループは、重複して計算されることを防ぐために削除する
  if b < 0
    pair_count = group[[-b, a]]
    group.delete([-b, a])
  else
    pair_count = group[[b, -a]]
    group.delete([b, -a])
  end

  ans *= (2 ** count - 1) + (2 ** pair_count - 1) + 1
  ans %= MOD
end

p (ans + worst_iwashi_count - 1) % MOD

このコードを提出したAtCoderのページはこちらです。
Submission #13492364 - AtCoder Beginner Contest 168

おわりに

考慮することが多くて難しいですね...!
これをコンテスト中に通せる人をほんと尊敬します。

この問題のポイントは、

  • f(j) = g(i) の形への式変形
  • グループごとに組み合わせ数を求めること
  • 小数で誤差を出さないようにすること
  • 0の扱い

だったと思います。
同じような考え方を使う問題が出てきたときに、この問題の解法を思い出して応用できるといいですね!

初めてAtCoderの解法をブログにまとめ、口頭で解説するというのをやってみました感想としては、めちゃくちゃ時間がかかりましたが圧倒的に理解が深まりました。

また機会があればやってみようと思います。

ご指摘・ご質問等あれば、ブログのコメント・TwitterDM いただければ返信させていただきます。

ここまでお読みいただきありがとうございました。