hitoare日記

たまに書きます

E - Multiplication 4(AtCoder Beginner Contest 173)

問題リンク

atcoder.jp


問題概要

 \(N\)個の整数\(A_1,A_2,...,A_N\)が与えられる

この中から、ちょうど\(K\)個の要素の積としてありうる値の最大値を求め、

10^9+7で割った余りを答えよ。

制約:

  • \(1 \leq K \leq N \leq 2 \times 10^5\)
  • \(|A_i| \leq 10^9\)
解法

 基本的な戦略としては、Aの要素を絶対値が大きい順にソートしてK個選んで積を計算した後、

それが正ならばそのまま出力、

負ならば

  • 選んだ正の要素のうち絶対値が一番小さいものを除き、選んでいなかった負の要素の中で絶対値が最も大きいものを掛ける
  • 選んだ負の要素のうち絶対値が一番小さいものを除き、選んでいなかった正の要素の中で絶対値が最も大きいものを掛ける

のいずれかで、解の絶対値が大きくなる方を選べば良い。

 

例:

6 3

6 -5 4 -3 2 -1

このとき、まずは\(6 \times (-5) \times 4 = -120\)を解の候補とする。

これは負なので次のどちらかを選択する。

  • 選んだ正の要素のなかで絶対値が最小の4を、選んでいなかった負の要素のなかで絶対値が最大の-3に変える。
  • (上の正負を逆転して)-5を2に変える。

このとき、前者は解の絶対値が\(3/4\)倍され、後者は\(2/5\)倍される。

\(3/4 > 2/5\)なので前者を選ぶ。

最終的な解は\(6 \times (-5) \times (-3) = 90\)。

 

以下の点に注意する。

  • そもそもK個の積が負にしかなりえない場合(サンプル2)。この時は絶対値が最もちいさいものが答えになる。
  • K個の積が負、もしくは0になる場合*1。この時は答えが0になる。
  • 上の「負ならば~」の部分で、選んだ要素が正/負のみ、選んでいなかった要素が正/負のみの場合。
  • 「負ならば~」の部分の解の変化の比較で、小数を使うと誤差の危険がある。\(A/B > C/D \Leftrightarrow AD > BC\)(ただしすべて正)を利用して整数のまま比較する。
  • 負の数の剰余。出力が「0以上10^9+6以下の整数」になるように調整する。
提出

https://atcoder.jp/contests/abc173/submissions/14993932

感想

かなり注意してやったけど、コーナーケースと全然関係ない論理ミスでWA出した。

*1:例えば
4 3
-1 -1 -1 0