C++の練習を兼ねて, AtCoder Beginner Contest 047 の 問題B（すぬけ君の塗り絵 2 イージー / Snuke’s Coloring 2 (ABC Edit)) ～ 問題D（高橋君と見えざる手 / An Invisible Hand) を解いてみた.
■感想.
1. とりあえず, 解説見ずに解けたので良かったと思う.
2. 問題B は, 最初, 方針が全く見えなかったが, 数列 a の値を確認する度に, 黒く塗りつぶす x, y座標の最小値, 最大値が変化することに気付いたので, 解答に到達できた(※個人的には, 非常に面白い問題と感じた).
2. 問題D は, 数列A の 各要素の後方について, 最大値の抽出が必要があることに気付けた(※下記, ソースでは, 数列B として抽出している)ため, 解答に到達できた.
本家のサイトARC #063 / ABC #047 解説をご覧下さい.
■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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. int W, H, N; cin >> W >> H >> N; // 2. 長方形を黒く塗りつぶしていく. int xMin = 0; int xMax = W; int yMin = 0; int yMax = H; FOR(i, 0, N) { int x, y, a; cin >> x >> y >> a; if(a == 1) xMin = max(x, xMin); if(a == 2) xMax = min(x, xMax); if(a == 3) yMin = max(y, yMin); if(a == 4) yMax = min(y, yMax); } // 3. 後処理. int ans = (xMax - xMin) * (yMax - yMin); if(xMax <= xMin || yMax <= yMin) ans = 0; cout << ans << endl; return 0; } |
■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 |
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) int main() { // 1. 入力情報取得. string S; cin >> S; // 2. 必要な操作回数をカウントする. int ans = 0; char bef = S[0]; // 前回出現した文字 FOR(i, 0, S.size()) { // 2-1. 現在の石をチェック. char cur = S[i]; // 2-2. 前回と異なる石の色であれば, カウントアップ. if(cur != bef) ans++; // 2-3. 前回出現した文字を更新. bef = cur; } // 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 53 54 55 56 |
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define FOR(i, a, b) for(LL i = (a); i < (b); ++i) #define FORR(i, a, b) for(LL i = (a); i >= (b); --i) int main() { // 1. 入力情報取得. LL N, T; cin >> N >> T; LL A[N] = {}; FOR(i, 0, N) cin >> A[i]; // 2. 高橋君の収益を少なくとも, 1円下げるために必要な合計コストの最小値を計算. // i < j において, A[i] < A[j] となっている組み合わせに限定したとき, // A[j] - A[i] が最大となるものの個数をカウントしていく問題と読み替えることができる. // ex. // 10 100 // 7 10 4 5 9 3 6 8 2 1 // -> A[2] = 4, A[4] = 9 と A[5] = 3, A[7] = 8 の 場合に, 最大5 となることが分かる. // // 右側から最大値を順次確認. // A = 7 10 4 5 9 3 6 8 2 1 // B = 10 9 9 9 8 8 8 2 1 1 // -> 例えば, 4より右側の最大値は 9, 6より右側の最大値は, 8 などと読み取ることが出来る. LL B[N] = {}; B[N - 1] = A[N - 1]; FORR(i, N - 2, 0) { if(A[i + 1] > B[i + 1]) B[i] = A[i + 1]; else B[i] = B[i + 1]; } // FOR(i, 0, N) cout << B[i] << endl; // 3. 数列 A, B の差分を保管. // 上記の例で確認したように, A[2] = 4, A[4] = 9 と A[5] = 3, A[7] = 8 の 場合に, 最大5 となるが, // 最大値を取るパターンが, 合計2回であることを抽出する必要がある. map<LL, LL> m; FOR(i, 0, N) { LL diff = max(0LL, B[i] - A[i]); m[diff]++; } // 4. 出力 ～ 後処理. // Display the last element in map : map iterator « map multimap « C++ Tutorial. // http://www.java2s.com/Tutorial/Cpp/0460__map-multimap/Displaythelastelementinmap.htm auto itr = m.end(); --itr; LL ans = itr->second; cout << ans << endl; return 0; } |
■参照サイト
AtCoder Beginner Contest 047