C++の練習を兼ねて, AtCoder Regular Contest 024 の 問題C (だれじゃ) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 計算量を削減するために, 累積和を使い, 出現回数をチェックしていくロジックが, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Regular Contest 024 解説 を ご覧下さい.
■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 43 44 45 46 47 48 49 50 51 52 53 54 55 |
// 解き直し. // https://www.slideshare.net/chokudai/arc024 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second #define all(x) x.begin(), x.end() int sCum[101010][26]; int main(){ // 1. 入力情報. int N, K; char c[101010]; scanf("%d %d", &N, &K); scanf("%s", c); // 2. 累積和. rep(i, N){ rep(j, 26) sCum[i + 1][j] = sCum[i][j]; sCum[i + 1][c[i] - 'a']++; } // 3. ペアを保存. // -> {出現回数, 位置} を 保存. map<string, vi> m; rep(i, N - K + 1){ string sCount; rep(j, 26) sCount += to_string(sCum[i + K][j] - sCum[i][j]); m[sCount].pb(i); } // 4. sort. for(auto &p : m) sort(all(p.b)); // 5. 判定. bool ok = false; for(auto &p : m){ // printf("p.a=%s p.b.front()=%d p.b.back()=%d\n", p.a.c_str(), p.b.front(), p.b.back()); if(abs(p.b.front() - p.b.back()) >= K) ok = true; if(ok) break; } // 6. 出力. printf("%s\n", ok ? "YES" : "NO"); 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 40 41 42 43 44 45 46 47 48 |
[入力例] 8 3 abcdbcae [出力例] YES [入力例] 7 4 abcdcba [出力例] NO [入力例] 8 1 issample [出力例] YES [入力例] 30 5 lujvpsozzdwiveigvtkusfrknrddwe [出力例] NO [入力例] 22 11 abracadabraabracadabra [出力例] YES [入力例] 100 10 wxxmdlhtjcpzbwjhbgfynhntmwiequmpfaoczyfyjccacshwizahrfryrsdleglzmuynpieidylytonbngrzzvnukkwczgjjphbb [出力例] YES [入力例] 500 25 csqeiypjxtpaadtrnvusdnleqpizvhywlfkgyzmpjgzfpbjauuxeisxcyxsbfxmoohtiohigcbhouoxkicfrpytvrxhmnrxkkfwplvdsnpzkaivlserltkhaypwclyirghuzuyhtbxioxydpckpmweygptacpcgccsqgtpcevigribhtsndqinktmredwjqkldnxnecjapwmyehsghfipfwxuhezinndyhmyipbgkjcyrsjadnxqmnntlgnafuzjlqgfbcpsiusbvylapckjuvgjutjvpajbnlhcsowtclxkdyxfieqzwkovrrdbaxqwvwqceqvmlkpdglwuzwfxkhmnfnwmqfpvwgvrvslzryzgurifqdvivcrgidfaadddegvrdvxiokhgxpteqnojvldecfzdeifgfbccccdeqggghiiinppqrssttvtvaksxptqdrfxenqzhyjldpwwrjabivtapnxaxlsgrieztkzsubvfzbnqj [出力例] YES |
■参照サイト
AtCoder Regular Contest 024