個人用メモ帳

2021年11月5日2021年11月5日

C++ の動作確認をしてみた（５７２）

C++の練習を兼ねて, AtCoder Grand Contest 055 の問題A (ABC Identity) を解いてみた.

■感想.
1. 問題Aは, 実装に苦労したものの, 解説見る前に, AC版に到達出来たので, とりあえず良かったと思う.
2. 個人的には, ６個以下の部分列に分解できるという性質が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Grand Contest 055 の各リンクをご覧下さい.

■C++版プログラム(問題A／AC版).

// 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;
    
}

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;

}

[入力例]
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

[入力例]

ABCCBA

[出力例]

111222

※但し, 上記のプログラムでは, 以下の内容が出力される.

112122

[入力例]

AABCBCAACBCB

[出力例]

111211241244

※但し, 上記のプログラムでは, 以下の内容が出力される.

111212221212

[入力例]

AAACCCBBB

[出力例]

111111111

[入力例]

BACBCACAABABCBCBBACAC

[出力例]

214221213141311432121

[入力例]

ABCCBCACACCCAACBABAABACCBCBBCBCABBBABCBAACBABAABACC

[出力例]

321121313111115212112122323324215114141523121221233

[入力例]

CCBCCACACABCBABABABBCCACBBABCBBCAAACAABACAABACCBBBCABCCABCAB

[出力例]

331332323214121212112212331323321112113413343112221321132132

[入力例]

333

ACCCCABABCCBCABACCBCCCAAACBAABCBCCBCBCCACCBBCCABACACBABCCAABCBAACBBACAAABABAABABBABCBBABBCBACCBAACCBABCCCCCCCABBBCACCACABACACABACBACAACCABACBACCBCCCAAAAACBCACAABAACCBBABCCBBACBABBBACBBCCCAACABBACACBBCCBBAABAACBCAABCCABABBBAABCAAABBBBBCCABACBAABCABBAAABCCABCACBCBBAACCAAACCBBBABBBBCAAABCCCCAACBBBBCABCCCBBCAACCAACACBBBBBABABBAACACAACCBBACBBCCAABBACBAACBCCCAAABAAACBCABBBBBBBCCCBACBBABBACACCABCBAAABACCBBCACBBACCCAAACBABBCAACCBABBBBCBCCCABCBBCACCBCACCCBBCBBABAACCBBAACBCCABBBCAABBCBBBACABBBBBABBACCAACCAACCCBAAAACABCACAACCACCAABAABBACACBACBBACCCACCABABABCABBAABCABBACACCACBBBCCBCCBABBACCCCCAAAABCACBACCCCCBBABABBCCACCAAAABBABBABCACABABCCBAABCACBACBAABBAAACCABABACABCCCACBCBAAAACBBABBACBBBCCAACCACCCACCBCBCBCCBAABBAABCBCCCBCBBBAAABCAAABACCCCCBACABABBAACBACBBAACABBBBCABABCAACBCACACACAABABBCCCAABACCACBABBBACABBACCCCBAAACBCABABAABCAACAACBBABCABBACCBAABAACABBCCBACBBABCCCCCCBACBACBCBAABAACBCBBBCCACBBCBBABBBAABCCCBBBCBACAAACCCBBCBBABBBAAACBABACABAACCBCABACBACABCBAACABCBBBBCBACAACCACBABBCCCCBCACBABBBCAAC

[出力例]

122221313223213122322211123113232232322122332213121231322113231123312111313113133132331332312231122313222222213332122121312121312312112213123122322211111232121131122331322331231333123322211213312123322331131123211322131333113211133333221312311321331113221321232331122111223331333321113222211233332132223321122112123333313133112161111223122113322312331211133323331213222222211123122322313113212333231122131223111333123221331123222212111321221311213111221223233112233121132221332212223132222232231133113311123333132131331131133233223131231223111311323232132233213223131131222112112322311111333321312311111223232211311333322322321313232112332131231233223331142526124111256452222311211231113322332333233131313312211221313331311122213222123333312321211223123112232111132121322313232323221211333221233231211123211233331222313212122132232231121321123312212232113312311213333331231231312212231311133231131121112213331113123222333113112111222312123212233132123123213122321311113123223323121133331323121113223

[入力例]

1000

ABBAACCCCBCCCBCCCBBBBAAABCAAABBCACBCAACCCACCCCACCCCCACBCCBAABCBBBCABABCACBBBCAAABAAAACBCCABABACCAABAABBCBABBBABBBBCCACBACCAACCACBCBCCCCBCBBACCACACACCBCBCCAAABBCCCCCACACABACBBAACAACABAAACBBACAABCACBBCABCACBCBBCBACABBCCABACBCACAACBAABCBBAAABBABABCBBBACBBBBACACAAAAABAABAACBBABABCAABCAAAABACBCBACCAAABBCCCCCBCCCBBABBABCBBCAACACBCBCCBBCBABACACBCCBACABCBACCCBBBAAAAABBCBBCBABBAACBBABBACCABABABAABACABBCBCBBBCBCBBACBCCACBBCACAABABCCABCAAAAAACCBBAAACCBBABCABBACACABCABBCBCCAACBAAAACCBBCAAAABABCBABBACACBABBABBBABCACBABABABCCBACCBAAAACAACCAABABBCACBBCBBACCCCCAACCACBCABCBACBACBABBCCCBCBBBAABCBABCBCCBBBCCACCBBCBCAAACACACBCCBCCACCBACBABABACCCCBBBCBACBAACBBBBBAAACACCAABBACBABACCBABACABBAABBABACBCBBACBCBAAABBAABABCCBCBBCACBCCBBBABCCAACAABBABCBABACCAABCACBACCBCBAACBBCACCBCCAACBBAABBBCABBBAAAAABAAABBCCCABBBAABCAACBBCACABCBCCBCACAAACABABCCCCBCACBABBABABAACBCBCBBBCBCACCABAABCCACBBCCABCCBCBCCABABCCCABBABCBBACCCCBABCACAABBBCCCBCBCABCACABCAAACBACABACCAABACBACBABBABABCAAAAAAACACBBABCAACCABABACCCAACBAAABBCCBBBBABBACCABAAABABACCACCCACCACCCCCCAABCBACAABCACACBBACBCCBCACCBCBBAAABBACBBBABABCAACCCBBAAAACCCACCCCABAABCCBCAACBCAAAACCCCBCCBCCAACCAACCAAACACCCCCCCCAACCABAAABAACACAAABCCACBBBCCBBABAABCBAAAABBBBBCBCCABBCCCCCCCAABAAACABABCBAACCBCCACAACBABAABCCAABBCBAABBCCACACABACBCCACBBCBACABCBACABBABCAABCBCCCAACCBBACAABCCBBAACACBBCAACBAABBBBBACBCBCBACACCCCACACAABAAAABBCCBCCBCABBCCCBACAACABAACCAAABBACBCCBCAAABBCCACCABBBCBBCCCCBACCBCBBBABCBACCBBCABACCBCBCBBACACBBBBABBBBBBCACBAACBBBBCACABACBACBCCACCBCABCBCACBCCCBABBAABBCBBAABBACBBAACCABAABBBCBCBBCBBAACCBAABBACCAABACACBBACCCBACCACBCAACCBBABACBABCCCACCCCACCACCBCBBBACBACBCBACCCAAAABCCAABCBBACCACAABABABCAABACBCCBCCCCCBCBBACCCCCBCABCBBBABBBBBBACACAACBABAABBACBCCBBCAAAACACBCBCABACACABAABABAAACBCABCAACCBCAAAAAABCCACBBCCCAABABCACAACBCACCBCBCABBACCCBBBCAACBCAAAABACAAABCCBABACCBBACBBABBABBCCCBAABACCCAABBCCCCCABACBABBAAAACABBACBABBCBAACCCCCACABBABABAAACCBAACAACCAAAABABBAACBCABCBBCBABAAAAABACACBAACABBCABABBBBCBABBBCBBCACBABBAACABBBCCABBABCBCCACBAABBBACABBABCABAACAACBBCAABABCCCBAABBACCCACCACCBBAABCAACCAABABCBBAAAAACCCABCABCBBBCCCBAACACBAABACACCACBBCCCBBACABACCACCABCCABCBBCAAAABCBCACAACCAABCACBBABBCCCCCCCCCCCCABCCCABCBAAACCBCCACBCCBCAACBBBACCCAABAABCBBACBCABACBCACACBCCACCCCAAAABCABBAABCCCAACACAACBBAAABCABBABCBABBAAAABAACBAAAABBBACBCBCABABCAABABABBABBACCCAAAAABBBCCAABBBCCBCBCCABCCBABBCAACCCBABABABBAABCCCBCCAABBBBACCBCBCBBCCBABBACCCBCABBBACCBCCACAABACCCABCABABBCBABBABCACBABBAACBBBCCACCAACCBBCBBBCACBCBABAABBBCCACBACCBBBCACACAACBBABCCAAABCBCCABBACCABBBAACACAAABAABACACBBABABABBCCAAABAAABACCAABBBBABCBBCABAABAABBBAACAABBBBBBABCCCCCBCBBCBBCCABACCABBABAAABCCBBCABAAABAABBCABCBBABBABBCBCAAACBCABBCCCCAAAACABCBBACABCBBABACBCBACBBCCCBACBBCBCBCCABCABBAACABAACCCCACBCCABCBCBCBCABABAAAACBABCABABACBABACBABACBBBACACBACCCBAABABBABCCCCBABBCACBACAABCCBBBBCBBCCAACAABCBBABABACCACCCCBABBBBABBBAAAAACCBCACCBCCBABBABCACACCABCAACCBBABAACACBCABAAAABACBBAAACBBCCAACAABCAABBCCACCACCBBACCABACCABBBBCCCBAAABABACBAACCBAACBBACBCCBCCCBCBACBBBCCBBBBACCCBACBBABBBBABABCCCBAAABBBBABBCABABAACBBBACBC

[出力例]

