C++の練習を兼ねて, AtCoder Beginner Contest 069 の 問題D（Grid Coloring）を解いてみた.
■感想.
1. 一筆書きのアイデアが, AtCoder Beginner Contest 109 の 問題D (Make Them Even) に類似していたので, 興味深かった.
2. コーディング後, 解説を見たら, 全く同じ方針だったので, 良かったと思う.
本家のサイトABC #069 / ARC #080 Editorialをご覧下さい.
■C++版プログラム.
|
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 |
#include <iostream> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) int main() { // 1. 入力情報取得. int H, W, N; cin >> H >> W; cin >> N; int A[N] = {}; FOR(i, 0, N) cin >> A[i]; // 2. A[i] の 累積和 を 保管. int B[N] = {}; B[0] = A[0]; FOR(i, 1, N) B[i] += (B[i - 1] + A[i]); // 3. サイズが, H×W の 1次元配列に, 1, 1, 1, ..., 2, 2, ..., 3, 3, ..., N を, 格納. int C[H * W] = {}; int index = 0; FOR(i, 0, H * W) { if(B[index] > i) C[i] = (index + 1); else C[i] = (++index + 1); } // 4. 一次元配列Cの要素を, ジグザグに出力させる. // C11 -> C12 -> ... -> C1W -> C2W -> ... -> C21 -> C31 -> ... bool evenLine = true; FOR(i, 0, H) { if(evenLine) { int start = W * i; FOR(j, 0, W) cout << C[start + j] << " "; } else { int start = W * (i + 1) - 1; FOR(j, 0, W) cout << C[start - j] << " "; } cout << endl; evenLine = !evenLine; // 反転. } // 5. 後処理. 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 |
[入力例] 2 2 3 2 1 1 [出力例] 1 1 3 2 [入力例] 3 5 5 1 2 3 4 5 [出力例] 1 2 2 3 3 4 4 4 4 3 5 5 5 5 5 [入力例] 1 1 1 1 [出力例] 1 [入力例] 4 4 7 1 2 3 4 3 2 1 [出力例] 1 2 2 3 4 4 3 3 4 4 5 5 7 6 6 5 [入力例] 9 4 11 1 2 3 4 5 6 5 4 3 2 1 [出力例] 1 2 2 3 4 4 3 3 4 4 5 5 6 5 5 5 6 6 6 6 7 7 7 6 7 7 8 8 9 9 8 8 9 10 10 11 |
■参照サイト
AtCoder Beginner Contest 069