C++の練習を兼ねて, AtCoder Regular Contest 035 の 問題A (A – 高橋くんと回文) ～ 問題B (B – アットコーダー王国のコンテスト事情) を解いてみた.
■感想.
1. 問題B は, 階乗を使う必要があることに気付けたので, AC版となったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトARC 035 解説をご覧下さい.
■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 |
#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 main(){ // 1. 入力情報. char c[1010]; scanf("%s", c); // 2. 回文判定. int l = strlen(c); bool ok = true; rep(i, l / 2){ // 2-1. 左右のいずれかに, '*' が 含まれる場合. if(c[i] == '*' || c[l - 1 - i] == '*') continue; // 2-2. 左右が異なる文字の場合. if(c[i] != c[l - 1 - i]){ ok = false; break; } } // 3. 出力. 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 |
[入力例] ab* [出力例] YES ※AtCoderのテストケースより [入力例] abc [出力例] NO ※AtCoderのテストケースより [入力例] a*bc* [出力例] YES ※AtCoderのテストケースより [入力例] *** [出力例] 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 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
// C++14(GCC 5.4.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--) #define a first #define b second const LL MOD = 1e9 + 7; const int LIMIT = 10101; LL FAC[LIMIT]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<LL, LL> m; rep(i, N){ LL t; scanf("%lld", &t); m[t]++; } FAC[0] = 1; repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD; // 2. コンテストペナルティが最小となる解き方は？ LL t = 0, p = 0, q = 1; for(auto &x : m){ rep(i, x.b) t += x.a, p += t; q = q * FAC[x.b] % MOD; } // 3. 出力. printf("%lld\n%lld\n", p, q); 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 60 61 62 63 64 65 66 67 68 |
[入力例] 2 20 10 [出力例] 40 1 ※AtCoderのテストケースより [入力例] 5 2 1 2 1 2 [出力例] 21 12 ※AtCoderのテストケースより [入力例] 13 1 1 1 1 1 1 1 1 1 1 1 1 1 [出力例] 91 227020758 ※AtCoderのテストケースより [入力例] 18 3 3 1 2 1 2 1 3 2 1 2 2 1 3 1 3 1 2 [出力例] 252 435456000 |
■参照サイト
AtCoder Regular Contest 035