C++の練習を兼ねて, AtCoder Beginner Contest 109 の 問題D（Make Them Even）を解いてみた.
■感想.
1. 下記 C++版プログラム(RE版) は, おそらくロジック的に間違ってないと思われるが, 時間内では, テストケース(C018_scrambled – C029_scrambled)で, Runtime Error となった.
2. Runtime Error の 原因としては, ネット上の情報で, “vectorは要素数が数万くらいになるとデータ構造がぶっ壊れる？？？” との指摘をされている記事があったので, vector を使ったことが原因と推測した.
※参照URL② にあるように, vector よりも 配列の方が, 処理は早いとのこと.
3. コンテスト終了後に, 解説を見たところ, 一筆書きによる解法が紹介されていたので, 下記 C++版プログラム(AC版) のような形で実装したところ, 全テストケースを通過出来た.
※但し, 一筆書きによるコイン情報の保存方法に, 一次元配列を使ったが, 不慣れなせいか, これを一筆書きの順で保存するロジックを構築するのに, 膨大な時間を使ってしまった(汗).
本家のサイトABC 109 解説をご覧下さい.
■C++版プログラム(RE版)
|
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 |
// C018_scrambled - C029_scrambled で, RE となった. #include <iostream> #include <vector> #include <algorithm> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) struct operation { int ys; // 始点(y1). int xs; // 始点(x1). int ye; // 終点(y'1). int xe; // 終点(x'1). }; int main() { // 1. 入力情報取得. int H, W; cin >> H >> W; // 2. マス目に数字を保存. int A[500][500] = {}; FOR(i, 1, H + 1) FOR(j, 1, W + 1) cin >> A[i][j]; // FOR(i, 1, H + 1) FOR(j, 1, W + 1) cout << A[i][j] << endl; // 3. 偶数枚のコインが置かれたマス目の最大数は, コイン無しのマス目も含み, H * W 以下となることに注意. // 現在確認しているマスのコインが, 奇数枚だったら, 1枚次のマスへ移動. vector<operation> operations; FOR(i, 1, H + 1) { FOR(j, 1, W + 1) { int v = A[i][j]; if(v % 2 != 0) { operation o; o.ys = i; o.xs = j; A[i][j]--; if(j < W) { o.ye = i; o.xe = j + 1; A[i][j + 1]++; operations.push_back(o); } else if(j == W && i < H) { o.ye = i + 1; o.xe = j; A[i + 1][j]++; operations.push_back(o); } } } } // 4. 出力 ～ 後処理. cout << operations.size() << endl; for(auto i = operations.begin(); i != operations.end(); ++i) { cout << i->ys << " " << i->xs << " " << i->ye << " " << i->xe << endl; } return 0; } |
■C++版プログラム(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 94 95 96 97 98 99 100 101 102 103 104 105 |
// 解き直し. // ABC 109 解説. // https://img.atcoder.jp/abc109/editorial.pdf #include <iostream> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) #define FORN(i, a, b, n) for(int i=(a); i<(b); i += n) // 保存時インデックスに対応するマス目としての 座標(y1) を 返却. // @param i: 保存時インデックス. // @param W: 横方向サイズ. // @return: マス目としての 座標(y1) を 返却. int getInputIndexY(int i, int W) { double y0 = (i + 0.0) / W; double y1 = i / W; int y = (y0 - y1 == 0.0) ? y1 : (y1 + 1); return y; } // 始点, 終点座標(y1, y'1) を 返却. // @param i: 保存時インデックス. // @param W: 横方向サイズ. // @return: マス目としての 始点, 終点座標(y1, y'1) を 返却. int getIndexY(int i, int W) { double y0 = (i + 0.0) / W; double y1 = i / W; int y = (y0 - y1 == 0.0) ? y1 : (y1 + 1); return y; } // 始点, 終点座標(x1, x'1) を 返却. // @param i: 保存時インデックス. // @param y: マス目のインデックス(座標y). // @param W: 横方向サイズ. // @return: マス目としての 始点, 終点座標(x1, x'1) を 返却. int getIndexX(int i, int y, int W) { // 偶奇判定. bool b = (y % 2 == 0); int x = i - W * (y - 1); x = b ? (W - x + 1) : x; return x; } int main() { // 1. 入力情報取得. int H, W; cin >> H >> W; // 2. マス目に数字を保存. int A[250000] = {}; // 操作回数チェック用. int B[250000] = {}; // 実際の操作を出力するときに使用. // 一筆書きとなるように保管. int size = H * W + 1; bool isEven = false; FORN(i, 1, size, W) { int y = getInputIndexY(i, W); if(isEven) FOR(j, 1, W + 1) cin >> A[y * W - j + 1]; else FOR(j, 1, W + 1) cin >> A[(y - 1) * W + j]; isEven = !isEven; // 偶奇切り替え. } FOR(i, 1, size) B[i] = A[i]; // FOR(i, 1, size) cout << A[i] << endl; // 3. 偶数枚のコインが置かれたマス目の最大数は, コイン無しのマス目も含み, H * W 以下となることに注意. // 現在確認しているマスのコインが, 奇数枚だったら, 1枚次のマスへ移動. // -> 一筆書きで, 操作回数をカウント(解説通り). int count = 0; FOR(i, 1, size - 1) { int v = A[i]; if(v % 2 != 0) { A[i]--; count++; A[i + 1]++; } } // 4. 出力 ～ 後処理. cout << count << endl; // -> 一筆書きで, 操作を出力(解説通り). FOR(i, 1, size - 1) { int v = B[i]; if(v % 2 != 0) { B[i]--; // 一筆書き上の始点(y1). int ys = getIndexY(i, W); // 一筆書き上の始点(x1). int xs = getIndexX(i, ys, W); // 一筆書き上の終点(y'1). int ye = getIndexY(i + 1, W); // 一筆書き上の終点(x'1). int xe = getIndexX(i + 1, ye, W); cout << ys << " " << xs << " " << ye << " " << xe << endl; B[i + 1]++; } } return 0; } |
■参照サイト
【参照URL①】AtCoder Beginner Contest 109
【参照URL②】vectorの要素数上限とか