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 のイワシは、-1/I のイワシとのみ相性が悪く、それ以外のイワシとは相性は悪くない

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

イワシの相性は、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_i$ と $B_i$ の最大公約数で割る必要があります。例：[1, 2] と [2, 4] は同じグループとして扱いたいためです。

$A_i$ が負の場合は、 $A_i$ と $B_i$ 両方に -1 を掛けて、 $A_i$ は必ず正の値にする必要があります。例：[-1, 2] と [1, -2] は同じグループとして扱いたいためです。

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

$A_i$ × $A_j$ = - $B_i$ × $B_j$

$A_i$ と $B_i$ のどちらも 0 のケース

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

$A_i$ と $B_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