ABC 159 E - Dividing Chocolate

初手の方針

総当りで間に合いそうだなと思ったものの実装が全然手つかず。発想も実装もまだまだ精進が足りないなと感じた。

縦方向をbit全探索しつつ固定して考え、横方向について貪欲法で調べていく。 1 の数がkを超えたらdividerの数をインクリメントする。

入力例1を例に取ると以下のような感じ

(0,0)
11100
10001
00111

(1,0)
11100
------
10001
00111

(0,1)
11100
10001
------
00111

(1,1)
11100
------
10001
------
00111

計算量はbit全探索で2^ h-1, 貪欲法でw*hとなり, w*h*2^h-1

書くと本当にこれだけなんだが、本番後に解いたにも関わらず実装力が足りなくて本当に大変だった。。。

データ構造はvector2つとmap1つを使った。

vector<ll> sec(h, 0); // 区切られた領域ごとの1の数
vector<ll> col(h,0); // 縦1列の区切られた領域ごとの1の数
map<ll, ll> m; // 各行がどの領域に属するかを示す

あらためてABC147のD問題の正直者/嘘つきの場合もそうだったが、今回のように区切る/区切らないのような2値のものを網羅する際に利用できる可能性がある。

部分最適が全体最適になる。貪欲法の1種でクラスカル法という最小全域木に関する問題があり貪欲法とUnionFindのあわせ技で解けるらしい、思考の整理も兼ねて一度解いておきたい。

Atcoderのテストケースはdropboxにアップロードされているんだが以下のケースが実装時考慮されておらず他の問題を解く際も気をつけたい。