C++の練習を兼ねて, AtCoder Beginner Contest 096 の 問題C（Grid Repainting 2) ～ 問題D (Five, Five Everywhere) を解いてみた.
■感想.
1. 問題C は, 結構前に解いた内容を記載した(※Pythonで記載してる理由).
2. 問題D は, 素数p の中で, p = 5 × n + 1 の形となっているものを探索すれば十分なことに気付いたので, 解答に辿り着いた.
-> 解説と全く同じ方針だったので, 及第点は取れたと思われる.
本家のサイトAtCoder Beginner Contest 096 解説をご覧下さい.
■Python版プログラム(問題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 |
# -*- coding: utf-8 -*- # 1. 入力情報取得. H, W = map(int, input().split()) board = [] for i in range(H): board.append(list(input())) # 2. 黒色着色時に, 'P' を置くことにするが, 可能であるかチェックする関数. def checkP(i, j, b, t): # 2-1. vertor [1, 0] 方向でチェック. if i < H - 1 and (t == '#' or t == 'P'): x = b[i + 1][j] if x == '#' or x == 'P': return True # 2-2. vertor [-1, 0] 方向でチェック. if i > 0 and (t == '#' or t == 'P'): x = b[i - 1][j] if x == '#' or x == 'P': return True # 2-3. vertor [0, 1] 方向でチェック. if j < W - 1 and (t == '#' or t == 'P'): x = b[i][j + 1] if x == '#' or x == 'P': return True # 2-4. vertor [0, -1] 方向でチェック. if j > 0 and (t == '#' or t == 'P'): x = b[i][j - 1] if x == '#' or x == 'P': return True # 2-5. 上記以外は, 'P' と置けない. return False # 3. 黒色着色('P' or '#' で, 黒色着色(※'P'に置き換え)). for i, r in enumerate(board): for j, c in enumerate(r): if c == 'P' or c == '#': if checkP(i, j, board, c): board[i][j] = 'P' # 4. 未着色の'#'が, 0個ならば, 'YES', 1個以上あれば, 'NO'. # Making a flat list out of list of lists in Python. # https://stackoverflow.com/questions/952914/making-a-flat-list-out-of-list-of-lists-in-python/952952#952952 board = [item for sublist in board for item in sublist] answer = ','.join(board) if answer.count('#') == 0: print('Yes') else: print('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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include <bits/stdc++.h> using namespace std; #define FORN(i, a, b, n) for(int i = (a); i < (b); i += n) int main() { // 1. 入力情報取得. int N; cin >> N; // 2. 素数を用意する. map<int, int> m; m[2]++; FORN(i, 3, 55555, 2) { bool isPrime = true; FORN(j, 3, sqrt(i) + 1, 2) { if(i % j == 0){ isPrime = false; break; } } if(isPrime) m[i]++; } // 3. 素数p の中で, p = 5 × n + 1 の形となっているものを探索. // ex. // 素数11 の 場合は, 11 = 5 * 2 + 1 -> OK // 素数13 の 場合は, 13 = 5 * 2 + 3 -> NG // 素数41 の 場合は, 41 = 5 * 8 + 1 -> OK // ... // -> 55個以上存在することが判明した. // 11 31 41 61 71 101 131 151 181 191 // 211 241 251 271 281 311 331 401 421 431 // 461 491 521 541 571 601 631 641 661 691 // 701 751 761 811 821 881 911 941 971 991 // 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 // 1291 1301 1321 1361 1381 1451 ... // for(auto & p : m) if((p.first - 1) % 5 == 0) cout << p.first << " "; // 4. 出力. // -> 3. の 条件 に絞りこんで出力. int counter = 0; for(auto &p : m){ int n = p.first; if((n - 1) % 5 == 0){ counter++; cout << n << " "; } if(counter >= N) break; } 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 |
[入力例] 5 ※AtCoderテストケースより [出力例] 11 31 41 61 71 [入力例] 6 ※AtCoderテストケースより [出力例] 11 31 41 61 71 101 [入力例] 8 ※AtCoderテストケースより [出力例] 11 31 41 61 71 101 131 151 [入力例] 55 [出力例] 11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 [入力例] 100 [出力例] 11 31 41 61 71 101 131 151 181 191 211 241 251 271 281 311 331 401 421 431 461 491 521 541 571 601 631 641 661 691 701 751 761 811 821 881 911 941 971 991 1021 1031 1051 1061 1091 1151 1171 1181 1201 1231 1291 1301 1321 1361 1381 1451 1471 1481 1511 1531 1571 1601 1621 1721 1741 1801 1811 1831 1861 1871 1901 1931 1951 2011 2081 2111 2131 2141 2161 2221 2251 2281 2311 2341 2351 2371 2381 2411 2441 2521 2531 2551 2591 2621 2671 2711 2731 2741 2791 2801 |
■参照サイト
AtCoder Beginner Contest 096