C++の練習を兼ねて, AtCoder Beginner Contest 081 の 問題C（Not so Diverse) ～ 問題D (Non-decreasing) を解いてみた.
■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.
本家のサイトAtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説をご覧下さい.
■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 |
#include <iostream> #include <map> #include <algorithm> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) #define max(x, y) ((x > y) ? x : y) int main() { // 1. 入力情報取得. int N, K; cin >> N >> K; map<int, int> m; FOR(i, 0, N) { int ai; cin >> ai; m[ai]++; } // 2. map の 値 で, 昇順ソート. // [入力値] // 10 3 // 5 1 3 2 4 1 1 2 3 4 // (整数, 出現回数) = (5, 1), (2, 2), (3, 2), (4, 2), (1, 3) なので, // 5 … 1回, 2 … 2回 の 合計3回書き換えれば 3種類以下となる. int size = m.size(); int A[size] = {}; int index = 0; for(auto i = m.begin(); i != m.end() ; ++i) A[index++] = i->second; sort(A, A + size); // 3. 書き換え回数をカウント. int rewrites = 0; FOR(i, 0, size) if(size - i > K) rewrites += A[i]; // 4 . 出力 ～ 後処理. cout << rewrites << 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 57 |
// 解き直し. // AtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説. // https://img.atcoder.jp/arc086/editorial.pdf #include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define FORR(i, a, b) for(int i = (a); i > (b); --i) int main() { // 1. 入力情報取得. int N; cin >> N; int A[N + 1]; // pair の 第一成分: インデックス(1 ～ N), 第二成分: 値. pair<int, int> aMax = {-1, -1e6}; pair<int, int> aMin = {-1, 1e6}; FOR(i, 1, N + 1) { int a; cin >> a; if(aMax.second < a) aMax.first = i, aMax.second = a; if(aMin.second > a) aMin.first = i, aMin.second = a; A[i] = a; } // 2. 解説通り. int iMax = aMax.first; int vMax = aMax.second; int iMin = aMin.first; int vMin = aMin.second; // 2-1. 配列A が, 非負整数の場合. // a(2) += a(1), a(3) += a(2), ..., a(N) += a(N - 1) の操作で実現できる. if(vMin >= 0) { cout << N - 1 << endl; FOR(i, 1, N) cout << i << " " << i + 1 << endl; } // 2-2. 配列A に, 負整数が混在する(abs(vMin) <= abs(vMax))場合. // すべての配列A の要素に, vMax を 加算後, 2-1. と同じ操作を追加すれば実現できる. if(vMin < 0 && abs(vMin) <= abs(vMax)) { cout << N * 2 - 1 << endl; FOR(i, 1, N + 1) cout << iMax << " " << i << endl; FOR(i, 1, N) cout << i << " " << i + 1 << endl; } // 2-3. 配列A に, 負整数が混在する(abs(vMin) > abs(vMax))場合. // すべての配列A の要素に, vMin を 加算後, 2-1. と類似の操作を追加すれば実現できる. if(vMin < 0 && abs(vMin) > abs(vMax)) { cout << N * 2 - 1 << endl; FOR(i, 1, N + 1) cout << iMin << " " << i << endl; FORR(i, N, 1) cout << i << " " << i - 1 << endl; } return 0; } |
■参照サイト
AtCoder Beginner Contest 081