C++の練習を兼ねて, AtCoder Grand Contest 007 の 問題A (Shik and Stone) ～ 問題B (Construct Sequences) を解いてみた.
■感想.
1. 解答を見る前に, 解答まで辿り着いたので良かったと思う.
2. 問題B は, 条件を満たす数列の例が見つかったので, 何とか解答に辿り着けた.
本家のサイトAtCoder Grand Contest 007 Editorialをご覧下さい.
■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 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <bits/stdc++.h> using namespace std; int main() { // 1. 入力情報取得. int H, W; cin >> H >> W; char a[H][W]; int sharp = 0; for(int i = 0; i < H; i++){ string s; cin >> s; for(int j = 0; j < W; j++){ a[i][j] = s[j]; if(s[j] == '#') sharp++; } } // for(int i = 0; i < H; i++){ // for(int j = 0; j < W; j++) cout << a[i][j] << " "; // cout << endl; // } // cout << sharp << endl; // 2. 移動する過程で, 駒が常に右または下に動いていた可能性があるかを判定. // 2-1. '#' の 個数が, H + W - 1 個で無ければ, "Impossible" のはず. if(sharp != H + W - 1){ cout << "Impossible" << endl; return 0; } // 2-2. '#' の マス で, 下方向 or 右方向 で, '#' でないマスが, 一つでもあれば, "Impossible" のはず. bool ok = true; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ // 右下隅のマスに到達したら, break; if(i == H - 1 && j == W - 1) break; // 下方向 かつ 右方向 ともに '#' の マスが見当たらない場合. if(a[i][j] == '#'){ if((i < H - 1 && a[i + 1][j] != '#') && (i < W - 1 && a[i][j + 1] != '#')){ // cout << "down: a[" << i << "][" << j << "]=" << a[i][j] << endl; ok = false; break; } } } if(!ok) break; } // 3. 出力. if(ok) cout << "Possible" << endl; else cout << "Impossible" << endl; return 0; } |
■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 41 42 43 44 45 46 47 48 49 50 51 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; int main() { // 1. 入力情報取得. LL N; cin >> N; LL p[N + 1]; p[0] = 0; for(LL i = 1; i < N + 1; i++) cin >> p[i]; // 2. 整数列 a, b を 構築. // [イメージ(方針)] // ex. // N = 3 の 場合(上段: a1, a2, a3, 下段: b1, b2, b3). // 10 20 30 // 30 20 10 // ↓ // (p1, p2, p3) = (2, 1, 3) などとする. // ↓ // 10 20 + 1 30 // 30 20 10 // ↓ // 10 + 2 20 + 1 30 // 30 20 10 // ↓ // 10 + 2 20 + 1 30 + 3 // 30 20 10 // ↓ // 12 21 33 // 30 20 10 // // 2-1. 整数列 a, b の ベース を構築. // -> ai + bi が 全て等しい状態. LL a[20001], b[20001]; a[0] = b[0] = 0; for(LL i = 1; i < 20001; i++) a[i] = 25000 * i; for(LL i = 1; i < 20001; i++) b[i] = a[20001 - i]; // 2-2. 順列情報から, 順列情報 の ソート順 となるように変更. for(LL i = 1; i < N + 1; i++) a[p[i]] += i; // 3. 出力 ～ 後処理. for(LL i = 1; i < N + 1; i++) cout << a[i] << " "; cout << endl; for(LL i = 1; i < N + 1; i++) cout << b[i] << " "; 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 |
[入力例] 2 1 2 [出力例] 25001 50002 500000000 499975000 ※AtCoderテストケースより [入力例] 3 3 2 1 [出力例] 25003 50002 75001 500000000 499975000 499950000 ※AtCoderテストケースより [入力例] 3 2 3 1 [出力例] 25003 50001 75002 500000000 499975000 499950000 ※AtCoderテストケースより [入力例] 5 3 5 1 2 4 [出力例] 25003 50004 75001 100005 125002 500000000 499975000 499950000 499925000 499900000 [入力例] 10 8 3 4 5 1 7 9 2 10 6 [出力例] 25005 50008 75002 100003 125004 150010 175006 200001 225007 250009 500000000 499975000 499950000 499925000 499900000 499875000 499850000 499825000 499800000 499775000 |
■参照サイト
AtCoder Grand Contest 007