[AtCoder] ABC 176 E – Bomber

2020年8月24日

問題

方針

方針1

行と列はそれぞれ独立に選ぶことができることに注目します。 \( i \) 行目にある爆弾の個数を \( R(i) \) とし、\( j \) 列目にある爆弾の個数を \( C(j) \) とします。マス \( (i, j)\) に爆弾を置くとき、このマスに爆破対象がなければ、\( R(i) + C(j) \) 個爆破でき、爆破対象があるとき、\( R(i) + C(j) – 1 \) 個爆破できます。

したがって、行と列の最大値を持つ番号について、そのマスに爆破対象がないかどうかを調べます。

方針2

他の人のコードを見た方法です。方針1より計算量が少なく済みます。行と列に存在する爆破対象の最大値をそれぞれ、\( R, C \) とします。また、爆破対象が \( R \) 個ある行の数を \( a \) とし、爆破対象が \( C \) 個ある列の数を \( b \) とします。このとき最適な行と列の選び方は最大でも \( ab \) 通りあります。 次に \( i \) 個目の爆破対象が \( ab \) 通りの中に含まれるかどうかを調べます。含まれた数が \( ab \) 個あるとき、答えは \( R + C – 1 \) となり、そうでないとき \( R + C \) となります。

コード

方針1

方針2