C++の練習を兼ねて, AtCoder Beginner Contest 068 の 問題D（Decrease (Contestant ver.)）を解いてみた.
■感想.
1. 問題を読んでも, 方針が全く見えなかった.
2. 解説を読んだところ, 目から鱗で, なるほど, と感心させられ, 大変勉強になったと思う.
本家のサイトAtCoder Regular Contest 079 Editorialをご覧下さい.
■C++版プログラム.
|
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 69 70 71 72 |
// 解き直し. // AtCoder Regular Contest 079 Editorial // https://atcoder.jp/img/arc079/editorial.pdf #include <iostream> using namespace std; #define FOR(i, a, b) for(int i=(a); i<(b); ++i) typedef long long LL; int main() { // 1. 入力情報取得. LL K; cin >> K; // 2. 数列 0, 1, ..., N - 1 を 考え, // 1, 2, ..., N, 1, 2, ..., N, の 順番で, 逆操作を行えばよいとのこと. // 2-1. N = 50 として, 確認することにする. int N = 50; LL sequence[N] = {}; FOR(i, 0, N) sequence[i] = i; // 2-2. K回繰り返すには... // 試しに, N = 10 と置いて, 10回繰り返す. // -> 0回目 と比べて, 各要素 が 1ずつ増加している. // 0回目 … 0 1 2 3 4 5 6 7 8 9 // 1回目 … 10 0 1 2 3 4 5 6 7 8 // 2回目 … 9 10 0 1 2 3 4 5 6 7 // ... // 9回目 … 2 3 4 5 6 7 8 9 10 0 // 10回目 … 1 2 3 4 5 6 7 8 9 10 <--- 0回目 から, 全体が, 1ずつ増加している. // N = 10; // int loop = 0; // int index = 0; // while(loop < N) { // FOR(i, 0, N) { // if(index == i) sequence[i] += N; // else sequence[i]--; // } // loop++; // index++; // index %= N; // } // FOR(i, 0, N) cout << sequence[i] << " "; // 2-3. 数列の base を作り, 全体 を increment. // K が, 非常に大きな数なので, K を N で 割ったときの商, 余りを計算してみる. LL quotient = K / N; LL remainder = K % N; // base. int index = 0; while(index < remainder) { FOR(i, 0, N) { if(index == i) sequence[i] += N; else sequence[i]--; } index++; } // increment. FOR(i, 0, N) sequence[i] += quotient; // 3. 出力 ～ 後処理. cout << N << endl; FOR(i, 0, N) cout << sequence[i] << " "; return 0; } |
■参照サイト
AtCoder Beginner Contest 068