見出し画像

ABC159【E問題の復習】愚直に実装する問題だったのか

3月22日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 159」に参加した。

【今回の結果】
     順位:3841 位(参加者:約 8352 名 上位 46 %くらい)
    レート:711(前回:708 前回比:+3)
パフォーマンス:737(前回:1093)

全6問出題され、A、B、C、DはACできた。A問題で10分以上使ってしまったので、そんなに順位が上がらなかった。A問題を見たとき、「あれ?」ってちょっと固まってしまった。また、D問題でもWAを1回出してしまったが、これは毎度おなじみのintだとはみ出るのに、intを指定していた点である。もう何回やってしまったことか。

話は変わってレートについて。順位については、上位50%以上であればとりあえずOKとしていたが、順位が上位40%から50%くらいだと、パフォーマンスが700くらいなので「もうレートもあまり変わらないのでは?」と思っている。ということで、目標を上位30%くらいに上げる。過去に同じようなことを言っていたらごめんなさい。といっても、まだABCの過去問のDやE問題はぜんぜん潰せていないので、上位30%が取れるのは、いつになることやら。

今回は、A、B、C、Dは特に「あれ?」と思うことはなかった(成長したな。いい傾向)ので、手も足もでなかったE問題の復習する。

E問題の復習

問題文は以下のリンクをご確認ください。

解説動画を見て、ほぼそのまま写しながらの復習。
自分にとって重要だと思ったポイントは以下の3つ。

【ポイント1】Hが小さいことに気がつく

まず、Hの上限が10と小さいので、横に区切ったパターンを全部試すことができる。bit全探索。まず横で区切ってしまってから、縦に区切って考えるという流れ。これに気がつかなかったので、ずっとできなかった。

【ポイント2】ブロックをどう管理したらいいのか

「ブロックで分割します」と問題にあったが、どう管理したいいかわからなかった。ブロック用の配列を用意すればいい。わかってしまったら簡単なこと。

【ポイント3】縦に区切るタイミングは、ブロックの1の数がKを超えたブロックが出てきた時

横に区切ったときに各行をブロックに分かれているから、数えることは難しくない。

なるほど。理解はできた。

ほぼ写したのでACするのは当然ですが、ACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;

const int INF = 1001001001;

int d[10][1010];

int main() {

 int H, W, K;
 cin >> H >> W >> K;

 vector<string> S(H);
 for (int i = 0; i < H; i++) {
   cin >> S[i];
 }

 int answer = INF;

 // 横で切るパターンを全部試す
 for (int bit = 0; bit < 1 << (H - 1); bit++) {

   // ブロック番号
   int group = 0;
   
   // 各行がどのブロックに属しているかを管理
   vector<int> id(H);
   for (int i = 0; i < H; i++) {
     id[i] = group;
     if (bit >> i & 1) {
       group++;
     }
   }

   // ブロックの個数は区切った数+1
   group++;

   // データ(ブロック内に1が何個あるかを管理する)を初期化
   for (int i = 0; i < group; i++) {
     for (int j = 0; j < W; j++) {
       d[i][j] = 0;
     }
   }

   // 各ブロックの1の数を数える(まだ行しか見ていない)
   for (int i = 0; i < H; i++) {
     for (int j = 0; j < W; j++) {
       d[id[i]][j] += (S[i][j] - '0');
     }
   }

   // 線を引いた数
   int count = group - 1;

   // 1が何個あるかを確認するための配列
   vector<int> now(group);

   // 線を引くべきか(false)必要ないか(true)を返す関数
   auto add = [&](int i) {

     // 全部のブロックの1の数を数える
     for (int j = 0; j < group; j++) {
       now[j] += d[j][i];
     }

     // K以下かを判定するフラグ
     bool flg = true;
     
     // 全部のブロックのうち1個でもKを超えているとダメ
     for (int j = 0; j < group; j++) {
       if (K < now[j]) {
         flg = false;
         break;
       }
     }

     return flg;
   
   };

   // 列(縦)を見ていく
   for (int i = 0; i < W; i++) {

     // Kを超えるブロックがある場合はそこで区切る必要がある
     if (!add(i)) {

       // 線を加える
       count++;
       
       // 初期化
       now = vector<int>(group);
       
       // 区切った後もダメな場合はこの区切り方は無理
       if (!add(i)) {
         count = INF;
         break;
       }

     }
   }

   answer = min(answer, count);

 }

 cout << answer << endl;

 return 0;

}

愚直に実装する問題。
これは次回は何も見ずにできなあかんな。


この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

スキありがとうございます!
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。