C++の練習を兼ねて, AtCoder Beginner Contest 239 の 問題C (Knight Fork) ～ 問題D (Prime Sum Game) を解いてみた.
■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 239 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C／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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; using vp = vector<P>; #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 #define a first #define b second int main(){ // 1. 入力情報. int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); // 2. 準備. vp v; repx(i, 1, 3){ repx(j, 1, 3){ if(i != j){ v.pb({+i, +j}); v.pb({-i, +j}); v.pb({+i, -j}); v.pb({-i, -j}); } } } // 3. 距離が, √5 の 点は？ set<P> st1, st2; for(auto &p : v){ st1.insert({x1 + p.a, y1 + p.b}); st2.insert({x2 + p.a, y2 + p.b}); } // 4. 存在チェック. bool ok = false; for(auto &p : st1){ if(st2.count(p)){ ok = true; break; } } // 5. 出力. printf("%s\n", ok ? "Yes" : "No"); 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 |
[入力例] 0 0 3 3 [出力例] Yes ※AtCoderテストケースより [入力例] 0 1 2 3 [出力例] No ※AtCoderテストケースより [入力例] 1000000000 1000000000 999999999 999999999 [出力例] Yes ※AtCoderテストケースより [入力例] 1 2 5 4 [出力例] Yes [入力例] 20 22 2 19 [出力例] No |
■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 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #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--) int a[303]; int main(){ // 1. 入力情報. int A, B, C, D; scanf("%d %d %d %d", &A, &B, &C, &D); // 2. 素数を取得. repx(i, 2, 303) if(!a[i]) repex(j, i * 2, 303, i) a[j]++; set<int> p; repx(i, 2, 303) if(!a[i]) p.insert(i); // 3. ゲーム. int ans = 0; repx(i, A, B + 1){ // 整数 i に 対して, 整数 j で, (i + j) が 素数となるものがあるか？ bool ok = false; repx(j, C, D + 1){ if(!ok && p.count(i + j)){ ans++; ok = true; } } } // 4. 出力. printf("%s\n", ans != (B - A + 1) ? "Takahashi" : "Aoki"); 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 |
[入力例] 2 3 3 4 [出力例] Aoki ※AtCoderテストケースより [入力例] 1 100 50 60 [出力例] Takahashi ※AtCoderテストケースより [入力例] 3 14 1 5 [出力例] Aoki ※AtCoderテストケースより [入力例] 20 22 2 19 [出力例] Aoki [入力例] 30 33 2 5 [出力例] Takahashi |
■参照サイト
デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）