133112222322232223333111321113321232112221222212222212322311323332131321233321113111123221313122113113323133313333221231221122123232222323312212121223232211133222221212131233112112131112331211321233213212323323121332213123212112311323311133131323331233331212111113113112331313211321111312323122111332222232223313313233211212323223323131212322312132312223331111133233231331123313312213131311312133232333232331232212332121131322132111111223311122331321331212132133232211231111223321111313231331212313313331321231313132231223111121122113133212332331222221122123213231231231332223233311323132322333221223323211121212322322122312313131222233323123112333331112122113312313122313121331133131232331232311133113132232332123223331322112113313231312211321231223231123321223221123311333213331111131113322213331132112332121323223212111213132222321231331313112323233323212213113221233221322323221313222133132331222231321211333222323213212132111231213122113123123134141421111111212441421122141412221122111224422221221441211121214414451113111111332123133213131223121121311212233322312223232133111223333111311113233211213312133331111211211331133113331311111111331132333233131333211312221122323321233332222212113221111111332333132321233112113133123233211332212332211313132312113122123132123132232133212111331122313321122331312213312332222231212123131111313133233332211211213221112313313233113332231211213332211311322212211112311212223212311221323112121223131222232222221312331222213132312312113112132121312111232233221223322312233113233222121221223311233223113323131223111231131213311223231232111311113113112122231231212311133332113321223113133232321332312112111112122311111213212223222222313133123233223121122133331312121323131323323233312132133112133333321131221113323213133121311212132231112221331213333231333211232311223122322322111233231113322111113231232233331322312322123311111313223232333112331331133332322331213212212323333323131233132213232222123222122131232233132221132232121131233222313223213235144122144242111244514333233233112213223322121311222223332132131113331223231221232332311333112321233233213321311322221313232233221323112113333333333332133321312223313323133132231112333221221311231321231323231332333322221321122133322323223112221321121312112222122312222111231313212132212121121123332222211133221113313133213312113223331212121122133313322111123313131133121123331321112331332322123332132121131211213231211223111332332233113111323131212211133231233111323232231121332221313321123321112232322212212323112121211332221222123322111121311321221221112232211111121333331311311332123321121222133113212221221132131121121131322231321133332222321311232131121231312311333123113131332132112232122333323133213131313212122223121321212312123121231112323123331221211213333121132312322133111131133223221311212123323333121111211122222331323313312112132323321322331121223231321222212311222311332232213221133233233112332123321111333122212123122331223112313313331312311133111123331231121111212133312221111211321212231112313

■参照サイト
AtCoder Grand Contest 055

2021年11月3日2021年11月3日

C++ の動作確認をしてみた（５７１）

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題C (Gacha) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, AC版に到達出来た.
2. 個人的には, 戻りが発生する箇所の考え方など, 大変勉強になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト京都大学プログラミングコンテスト 2021 解説の各リンクをご覧下さい.

■C++版プログラム(問題C／AC版).

