C++の練習を兼ねて, AtCoder Beginner Contest 159 の 問題E (E – Dividing Chocolate) を解いてみた.
■感想.
1. 解答を見る前にAC版となったものの, 実装に苦労した.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 159 解説をご覧下さい.
■C++版プログラム(問題E／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define all(x) x.begin(), x.end() string board[11]; int CUM[11][1010]; int main(){ // 1. 入力情報. int H, W, K; scanf("%d %d %d", &H, &W, &K); rep(i, H){ char c[1010]; scanf("%s", c); string s(c); board[i] = s; } // 2. ホワイトチョコレートについて, 二次元累積和を保存. repx(i, 1, H + 1){ repx(j, 1, W + 1){ CUM[i][j] = (board[i - 1][j - 1] - '0') + CUM[i - 1][j] + CUM[i][j - 1] - CUM[i - 1][j - 1]; } } // 3. 分割に必要な操作の回数をチェック. int ans = 2020; rep(i, 1 << (H - 1)){ // チェック対象の行数を保存. vector<int> row, col; row.pb(0); row.pb(H); rep(j, H - 1) if((i >> j) & 1) row.pb(H - 1 - j); sort(all(row)); // printf("--- row start i=%d ---\n", i); // for(auto &p : row) printf("%d ", p); // puts("\n--- row end ---"); // 列方向にチェック. int s = 0, e = 0; priority_queue<int> pq; while(e < W){ bool ok = true; int white = 0; while(ok && e < W){ e++; rep(j, row.size() - 1){ // 各ブロックのホワイトチョコレートの個数を確認. white = CUM[row[j + 1]][e] - CUM[row[j]][e] - CUM[row[j + 1]][s] + CUM[row[j]][s]; // printf("i=%d s=%d e=%d white=%d\n", i, s, e, white); if(white > K){ ok = false; break; } } } // 各ブロックのホワイトチョコレートの個数を詰め直し. if(white > K){ rep(j, row.size() - 1){ pq.push(CUM[row[j + 1]][e - 1] - CUM[row[j]][e - 1] - CUM[row[j + 1]][s] + CUM[row[j]][s]); } col.pb(e - 1), s = e - 1; }else{ rep(j, row.size() - 1){ pq.push(CUM[row[j + 1]][e] - CUM[row[j]][e] - CUM[row[j + 1]][s] + CUM[row[j]][s]); } col.pb(e), s = e; } // printf("s=%d e=%d white=%d\n", s, e, white); } // printf("--- col i=%d ---\n", i); // for(auto &p : col) printf("%d ", p); // puts("\n--- col end ---"); // 必要な操作数を更新. int rCount = row.size(), cCount = col.size(); if(row.front() == 0) rCount--; if(row.back() == H) rCount--; if(col.back() == W) cCount--; if(pq.top() <= K) ans = min(ans, rCount + cCount); } // 4. 出力. printf("%d\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
[入力例] 3 5 4 11100 10001 00111 [出力例] 2 ※AtCoderテストケースより [入力例] 3 5 8 11100 10001 00111 [出力例] 0 ※AtCoderテストケースより [入力例] 4 10 4 1110010010 1000101110 0011101001 1101000111 [出力例] 3 ※AtCoderテストケースより [入力例] 2 575 2 10100001001101111000100111111000010101011110011000010101010001001011000111100111111101000110000011110110100111000100101110110010110000101100111001110101111110101000101111001001100001000100100111010010011100001001101010110011000000101111011011001000100111100101100101011001000110010101100100001010101010110000101110110101110100001010110001100010101100001000101110010011010110110110001000111111110001010111101101001010111101101100001110011000110010010011100100011111000001100000101111110111110110011100111000001111001111100101010000000111100011011110001110001100100010010000010 10010101110000010011010100000100001100000101011111100110110010011010101001000001111101111101111100001111110101100000011100011100101001000000101010001000011001010101111001000011001010110111011011111011100111011101000110011110010000010110000101001110111011100010001111000010111011100111110010000000011101100100000110000100110110101101011001101110101101101011101001010000100001100101000001010010101011000101100000111100001010101100010000000000001010101100011100011000110110101110001100111100111001001000010110011110010100110111110111100101001101111111110011100001000010011111110 [出力例(random_01)] 175 ※AtCoderテストケースより [入力例] 3 5 1 11111 11111 11111 [出力例] 6 [入力例] 10 50 11 01010000010000010011111110100011001111010110000100 11001000000001111010001011110111111100011000110110 00001111001010000110100100101000100001110110011011 01010011111110100110001011000011111000110000000001 00000111000011101000110011100101110101000101010011 11101001101100010100001000010111111110001110011100 01111000111110100010001101011111110010111100001001 00101110100100100110110110100010011111010100111010 01100001101010110001000111000011110001000001001100 11111010111111110101101101011001001001010110110101 [出力例] 9 |
■参照サイト
AtCoder Beginner Contest 159
AtCoder Beginner Contest 159 (E)