C++の練習を兼ねて, キーエンス プログラミング コンテスト 2019 の 問題D (Double Landscape) を解いてみた.
■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 書き込む数字を大きい方から見ていくという, 解説のロジックが興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト キーエンス プログラミング コンテスト 2019 解説 を ご覧下さい.
■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 |
// 解き直し. // https://img.atcoder.jp/keyence2019/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) const LL MOD = 1e9 + 7; int a[1010101], b[1010101], aCum[1010101], bCum[1010101]; int main(){ // 1. 入力情報. int N, M; scanf("%d %d", &N, &M); set<int> aSt, bSt; rep(i, N){ int x; scanf("%d", &x); a[x]++; aCum[x]++; aSt.insert(x); } rep(i, M){ int x; scanf("%d", &x); b[x]++; bCum[x]++; bSt.insert(x); } // 2. 例外(a, b で 同じ値が含まれる場合). if((aSt.size() != N) || (bSt.size() != M)){ puts("0"); return 0; } // 3. 累積和. rep(i, N * M + 1){ aCum[i + 1] += aCum[i]; bCum[i + 1] += bCum[i]; } // 4. x が 大きい順に確認. LL ans = 1; repr(x, N * M, 1){ // 4-1. a, b の 両方に現れる. if(a[x] && b[x]) continue; // 4-2. a のみ現れる. if(a[x] && !b[x]){ ans *= (bCum[N * M] - bCum[x - 1]); ans %= MOD; } // 4-3. b のみ現れる. if(!a[x] && b[x]){ ans *= (aCum[N * M] - aCum[x - 1]); ans %= MOD; } // 4-4. a, b に 現れない. if(!a[x] && !b[x]){ LL y = (aCum[N * M] - aCum[x - 1]) * (bCum[N * M] - bCum[x - 1]); y %= MOD; y += MOD - (N * M - x); y %= MOD; ans *= y; ans %= MOD; } } // 5. 出力. printf("%lld\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 |
[入力例] 2 2 4 3 3 4 [出力例] 2 ※AtCoderテストケースより [入力例] 3 3 5 9 7 3 6 9 [出力例] 0 ※AtCoderテストケースより [入力例] 2 2 4 4 4 4 [出力例] 0 ※AtCoderテストケースより [入力例] 14 13 158 167 181 147 178 151 179 182 176 169 180 129 175 168 181 150 178 179 167 180 176 169 182 177 175 159 173 [出力例] 343772227 ※AtCoderテストケースより [入力例] 2 3 3 6 4 6 5 [出力例] 6 [入力例] 5 10 10 20 30 40 50 41 42 43 44 50 45 46 47 48 49 [出力例] 202566790 [入力例] 18 11 163 190 191 192 193 194 195 196 171 186 187 188 189 176 177 178 197 198 121 185 160 111 196 189 165 144 184 180 198 [出力例] 710475014 |
■参照サイト
キーエンス プログラミング コンテスト 2019