C++の練習を兼ねて, AtCoder Beginner Contest 099 の 問題D (D – Good Grid) を解いてみた.
■感想.
1. 解説を見る前に解けたので, 及第点は, 取れたように思う.
2. グリッドを, 対角線方向に眺めて, i + j = 0 ～ (2 × N – 2) の範囲で, 集計する方針で対応したが, 解説見たところ, もっと簡潔に解けることが示されていたので, 大変勉強になった.
本家のサイトABC099解説をご覧下さい.
■C++版プログラム(問題D／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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; typedef pair<LL, int> pli; LL d[33][33], c[555][555]; // i + j = k の 場合に, 色X から 色Y に 塗り替えた場合の違和感を保存. // -> k と 色Y に塗り替えた場合の違和感 を 保存. LL discomfort[1111][33]; // k を 3で割った余りが, 0, 1, 2 の パターン に 集約. LL dp[3][33]; int main() { // 1. 入力情報取得. int N, C; scanf("%d %d", &N, &C); for(int i = 0; i < C; i++) for(int j = 0; j < C; j++) scanf("%lld", &d[i][j]); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) scanf("%lld", &c[i][j]); for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) c[i][j]--; // 2. 違和感を集計. // マス(i, j) (但し, i + j = k とする) を, 色y に塗り替えた場合の違和感を調査. for(int k = 0; k < N; k++){ for(int i = 0; i <= k && i < N; i++){ int j = k - i; for(int y = 0; y < C; y++) discomfort[k][y] += d[c[i][j]][y]; } } for(int k = N; k < 2 * N - 1; k++){ for(int i = k - (N - 1); i < N; i++){ int j = k - i; for(int y = 0; y < C; y++) discomfort[k][y] += d[c[i][j]][y]; } } // for(int k = 0; k < 2 * N - 1; k++){ // for(int y = 0; y < C; y++) printf("discomfort[%d][%d]=%lld ", k, y, discomfort[k][y]); // printf("\n"); // } // 3. 違和感の和を集計(k を 3 で割ったときの余りで分類). // 各 k ごとに, 色y に塗り替えた場合の違和感の最小値を選択. for(int k = 0; k < 2 * N - 1; k++){ for(int y = 0; y <= 32; y++){ int kmod = k % 3; if(kmod == 0) dp[kmod][y] += discomfort[k][y]; if(kmod == 1) dp[kmod][y] += discomfort[k][y]; if(kmod == 2) dp[kmod][y] += discomfort[k][y]; } } // for(int k = 0; k < C; k++){ // for(int y = 0; y < C; y++) printf("dp[%d][%d]=%lld ", k, y, dp[k][y]); // printf("\n"); // } // 4. 最小値を計算. // 以下の条件で, 色を変更したと仮定して, 全探索で確認. // kmod == 0: 色 y0 // kmod == 1: 色 y1 // kmod == 2: 色 y2 LL ans = 1e9; for(int y0 = 0; y0 < C; y0++){ for(int y1 = 0; y1 < C; y1++){ for(int y2 = 0; y2 < C; y2++){ if(y0 != y1 && y1 != y2 && y2 != y0){ ans = min(ans, dp[0][y0] + dp[1][y1] + dp[2][y2]); } } } } // 5. 出力 ～ 後処理. 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 |
[入力例] 2 3 0 1 1 1 0 1 1 4 0 1 2 3 3 [出力例(debug版)] dp[0][0]=0 dp[0][1]=1 dp[0][2]=1 dp[1][0]=2 dp[1][1]=4 dp[1][2]=1 dp[2][0]=1 dp[2][1]=4 dp[2][2]=0 3 ※AtCoderテストケースより [入力例] 4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2 [出力例(debug版)] dp[0][0]=162 dp[0][1]=48 dp[0][2]=390 dp[1][0]=162 dp[1][1]=36 dp[1][2]=319 dp[2][0]=257 dp[2][1]=104 dp[2][2]=230 428 ※AtCoderテストケースより [入力例] 10 7 0 1 2 3 4 5 6 7 0 8 9 10 11 12 13 14 0 15 16 17 18 19 20 21 0 22 23 24 25 26 27 28 0 29 30 31 32 33 34 35 0 36 37 38 39 40 41 42 0 2 5 5 4 2 3 4 5 3 3 5 6 2 7 1 7 6 6 1 5 1 6 4 5 4 2 1 1 2 7 4 7 4 1 4 4 7 4 2 2 4 4 7 3 5 5 5 1 6 1 2 2 6 6 2 7 3 7 1 4 1 3 7 3 7 7 1 1 5 5 7 4 4 4 7 1 5 7 2 1 1 5 1 2 1 3 1 2 5 3 3 3 2 1 4 2 1 5 2 7 [出力例(debug版)] dp[0][0]=505 dp[0][1]=483 dp[0][2]=521 dp[0][3]=487 dp[0][4]=539 dp[0][5]=585 dp[0][6]=474 dp[1][0]=634 dp[1][1]=643 dp[1][2]=637 dp[1][3]=594 dp[1][4]=521 dp[1][5]=706 dp[1][6]=594 dp[2][0]=567 dp[2][1]=552 dp[2][2]=567 dp[2][3]=546 dp[2][4]=568 dp[2][5]=605 dp[2][6]=528 dp[3][0]=0 dp[3][1]=7 dp[3][2]=0 dp[3][3]=8 dp[3][4]=9 dp[3][5]=10 dp[3][6]=11 dp[4][0]=0 dp[4][1]=50 dp[4][2]=52 dp[4][3]=54 dp[4][4]=56 dp[4][5]=0 dp[4][6]=58 dp[5][0]=0 dp[5][1]=56 dp[5][2]=59 dp[5][3]=62 dp[5][4]=65 dp[5][5]=39 dp[5][6]=34 dp[6][0]=0 dp[6][1]=76 dp[6][2]=72 dp[6][3]=83 dp[6][4]=43 dp[6][5]=89 dp[6][6]=57 1532 |
■参照サイト
AtCoder Beginner Contest 099