505.1

知識レスなセットだったのですばらしいと思います。

300

矩形領域に縦にN-1本、横にM-1本の線を引いて、N*Mの領域に分割する。領域の面積が分かっている部分が指定されるので、後何か所分かれば、全体の面積が分かるか答えよ、という問題。

長方形の頂点になるような4つの領域のうち3つが分かれば、4つ目が分かる、というのを再帰的にやっていけば分かりそう。取り敢えず行列の行置換、列置換をしてやると、面積の分かっている領域は矩形になり、二つの矩形をつなぐには1個だけ塗れば十分で、全く塗れていない矩形については、max(X,Y)+min(X,Y)-1個塗ればいいはず。

500

A以上B以下かC以上D以下の整数からなる集合Sの部分集合で、Sの任意の要素の倍数のいずれかを含んでいるもののうち、一番要素数の少ないものの要素数を答えよ、という問題。

取り敢えず、A以上でBの半分以下のものは二倍してやるとA以上B以下なので無視できる。B/2+1以上B以下について、B/2+1をk倍すると初めてC以上になるとすると、B/2+1以上D/k以下はk倍するとC以上D以下になるので無視して良い。D/k+1から、k-1倍するとC以上D以下になる最小の値までは無視できない。これをBに到達するまで交互に計算していくだけ。C以上D以下の領域については、D/2+1以上D以下の範囲だけ無視できないのでそれをカウントしてやる。

1000

整数配列が与えられるので、すべての要素の積とすべての要素の和が等しくなるように変形することを考えるとき、最終的な整数配列と最初の整数配列との差分の最小値を答えよ、という問題。

考慮すべきは3パターンで、1)どれか一つを0にする、2)どれか一つを残し、他を同数かつ偶数個の-1と1にする、3)すべての絶対値が1以上で、複数個が2以上になるようにする。

1と2のケースは探索するだけ。1の場合は、0にするヤツの絶対値と他のヤツの合計値の絶対値の和が最小になるヤツを探すだけ。2のケースはソートして、他のヤツを前から(n-1)/2個を-1に、残りを1にすることにしてやって、最小になるヤツを探す。

3のケースはやや面倒だけれど、仮に絶対値が2以上のヤツがいると、積が大きくなる分量は明らかに和よりも大きくなるので、和だけを操作できる絶対値1のヤツをたくさん用意しないといけなくなる。このことから、積の絶対値は配列の要素数の定数倍で抑えられるので、適当に100くらいが積の絶対値として、全探索するだけ。-1と1の数を調整してやって、後はソートして差分を計算する。

3のケースの実装ゲーの要素が強いけれど、本番では1のケースでバグり、2のケースを実装せず、3のケースは問題なく動いていた...。