// 解き直し.
// https://atcoder.jp/contests/kupc2021/editorial/2862
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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 a first
#define b second
LL a[202020], b[202020];
int aCum[202020], bCum[202020], diff[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<LL, int> im;
    im[0] = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        im[a[i]] = 0;
    }
    rep(i, N){
        scanf("%lld", &b[i]);
        im[b[i]] = 0;
    }
    
    // 2. 番号付け.
    map<int, LL> om;
    int idx = -1;
    for(auto &p : im) p.b = ++idx, om[idx] = p.a;
    
    // 3. 累積和.
    rep(i, N){
        aCum[im[a[i]]]++;
        bCum[im[b[i]]]++;
    }
    rep(i, 202020 - 1){
        // ガチャ.
        aCum[i + 1] += aCum[i];
        
        // コイン.
        bCum[i + 1] += bCum[i];
        
        // コイン - ガチャ.
        diff[i + 1] = bCum[i + 1] - aCum[i + 1];
    }
    
    // 4. 全探索.
    LL ans = 202020202020202020, l = 0, r = 0, o = 0;
    bool isPlus = true;
    rep(f, idx + 1){
        // 最終地点が, f の 場合.
        l = om[f] - om[0];
        r = (om[idx] - om[f]) * 2;
        
        // 符号がマイナスの場合は, 戻りが発生する.
        if(!isPlus) o += (om[f] - om[f - 1]) * 2;
        
        // 符号チェック.
        isPlus = (diff[f] < 0) ? false : true;
        
        // 最小値更新.
        ans = min(ans, l + r + o);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/kupc2021/editorial/2862

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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 a first

#define b second

LL a[202020], b[202020];

int aCum[202020], bCum[202020], diff[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<LL, int> im;

im[0] = 0;

rep(i, N){

scanf("%lld", &a[i]);

im[a[i]] = 0;

}

rep(i, N){

scanf("%lld", &b[i]);

im[b[i]] = 0;

}

// 2. 番号付け.

map<int, LL> om;

int idx = -1;

for(auto &p : im) p.b = ++idx, om[idx] = p.a;

// 3. 累積和.

rep(i, N){

aCum[im[a[i]]]++;

bCum[im[b[i]]]++;

}

rep(i, 202020 - 1){

// ガチャ.

aCum[i + 1] += aCum[i];

// コイン.

bCum[i + 1] += bCum[i];

// コイン - ガチャ.

diff[i + 1] = bCum[i + 1] - aCum[i + 1];

}

// 4. 全探索.

LL ans = 202020202020202020, l = 0, r = 0, o = 0;

bool isPlus = true;

rep(f, idx + 1){

// 最終地点が, f の場合.

l = om[f] - om[0];

r = (om[idx] - om[f]) * 2;

// 符号がマイナスの場合は, 戻りが発生する.

if(!isPlus) o += (om[f] - om[f - 1]) * 2;

// 符号チェック.

isPlus = (diff[f] < 0) ? false : true;

// 最小値更新.

ans = min(ans, l + r + o);

}

// 5. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
4
1 6 7 12
3 5 10 11

[出力例]
21
※AtCoderテストケースより

[入力例]
2
1 2
1 1000000000

[出力例]
1999999998
※AtCoderテストケースより

[入力例]
5
2 8 9 10 13
3 5 6 12 15

[出力例]
22

※実際, 以下の行動で, 移動距離 22 となる.
座標  3 (コイン)
座標  2 (ガチャ)
座標  5 (コイン)
座標  6 (コイン)
座標  8 (ガチャ)
座標  9 (ガチャ)
座標 12 (コイン)
座標 13 (ガチャ)
座標 15 (コイン)
座標 10 (ガチャ)
-> 3 + (3 - 2) * 2 + (10 - 3) + (15 - 10) * 2 = 22

[入力例]
8
1 6 23 50 55 63 83 100
11 15 31 35 72 88 93 97

[出力例]
189

※実際, 以下の行動で, 移動距離 189 となる.
座標  11 (コイン)
座標  15 (コイン)
座標   6 (ガチャ)
座標   1 (ガチャ)
座標  31 (コイン)
座標  23 (ガチャ)
座標  35 (コイン)
座標  50 (ガチャ)
座標  72 (コイン)
座標  88 (コイン)
座標  93 (コイン)
座標  97 (コイン)
座標 100 (ガチャ)
座標  83 (ガチャ)
座標  63 (ガチャ)
座標  55 (ガチャ)
-> 1 + (15 - 1) * 2 + (31 - 1) + (31 - 23) * 2 + (55 - 31) + (100 - 55) * 2 = 189

[入力例]
15
3 8 14 32 34 35 51 57 73 80 83 88 95 98 100
10 18 23 25 27 28 40 44 59 64 68 82 107 111 118

[出力例]
181

※実際, 以下の行動で, 移動距離 181 となる.
座標  10 (コイン)
座標  18 (コイン)
座標  23 (コイン)
座標  14 (ガチャ)
座標   8 (ガチャ)
座標   3 (ガチャ)
座標  25 (コイン)
座標  27 (コイン)
座標  28 (コイン)
座標  32 (ガチャ)
座標  34 (ガチャ)
座標  35 (ガチャ)
座標  40 (コイン)
座標  44 (コイン)
座標  51 (ガチャ)
座標  57 (ガチャ)
座標  59 (コイン)
座標  64 (コイン)
座標  68 (コイン)
座標  73 (ガチャ)
座標  80 (ガチャ)
座標  82 (コイン)
座標  83 (ガチャ)
座標  88 (ガチャ)
座標 107 (コイン)
座標 111 (コイン)
座標 118 (コイン)
座標 100 (ガチャ)
座標  98 (ガチャ)
座標  95 (ガチャ)
-> 23 + (23 - 3) * 2 + (95 - 23) + (118 - 95) * 2 = 181

[入力例]
10
688454010 695372079 700190565 739169216 787159174 793136394 796656444 814339966 822191962 869694568
663823866 681857178 702347983 719953098 721150465 757252320 774871450 831521457 849407523 880851457

[出力例]
951677784

※実際, 以下の行動で, 移動距離 951677784 となる.
座標 663823866 (コイン)
座標 681857178 (コイン)
座標 688454010 (ガチャ)
座標 695372079 (ガチャ)
座標 702347983 (コイン)
座標 700190565 (ガチャ)
座標 719953098 (コイン)
座標 721150465 (コイン)
座標 739169216 (ガチャ)
座標 757252320 (コイン)
座標 774871450 (コイン)
座標 787159174 (ガチャ)
座標 793136394 (ガチャ)
座標 796656444 (ガチャ)
座標 831521457 (コイン)
座標 849407523 (コイン)
座標 880851457 (コイン)
座標 869694568 (ガチャ)
座標 822191962 (ガチャ)
座標 814339966 (ガチャ)
-> 702347983 + (702347983 - 700190565) * 2 + (814339966 - 702347983) + (880851457 - 814339966) * 2 = 951677784

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

[入力例]

1 6 7 12

3 5 10 11

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 1000000000

[出力例]

1999999998

※AtCoderテストケースより

[入力例]

2 8 9 10 13

3 5 6 12 15

[出力例]

※実際, 以下の行動で, 移動距離 22 となる.

座標 3 (コイン)

座標 2 (ガチャ)

座標 5 (コイン)

座標 6 (コイン)

座標 8 (ガチャ)

座標 9 (ガチャ)

座標 12 (コイン)

座標 13 (ガチャ)

座標 15 (コイン)

座標 10 (ガチャ)

-> 3 + (3 - 2) * 2 + (10 - 3) + (15 - 10) * 2 = 22

[入力例]

1 6 23 50 55 63 83 100

11 15 31 35 72 88 93 97

[出力例]

189

※実際, 以下の行動で, 移動距離 189 となる.

座標 11 (コイン)

座標 15 (コイン)

座標 6 (ガチャ)

座標 1 (ガチャ)

座標 31 (コイン)

座標 23 (ガチャ)

座標 35 (コイン)

座標 50 (ガチャ)

座標 72 (コイン)

座標 88 (コイン)

座標 93 (コイン)

座標 97 (コイン)

座標 100 (ガチャ)

座標 83 (ガチャ)

座標 63 (ガチャ)

座標 55 (ガチャ)

-> 1 + (15 - 1) * 2 + (31 - 1) + (31 - 23) * 2 + (55 - 31) + (100 - 55) * 2 = 189

[入力例]

3 8 14 32 34 35 51 57 73 80 83 88 95 98 100

10 18 23 25 27 28 40 44 59 64 68 82 107 111 118

[出力例]

181

※実際, 以下の行動で, 移動距離 181 となる.

座標 10 (コイン)

座標 18 (コイン)

座標 23 (コイン)

座標 14 (ガチャ)

座標 8 (ガチャ)

座標 3 (ガチャ)

座標 25 (コイン)

座標 27 (コイン)

座標 28 (コイン)

座標 32 (ガチャ)

座標 34 (ガチャ)

座標 35 (ガチャ)

座標 40 (コイン)

座標 44 (コイン)

座標 51 (ガチャ)

座標 57 (ガチャ)

座標 59 (コイン)

座標 64 (コイン)

座標 68 (コイン)

座標 73 (ガチャ)

座標 80 (ガチャ)

座標 82 (コイン)

座標 83 (ガチャ)

座標 88 (ガチャ)

座標 107 (コイン)

座標 111 (コイン)

座標 118 (コイン)

座標 100 (ガチャ)

座標 98 (ガチャ)

座標 95 (ガチャ)

-> 23 + (23 - 3) * 2 + (95 - 23) + (118 - 95) * 2 = 181

[入力例]

688454010 695372079 700190565 739169216 787159174 793136394 796656444 814339966 822191962 869694568

663823866 681857178 702347983 719953098 721150465 757252320 774871450 831521457 849407523 880851457

[出力例]

951677784

※実際, 以下の行動で, 移動距離 951677784 となる.

座標 663823866 (コイン)

座標 681857178 (コイン)

座標 688454010 (ガチャ)

座標 695372079 (ガチャ)

座標 702347983 (コイン)

座標 700190565 (ガチャ)

座標 719953098 (コイン)

座標 721150465 (コイン)

座標 739169216 (ガチャ)

座標 757252320 (コイン)

座標 774871450 (コイン)

座標 787159174 (ガチャ)

座標 793136394 (ガチャ)

座標 796656444 (ガチャ)

座標 831521457 (コイン)

座標 849407523 (コイン)

座標 880851457 (コイン)

座標 869694568 (ガチャ)

座標 822191962 (ガチャ)

座標 814339966 (ガチャ)

-> 702347983 + (702347983 - 700190565) * 2 + (814339966 - 702347983) + (880851457 - 814339966) * 2 = 951677784

■参照サイト
京都大学プログラミングコンテスト 2021

2021年11月1日

C++ の動作確認をしてみた（５７０）

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題F (Problem where +s Separate Digits) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 確率, 期待値の考え方で, 解いていく方針が, 不思議な印象を受けたとともに, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 224 解説の各リンクをご覧下さい.

■C++版プログラム(問題F／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2805
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
const LL MOD = 998244353;
LL mPowP2[202020], mPowM2[202020], mPow10[202020], mCum[202020];

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string s(c);
    int N = s.size();
    
    // 2. 例外.
    if(N == 1){
        printf("%s\n", s.c_str());
        return 0;
    }
    
    // 3. 2, 10 の 冪乗.
    mPowP2[0] = mPowM2[0] = mPow10[0] = 1;
    rep(i, N + 1){
        mPowP2[i + 1] = (2 * mPowP2[i]) % MOD;
        mPowM2[i + 1] = (499122177 * mPowM2[i]) % MOD;
        mPow10[i + 1] = (10 * mPow10[i]) % MOD;
    }
    
    // 4. 累積和.
    // ex.
    // k = 1 -> 0 +                                                  (+     1 * 1 /  1)
    // k = 2 -> 1 * 1 / 2                                            (+    10 * 1 /  2)
    // k = 3 -> 1 * 1 / 2 + 10 * 1 / 4                               (+   100 * 1 /  4)
    // k = 4 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8                 (+  1000 * 1 /  8)
    // k = 5 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 + 1000 * 1 / 16 (+ 10000 * 1 / 16)
    // ...
    // -> 例外部分は, 後述の集計時に考慮すれば十分のはず.
    repx(i, 2, N + 1){
        mCum[i] += mCum[i - 1];
        mCum[i] %= MOD;
        mCum[i] += mPowM2[i - 1] * mPow10[i - 2];
        mCum[i] %= MOD;
    }
    
    // 5. 文字列 S の 各文字について, 集計.
    // -> 文字列 S の 右から k文字目 を x と 見て計算.
    LL ans = 0;
    repx(k, 1, N + 1){
        // 等比数列の和.
        int i = N - k;
        LL x = (LL)(s[i] - '0');
        ans += x * mCum[k];
        ans %= MOD;
        
        // 例外.
        ans += x * mPowM2[k - 1] * mPow10[k - 1];
        ans %= MOD;
    }
    
    // 6. 2 の |S| - 1 乗 を 乗ずる.
    ans *= mPowP2[N - 1];
    ans %= MOD;
    
    // 7. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2805

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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--)

const LL MOD = 998244353;

LL mPowP2[202020], mPowM2[202020], mPow10[202020], mCum[202020];

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string s(c);

int N = s.size();

// 2. 例外.

if(N == 1){

printf("%s\n", s.c_str());

return 0;

}

// 3. 2, 10 の冪乗.

mPowP2[0] = mPowM2[0] = mPow10[0] = 1;

rep(i, N + 1){

mPowP2[i + 1] = (2 * mPowP2[i]) % MOD;

mPowM2[i + 1] = (499122177 * mPowM2[i]) % MOD;

mPow10[i + 1] = (10 * mPow10[i]) % MOD;

}

// 4. 累積和.

// ex.

// k = 1 -> 0 + (+ 1 * 1 / 1)

// k = 2 -> 1 * 1 / 2 (+ 10 * 1 / 2)

// k = 3 -> 1 * 1 / 2 + 10 * 1 / 4 (+ 100 * 1 / 4)

// k = 4 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 (+ 1000 * 1 / 8)

// k = 5 -> 1 * 1 / 2 + 10 * 1 / 4 + 100 * 1 / 8 + 1000 * 1 / 16 (+ 10000 * 1 / 16)

// ...

// -> 例外部分は, 後述の集計時に考慮すれば十分のはず.

repx(i, 2, N + 1){

mCum[i] += mCum[i - 1];

mCum[i] %= MOD;

mCum[i] += mPowM2[i - 1] * mPow10[i - 2];

mCum[i] %= MOD;

}

// 5. 文字列 S の各文字について, 集計.

// -> 文字列 S の右から k文字目を x と見て計算.

LL ans = 0;

repx(k, 1, N + 1){

// 等比数列の和.

int i = N - k;

LL x = (LL)(s[i] - '0');

ans += x * mCum[k];

ans %= MOD;

// 例外.

ans += x * mPowM2[k - 1] * mPow10[k - 1];

ans %= MOD;

}

// 6. 2 の |S| - 1 乗を乗ずる.

ans *= mPowP2[N - 1];

ans %= MOD;

// 7. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
1234

[出力例]
1736
※AtCoderテストケースより

[入力例]
1

[出力例]
1
※AtCoderテストケースより

[入力例]
31415926535897932384626433832795

[出力例]
85607943
※AtCoderテストケースより

[入力例]
11

[出力例]
13

[入力例]
111

[出力例]
138

[入力例]
2021

[出力例]
2344

[入力例]
20211101

[出力例]
23511616

[入力例]
2236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274

[出力例]
83041925

[入力例]

1234

[出力例]

1736

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

31415926535897932384626433832795

[出力例]

85607943

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

111

[出力例]

138

[入力例]

2021

[出力例]

2344

[入力例]

20211101

[出力例]

23511616

[入力例]

2236067977499789696409173668731276235440618359611525724270897245410520925637804899414414408378782274

[出力例]

83041925

■参照サイト
AtCoder Beginner Contest 224

2021年10月31日2021年10月31日

C++ の動作確認をしてみた（５６９）

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題B (Painting with Many Orders) を解いてみた.

■感想.
1. 問題B は, 規則性を抽出できたので, AC版に到達できたと思う.
2. 個人的には, すべての黒いマスが, 少なくとも１つの白いマスに隣接しているという条件が含まれることで, より問題が, 面白くなっている印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト京都大学プログラミングコンテスト 2021 解説の各リンクをご覧下さい.

■C++版プログラム(問題B／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#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--)
char ans[505][505];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 初期化.
    rep(i, 505) rep(j, 505) ans[i][j] = '.';
    
    // 3. 編集.
    // ex.
    // N = 8
    // #######.
    // ........
    // #.#.#.#.
    // #...#.#.
    // #.###.#.
    // #.....#.
    // #.#####.
    // #.......
    // -> 上記のような出力を実現したい.
    // 3-1. 1行目, 1列目.
    rep(j, N - 1) ans[0][j] = '#';
    repx(i, 2, N) ans[i][0] = '#';
    
    // 3-2. 矩形範囲.
    // -> N = 8 ならば, 8 - 3 = 5 なので, 1, 3, 5 を 見る.
    if(N - 3 > 0){
        int n = N - 3;
        repex(a, 2 - (n % 2), N - 2, 2){
            // 行方向.
            repr(j, a + 1, 2) ans[a + 1][j] = '#';
            
            // 列方向.
            repr(i, a + 1, 2) ans[i][a + 1] = '#';
        }
    }
    
    // 4. 出力.
    rep(i, N){
        rep(j, N) printf("%c", ans[i][j]);
        puts("");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

#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--)

char ans[505][505];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 初期化.

rep(i, 505) rep(j, 505) ans[i][j] = '.';

// 3. 編集.

// ex.

// N = 8

// #######.

// ........

// #.#.#.#.

// #...#.#.

// #.###.#.

// #.....#.

// #.#####.

// #.......

// -> 上記のような出力を実現したい.

// 3-1. 1行目, 1列目.

rep(j, N - 1) ans[0][j] = '#';

repx(i, 2, N) ans[i][0] = '#';

// 3-2. 矩形範囲.

// -> N = 8 ならば, 8 - 3 = 5 なので, 1, 3, 5 を見る.

if(N - 3 > 0){

int n = N - 3;

repex(a, 2 - (n % 2), N - 2, 2){

// 行方向.

repr(j, a + 1, 2) ans[a + 1][j] = '#';

// 列方向.

repr(i, a + 1, 2) ans[i][a + 1] = '#';

}

// 4. 出力.

rep(i, N){

rep(j, N) printf("%c", ans[i][j]);

puts("");

}

return 0;

}

[入力例]
3

[出力例]
..#
#.#
...
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
##.
...
#..

[入力例]
2

[出力例]
#.
..

[入力例]
4

[出力例]
###.
....
#.#.
#...

[入力例]
5

[出力例]
####.
.....
#..#.
#.##.
#....

[入力例]
6

[出力例]
#####.
......
#.#.#.
#...#.
#.###.
#.....

[入力例]
7

[出力例]
######.
.......
#..#.#.
#.##.#.
#....#.
#.####.
#......

[入力例]
8

[出力例]
#######.
........
#.#.#.#.
#...#.#.
#.###.#.
#.....#.
#.#####.
#.......

[入力例]
10

[出力例]
#########.
..........
#.#.#.#.#.
#...#.#.#.
#.###.#.#.
#.....#.#.
#.#####.#.
#.......#.
#.#######.
#.........

[入力例]

[出力例]

..#

#.#

...

※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.

##.

...

#..

[入力例]

[出力例]

[入力例]

[出力例]

###.

....

#.#.

#...

[入力例]

[出力例]

####.

.....

#..#.

#.##.

#....

[入力例]

[出力例]

#####.

......

#.#.#.

#...#.

#.###.

#.....

[入力例]

[出力例]

######.

.......

#..#.#.

#.##.#.

#....#.

#.####.

#......

[入力例]

[出力例]

#######.

........

#.#.#.#.

#...#.#.

#.###.#.

#.....#.

#.#####.

#.......

[入力例]

[出力例]

#########.

..........

#.#.#.#.#.

#...#.#.#.

#.###.#.#.

#.....#.#.

#.#####.#.

#.......#.

#.#######.

#.........

■参照サイト
京都大学プログラミングコンテスト 2021

2021年10月31日

C++ の動作確認をしてみた（５６８）

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題E (Integers on Grid) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 224 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2814
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using T3 = tuple<int, int, int>;
using T4 = tuple<int, int, int, 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 all(x) x.begin(), x.end()
#define a first
#define b second
int dp[202020], rMax[202020], cMax[202020];

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    vector<T4> t;
    map<int, int> m;
    rep(i, N){
        int r, c, a;
        scanf("%d %d %d", &r, &c, &a);
        t.emplace_back(a, r, c, i);
        m[a] = 0;
    }
    
    // 2. sort.
    sort(all(t));
    
    // 3. マスに記載された整数 X の並び替え.
    int idx = -1;
    for(auto &p : m) p.b = ++idx;
    
    // 4. 整数 X ごとに分類.
    vector<vector<T3>> u(idx + 1);
    for(auto &p : t){
        int a = get<0>(p);
        int r = get<1>(p);
        int c = get<2>(p);
        int j = get<3>(p);
        u[m[a]].emplace_back(r, c, j);
    }
    
    // 5. dp更新.
    repr(i, idx, 0){
        // dp更新.
        for(auto &p : u[i]){
            int r = get<0>(p);
            int c = get<1>(p);
            int j = get<2>(p);
            dp[j] = max(rMax[r], cMax[c]);
        }
        
        // rMax, cMax更新.
        for(auto &p : u[i]){
            int r = get<0>(p);
            int c = get<1>(p);
            int j = get<2>(p);
            rMax[r] = max(rMax[r], dp[j] + 1);
            cMax[c] = max(cMax[c], dp[j] + 1);
        }
    }
    
    // 6. 出力.
    rep(i, N) printf("%d\n", dp[i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2814

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using T3 = tuple<int, int, int>;

using T4 = tuple<int, int, int, 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 all(x) x.begin(), x.end()

#define a first

#define b second

int dp[202020], rMax[202020], cMax[202020];

int main(){

// 1. 入力情報.

int H, W, N;

scanf("%d %d %d", &H, &W, &N);

vector<T4> t;

map<int, int> m;

rep(i, N){

int r, c, a;

scanf("%d %d %d", &r, &c, &a);

t.emplace_back(a, r, c, i);

m[a] = 0;

}

// 2. sort.

sort(all(t));

// 3. マスに記載された整数 X の並び替え.

int idx = -1;

for(auto &p : m) p.b = ++idx;

// 4. 整数 X ごとに分類.

vector<vector<T3>> u(idx + 1);

for(auto &p : t){

int a = get<0>(p);

int r = get<1>(p);

int c = get<2>(p);

int j = get<3>(p);

u[m[a]].emplace_back(r, c, j);

}

// 5. dp更新.

repr(i, idx, 0){

// dp更新.

for(auto &p : u[i]){

int r = get<0>(p);

int c = get<1>(p);

int j = get<2>(p);

dp[j] = max(rMax[r], cMax[c]);

}

// rMax, cMax更新.

for(auto &p : u[i]){

int r = get<0>(p);

int c = get<1>(p);

int j = get<2>(p);

rMax[r] = max(rMax[r], dp[j] + 1);

cMax[c] = max(cMax[c], dp[j] + 1);

}

// 6. 出力.

rep(i, N) printf("%d\n", dp[i]);

return 0;

}

[入力例]
3 3 7
1 1 4
1 2 7
2 1 3
2 3 5
3 1 2
3 2 5
3 3 5

[出力例]
1
0
2
0
3
1
0
※AtCoderテストケースより

[入力例]
5 7 20
2 7 8
2 6 4
4 1 9
1 5 4
2 2 7
5 5 2
1 7 2
4 6 6
1 4 1
2 1 10
5 6 9
5 3 3
3 7 9
3 6 3
4 3 4
3 3 10
4 2 1
3 5 4
1 2 6
4 7 9

[出力例]
2
4
1
5
3
6
6
2
7
0
0
4
1
5
3
0
5
2
4
0
※AtCoderテストケースより

[入力例]
5 6 18
1 1 3
1 5 7
2 1 1
2 2 4
2 4 6
2 5 6
2 6 8
3 1 2
3 2 3
3 3 5
3 4 5
3 5 5
3 6 7
4 2 2
4 3 4
4 4 4
4 6 6
5 3 3

[出力例]
1
0
5
2
1
1
0
4
3
2
2
2
1
4
3
3
2
4

[入力例]
10 8 30
2 1 9
3 1 10
4 1 9
5 1 6
6 1 5
7 1 2
8 1 1
3 2 9
4 2 8
5 2 7
6 2 4
7 2 3
3 3 8
4 3 7
6 3 5
3 4 9
4 4 11
3 5 10
3 6 8
4 6 9
5 6 10
6 6 11
7 6 12
3 7 7
4 7 6
5 7 5
5 8 4
6 8 3
7 8 2
8 8 1

[出力例]
1
0
1
6
7
10
11
1
4
5
8
9
2
5
6
1
0
0
4
3
2
1
0
5
6
7
8
9
10
11

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

[入力例]

3 3 7

1 1 4

1 2 7

2 1 3

2 3 5

3 1 2

3 2 5

3 3 5

[出力例]

※AtCoderテストケースより

[入力例]

5 7 20

2 7 8

2 6 4

4 1 9

1 5 4

2 2 7

5 5 2

1 7 2

4 6 6

1 4 1

2 1 10

5 6 9

5 3 3

3 7 9

3 6 3

4 3 4

3 3 10

4 2 1

3 5 4

1 2 6

4 7 9

[出力例]

※AtCoderテストケースより

[入力例]

5 6 18

1 1 3

1 5 7

2 1 1

2 2 4

2 4 6

2 5 6

2 6 8

3 1 2

3 2 3

3 3 5

3 4 5

3 5 5

3 6 7

4 2 2

4 3 4

4 4 4

4 6 6

5 3 3

[出力例]

[入力例]

10 8 30

2 1 9

3 1 10

4 1 9

5 1 6

6 1 5

7 1 2

8 1 1

3 2 9

4 2 8

5 2 7

6 2 4

7 2 3

3 3 8

4 3 7

6 3 5

3 4 9

4 4 11

3 5 10

3 6 8

4 6 9

5 6 10

6 6 11

7 6 12

3 7 7

4 7 6

5 7 5

5 8 4

6 8 3

7 8 2

8 8 1

[出力例]

■参照サイト
AtCoder Beginner Contest 224

2021年10月30日2021年10月30日

C++ の動作確認をしてみた（５６７）

C++の練習を兼ねて, AtCoder Beginner Contest 222 の問題E (Red and Blue Tree) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 222 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc222/editorial/2751
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, 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
const LL MOD = 998244353;
int a[101], c[1010];
LL dp[1010][101010];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    rep(i, M){
        scanf("%d", &a[i]);
        a[i]--;
    }
    vvi G(N);
    map<P, int> E;
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        G[u].pb(v);
        G[v].pb(u);
        
        // 辺 i は, (u[i], v[i]) or (v[i], u[i]) と 読み替え.
        E[{u, v}] = i;
        E[{v, u}] = i;
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                // 未訪問の頂点を処理.
                if(d[e])   continue;
                if(e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    
    // 3. 最短経路.
    auto f = [&](vvi &G, int g, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 g をキュー q に追加.
        q.push(g);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]){
                if(d[e] == d[u] - 1){
                    // 距離が 1 小さい頂点を追加.
                    q.push(e);
                    
                    // 最短経路を構成する辺とみて, カウントアップ.
                    c[E[{e, u}]]++;
                }
            }
        }
        return;
    };
    
    // 4. 各辺を通過する数を計算.
    rep(i, M - 1){
        // 辺情報.
        int s = a[i];
        int g = a[i + 1];
        
        // 最短距離.
        int d[1010];
        rep(j, 1010) d[j] = 0;
        bfs(G, s, d);
        // puts("\n----- bfs start -----");
        // rep(j, N) printf("%d ", d[j]);
        // puts("\n----- bfs end -----");
        
        // 最短経路.
        f(G, g, d);
        // puts("----- shortest path start -----");
        // rep(j, N - 1) printf("%d ", c[j]);
        // puts("\n----- shortest path end -----");
    }
    
    // 5. 例外チェック.
    // -> (K + S) / 2 が 整数でない, 0未満.
    int S = 0;
    rep(i, N - 1) S += c[i];
    int x = (K + S) / 2;
    // printf("S=%d K=%d x=%d\n", S, K, x);
    if(x * 2 != K + S || x < 0){
        puts("0");
        return 0;
    }
    
    // 6. dp更新.
    rep(i, 1010) dp[i][0] = 1;
    rep(i, N - 1){
        // 前回分反映.
        if(i) rep(j, 101010) dp[i][j] = dp[i - 1][j];
        
        // 今回分反映.
        repr(j, 101009, 0){
            int at = j + c[i];
            if(at <= 101009){
                if(dp[i][j]){
                    dp[i][at] += dp[i][j];
                    dp[i][at] %= MOD;
                }
            }
        }
    }
    // rep(i, N - 1){
    //     rep(j, 10) printf("%lld ", dp[i][j]);
    //     puts("");
    // }
    
    // 7. 出力.
    printf("%lld\n", dp[N - 2][x]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 解き直し.

// https://atcoder.jp/contests/abc222/editorial/2751

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, 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

const LL MOD = 998244353;

int a[101], c[1010];

LL dp[1010][101010];

int main(){

// 1. 入力情報.

int N, M, K;

scanf("%d %d %d", &N, &M, &K);

rep(i, M){

scanf("%d", &a[i]);

a[i]--;

}

vvi G(N);

map<P, int> E;

rep(i, N - 1){

int u, v;

scanf("%d %d", &u, &v);

u--;

v--;

G[u].pb(v);

G[v].pb(u);

// 辺 i は, (u[i], v[i]) or (v[i], u[i]) と読み替え.

E[{u, v}] = i;

E[{v, u}] = i;

}

// 2. bfs.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](vvi &G, int s, int* d){

// 空のキュー.

queue<int> q;

// 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &e : G[u]){

// 未訪問の頂点を処理.

if(d[e]) continue;

if(e != s) d[e] = d[u] + 1, q.push(e);

}

return;

};

// 3. 最短経路.

auto f = [&](vvi &G, int g, int* d){

// 空のキュー.

queue<int> q;

// 探索地点 g をキュー q に追加.

q.push(g);

while(!q.empty()){

// キューから取り出す.

int u = q.front();

q.pop();

// 隣接頂点をチェック.

for(auto &e : G[u]){

if(d[e] == d[u] - 1){

// 距離が 1 小さい頂点を追加.

q.push(e);

// 最短経路を構成する辺とみて, カウントアップ.

c[E[{e, u}]]++;

}

return;

};

// 4. 各辺を通過する数を計算.

rep(i, M - 1){

// 辺情報.

int s = a[i];

int g = a[i + 1];

// 最短距離.

int d[1010];

rep(j, 1010) d[j] = 0;

bfs(G, s, d);

// puts("\n----- bfs start -----");

// rep(j, N) printf("%d ", d[j]);

// puts("\n----- bfs end -----");

// 最短経路.

f(G, g, d);

// puts("----- shortest path start -----");

// rep(j, N - 1) printf("%d ", c[j]);

// puts("\n----- shortest path end -----");

}

// 5. 例外チェック.

// -> (K + S) / 2 が整数でない, 0未満.

int S = 0;

rep(i, N - 1) S += c[i];

int x = (K + S) / 2;

// printf("S=%d K=%d x=%d\n", S, K, x);

if(x * 2 != K + S || x < 0){

puts("0");

return 0;

}

// 6. dp更新.

rep(i, 1010) dp[i][0] = 1;

rep(i, N - 1){

// 前回分反映.

if(i) rep(j, 101010) dp[i][j] = dp[i - 1][j];

// 今回分反映.

repr(j, 101009, 0){

int at = j + c[i];

if(at <= 101009){

if(dp[i][j]){

dp[i][at] += dp[i][j];

dp[i][at] %= MOD;

}

// rep(i, N - 1){

// rep(j, 10) printf("%lld ", dp[i][j]);

// puts("");

// }

// 7. 出力.

printf("%lld\n", dp[N - 2][x]);

return 0;

}

[入力例]
4 5 0
2 3 2 1 4
1 2
2 3
3 4

[出力例]
2
※AtCoderテストケースより

[入力例]
3 10 10000
1 2 1 2 1 2 2 1 1 2
1 2
1 3

[出力例]
0
※AtCoderテストケースより

[入力例]
10 2 -1
1 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

[出力例]
126
※AtCoderテストケースより

[入力例]
5 8 -1
1 4 1 4 2 1 3 5
1 2
4 1
3 1
1 5

[出力例]
2
※AtCoderテストケースより

[入力例]
2 2 1
2 1
1 2

[出力例]
1

[入力例]
7 7 3
2 1 6 4 5 7 3
2 1
2 3
1 7
1 5
3 6
4 3

[出力例]
8

[入力例]
13 36 2
2 10 11 3 6 7 13 4 12 7 5 12 8 6 11 10 9 11 5 13 4 3 12 6 6 2 1 11 10 4 4 13 7 3 7 2
2 1
2 7
2 3
2 8
8 9
10 8
10 11
10 6
3 4
5 3
5 13
5 12

[出力例]
226

[入力例]
21 77 6
18 9 4 6 8 18 9 9 15 7 4 19 15 19 7 20 9 7 1 16 14 6 13 10 14 16 5 1 7 7 15 18 18 10 15 5 2 19 1 1 9 7 9 16 18 5 8 17 18 12 1 3 18 20 10 9 9 18 16 14 8 15 12 15 6 11 5 2 2 12 14 1 19 12 21 13 10
7 1
4 1
6 1
2 3
2 5
2 7
7 8
11 10
12 10
9 10
9 8
9 16
16 17
18 17
8 13
13 15
13 14
8 19
19 20
19 21

[出力例]
12318

[入力例]
30 100 -8
4 8 16 20 19 2 28 29 12 14 22 13 9 29 24 17 24 1 17 19 19 2 20 10 2 25 9 21 5 4 11 27 20 6 28 24 6 29 27 22 16 8 23 5 21 27 5 1 29 26 30 11 10 20 4 20 28 22 19 19 8 6 14 1 5 5 14 25 4 29 3 29 19 21 24 30 8 24 7 28 3 21 18 4 6 5 17 2 15 29 12 5 29 13 18 7 22 3 23 2
1 5
2 1
15 1
14 1
4 1
3 1
3 13
3 12
12 22
12 23
16 15
17 15
16 27
16 26
26 29
26 28
2 30
2 6
2 7
7 24
25 7
5 8
9 5
18 14
14 19
4 10
4 11
20 11
21 11

[出力例]
5324136

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

[入力例]

4 5 0

2 3 2 1 4

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 10 10000

1 2 1 2 1 2 2 1 1 2

1 2

1 3

[出力例]

※AtCoderテストケースより

[入力例]

10 2 -1

1 10

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

[出力例]

126

※AtCoderテストケースより

[入力例]

5 8 -1

1 4 1 4 2 1 3 5

1 2

4 1

3 1

1 5

[出力例]

※AtCoderテストケースより

[入力例]

2 2 1

2 1

1 2

[出力例]

[入力例]

7 7 3

2 1 6 4 5 7 3

2 1

2 3

1 7

1 5

3 6

4 3

[出力例]

[入力例]

13 36 2

2 10 11 3 6 7 13 4 12 7 5 12 8 6 11 10 9 11 5 13 4 3 12 6 6 2 1 11 10 4 4 13 7 3 7 2

2 1

2 7

2 3

2 8

8 9

10 8

10 11

10 6

3 4

5 3

5 13

5 12

[出力例]

226

[入力例]

21 77 6

18 9 4 6 8 18 9 9 15 7 4 19 15 19 7 20 9 7 1 16 14 6 13 10 14 16 5 1 7 7 15 18 18 10 15 5 2 19 1 1 9 7 9 16 18 5 8 17 18 12 1 3 18 20 10 9 9 18 16 14 8 15 12 15 6 11 5 2 2 12 14 1 19 12 21 13 10

7 1

4 1

6 1

2 3

2 5

2 7

7 8

11 10

12 10

9 10

9 8

9 16

16 17

18 17

8 13

13 15

13 14

8 19

19 20

19 21

[出力例]

12318

[入力例]

30 100 -8

4 8 16 20 19 2 28 29 12 14 22 13 9 29 24 17 24 1 17 19 19 2 20 10 2 25 9 21 5 4 11 27 20 6 28 24 6 29 27 22 16 8 23 5 21 27 5 1 29 26 30 11 10 20 4 20 28 22 19 19 8 6 14 1 5 5 14 25 4 29 3 29 19 21 24 30 8 24 7 28 3 21 18 4 6 5 17 2 15 29 12 5 29 13 18 7 22 3 23 2

1 5

2 1

15 1

14 1

4 1

3 1

3 13

3 12

12 22

12 23

16 15

17 15

16 27

16 26

26 29

26 28

2 30

2 6

2 7

7 24

25 7

5 8

9 5

18 14

14 19

4 10

4 11

20 11

21 11

[出力例]

5324136

■参照サイト
エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）

2021年10月28日2021年10月28日

C++ の動作確認をしてみた（５６６）

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題C (Triangle?) ～問題D (8 Puzzle on Graph) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索(応用版, 連想配列の利用)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 224 解説の各リンクをご覧下さい.

■C++版プログラム(問題C／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
LL x[303], y[303];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. 三角形の面積が正となるものは？
    int ans = 0;
    rep(i, N){
        repx(j, i + 1, N){
            repx(k, j + 1, N){
                // 点(x[i], y[i]) を 基準として考える.
                LL dx1 = x[j] - x[i], dy1 = y[j] - y[i];
                LL dx2 = x[k] - x[i], dy2 = y[k] - y[i];
                
                // 三角形の面積の二倍.
                LL s = abs(dx1 * dy2 - dy1 * dx2);
                
                // カウント.
                if(s) ans++;
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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--)

LL x[303], y[303];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld %lld", &x[i], &y[i]);

// 2. 三角形の面積が正となるものは？

int ans = 0;

rep(i, N){

repx(j, i + 1, N){

repx(k, j + 1, N){

// 点(x[i], y[i]) を基準として考える.

LL dx1 = x[j] - x[i], dy1 = y[j] - y[i];

LL dx2 = x[k] - x[i], dy2 = y[k] - y[i];

// 三角形の面積の二倍.

LL s = abs(dx1 * dy2 - dy1 * dx2);

// カウント.

if(s) ans++;

}

// 3. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
4
0 1
1 3
1 1
-1 -1

[出力例]
3
※AtCoderテストケースより

[入力例]
20
224 433
987654321 987654321
2 0
6 4
314159265 358979323
0 0
-123456789 123456789
-1000000000 1000000000
124 233
9 -6
-4 0
9 5
-7 3
333333333 -333333333
-9 -1
7 -10
-1 5
324 633
1000000000 -1000000000
20 0

[出力例]
1124
※AtCoderテストケースより

[入力例]
25
524 378
4912 11687
1572 1134
1683 7524
11403 2790
2096 1512
4486 4715
3198 1800
1531 2059
2620 1890
10956 8787
5357 7672
12062 1210
14608 11716
3144 2268
3668 2646
4192 3024
18260 14645
4716 3402
1822 18104
5372 11052
2733 27156
5240 3780
3644 36208
5466 54312

[出力例]
2211

[入力例]

0 1

1 3

1 1

-1 -1

[出力例]

※AtCoderテストケースより

[入力例]

224 433

987654321 987654321

2 0

6 4

314159265 358979323

0 0

-123456789 123456789

-1000000000 1000000000

124 233

9 -6

-4 0

9 5

-7 3

333333333 -333333333

-9 -1

7 -10

-1 5

324 633

1000000000 -1000000000

20 0

[出力例]

1124

※AtCoderテストケースより

[入力例]

524 378

4912 11687

1572 1134

1683 7524

11403 2790

2096 1512

4486 4715

3198 1800

1531 2059

2620 1890

10956 8787

5357 7672

12062 1210

14608 11716

3144 2268

3668 2646

4192 3024

18260 14645

4716 3402

1822 18104

5372 11052

2733 27156

5240 3780

3644 36208

5466 54312

[出力例]

2211

■C++版プログラム(問題D／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc224/editorial/2813
// 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 all(x) x.begin(), x.end()
int g[10][10], p[10], q[10];

int main(){
    
    // 1. 入力情報.
    int M;
    scanf("%d", &M);
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    
    // 2. 初期状態.
    rep(i, 10) q[i] = 9;
    rep(i, 8){
        scanf("%d", &p[i]);
        q[p[i]] = i + 1;
    }
    string s = "";
    repx(i, 1, 10) s.pb(q[i] + '0');
    // printf("%s\n", s.c_str());
    
    // 3. 駒の配置(全通り).
    map<string, int> m;
    vi z(9);
    iota(all(z), 1);
    do{
        // 3-1. 駒の配置を作成.
        string t = "";
        rep(i, 9) t.pb(z[i] + '0');
        
        // 3-2. 保存.
        m[t] = -1;
        // printf("%s\n", t.c_str());
    }while(next_permutation(all(z)));
    
    // 4. 初期状態 から コマの配置までの距離を計算.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](string s, map<string, int> &d){
        // 4-1. 空のキュー.
        queue<string> q;
        
        // 4-2. 開始地点の距離.
        d[s] = 0;
        
        // 4-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 4-4. キューから取り出す.
            string u = q.front();
            q.pop();
            
            // 4-5. グラフの辺を全探索.
            rep(i, 9){
                repx(j, i + 1, 9){
                    // 辺(i, j) が存在するか？
                    if(g[i][j]){
                        // s[i] = 9 or s[j] = 9 の 場合.
                        if(u[i] == '9' || u[j] == '9'){
                            // コピー作成.
                            string v = u;
                            
                            // s[i], s[j] を 入れ替え.
                            swap(v[i], v[j]);
                            
                            // 未訪問ならば追加.
                            if(m[v] == -1){
                                m[v] = m[u] + 1;
                                q.push(v);
                            }
                        }
                    }
                }
            }
        }
        return;
    };
    bfs(s, m);
    
    // 5. 出力.
    printf("%d\n", m["123456789"]);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/abc224/editorial/2813

// 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 all(x) x.begin(), x.end()

int g[10][10], p[10], q[10];

int main(){

// 1. 入力情報.

int M;

scanf("%d", &M);

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--;

b--;

g[a][b] = 1;

g[b][a] = 1;

}

// 2. 初期状態.

rep(i, 10) q[i] = 9;

rep(i, 8){

scanf("%d", &p[i]);

q[p[i]] = i + 1;

}

string s = "";

repx(i, 1, 10) s.pb(q[i] + '0');

// printf("%s\n", s.c_str());

// 3. 駒の配置(全通り).

map<string, int> m;

vi z(9);

iota(all(z), 1);

do{

// 3-1. 駒の配置を作成.

string t = "";

rep(i, 9) t.pb(z[i] + '0');

// 3-2. 保存.

m[t] = -1;

// printf("%s\n", t.c_str());

}while(next_permutation(all(z)));

// 4. 初期状態からコマの配置までの距離を計算.

// https://ja.wikipedia.org/wiki/幅優先探索

auto bfs = [&](string s, map<string, int> &d){

// 4-1. 空のキュー.

queue<string> q;

// 4-2. 開始地点の距離.

d[s] = 0;

// 4-3. 探索地点 s をキュー q に追加.

q.push(s);

while(!q.empty()){

// 4-4. キューから取り出す.

string u = q.front();

q.pop();

// 4-5. グラフの辺を全探索.

rep(i, 9){

repx(j, i + 1, 9){

// 辺(i, j) が存在するか？

if(g[i][j]){

// s[i] = 9 or s[j] = 9 の場合.

if(u[i] == '9' || u[j] == '9'){

// コピー作成.

string v = u;

// s[i], s[j] を入れ替え.

swap(v[i], v[j]);

// 未訪問ならば追加.

if(m[v] == -1){

m[v] = m[u] + 1;

q.push(v);

}

return;

};

bfs(s, m);

// 5. 出力.

printf("%d\n", m["123456789"]);

return 0;

}

[入力例]
5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

[出力例]
5
※AtCoderテストケースより

[入力例]
5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

[出力例]
0
※AtCoderテストケースより

[入力例]
12
8 5
9 6
4 5
4 1
2 5
8 9
2 1
3 6
8 7
6 5
7 4
2 3
1 2 3 4 5 6 8 7

[出力例]
-1
※AtCoderテストケースより

[入力例]
12
6 5
5 4
4 1
4 7
8 5
2 1
2 5
6 9
3 6
9 8
8 7
3 2
2 3 4 6 1 9 7 8

[出力例]
16
※AtCoderテストケースより

[入力例]
0
1 6 4 8 5 2 3 7

[出力例]
-1

[入力例]
11
1 9
1 6
2 6
2 4
4 9
6 9
3 6
3 9
5 9
5 7
7 9
6 4 2 1 7 3 5 8

[出力例]
11

[入力例]
30
4 7
1 9
2 5
1 5
3 5
6 8
2 4
3 9
4 9
3 7
5 6
5 9
1 2
3 6
5 7
7 8
2 3
2 9
3 8
7 9
2 6
2 8
1 4
2 7
3 4
4 6
4 8
1 8
1 3
4 5
3 2 6 7 5 1 4 8

[出力例]
7

[入力例]
36
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
8 5 7 3 6 2 4 1

[出力例]
11

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

[入力例]

1 2

1 3

1 9

2 9

3 9

3 9 2 4 5 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 3

1 9

2 9

3 9

1 2 3 4 5 6 7 8

[出力例]

※AtCoderテストケースより

[入力例]

8 5

9 6

4 5

4 1

2 5

8 9

2 1

3 6

8 7

6 5

7 4

2 3

1 2 3 4 5 6 8 7

[出力例]

-1

※AtCoderテストケースより

[入力例]

6 5

5 4

4 1

4 7

8 5

2 1

2 5

6 9

3 6

9 8

8 7

3 2

2 3 4 6 1 9 7 8

[出力例]

※AtCoderテストケースより

[入力例]

1 6 4 8 5 2 3 7

[出力例]

-1

[入力例]

1 9

1 6

2 6

2 4

4 9

6 9

3 6

3 9

5 9

5 7

7 9

6 4 2 1 7 3 5 8

[出力例]

[入力例]

4 7

1 9

2 5

1 5

3 5

6 8

2 4

3 9

4 9

3 7

5 6

5 9

1 2

3 6

5 7

7 8

2 3

2 9

3 8

7 9

2 6

2 8

1 4

2 7

3 4

4 6

4 8

1 8

1 3

4 5

3 2 6 7 5 1 4 8

[出力例]

[入力例]

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

2 3

2 4

2 5

2 6

2 7

2 8

2 9

3 4

3 5

3 6

3 7

3 8

3 9

4 5

4 6

4 7

4 8

4 9

5 6

5 7

5 8

5 9

6 7

6 8

6 9

7 8

7 9

8 9

8 5 7 3 6 2 4 1

[出力例]

■参照サイト
AtCoder Beginner Contest 224

2021年10月27日

C++ の動作確認をしてみた（５６５）

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題F (Parenthesis Checking) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説プログラムを参考に提出して, ようやく, AC版に到達出来た.
2. 遅延評価セグメント木が復習できたので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 223 解説の各リンクをご覧下さい.

■C++版プログラム(問題F／AC版).

// 解答不能.
// https://atcoder.jp/contests/abc223/editorial/2774
// 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--)
const int INF = 2020202020;

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp)
// -> 一部改変(2021/10/27).
template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct LazySegmentTree{
  public:
    LazySegmentTree() : LazySegmentTree(0){}
    explicit LazySegmentTree(int n) : LazySegmentTree(vector<S>(n, e())){}
    explicit LazySegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        lz = vector<F>(size, id());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        repr(i, log, 1) push(p >> i);
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        p += size;
        repr(i, log, 1) push(p >> i);
        return d[p];
    }
    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return e();
        l += size;
        r += size;
        repr(i, log, 1){
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }
        S sml = e(), smr = e();
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod(){
        return d[1];
    }
    void apply(int p, F f){
        assert(0 <= p && p < _n);
        p += size;
        repr(i, log, 1) push(p >> i);
        d[p] = mapping(f, d[p]);
        repx(i, 1, log + 1) update(p >> i);
    }
    void apply(int l, int r, F f){
        assert(0 <= l && l <= r && r <= _n);
        if(l == r) return;
        l += size;
        r += size;
        repr(i, log, 1){
            if(((l >> i) << i) != l) push(l >> i);
            if(((r >> i) << i) != r) push((r - 1) >> i);
        }
        {
            int l2 = l, r2 = r;
            while(l < r){
                if(l & 1) all_apply(l++, f);
                if(r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }
        repx(i, 1, log + 1){
            if(((l >> i) << i) != l) update(l >> i);
            if(((r >> i) << i) != r) update((r - 1) >> i);
        }
    }
private:
    int _n, size, log;
    vector<S> d;
    vector<F> lz;
    void update(int k){
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
    void all_apply(int k, F f){
        d[k] = mapping(f, d[k]);
        if(k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k){
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

int op(int a, int b){
    return min(a, b);
}
int e(){
    return INF;
}
int mapping(int f, int x){
    return f + x;
}
int composition(int f, int g){
    return f + g;
}
int id(){
    return 0;
}

int main(){
    
    // 1. 入力情報.
    int N, Q;
    char c[202020];
    scanf("%d %d %s", &N, &Q, c);
    string s(c);
    
    // 2. 前処理.
    vi v(N + 1);
    rep(i, N) v[i + 1] = (s[i] == '(') ? v[i] + 1 : v[i] - 1;
    
    // 3. クエリ回答.
    LazySegmentTree<int, op, e, int, mapping, composition, id> seg(v);
    rep(i, Q){
        // 3-1. クエリ情報.
        int t, l, r;
        scanf("%d %d %d", &t, &l, &r);
        
        // 3-2. パターン 1.
        if(t == 1){
            // l文字目, r文字目更新.
            if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2);
            if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2);
            
            // l文字目, r文字目 を 入れ替え.
            swap(s[l - 1], s[r - 1]);
        }
        
        // 3-3. パターン 2.
        if(t == 2){
            // (l - 1)文字目, r文字目 までの累積和.
            int lCum = seg.get(l - 1);
            int rCum = seg.get(r);
            
            // [l - 1, r] の 最小値.
            int bMin = seg.prod(l - 1, r + 1);
            
            // 出力.
            printf("%s\n", (bMin == lCum && lCum == rCum) ? "Yes" : "No");
        }
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

// 解答不能.

// https://atcoder.jp/contests/abc223/editorial/2774

// 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--)

const int INF = 2020202020;

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/lazysegtree.hpp)

// -> 一部改変(2021/10/27).

template <class S,

S (*op)(S, S),

S (*e)(),

class F,

S (*mapping)(F, S),

F (*composition)(F, F),

F (*id)()>

struct LazySegmentTree{

public:

LazySegmentTree() : LazySegmentTree(0){}

explicit LazySegmentTree(int n) : LazySegmentTree(vector<S>(n, e())){}

explicit LazySegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

lz = vector<F>(size, id());

rep(i, _n) d[size + i] = v[i];

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

repr(i, log, 1) push(p >> i);

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

p += size;

repr(i, log, 1) push(p >> i);

return d[p];

}

S prod(int l, int r){

assert(0 <= l && l <= r && r <= _n);

if(l == r) return e();

l += size;

r += size;

repr(i, log, 1){

if(((l >> i) << i) != l) push(l >> i);

if(((r >> i) << i) != r) push((r - 1) >> i);

}

S sml = e(), smr = e();

while(l < r){

if(l & 1) sml = op(sml, d[l++]);

if(r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod(){

return d[1];

}

void apply(int p, F f){

assert(0 <= p && p < _n);

p += size;

repr(i, log, 1) push(p >> i);

d[p] = mapping(f, d[p]);

repx(i, 1, log + 1) update(p >> i);

}

void apply(int l, int r, F f){

assert(0 <= l && l <= r && r <= _n);

if(l == r) return;

l += size;

r += size;

repr(i, log, 1){

if(((l >> i) << i) != l) push(l >> i);

if(((r >> i) << i) != r) push((r - 1) >> i);

}

{

int l2 = l, r2 = r;

while(l < r){

if(l & 1) all_apply(l++, f);

if(r & 1) all_apply(--r, f);

l >>= 1;

r >>= 1;

}

l = l2;

r = r2;

}

repx(i, 1, log + 1){

if(((l >> i) << i) != l) update(l >> i);

if(((r >> i) << i) != r) update((r - 1) >> i);

}

private:

int _n, size, log;

vector<S> d;

vector<F> lz;

void update(int k){

d[k] = op(d[2 * k], d[2 * k + 1]);

}

void all_apply(int k, F f){

d[k] = mapping(f, d[k]);

if(k < size) lz[k] = composition(f, lz[k]);

}

void push(int k){

all_apply(2 * k, lz[k]);

all_apply(2 * k + 1, lz[k]);

lz[k] = id();

}

};

int op(int a, int b){

return min(a, b);

}

int e(){

return INF;

}

int mapping(int f, int x){

return f + x;

}

int composition(int f, int g){

return f + g;

}

int id(){

return 0;

}

int main(){

// 1. 入力情報.

int N, Q;

char c[202020];

scanf("%d %d %s", &N, &Q, c);

string s(c);

// 2. 前処理.

vi v(N + 1);

rep(i, N) v[i + 1] = (s[i] == '(') ? v[i] + 1 : v[i] - 1;

// 3. クエリ回答.

LazySegmentTree<int, op, e, int, mapping, composition, id> seg(v);

rep(i, Q){

// 3-1. クエリ情報.

int t, l, r;

scanf("%d %d %d", &t, &l, &r);

// 3-2. パターン 1.

if(t == 1){

// l文字目, r文字目更新.

if(s[l - 1] == '(' && s[r - 1] == ')') seg.apply(l, r, -2);

if(s[l - 1] == ')' && s[r - 1] == '(') seg.apply(l, r, 2);

// l文字目, r文字目を入れ替え.

swap(s[l - 1], s[r - 1]);

}

// 3-3. パターン 2.

if(t == 2){

// (l - 1)文字目, r文字目までの累積和.

int lCum = seg.get(l - 1);

int rCum = seg.get(r);

// [l - 1, r] の最小値.

int bMin = seg.prod(l - 1, r + 1);

// 出力.

printf("%s\n", (bMin == lCum && lCum == rCum) ? "Yes" : "No");

}

return 0;

}

[入力例]
5 3
(())(
2 1 4
2 1 2
2 4 5

[出力例]
Yes
No
No
※AtCoderのテストケースより

[入力例]
5 3
(())(
2 1 4
1 1 4
2 1 4

[出力例]
Yes
No
※AtCoderのテストケースより

[入力例]
8 8
(()(()))
2 2 7
2 2 8
1 2 5
2 3 4
1 3 4
1 3 5
1 1 4
1 6 8

[出力例]
Yes
No
No
※AtCoderのテストケースより

[入力例]
20 15
()(())((((()))))(())
2 1 2
2 3 6
1 18 19
2 7 16
2 17 20
1 5 12
2 2 7
1 6 19
1 11 15
2 8 15
1 7 13
2 13 18
1 3 16
2 5 8
2 15 20

[出力例]
Yes
Yes
Yes
Yes
No
No
Yes
No
Yes

[入力例]
50 20
((()(((()(()((()))(()))(())())))))))))((()))()))))
2 19 22
1 17 20
1 7 11
2 17 20
2 18 28
2 39 44
1 15 24
1 20 39
2 24 27
2 3 26
2 40 43
1 12 31
2 22 32
2 28 29
1 9 15
2 18 23
2 13 16
1 12 37
2 45 48
1 5 8

[出力例]
Yes
Yes
No
Yes
Yes
No
Yes
No
Yes
No
Yes
No

[入力例]
100 30
()(()((()())()((())()()()()((((((())())(((()()(()))())())(()))))(())())((())((((())))))))(()))(()()(
1 37 61
2 7 12
2 30 39
1 23 61
2 25 26
1 7 50
2 9 56
2 45 56
2 77 86
1 40 73
2 28 57
1 6 11
2 47 54
1 34 65
2 40 64
2 73 76
1 6 23
2 29 65
1 15 30
1 32 42
1 43 44
2 20 27
2 44 57
1 34 60
2 26 63
1 49 58
1 17 57
2 90 93
1 30 51
2 96 99

[出力例]
Yes
Yes
No
No
Yes
Yes
No
Yes
No
Yes
No
Yes
Yes
No
Yes
Yes

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

[入力例]

5 3

(())(

2 1 4

2 1 2

2 4 5

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 3

(())(

2 1 4

1 1 4

2 1 4

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

8 8

(()(()))

2 2 7

2 2 8

1 2 5

2 3 4

1 3 4

1 3 5

1 1 4

1 6 8

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

20 15

()(())((((()))))(())

2 1 2

2 3 6

1 18 19

2 7 16

2 17 20

1 5 12

2 2 7

1 6 19

1 11 15

2 8 15

1 7 13

2 13 18

1 3 16

2 5 8

2 15 20

[出力例]

Yes

[入力例]

50 20

((()(((()(()((()))(()))(())())))))))))((()))()))))

2 19 22

1 17 20

1 7 11

2 17 20

2 18 28

2 39 44

1 15 24

1 20 39

2 24 27

2 3 26

2 40 43

1 12 31

2 22 32

2 28 29

1 9 15

2 18 23

2 13 16

1 12 37

2 45 48

1 5 8

[出力例]

Yes

[入力例]

100 30

()(()((()())()((())()()()()((((((())())(((()()(()))())())(()))))(())())((())((((())))))))(()))(()()(

1 37 61

2 7 12

2 30 39

1 23 61

2 25 26

1 7 50

2 9 56

2 45 56

2 77 86

1 40 73

2 28 57

1 6 11

2 47 54

1 34 65

2 40 64

2 73 76

1 6 23

2 29 65

1 15 30

1 32 42

1 43 44

2 20 27

2 44 57

1 34 60

2 26 63

1 49 58

1 17 57

2 90 93

1 30 51

2 96 99

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 223

2021年10月26日

C++ の動作確認をしてみた（５６４）

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題E (Placing Rectangles) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 全探索を使うテクニックが面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Beginner Contest 223 解説の各リンクをご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://atcoder.jp/contests/abc223/editorial/2781
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#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--)
LL p[11];

int main(){
    
    // 1. 入力情報.
    rep(i, 5) scanf("%lld", &p[i]);
    
    // 2. 分割できるか(全探索).
    bool ok = false;
    rep(i, 2){
        rep(j, 2){
            if(i != j){
                // X, Y を 選択.
                LL X = p[i], Y = p[j];
                repx(a, 2, 5){
                    repx(b, 2, 5){
                        repx(c, 2, 5){
                            if(a != b && b != c && c != a){
                                // A, B, C を 選択.
                                LL A = p[a], B = p[b], C = p[c];
                                
                                // 一つ目の長方形.
                                // A を 収納.
                                LL ha = A / X;
                                if(A % X != 0) ha++;
                                
                                // 二つ目の長方形.
                                // -> 縦, 横方向をチェック.
                                LL hbc = Y - ha;
                                if(hbc > 0){
                                    // 横方向で分割できるか？
                                    // B を 収納.
                                    LL hb = B / X;
                                    if(B % X != 0) hb++;
                                    
                                    // C を 収納.
                                    LL hc = C / X;
                                    if(C % X != 0) hc++;
                                    
                                    // 分割OK.
                                    if(hb + hc <= hbc) ok = true;
                                    
                                    // 縦方向で分割できるか？
                                    // B を 収納.
                                    LL wb = B / hbc;
                                    if(B % hbc != 0) wb++;
                                    
                                    // C を 収納.
                                    LL wc = C / hbc;
                                    if(C % hbc != 0) wc++;
                                    
                                    // 分割OK.
                                    if(wb + wc <= X) ok = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc223/editorial/2781

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#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--)

LL p[11];

int main(){

// 1. 入力情報.

rep(i, 5) scanf("%lld", &p[i]);

// 2. 分割できるか(全探索).

bool ok = false;

rep(i, 2){

rep(j, 2){

if(i != j){

// X, Y を選択.

LL X = p[i], Y = p[j];

repx(a, 2, 5){

repx(b, 2, 5){

repx(c, 2, 5){

if(a != b && b != c && c != a){

// A, B, C を選択.

LL A = p[a], B = p[b], C = p[c];

// 一つ目の長方形.

// A を収納.

LL ha = A / X;

if(A % X != 0) ha++;

// 二つ目の長方形.

// -> 縦, 横方向をチェック.

LL hbc = Y - ha;

if(hbc > 0){

// 横方向で分割できるか？

// B を収納.

LL hb = B / X;

if(B % X != 0) hb++;

// C を収納.

LL hc = C / X;

if(C % X != 0) hc++;

// 分割OK.

if(hb + hc <= hbc) ok = true;

// 縦方向で分割できるか？

// B を収納.

LL wb = B / hbc;

if(B % hbc != 0) wb++;

// C を収納.

LL wc = C / hbc;

if(C % hbc != 0) wc++;

// 分割OK.

if(wb + wc <= X) ok = true;

}

// 3. 出力.

printf("%s\n", ok ? "Yes" : "No");

return 0;

}

[入力例]
3 3 2 2 3

[出力例]
Yes
※AtCoderテストケースより

[入力例]
3 3 4 4 1

[出力例]
No
※AtCoderテストケースより

[入力例]
1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

[出力例]
No
※AtCoderテストケースより

[入力例]
3 5 10 2 3

[出力例]
Yes

[入力例]
5 5 12 8 5

[出力例]
Yes

[入力例]
5 5 13 7 3

[出力例]
No

[入力例]
3 10 13 10 5

[出力例]
Yes

[入力例]
3 10 13 11 4

[出力例]
No

[入力例]
3 10 9 18 3

[出力例]
Yes

[入力例]

3 3 2 2 3

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 3 4 4 1

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000 1000000000000000000 1000000000000000000 1000000000000000000

[出力例]

※AtCoderテストケースより

[入力例]

3 5 10 2 3

[出力例]

Yes

[入力例]

5 5 12 8 5

[出力例]

Yes

[入力例]

5 5 13 7 3

[出力例]

[入力例]

3 10 13 10 5

[出力例]

Yes

[入力例]

3 10 13 11 4

[出力例]

[入力例]

3 10 9 18 3

[出力例]

Yes

■参照サイト
AtCoder Beginner Contest 223

2021年10月25日

C++ の動作確認をしてみた（５６３）

C++の練習を兼ねて, AtCoder Library Practice Contest の問題G (SCC) を解いてみた.

■感想.
1. 問題Gは, 強連結成分分解を使う方針で, AC版に到達出来た.
2. 強連結成分分解(Strongly Connected Component)について, 改めて復習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

■C++版プログラム(問題G／AC版).

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using P = pair<int, int>;
using PQ = priority_queue<P>;
#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 a first
#define b second
#define pb push_back
const int MAX = 505050;
int memo[MAX], scc[MAX];

int main(){
    
    // 1. 入力情報.
    int N, M, a, b;
    scanf("%d %d", &N, &M);
    vvi G1(N), G2(N);
    rep(i, M){
        scanf("%d %d", &a, &b);
        G1[a].pb(b);  // 有向辺.
        G2[b].pb(a);  // 有向辺(逆向き).
    }
    
    // 強連結成分分解(Strongly Connected Component).
    // https://manabitimes.jp/math/1250
    // 2. 行き止まりの順番を保存.
    int idx = 0;
    PQ pq;
    auto dfs1 = [&](auto&& self, int c) -> void{
        // 訪問済フラグ設定.
        memo[c] = 1;
        
        // 取り出した要素を処理.
        for(auto &n : G1[c]) if(!memo[n]) self(self, n);
        
        // 行き止まりの順番を保存.
        pq.push({++idx, c});
    };
    rep(i, N) if(!memo[i]) dfs1(dfs1, i);
    
    // 3. 強連結成分に分解.
    vvi ans(N + 1);
    idx = 0;
    auto dfs2 = [&](auto&& self, int c) -> void{
        // 連結成分番号設定.
        scc[c] = idx;
        
        // 取り出した要素を処理.
        for(auto &n : G2[c]) if(!scc[n]) self(self, n);
        
        // 頂点を保存(トポロジカルソート).
        ans[idx].pb(c);
    };
    while(!pq.empty()){
        // 要素を取り出す.
        P p = pq.top();
        pq.pop();
        
        // 連結成分番号が設定済み.
        if(scc[p.b]) continue;
        
        // インクリメント.
        idx++;
        
        // 連結成分番号設定.
        dfs2(dfs2, p.b);
    }
    
    // 4. 出力.
    printf("%d\n", idx);
    repx(i, 1, idx + 1){
        // 4-1. 強連結成分の頂点数.
        int l = ans[i].size();
        printf("%d ", l);
        
        // 4-2. 頂点を出力.
        rep(j, l){
            printf("%d", ans[i][j]);
            printf("%s", (j < l - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using P = pair<int, int>;

using PQ = priority_queue<P>;

#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 a first

#define b second

#define pb push_back

const int MAX = 505050;

int memo[MAX], scc[MAX];

int main(){

// 1. 入力情報.

int N, M, a, b;

scanf("%d %d", &N, &M);

vvi G1(N), G2(N);

rep(i, M){

scanf("%d %d", &a, &b);

G1[a].pb(b); // 有向辺.

G2[b].pb(a); // 有向辺(逆向き).

}

// 強連結成分分解(Strongly Connected Component).

// https://manabitimes.jp/math/1250

// 2. 行き止まりの順番を保存.

int idx = 0;

PQ pq;

auto dfs1 = [&](auto&& self, int c) -> void{

// 訪問済フラグ設定.

memo[c] = 1;

// 取り出した要素を処理.

for(auto &n : G1[c]) if(!memo[n]) self(self, n);

// 行き止まりの順番を保存.

pq.push({++idx, c});

};

rep(i, N) if(!memo[i]) dfs1(dfs1, i);

// 3. 強連結成分に分解.

vvi ans(N + 1);

idx = 0;

auto dfs2 = [&](auto&& self, int c) -> void{

// 連結成分番号設定.

scc[c] = idx;

// 取り出した要素を処理.

for(auto &n : G2[c]) if(!scc[n]) self(self, n);

// 頂点を保存(トポロジカルソート).

ans[idx].pb(c);

};

while(!pq.empty()){

// 要素を取り出す.

P p = pq.top();

pq.pop();

// 連結成分番号が設定済み.

if(scc[p.b]) continue;

// インクリメント.

idx++;

// 連結成分番号設定.

dfs2(dfs2, p.b);

}

// 4. 出力.

printf("%d\n", idx);

repx(i, 1, idx + 1){

// 4-1. 強連結成分の頂点数.

int l = ans[i].size();

printf("%d ", l);

// 4-2. 頂点を出力.

rep(j, l){

printf("%d", ans[i][j]);

printf("%s", (j < l - 1) ? " " : "\n");

}

return 0;

}

[入力例]
6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

[出力例]
4
1 5
2 4 1
1 2
2 3 0
※AtCoderテストケースより

[入力例]
11 14
0 1
1 0
0 7
7 9
9 8
7 8
8 10
10 7
1 2
2 5
2 3
5 4
4 2
3 4

[出力例]
4
1 6
2 1 0
4 9 8 10 7
4 5 3 4 2

[入力例]
7 10
0 6
6 0
0 1
1 2
2 1
2 3
2 4
4 3
5 4
3 5

[出力例]
3
2 6 0
2 2 1
3 5 4 3

[入力例]
20 25
0 1
1 0
0 7
7 8
8 18
1 9
9 10
10 11
10 12
11 12
12 9
1 2
2 3
3 6
6 5
5 4
4 2
4 19
13 1
13 14
13 17
17 15
16 17
15 16
14 15

[出力例]
10
1 13
1 14
3 16 17 15
2 1 0
1 7
1 8
1 18
5 3 6 5 4 2
1 19
4 10 11 12 9

100

101

[入力例]

6 7

1 4

5 2

3 0

5 5

4 1

0 3

4 2

[出力例]

1 5

2 4 1

1 2

2 3 0

※AtCoderテストケースより

[入力例]

11 14

0 1

1 0

0 7

7 9

9 8

7 8

8 10

10 7

1 2

2 5

2 3

5 4

4 2

3 4

[出力例]

1 6

2 1 0

4 9 8 10 7

4 5 3 4 2

[入力例]

7 10

0 6

6 0

0 1

1 2

2 1

2 3

2 4

4 3

5 4

3 5

[出力例]

2 6 0

2 2 1

3 5 4 3

[入力例]

20 25

0 1

1 0

0 7

7 8

8 18

1 9

9 10

10 11

10 12

11 12

12 9

1 2

2 3

3 6

6 5

5 4

4 2

4 19

13 1

13 14

13 17

17 15

16 17

15 16

14 15

[出力例]

1 13

1 14

3 16 17 15

2 1 0

1 7

1 8

1 18

5 3 6 5 4 2

1 19

4 10 11 12 9

■参照サイト
AtCoder Library Practice Contest
021 – Come Back in One Piece
強連結成分分解の意味とアルゴリズム

C++の練習を兼ねて, AtCoder Grand Contest 055 の 問題A (ABC Identity) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の 問題C (Gacha) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題F (Problem where +s Separate Digits) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の 問題B (Painting with Many Orders) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題E (Integers on Grid) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 222 の 問題E (Red and Blue Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の 問題C (Triangle?) ～ 問題D (8 Puzzle on Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の 問題F (Parenthesis Checking) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の 問題E (Placing Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Library Practice Contest の 問題G (SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 055 の問題A (ABC Identity) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題C (Gacha) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題F (Problem where +s Separate Digits) を解いてみた.

C++の練習を兼ねて, 京都大学プログラミングコンテスト 2021 の問題B (Painting with Many Orders) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題E (Integers on Grid) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 222 の問題E (Red and Blue Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 224 の問題C (Triangle?) ～問題D (8 Puzzle on Graph) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題F (Parenthesis Checking) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 223 の問題E (Placing Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Library Practice Contest の問題G (SCC) を解いてみた.