2021/04/05 - Lru Room

概略

今日は珍しく早朝に目が覚めて朝から焼肉を決めた. そのせいかパワーが高かった気がする.

そろそろ技術記事も書こうかなと思いつ何を書いたらいいやら, GKEのdeploymentの構成方法みたいなの書いたら需要あるのかな.

今日の競プロ

ランダム

今日はABC159E Dividing Chocolate

ホワイトチョコがk枚以下になるようにチョコを割っていく問題.

一見ムリでは? となるが, 制約がゆるい.

もし1列のみであれば, 左から取れるだけホワイトチョコの部分を取って貪欲に行くのが最適.

2列でも横に割れないなら貪欲が最適

Hが10と少なく, 割り方を全探索しても1024, これに対し, W方向1000を貪欲に解くとしても最大で1024 * 10 * 1000なので横方向の割り方を決めて貪欲にやっていきで間に合う.

$O(2^H HW)$

submit result

#include <bits/stdc++.h>
using namespace std;
int main(){
  int h, w, k;
  cin >> h >> w >> k;
  vector<vector<char>> s(h, vector<char>(w));
  // 文字を数値に直しておく
  for(auto &si: s) for(auto &sij: si) {cin >> sij; sij -= '0';}

  int hseplim = (1 << (h - 1));
  int ans = h + w;

  // W方向は割り方を全探索する
  for(uint pat = 0; pat < hseplim; pat++){
    bitset<10> bs(pat);
    int hsep = bs.count();
    
    vector<int> sep(hsep + 1, 0);
    int vsep = 0;
    bool b = false;
    for(int x=0; x<w; x++){
      vector<int> tsep(hsep + 1, 0);
      int curidx = 0;
      for(int y=0; y<h && !b; y++){
        if(s[y][x]) tsep[curidx]++;
        // 1列だけのカウントでkを超える場合その割方で条件達成不可なので飛ばす.
        if(tsep[curidx] > k) b = true;
        if(bs[y]) curidx++;
      }
      if(b) break;

      // 各区間のホワイトチョコの合計を計算しとく. ここでoverするならこの手前で割ったことにすればよい
      bool over = false;
      for(int i=0; i<=hsep; i++) if(sep[i] + tsep[i] > k) over = true;
      if(over) {vsep++;}
      for(int i=0; i<=hsep; i++) sep[i] = over ? tsep[i] : sep[i] + tsep[i];
    }
    if(b) continue;
    ans = min(ans, hsep + vsep);
  }
  cout << ans << endl;
}