C++の練習を兼ねて, AtCoder Beginner Contest 045 の 問題C（たくさんの数式 / Many Formulas) ～ 問題D (すぬけ君の塗り絵 / Snuke’s Coloring) を解いてみた.
■感想.
1. とりあえず, 解説見ずに解けたので良かったと思う.
2. 問題C は, 方針を決めることが出来たが, 結構ゴリゴリ書く羽目になってしまったように思う.
3. 問題D は, 計算量を減らすのに, 黒いマスに関係する3行3列の連続するマス目に限定させる方法に, 辿り着いたので解答出来たと思う.
4. 解説と, ほぼ同じ方針だったので, 及第点は, 取れたと思う.
本家のサイトABC 045 / ARC 061 解説をご覧下さい.
■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 54 55 56 57 58 59 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. const int a[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512}; string S; cin >> S; // 2. 考えられる数式を組み立てて, 総和を計算. // ex. // i == 25 -> 00011001 と読み替えて, 1 を '+' と見る. // この場合, 123456789 -> 1234 + 5 + 678 + 9 となる. // -> 上記の場合, 数式自体は, 2の8乗 == 256通り(00000000 ～ 11111111) と理解される. int l = S.size(); int limit = a[l - 1]; LL ans = 0; FOR(i, 0, limit) { // 2-1. i を 2進数表記に変換. stringstream ss; ss << bitset<9>(i); string s = ss.str(); // 2-2. 2進数表記の桁数を, 文字列Sの長さ - 1 に揃える. // ex. // l == 3 の場合, 000000011 -> 11 のように変換. s = s.substr(10 - l, l - 1); // cout << s << endl; // 2-3. 数式を組み立て, 保存. LL f = S[0] - '0'; vector<LL> v; FOR(j, 0, s.size()) { if(s[j] == '0') f = 10 * f + S[j + 1] - '0'; if(s[j] == '1') { v.push_back(f); f = S[j + 1] - '0'; } } v.push_back(f); // 2-4. 数式の和を計算. LL t = 0; for(auto &p : v) t += p; // cout << t << endl; ans += t; } // 3. 出力 ～ 後処理. cout << ans << endl; return 0; } |
■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 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. LL H, W, N; cin >> H >> W >> N; // 3行3列の連続するマス目(以下, 領域X と略記)の中心座標を, 一次元に変換後, // カウントアップし, その情報を保存. map<LL, LL> m; // 2. 黒いマスの座標(a, b) について, // どの領域X から カウントアップされるかを確認. FOR(i, 0, N) { LL a, b; cin >> a >> b; FOR(r, -1, 2) { FOR(c, -1, 2) { // 黒いマスの座標(a, b) に対応する, 領域X の 中心座標(ca, cb) を 取得. LL ca = a + r; LL cb = b + c; // 中心座標(ca, cb) を 1次元に変換. if(ca >= 2 && cb >= 2 && ca <= H - 1 && cb <= W - 1) { // 対象となる 領域X について, 中心座標を, 一次元に変換後, カウントアップ. LL cIndex = cb + (ca - 1) * W; m[cIndex]++; } } } } // 3. 上記で収集した, 領域X の 中心座標 及び, カウントアップに関する情報を集計. // -> ans[i] に, 黒いマスが, i個あるものを保管. LL ans[10] = {}; LL total = 0; for(auto &p : m) { total++; ans[p.second]++; } ans[0] = (H - 2) * (W - 2) - total; // 4. 出力 ～ 後処理. FOR(i, 0, 10) cout << ans[i] << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 045