C++の練習を兼ねて, AtCoder Grand Contest 027 の 問題D (Modulo Matrix) を解いてみた.
■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイト AtCoder Grand Contest 027 解説 を ご覧下さい.
■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 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
// 解き直し. // https://img.atcoder.jp/agc027/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; #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 const int LIMIT = 101010; const int MAX = 500; LL a[LIMIT], c1[MAX][MAX], c2[MAX][MAX], ans[MAX][MAX]; set<LL> c[MAX][MAX]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 素数を用意. repx(i, 2, LIMIT){ if(a[i]) continue; repex(j, i * 2, LIMIT, i) a[j]++; } vl p; repx(i, 2, LIMIT) if(!a[i] && p.size() < MAX * 2) p.pb((LL)i); // 3. 市松模様を敷き詰める. rep(i, MAX){ // 3-1. 左上 -> 右下. int b = 2 * i; rep(j, b + 1){ int r = j; int c = b - j; if(r >= 0 && r < MAX && c >= 0 && c < MAX) c1[r][c] = p[i]; } // 3-2. 右上 -> 左下. rep(j, b + 1){ int r = j; int c = MAX - b + j; if(r >= 0 && r < MAX && c >= 0 && c < MAX) c2[r][c] = p[i + MAX]; } } // 4. 素数部分を確定させる. rep(i, MAX){ rep(j, MAX){ ans[i][j] = c1[i][j] * c2[i][j]; c[i][j].insert(c1[i][j]); c[i][j].insert(c2[i][j]); } } // 5. 未確定部分を敷き詰める. // -> 1e15 制約に注意. rep(i, MAX){ rep(j, MAX){ // 5-1. すでに確定している場合は, Skip. if(ans[i][j]) continue; // 5-2. 上下左右を取得. set<LL> st; if(i) for(auto &q : c[i - 1][j]) st.insert(q); if(i < MAX - 1) for(auto &q : c[i + 1][j]) st.insert(q); if(j) for(auto &q : c[i][j - 1]) st.insert(q); if(j < MAX - 1) for(auto &q : c[i][j + 1]) st.insert(q); // 5-3. 最小公倍数. LL lcd = 1LL; for(auto &q : st) lcd *= q; assert(lcd <= 1e15); // 5-4. 値を設定. ans[i][j] = ++lcd; } } // 6. すべて異なっているかチェック. set<LL> st; rep(i, MAX) rep(j, MAX) st.insert(ans[i][j]); assert(st.size() == MAX * MAX); // 7. 出力. rep(i, N){ rep(j, N){ printf("%lld", ans[i][j]); printf("%s", (j < N - 1) ? " " : "\n"); } } 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 |
[入力例] 2 [出力例] 4 7 23 10 ※AtCoderのテストケースより ※但し, 上記のプログラムでは, 以下の値が出力される. 11402 194734759 195350467 17103 [入力例] 3 [出力例] 11402 194734759 17079 195350467 17103 486836896 17133 488376166 28505 [入力例] 4 [出力例] 11402 194734759 17079 485812156 195350467 17103 486836896 28465 17133 488376166 28505 1135952756 489746806 28555 1139544386 39907 [入力例] 5 [出力例] 11402 194734759 17079 485812156 28445 195350467 17103 486836896 28465 1133561696 17133 488376166 28505 1135952756 39851 489746806 28555 1139544386 39907 2499096062 28585 1142742546 39977 2506997648 62711 |
■参照サイト
AtCoder Grand Contest 027