C++の練習を兼ねて, AtCoder Regular Contest 051 の 問題A (塗り絵) ～ 問題B (互除法) を解いてみた.
■感想.
1. 問題A は, 図形の性質を絞り込めた点, 問題B は, Fibonacci数列 に 帰着出来たので, AC版になったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 051 解説をご覧下さい.
■C++版プログラム(問題A／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 |
#include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報. int x1, y1, r; int x2, y2, x3, y3; scanf("%d %d %d %d %d %d %d", &x1, &y1, &r, &x2, &y2, &x3, &y3); // 2. 赤が無い場合. int cLx = x1 - r, cRx = x1 + r, cUy = y1 + r, cDy = y1 - r; if(x2 <= cLx && x3 >= cRx && y2 <= cDy && y3 >= cUy){ puts("NO"); puts("YES"); return 0; } // 3. 青が無い場合. // -> 円の中心から, 長方形の四隅が, いずれも 距離 r 以下となっている場合. int lu = (x2 - x1) * (x2 - x1) + (y3 - y1) * (y3 - y1); // 左上. int ld = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // 左下. int ru = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1); // 右上. int rd = (x3 - x1) * (x3 - x1) + (y2 - y1) * (y2 - y1); // 右下. int r2 = r * r; if(lu <= r2 && ld <= r2 && ru <= r2 && rd <= r2){ puts("YES"); puts("NO"); return 0; } // 4. それ以外. puts("YES"); puts("YES"); 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 |
[入力例] -1 -1 2 2 3 4 5 [出力例] YES YES ※AtCoderのテストケースより [入力例] 0 1 1 -2 0 4 3 [出力例] NO YES ※AtCoderのテストケースより [入力例] 0 0 5 -2 -2 2 1 [出力例] YES NO ※AtCoderのテストケースより [入力例] 0 0 2 0 0 4 4 [出力例] YES YES ※AtCoderのテストケースより [入力例] 0 0 5 -4 -4 4 4 [出力例] YES YES ※AtCoderのテストケースより |
■C++版プログラム(問題B／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 |
#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 f[41]; int main(){ // 1. 入力情報. int K; scanf("%d", &K); // 2. Fibonacci数列を計算. f[0] = 1, f[1] = 1; repx(i, 2, 41) f[i] = f[i - 1] + f[i - 2]; // rep(i, 41) printf("%d\n", f[i]); // 3. 出力. printf("%d %d\n", f[K - 1], f[K]); 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 |
[入力例] 1 [出力例] 1 1 ※AtCoderのテストケースより [入力例] 3 [出力例] 4 5 ※AtCoderのテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. 2 3 [入力例] 12 [出力例] 314159265 358979323 ※AtCoderのテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. 144 233 [入力例] 25 [出力例] 75025 121393 [入力例] 40 [出力例] 102334155 165580141 |
■参照サイト
AtCoder Regular Contest 051