C++の練習を兼ねて, AtCoder Beginner Contest 128 の 問題F (F – Frog Jump) を解いてみた.
■感想.
1. 解答の方針が, 全く見えなかったので, 解説を読んだうえで, 実装した.
2. 但し, 実装上, 部分的に, いくつも推測(ex. 同じ座標を二度通らない, kの上限など)しているため, 題意と, ズレている可能性があると思われる.
3. テストケースの自作が困難だったため 実装後, ネット上のatcoder_testcases ABC128で, テストケースをいくつか確認後, 提出した.
4. 余談としては, 前問 である 問題E (E – Roadwork) は, 知識不足(イベントソート) かつ (解説を読んだものの)解答不能だったため, 時間を見つけて, 類題など探して, 理解を深めていく必要があると思っている.
本家のサイトABC 128解説をご覧下さい.
■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 |
// 解き直し. // ABC 128解説. // https://img.atcoder.jp/abc128/editorial.pdf #include <bits/stdc++.h> using namespace std; using LL = long long; LL S[123321]; int main() { // 1. 入力情報取得. int N; scanf("%d", &N); for(int i = 0; i < N; i++) scanf("%lld", S + i); // 2. 解説通り. // 以下の情報から, 計算するとのこと. // 0, (N - 1) - k * C, C, (N - 1) - (k - 1) * C, 2 * C, ... k * C, N - 1. // -> f(k + 1, C) = f(k, C) + S[N - 1 - k * C] + S[k * C] (k >= 0) LL ans = 0; for(int c = 1; c < N; c++){ LL cur = 0, bef = 0; map<LL, int> route; // 経路情報を保存. for(int k = 0; k < (N - 1) / c; k++){ // 2-1. 経路情報チェック. // すでに通っていた場合は, 終了. int pos1 = N - 1 - k * c; int pos2 = k * c; route[pos1]++, route[pos2]++; if(route[pos1] != 1 || route[pos2] != 1) break; // 2-2. cur更新. cur = bef + S[pos1] + S[pos2]; // 2-3. 最終得点更新. ans = max(ans, cur); // 2-4. bef更新. bef = cur; } } // 3. 出力 ～ 後処理. printf("%lld\n", ans); 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 |
[入力例] 5 0 2 5 1 0 [出力例] 3 ※AtCoderテストケースより [入力例] 6 0 10 -7 -4 -13 0 [出力例] 0 ※AtCoderテストケースより [入力例] 11 0 -4 0 -99 31 14 -15 -39 43 18 0 [出力例] 59 ※AtCoderテストケースより [入力例(09.txt)] 35 0 7 0 -4 -2 -2 -10 3 9 -4 10 8 4 4 7 -10 0 -10 8 -1 -5 -7 -2 -7 3 0 -4 8 -2 -2 -2 3 9 4 0 [出力例] 27 ※AtCoderテストケースより [入力例(10.txt)] 22 0 -10 -8 -5 10 -1 -5 -9 4 0 -1 -4 -4 -1 -6 -7 8 -5 -2 4 0 0 [出力例] 11 ※AtCoderテストケースより |
■参照サイト
AtCoder Beginner Contest 128
atcoder_testcases ABC128