bobuhiro11's diary

ABC 173 E - Multiplication 4

06 Jul 2020

提出したコード

コンテスト後追加されたテストケース after_contest01.txt でコケた。 それ以外は自力で通ったので考察の詰めが甘かった。 まず、(A)答えが負となる場合と(B)答えが非負となる場合で場合分けをする。 (A)の場合には、絶対値の小さい順に貪欲にとればよい。(B)の場合を考えていく。まず、キューを2つ用意しておく。

単純に、負数同士の積は正という性質を使う。 $K$が2個以上残っている場合には、2つのキューからそれぞれ2つの値を取り出して、大小比較をする。 例えば、$9 \cdot 6 = 54 < -8 \cdot -7 = 56$ であれば、負数のキューから2つ値を取り出せばよい。 一方で、非負なキューのほうが大きい場合には、非負のキューから1つ値を取り出せばよい。 繰り返しになるが、非負なキューから取り出す場合には、1つの値だけでよいことに注意する。 https://twitter.com/shirakia/status/1279773457413074944で例が言及されている。after_contest01.txtもこのケースに該当しそう。

そのあとは、非負なキューからとる場合は1つずつ、負なキューからとる場合は2つずつのペアとして、取り出していけばよい。 (B)の計算途中で、どうしても答えを正数にすることができない場合には、(A)の結果を答えとする。


< ABC 172 F - Unfair Nim ABC 173 F - Intervals on Tree >