C++の練習を兼ねて, AtCoder Grand Contest 055 の 問題A (ABC Identity) を解いてみた.
■感想.
1. 問題Aは, 実装に苦労したものの, 解説見る前に, AC版に到達出来たので, とりあえず良かったと思う.
2. 個人的には, 6個以下の部分列に分解できるという性質が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Grand Contest 055 の 各リンク を ご覧下さい.
■C++版プログラム(問題A/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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using vi = vector<int>; using vvi = vector<vi>; #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 all(x) x.begin(), x.end() int ans[606060]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); char x[606060]; scanf("%s", x); string s(x); // 2. 部分列に分解. int idx = 0; rep(i, 6){ // インクリメント. idx++; // 出現位置. vvi pos(3); rep(j, N * 3){ if(!ans[j]){ if(s[j] == 'A') pos[0].pb(j); if(s[j] == 'B') pos[1].pb(j); if(s[j] == 'C') pos[2].pb(j); } } // 6通り確認. int maxT = -1, maxAt = -1; vvi ok; vi z(3); iota(all(z), 0); do{ // 'A', 'B', 'C' の 出現位置. vi at; // 変数用意. int count = 0; int pz0 = pos[z[0]].size(); int pz2 = pos[z[2]].size(); // 矛盾している場合. if(!pz0 || !pz2) break; // 対象文字を何文字取れるか. rep(j, pz0){ // 左から一番遠い位置. int at0 = pos[z[0]][j]; // 右から一番遠い位置. if(j + 1 > pz2) break; int at2 = pos[z[2]][pz2 - 1 - j]; // 矛盾していたら終了. if(at2 < at0) break; // 中央部分の文字数をチェック. int l = lower_bound(all(pos[z[1]]), at0) - pos[z[1]].begin(); int r = lower_bound(all(pos[z[1]]), at2) - pos[z[1]].begin(); if(r - l <= count) break; // 文字数. count = j + 1; } // 最大値更新. if(maxT < count){ maxT = count; maxAt = ok.size(); } // z[0] を 保存. rep(j, count) at.pb(pos[z[0]][j]); // z[2] を 保存. rep(j, count) at.pb(pos[z[2]][pz2 - 1 - j]); // z[1] を 保存. int l = lower_bound(all(pos[z[1]]), pos[z[0]][count - 1]) - pos[z[1]].begin(); repx(j, l, l + count) at.pb(pos[z[1]][j]); // 保存. ok.pb(at); }while(next_permutation(all(z))); // 訪問済みフラグ設定. // -> 一番文字列を長く取れた部分を設定. if(maxAt != -1){ for(auto &o : ok[maxAt]){ ans[o] = idx; s[o] = '_'; } } } // 3. 出力. rep(i, N * 3) printf("%d", ans[i]); 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 49 50 51 52 53 54 55 56 57 58 59 60 61 |
[入力例] 2 ABCCBA [出力例] 111222 ※但し, 上記のプログラムでは, 以下の内容が出力される. 112122 [入力例] 4 AABCBCAACBCB [出力例] 111211241244 ※但し, 上記のプログラムでは, 以下の内容が出力される. 111212221212 [入力例] 3 AAACCCBBB [出力例] 111111111 [入力例] 7 BACBCACAABABCBCBBACAC [出力例] 214221213141311432121 [入力例] 17 ABCCBCACACCCAACBABAABACCBCBBCBCABBBABCBAACBABAABACC [出力例] 321121313111115212112122323324215114141523121221233 [入力例] 20 CCBCCACACABCBABABABBCCACBBABCBBCAAACAABACAABACCBBBCABCCABCAB [出力例] 331332323214121212112212331323321112113413343112221321132132 [入力例] 333 ACCCCABABCCBCABACCBCCCAAACBAABCBCCBCBCCACCBBCCABACACBABCCAABCBAACBBACAAABABAABABBABCBBABBCBACCBAACCBABCCCCCCCABBBCACCACABACACABACBACAACCABACBACCBCCCAAAAACBCACAABAACCBBABCCBBACBABBBACBBCCCAACABBACACBBCCBBAABAACBCAABCCABABBBAABCAAABBBBBCCABACBAABCABBAAABCCABCACBCBBAACCAAACCBBBABBBBCAAABCCCCAACBBBBCABCCCBBCAACCAACACBBBBBABABBAACACAACCBBACBBCCAABBACBAACBCCCAAABAAACBCABBBBBBBCCCBACBBABBACACCABCBAAABACCBBCACBBACCCAAACBABBCAACCBABBBBCBCCCABCBBCACCBCACCCBBCBBABAACCBBAACBCCABBBCAABBCBBBACABBBBBABBACCAACCAACCCBAAAACABCACAACCACCAABAABBACACBACBBACCCACCABABABCABBAABCABBACACCACBBBCCBCCBABBACCCCCAAAABCACBACCCCCBBABABBCCACCAAAABBABBABCACABABCCBAABCACBACBAABBAAACCABABACABCCCACBCBAAAACBBABBACBBBCCAACCACCCACCBCBCBCCBAABBAABCBCCCBCBBBAAABCAAABACCCCCBACABABBAACBACBBAACABBBBCABABCAACBCACACACAABABBCCCAABACCACBABBBACABBACCCCBAAACBCABABAABCAACAACBBABCABBACCBAABAACABBCCBACBBABCCCCCCBACBACBCBAABAACBCBBBCCACBBCBBABBBAABCCCBBBCBACAAACCCBBCBBABBBAAACBABACABAACCBCABACBACABCBAACABCBBBBCBACAACCACBABBCCCCBCACBABBBCAAC [出力例] 122221313223213122322211123113232232322122332213121231322113231123312111313113133132331332312231122313222222213332122121312121312312112213123122322211111232121131122331322331231333123322211213312123322331131123211322131333113211133333221312311321331113221321232331122111223331333321113222211233332132223321122112123333313133112161111223122113322312331211133323331213222222211123122322313113212333231122131223111333123221331123222212111321221311213111221223233112233121132221332212223132222232231133113311123333132131331131133233223131231223111311323232132233213223131131222112112322311111333321312311111223232211311333322322321313232112332131231233223331142526124111256452222311211231113322332333233131313312211221313331311122213222123333312321211223123112232111132121322313232323221211333221233231211123211233331222313212122132232231121321123312212232113312311213333331231231312212231311133231131121112213331113123222333113112111222312123212233132123123213122321311113123223323121133331323121113223 [入力例] 1000 ABBAACCCCBCCCBCCCBBBBAAABCAAABBCACBCAACCCACCCCACCCCCACBCCBAABCBBBCABABCACBBBCAAABAAAACBCCABABACCAABAABBCBABBBABBBBCCACBACCAACCACBCBCCCCBCBBACCACACACCBCBCCAAABBCCCCCACACABACBBAACAACABAAACBBACAABCACBBCABCACBCBBCBACABBCCABACBCACAACBAABCBBAAABBABABCBBBACBBBBACACAAAAABAABAACBBABABCAABCAAAABACBCBACCAAABBCCCCCBCCCBBABBABCBBCAACACBCBCCBBCBABACACBCCBACABCBACCCBBBAAAAABBCBBCBABBAACBBABBACCABABABAABACABBCBCBBBCBCBBACBCCACBBCACAABABCCABCAAAAAACCBBAAACCBBABCABBACACABCABBCBCCAACBAAAACCBBCAAAABABCBABBACACBABBABBBABCACBABABABCCBACCBAAAACAACCAABABBCACBBCBBACCCCCAACCACBCABCBACBACBABBCCCBCBBBAABCBABCBCCBBBCCACCBBCBCAAACACACBCCBCCACCBACBABABACCCCBBBCBACBAACBBBBBAAACACCAABBACBABACCBABACABBAABBABACBCBBACBCBAAABBAABABCCBCBBCACBCCBBBABCCAACAABBABCBABACCAABCACBACCBCBAACBBCACCBCCAACBBAABBBCABBBAAAAABAAABBCCCABBBAABCAACBBCACABCBCCBCACAAACABABCCCCBCACBABBABABAACBCBCBBBCBCACCABAABCCACBBCCABCCBCBCCABABCCCABBABCBBACCCCBABCACAABBBCCCBCBCABCACABCAAACBACABACCAABACBACBABBABABCAAAAAAACACBBABCAACCABABACCCAACBAAABBCCBBBBABBACCABAAABABACCACCCACCACCCCCCAABCBACAABCACACBBACBCCBCACCBCBBAAABBACBBBABABCAACCCBBAAAACCCACCCCABAABCCBCAACBCAAAACCCCBCCBCCAACCAACCAAACACCCCCCCCAACCABAAABAACACAAABCCACBBBCCBBABAABCBAAAABBBBBCBCCABBCCCCCCCAABAAACABABCBAACCBCCACAACBABAABCCAABBCBAABBCCACACABACBCCACBBCBACABCBACABBABCAABCBCCCAACCBBACAABCCBBAACACBBCAACBAABBBBBACBCBCBACACCCCACACAABAAAABBCCBCCBCABBCCCBACAACABAACCAAABBACBCCBCAAABBCCACCABBBCBBCCCCBACCBCBBBABCBACCBBCABACCBCBCBBACACBBBBABBBBBBCACBAACBBBBCACABACBACBCCACCBCABCBCACBCCCBABBAABBCBBAABBACBBAACCABAABBBCBCBBCBBAACCBAABBACCAABACACBBACCCBACCACBCAACCBBABACBABCCCACCCCACCACCBCBBBACBACBCBACCCAAAABCCAABCBBACCACAABABABCAABACBCCBCCCCCBCBBACCCCCBCABCBBBABBBBBBACACAACBABAABBACBCCBBCAAAACACBCBCABACACABAABABAAACBCABCAACCBCAAAAAABCCACBBCCCAABABCACAACBCACCBCBCABBACCCBBBCAACBCAAAABACAAABCCBABACCBBACBBABBABBCCCBAABACCCAABBCCCCCABACBABBAAAACABBACBABBCBAACCCCCACABBABABAAACCBAACAACCAAAABABBAACBCABCBBCBABAAAAABACACBAACABBCABABBBBCBABBBCBBCACBABBAACABBBCCABBABCBCCACBAABBBACABBABCABAACAACBBCAABABCCCBAABBACCCACCACCBBAABCAACCAABABCBBAAAAACCCABCABCBBBCCCBAACACBAABACACCACBBCCCBBACABACCACCABCCABCBBCAAAABCBCACAACCAABCACBBABBCCCCCCCCCCCCABCCCABCBAAACCBCCACBCCBCAACBBBACCCAABAABCBBACBCABACBCACACBCCACCCCAAAABCABBAABCCCAACACAACBBAAABCABBABCBABBAAAABAACBAAAABBBACBCBCABABCAABABABBABBACCCAAAAABBBCCAABBBCCBCBCCABCCBABBCAACCCBABABABBAABCCCBCCAABBBBACCBCBCBBCCBABBACCCBCABBBACCBCCACAABACCCABCABABBCBABBABCACBABBAACBBBCCACCAACCBBCBBBCACBCBABAABBBCCACBACCBBBCACACAACBBABCCAAABCBCCABBACCABBBAACACAAABAABACACBBABABABBCCAAABAAABACCAABBBBABCBBCABAABAABBBAACAABBBBBBABCCCCCBCBBCBBCCABACCABBABAAABCCBBCABAAABAABBCABCBBABBABBCBCAAACBCABBCCCCAAAACABCBBACABCBBABACBCBACBBCCCBACBBCBCBCCABCABBAACABAACCCCACBCCABCBCBCBCABABAAAACBABCABABACBABACBABACBBBACACBACCCBAABABBABCCCCBABBCACBACAABCCBBBBCBBCCAACAABCBBABABACCACCCCBABBBBABBBAAAAACCBCACCBCCBABBABCACACCABCAACCBBABAACACBCABAAAABACBBAAACBBCCAACAABCAABBCCACCACCBBACCABACCABBBBCCCBAAABABACBAACCBAACBBACBCCBCCCBCBACBBBCCBBBBACCCBACBBABBBBABABCCCBAAABBBBABBCABABAACBBBACBC [出力例] 133112222322232223333111321113321232112221222212222212322311323332131321233321113111123221313122113113323133313333221231221122123232222323312212121223232211133222221212131233112112131112331211321233213212323323121332213123212112311323311133131323331233331212111113113112331313211321111312323122111332222232223313313233211212323223323131212322312132312223331111133233231331123313312213131311312133232333232331232212332121131322132111111223311122331321331212132133232211231111223321111313231331212313313331321231313132231223111121122113133212332331222221122123213231231231332223233311323132322333221223323211121212322322122312313131222233323123112333331112122113312313122313121331133131232331232311133113132232332123223331322112113313231312211321231223231123321223221123311333213331111131113322213331132112332121323223212111213132222321231331313112323233323212213113221233221322323221313222133132331222231321211333222323213212132111231213122113123123134141421111111212441421122141412221122111224422221221441211121214414451113111111332123133213131223121121311212233322312223232133111223333111311113233211213312133331111211211331133113331311111111331132333233131333211312221122323321233332222212113221111111332333132321233112113133123233211332212332211313132312113122123132123132232133212111331122313321122331312213312332222231212123131111313133233332211211213221112313313233113332231211213332211311322212211112311212223212311221323112121223131222232222221312331222213132312312113112132121312111232233221223322312233113233222121221223311233223113323131223111231131213311223231232111311113113112122231231212311133332113321223113133232321332312112111112122311111213212223222222313133123233223121122133331312121323131323323233312132133112133333321131221113323213133121311212132231112221331213333231333211232311223122322322111233231113322111113231232233331322312322123311111313223232333112331331133332322331213212212323333323131233132213232222123222122131232233132221132232121131233222313223213235144122144242111244514333233233112213223322121311222223332132131113331223231221232332311333112321233233213321311322221313232233221323112113333333333332133321312223313323133132231112333221221311231321231323231332333322221321122133322323223112221321121312112222122312222111231313212132212121121123332222211133221113313133213312113223331212121122133313322111123313131133121123331321112331332322123332132121131211213231211223111332332233113111323131212211133231233111323232231121332221313321123321112232322212212323112121211332221222123322111121311321221221112232211111121333331311311332123321121222133113212221221132131121121131322231321133332222321311232131121231312311333123113131332132112232122333323133213131313212122223121321212312123121231112323123331221211213333121132312322133111131133223221311212123323333121111211122222331323313312112132323321322331121223231321222212311222311332232213221133233233112332123321111333122212123122331223112313313331312311133111123331231121111212133312221111211321212231112313 |
■参照サイト
AtCoder Grand Contest 055