C++の練習を兼ねて, AtCoder Grand Contest 008 の 問題D (D – K-th K) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を見て, 実装した.
2. ややこしい実装となったが, 何とかAC版になった.
本家のサイトAGC 008 Editorialをご覧下さい.
■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 76 |
// 解き直し. // AGC 008 Editorial // https://img.atcoder.jp/agc008/editorial.pdf #include <bits/stdc++.h> using namespace std; #define pb push_back #define pf push_front const int MAX = 555; int IX[MAX], OX[MAX * MAX + 1], ANS[MAX * MAX + 1]; deque<int> lDq, rDq; int main(){ // 1. 入力情報取得. int N; scanf("%d", &N); for(int i = 1; i <= N; i++){ scanf("%d", &IX[i]); OX[IX[i]] = i; ANS[IX[i]] = i; } // 2. 解説通り. // 2-1. 左側から配置していく. for(int i = 0; i <= MAX * MAX; i++){ int index = OX[i]; // index - 1 個 を 配置. if(index > 0) for(int j = 1; j < index; j++) lDq.pb(index); } // 2-2. 右側から配置していく. for(int i = MAX * MAX; i >= 0; i--){ int index = OX[i]; // N - index 個 を 配置. if(index > 0) for(int j = 1; j <= N - index; j++) rDq.pf(index); } // 3. 数列作成. int index = 1; while(!lDq.empty()){ int d = lDq.front(); while(ANS[index] > 0) index++; lDq.pop_front(); ANS[index] = d; index++; } while(!rDq.empty()){ int d = rDq.front(); while(ANS[index] > 0) index++; rDq.pop_front(); ANS[index] = d; index++; } // 4. 整合性チェック. bool ok = true; for(int i = 1; i <= N; i++){ int count = 0; for(int j = 1; j <= N * N; j++){ if(ANS[j] == i) count++; if(count == i){ if(j != IX[i]) ok = false; break; } } if(!ok) break; } // 5. 出力. if(!ok){ printf("%s\n", "No"); return 0; } printf("%s\n", "Yes"); for(int i = 1; i <= MAX * MAX; i++) if(ANS[i] != 0) printf("%d ", ANS[i]); 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 |
[入力例] 3 1 5 9 [出力例] Yes 1 2 3 3 2 1 1 2 3 ※AtCoderテストケースより [入力例] 2 4 1 [出力例] No ※AtCoderテストケースより [入力例] 5 1 5 9 11 15 [出力例] Yes 1 2 3 3 2 4 4 4 3 5 4 5 5 5 5 1 1 1 1 2 2 2 3 3 4 |
■参照サイト
AtCoder Grand Contest 008