C++の練習を兼ねて, AtCoder Beginner Contest 146 の 問題F (F – Sugoroku) を解いてみた.
■感想.
1. 方針が見えなかったので, 解説を参考に実装した.
2. 前問に引き続き, 自力で解答出来なかったものの, どちらの問題も楽しく, 非常に勉強になったと思う.
3. また, これで解けてしまうことが摩訶不思議に思えた.
本家のサイトABC 146解説をご覧下さい.
■C++版プログラム(問題F／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 60 61 62 63 64 65 |
// AC版. // 解き直し. // ABC 146解説. // https://img.atcoder.jp/abc146/editorial.pdf #include <bits/stdc++.h> using namespace std; #define pb push_back #define repx(i, a, b) for(int i = a; i < b; i++) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) const int INF = 2020202020; const int MAX = 111111; int d[MAX]; int main(){ // 1. 入力情報. int N, M; char S[111111]; scanf("%d %d %s", &N, &M, S); rep(i, MAX) d[i] = INF; // 2. 解説通り. // 連続する '1' が, M以上のものが存在したら, ゴールへの到達は不可能. int maxOne = 0, one = 0; rep(i, N + 1){ if(S[i] == '1') one++; else maxOne = max(maxOne, one), one = 0; } if(maxOne >= M){ puts("-1"); return 0; } // 3. 目的地点から, 各出発地点までの最短手数を求める. int bef = N, dx = 1, mIndex; d[N] = 0; repr(i, N - 1, 0){ if(bef - i > M){ bef = mIndex; dx++; } if(S[i] == '0' && bef - i <= M){ d[i] = dx; mIndex = i; } } // rep(i, N + 1) printf("%d ", d[i]); // printf("\n"); // 4. 最短経路の情報を保存. vector<int> v; int r = d[0]; rep(i, N + 1) if(d[i] == r) v.pb(i), r--; // 5. 出力. int l = v.size(); rep(i, l - 1){ printf("%d", v[i + 1] - v[i]); if(i < l - 2) printf(" "); } printf("\n"); 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 |
[入力例] 9 3 0001000100 [出力例(debug版)] 4 3 3 2020202020 2 2 1 2020202020 1 0 1 3 2 3 ※AtCoderテストケースより [入力例] 5 4 011110 [出力例(debug版)] -1 ※AtCoderテストケースより [入力例] 6 6 0101010 [出力例(debug版)] 1 2020202020 1 2020202020 1 2020202020 0 6 ※AtCoderテストケースより [入力例] 100 10 01110011110001111100001111110000011100111100011111000011111100000111001111000111110000111111010011100 [出力例] 10 8 10 4 10 8 10 4 10 8 10 8 [入力例] 300 8 0110110000011110000111011010111001100011011011001101000011010111101101011001011010010101011011011011101110111101000001010000110101011100110011011111010000000101010000101000110111110010111110000101000011100000110111100011011001110000110011110011110101001100100100010001011110110111010101101000000110000 [出力例] 3 6 8 8 7 8 6 6 8 8 8 8 7 6 8 5 8 8 8 8 6 4 8 7 7 6 3 8 8 8 8 5 8 6 6 6 8 6 8 8 8 8 8 |
■参照サイト
AtCoder Beginner Contest 146