C++ | 個人用メモ帳

2023年11月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題E (Joint Two Strings) を解いてみた.

■感想.
1. 問題Eは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題E で, 二分探索の復習が出来たので, 良かったとおもう.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
#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 main(){
    
    // 1. 入力情報.
    int N;
    char t[505050];
    scanf("%d %s", &N, t);
    int ts = strlen(t);
    vs v;
    rep(i, N){
        string s;
        cin >> s;
        v.pb(s);
    }
    
    // 2. 文字列 T と, 何文字一致するか？
    vi lCount, rCount;
    for(auto &s : v){
        // 文字列 S の 各文字の出現位置は？
        vvi idxs(26);
        rep(i, s.size()) idxs[s[i] - 'a'].pb(i);
        
        // 左から数える場合.
        int idx = -1, c = 0;
        rep(i, ts){
            int cur = t[i] - 'a';
            if(!idxs[cur].size()) break;
            int at = upper_bound(all(idxs[cur]), idx) - idxs[cur].begin();
            if(at == idxs[cur].size()) break;
            if(idx >= idxs[cur][at]) break;
            idx = idxs[cur][at];
            ++c;
        }
        lCount.pb(c);
        
        // 右から数える場合.
        idx = s.size(), c = 0;
        repr(i, ts - 1, 0){
            int cur = t[i] - 'a';
            if(!idxs[cur].size()) break;
            int at = lower_bound(all(idxs[cur]), idx) - idxs[cur].begin();
            if(!at && idx <= idxs[cur][at]) break;
            idx = idxs[cur][max(0, at - 1)];
            ++c;
        }
        rCount.pb(c);
    }
    
    // 3. sort.
    sort(all(lCount));
    sort(all(rCount));
    
    // 4. 集計.
    LL ans = 0;
    for(auto &l : lCount){
        int at = lower_bound(all(rCount), ts - l) - rCount.begin();
        ans += (LL)(rCount.size() - at);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

using vs = vector<string>;

#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 main(){

// 1. 入力情報.

int N;

char t[505050];

scanf("%d %s", &N, t);

int ts = strlen(t);

vs v;

rep(i, N){

string s;

cin >> s;

v.pb(s);

}

// 2. 文字列 T と, 何文字一致するか？

vi lCount, rCount;

for(auto &s : v){

// 文字列 S の各文字の出現位置は？

vvi idxs(26);

rep(i, s.size()) idxs[s[i] - 'a'].pb(i);

// 左から数える場合.

int idx = -1, c = 0;

rep(i, ts){

int cur = t[i] - 'a';

if(!idxs[cur].size()) break;

int at = upper_bound(all(idxs[cur]), idx) - idxs[cur].begin();

if(at == idxs[cur].size()) break;

if(idx >= idxs[cur][at]) break;

idx = idxs[cur][at];

++c;

}

lCount.pb(c);

// 右から数える場合.

idx = s.size(), c = 0;

repr(i, ts - 1, 0){

int cur = t[i] - 'a';

if(!idxs[cur].size()) break;

int at = lower_bound(all(idxs[cur]), idx) - idxs[cur].begin();

if(!at && idx <= idxs[cur][at]) break;

idx = idxs[cur][max(0, at - 1)];

++c;

}

rCount.pb(c);

}

// 3. sort.

sort(all(lCount));

sort(all(rCount));

// 4. 集計.

LL ans = 0;

for(auto &l : lCount){

int at = lower_bound(all(rCount), ts - l) - rCount.begin();

ans += (LL)(rCount.size() - at);

}

// 5. 出力.

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

return 0;

}

[入力例]
3 bac
abba
bcb
aaca

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

[入力例]
5 xx
x
x
x
x
x

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

[入力例]
10 ms
mkgn
m
hlms
vmsle
mxsm
nnzdhi
umsavxlb
ffnsybomr
yvmm
naouel

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

[入力例]
3 a
a
a
a

[出力例]
9

[入力例]
5 pqr
smcmwubocdxvlifbvncjmvrpyq
mhjzknucbwjyprclfyhlgrmhgp
vhmdqgdikfooemfqlgkeocqntw
uglthudqauvtlnvztvtopvukbr
xmdthyfzaeubkdmjapnplgnyyf

[出力例]
6

[入力例]
10 atcoder
swlazbtdveckiojddjvezrrsjzimjjog
noajutwvbcmuzoswnctqobguletpsq
xcfgesaszjcpetuyxufehuiffg
tkrvoawtwcyizodxbdwxeecrrdiadeezrckw
forgemtxmwnblzyhzpsjrcynhx
dkaawtxfkciqkogptdjzblukvgpqjn
pttmiajkmezpmmvyrdujkeqerynzm
dplzhanztxxcfoozvadexeiprlzrlklyui
qskedvmgavbtfdvcmecwerwjwgqoch
ditpzonoidultevbrzsddrueqarysfcbt

[出力例]
61

[入力例]
30 abracadabra
frlhabracacdavbacadyjotqfiajpfrsfalqmpqzm
pnsabraaasbboigplsbkqaytpztlty
dabrarenuxjbnmwejvumayzqmjacadyueir
vrafdksqwxwphvbabracxadyaubraxsnhiyimkgj
vopsvoomcfekesrqblqxjacaderhok
hephqdabrahgabrailbwcnykgnueerasxlz
dfdoqdncuaybkxabracxmzgjnmtkioc
apbiybracaudabirglrzehsfuhrhuoczuduwb
ruxxacadfdcacadizqzeefryriesteziip
xzqjtdewrnyabraquyjhabracaidabirayberuirmjf
hafudwmabracadabrampgdabraurlmyacdayrmezgrnkd
ccamcpjhmcinhabracadabrauubcytmtoyksr
rtgpyiaqqcthxabracadadbrdaduhazyiintogf
nciseywsrseoyiodabraskzmabraqsmknfc
qabracaydaubrasgnjpsyonenfehongsupwralz
xdsbjgybfbmiabraicaodabrayeetrlzqyikhxv
wopsvxldeemevmebagfmdabratnnabraodq
ccdsyjhxfmvltkgvdxdacadfzijmtk
pjrxhwalfpetfydzcabracieagtvswdabrah
egvbabacadaebrcrzxhqsxpxglqucndgzllk
wlpdpbvlhrleulaoahghgjlacadddz
qebhqkeksdiviwwabracadabrarvhwxlizrjx
vzifenabrabznwcwkcdblrwxbbzdabrajks
lpepabjpuxabrarhupexbcwivbapol
dwomabracaudaobrargvgrkfpodelkgzntgszzr
qwvbgaivdyummkaraptmdabrablkecktwm
ytguxctdeoclbpacadzybhumyzlxjo
ykxggshcsuxutqbupmqzpscrgdabrag
gixkvjvuimdfgmttdhabatinoxmbp
pzslmvoulsgxnxocjgmifdabraqfxym

[出力例]
606

100

101

102

103

104

105

106

107

108

109

110

[入力例]

3 bac

abba

bcb

aaca

[出力例]

※AtCoderテストケースより

[入力例]

5 xx

[出力例]

※AtCoderテストケースより

[入力例]

10 ms

mkgn

hlms

vmsle

mxsm

nnzdhi

umsavxlb

ffnsybomr

yvmm

naouel

[出力例]

※AtCoderテストケースより

[入力例]

3 a

[出力例]

[入力例]

5 pqr

smcmwubocdxvlifbvncjmvrpyq

mhjzknucbwjyprclfyhlgrmhgp

vhmdqgdikfooemfqlgkeocqntw

uglthudqauvtlnvztvtopvukbr

xmdthyfzaeubkdmjapnplgnyyf

[出力例]

[入力例]

10 atcoder

swlazbtdveckiojddjvezrrsjzimjjog

noajutwvbcmuzoswnctqobguletpsq

xcfgesaszjcpetuyxufehuiffg

tkrvoawtwcyizodxbdwxeecrrdiadeezrckw

forgemtxmwnblzyhzpsjrcynhx

dkaawtxfkciqkogptdjzblukvgpqjn

pttmiajkmezpmmvyrdujkeqerynzm

dplzhanztxxcfoozvadexeiprlzrlklyui

qskedvmgavbtfdvcmecwerwjwgqoch

ditpzonoidultevbrzsddrueqarysfcbt

[出力例]

[入力例]

30 abracadabra

frlhabracacdavbacadyjotqfiajpfrsfalqmpqzm

pnsabraaasbboigplsbkqaytpztlty

dabrarenuxjbnmwejvumayzqmjacadyueir

vrafdksqwxwphvbabracxadyaubraxsnhiyimkgj

vopsvoomcfekesrqblqxjacaderhok

hephqdabrahgabrailbwcnykgnueerasxlz

dfdoqdncuaybkxabracxmzgjnmtkioc

apbiybracaudabirglrzehsfuhrhuoczuduwb

ruxxacadfdcacadizqzeefryriesteziip

xzqjtdewrnyabraquyjhabracaidabirayberuirmjf

hafudwmabracadabrampgdabraurlmyacdayrmezgrnkd

ccamcpjhmcinhabracadabrauubcytmtoyksr

rtgpyiaqqcthxabracadadbrdaduhazyiintogf

nciseywsrseoyiodabraskzmabraqsmknfc

qabracaydaubrasgnjpsyonenfehongsupwralz

xdsbjgybfbmiabraicaodabrayeetrlzqyikhxv

wopsvxldeemevmebagfmdabratnnabraodq

ccdsyjhxfmvltkgvdxdacadfzijmtk

pjrxhwalfpetfydzcabracieagtvswdabrah

egvbabacadaebrcrzxhqsxpxglqucndgzllk

wlpdpbvlhrleulaoahghgjlacadddz

qebhqkeksdiviwwabracadabrarvhwxlizrjx

vzifenabrabznwcwkcdblrwxbbzdabrajks

lpepabjpuxabrarhupexbcwivbapol

dwomabracaudaobrargvgrkfpodelkgzntgszzr

qwvbgaivdyummkaraptmdabrablkecktwm

ytguxctdeoclbpacadzybhumyzlxjo

ykxggshcsuxutqbupmqzpscrgdabrag

gixkvjvuimdfgmttdhabatinoxmbp

pzslmvoulsgxnxocjgmifdabraqfxym

[出力例]

606

■参照サイト
日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）

2023年10月29日2023年10月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題C (Error Correction) ～問題D (Square Permutation) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 全探索の復習が出来たので, 良かったとおもう.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<string>;
#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

int main(){
    
    // 1. 入力情報.
    int N;
    char c[505050];
    scanf("%d %s", &N, c);
    string u(c);
    vs v;
    rep(i, N){
        string s;
        cin >> s;
        v.pb(s);
    }
    
    // 2. 集計.
    int us = u.size();
    vi ans;
    rep(i, N){
        // 2-1. T, T' の文字数が同じ.
        string t = v[i];
        int ts = t.size();
        if(ts == us){
            int diff = 0;
            rep(j, ts) if(t[j] != u[j]) ++diff;
            if(diff <= 1) ans.pb(i + 1);
            continue;
        }
        
        // 2-2. T が T' より 1文字多い.
        if(ts == us + 1){
            int idx = ts - 1;
            rep(j, us){
                if(t[j] != u[j]){
                    idx = j;
                    break;
                }
            }
            bool ok = true;
            repx(j, idx + 1, ts) if(t[j] != u[j - 1]) ok = false;
            if(ok) ans.pb(i + 1);
            continue;
        }
        
        // 2-3. T' が T より 1文字多い.
        if(us == ts + 1){
            int idx = us - 1;
            rep(j, ts){
                if(t[j] != u[j]){
                    idx = j;
                    break;
                }
            }
            bool ok = true;
            repx(j, idx + 1, us) if(u[j] != t[j - 1]) ok = false;
            if(ok) ans.pb(i + 1);
            continue;
        }
    }
    
    // 3. 出力.
    int n = ans.size();
    printf("%d\n", n);
    rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vs = vector<string>;

#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

int main(){

// 1. 入力情報.

int N;

char c[505050];

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

string u(c);

vs v;

rep(i, N){

string s;

cin >> s;

v.pb(s);

}

// 2. 集計.

int us = u.size();

vi ans;

rep(i, N){

// 2-1. T, T' の文字数が同じ.

string t = v[i];

int ts = t.size();

if(ts == us){

int diff = 0;

rep(j, ts) if(t[j] != u[j]) ++diff;

if(diff <= 1) ans.pb(i + 1);

continue;

}

// 2-2. T が T' より 1文字多い.

if(ts == us + 1){

int idx = ts - 1;

rep(j, us){

if(t[j] != u[j]){

idx = j;

break;

}

bool ok = true;

repx(j, idx + 1, ts) if(t[j] != u[j - 1]) ok = false;

if(ok) ans.pb(i + 1);

continue;

}

// 2-3. T' が T より 1文字多い.

if(us == ts + 1){

int idx = us - 1;

rep(j, ts){

if(t[j] != u[j]){

idx = j;

break;

}

bool ok = true;

repx(j, idx + 1, us) if(u[j] != t[j - 1]) ok = false;

if(ok) ans.pb(i + 1);

continue;

}

// 3. 出力.

int n = ans.size();

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

rep(i, n) printf("%d%s", ans[i], (i < n - 1) ? " " : "\n");

return 0;

}

[入力例]
5 ababc
ababc
babc
abacbc
abdbc
abbac

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

[入力例]
1 aoki
takahashi

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

[入力例]
9 atcoder
atoder
atcode
athqcoder
atcoder
tacoder
jttcoder
atoder
atceoder
atcoer

[出力例]
6
1 2 4 7 8 9
※AtCoderテストケースより

[入力例]
17 iroha
iroha
hiroha
ijroha
irsoha
iropha
irohia
irohab
roha
ioha
irha
iroa
iroh
zroha
izoha
irzha
iroza
irohz

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

[入力例]
25 beginner
eehccbkoonm
beginner
aiehciglanf
oahkoknoej
beganner
hbjgfdnfj
beginnerr
kcfkicnfgik
begnner
aljndjalikk
beginnner
mjojjddmoff
ihajahecfkdk
eginner
ccccmohebjjmk
kefohsdsdaghado
mjbclodfyguekdf
beginer
lgagnbecondbi
mgibkkakneeeffo
fhhoojmkjijctm
begannner
fggfjbnjbdddfju
cceefhmgiddhlqobi
biginner

[出力例]
8
2 5 7 9 11 14 18 25

[入力例]

5 ababc

ababc

babc

abacbc

abdbc

abbac

[出力例]

1 2 3 4

※AtCoderテストケースより

[入力例]

1 aoki

takahashi

[出力例]

※AtCoderテストケースより

[入力例]

9 atcoder

atoder

atcode

athqcoder

atcoder

tacoder

jttcoder

atoder

atceoder

atcoer

[出力例]

1 2 4 7 8 9

※AtCoderテストケースより

[入力例]

17 iroha

iroha

hiroha

ijroha

irsoha

iropha

irohia

irohab

roha

ioha

irha

iroa

iroh

zroha

izoha

irzha

iroza

irohz

[出力例]

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

[入力例]

25 beginner

eehccbkoonm

beginner

aiehciglanf

oahkoknoej

beganner

hbjgfdnfj

beginnerr

kcfkicnfgik

begnner

aljndjalikk

beginnner

mjojjddmoff

ihajahecfkdk

eginner

ccccmohebjjmk

kefohsdsdaghado

mjbclodfyguekdf

beginer

lgagnbecondbi

mgibkkakneeeffo

fhhoojmkjijctm

begannner

fggfjbnjbdddfju

cceefhmgiddhlqobi

biginner

[出力例]

2 5 7 9 11 14 18 25

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
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--)

int main(){
    
    // 1. 入力情報.
    int N;
    char s[22];
    scanf("%d %s", &N, s);
    
    // 2. 各数字の出現数は？
    vi cs(10, 0);
    rep(i, N) ++cs[s[i] - '0'];
    
    // 3. 全探索.
    int ans = 0;
    rep(i, 10000001){
        string t = to_string((LL)i * (LL)i);
        if(t.size() > N) break;
        while(t.size() < N) t = '0' + t;
        vi ct(10, 0);
        rep(j, N) ++ct[t[j] - '0'];
        if(cs == ct) ++ans;
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

int main(){

// 1. 入力情報.

int N;

char s[22];

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

// 2. 各数字の出現数は？

vi cs(10, 0);

rep(i, N) ++cs[s[i] - '0'];

// 3. 全探索.

int ans = 0;

rep(i, 10000001){

string t = to_string((LL)i * (LL)i);

if(t.size() > N) break;

while(t.size() < N) t = '0' + t;

vi ct(10, 0);

rep(j, N) ++ct[t[j] - '0'];

if(cs == ct) ++ans;

}

// 4. 出力.

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

return 0;

}

[入力例]
4
4320

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

[入力例]
3
010

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

[入力例]
13
8694027811503

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

[入力例]
5
57006

[出力例]
3

[入力例]
5
05920

[出力例]
3

[入力例]
8
112035

[出力例]
0

[入力例]
11
00123456789

[出力例]
260

[入力例]
14
00112234566789

[出力例]
2077
※整数 N, 文字列 S が, 問題文の制約条件から範囲外であるケース.

[入力例]

4320

[出力例]

※AtCoderテストケースより

[入力例]

010

[出力例]

※AtCoderテストケースより

[入力例]

8694027811503

[出力例]

840

※AtCoderテストケースより

[入力例]

57006

[出力例]

[入力例]

05920

[出力例]

[入力例]

112035

[出力例]

[入力例]

00123456789

[出力例]

260

[入力例]

00112234566789

[出力例]

2077

※整数 N, 文字列 S が, 問題文の制約条件から範囲外であるケース.

■参照サイト
日本レジストリサービス（JPRS）プログラミングコンテスト2023（AtCoder Beginner Contest 324）

2023年10月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題A (Replace C or Swap AB) ～問題B (Make Multiples) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 解説のロジックで, 計算可能であることが, 非常に不思議な印象を受けた.
3. 問題Bで, 苦手な動的計画法の訓練が積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7182
// C++20(GCC 12.2)
#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 main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        scanf("%d ", &N);
        char x[N + 1], y[N + 1];
        scanf("%s %s", x, y);
        string X(x), Y(y);
        
        // 2-2. 'C' の 位置をチェック.
        bool ok = true;
        vi yc;
        rep(j, N){
            if(Y[j] == 'C'){
                yc.pb(j);
                if(X[j] != 'C') ok = false;
            }
        }
        yc.pb(N);
        
        // 2-3. 例外.
        if(!ok){
            puts("No");
            continue;
        }
        
        // 2-4. 各区切りごとに判定.
        int s = 0;
        for(auto &e : yc){
            vi xa, xc, ya;
            repx(j, s, e){
                // 'A', 'C' の インデックスを集める.
                if(X[j] == 'A') xa.pb(j);
                if(X[j] == 'C') xc.pb(j);
                if(Y[j] == 'A') ya.pb(j);
            }
            
            // 次へ.
            s = e + 1;
            
            // 文字列 X に含まれる 'A' が 多い.
            if(xa.size() > ya.size()){
                ok = false;
                continue;
            }
            
            // 文字列 X に含まれる 'A' が 少ない.
            if(xa.size() + xc.size() < ya.size()){
                ok = false;
                continue;
            }
            
            // 文字列 X に 含まれる 'A' を 調整.
            int cur = -1;
            while(xa.size() < ya.size()) xa.pb(xc[++cur]);
            
            // sort.
            sort(all(xa));
            
            // 比較.
            rep(j, xa.size()) if(xa[j] > ya[j]) ok = false;
        }
        
        // 2-5. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7182

// C++20(GCC 12.2)

#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 main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 2-1. 各テストケース.

int N;

scanf("%d ", &N);

char x[N + 1], y[N + 1];

scanf("%s %s", x, y);

string X(x), Y(y);

// 2-2. 'C' の位置をチェック.

bool ok = true;

vi yc;

rep(j, N){

if(Y[j] == 'C'){

yc.pb(j);

if(X[j] != 'C') ok = false;

}

yc.pb(N);

// 2-3. 例外.

if(!ok){

puts("No");

continue;

}

// 2-4. 各区切りごとに判定.

int s = 0;

for(auto &e : yc){

vi xa, xc, ya;

repx(j, s, e){

// 'A', 'C' のインデックスを集める.

if(X[j] == 'A') xa.pb(j);

if(X[j] == 'C') xc.pb(j);

if(Y[j] == 'A') ya.pb(j);

}

// 次へ.

s = e + 1;

// 文字列 X に含まれる 'A' が多い.

if(xa.size() > ya.size()){

ok = false;

continue;

}

// 文字列 X に含まれる 'A' が少ない.

if(xa.size() + xc.size() < ya.size()){

ok = false;

continue;

}

// 文字列 X に含まれる 'A' を調整.

int cur = -1;

while(xa.size() < ya.size()) xa.pb(xc[++cur]);

// sort.

sort(all(xa));

// 比較.

rep(j, xa.size()) if(xa[j] > ya[j]) ok = false;

}

// 2-5. 出力.

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

}

return 0;

}

[入力例]
6
3 ABC ABC
1 C B
1 B C
2 AB BA
2 BA AB
3 CCB ABA

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

[入力例]
7
5 ABABA BABAB
5 ABCBC BBABA
5 CCCCC CBABC
5 BBAAA AAABB
5 AAABB BBAAA
5 ACACB BAACB
5 ACACB BBACA

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

[入力例]
10
1 C B
2 AB BA
3 ACB ACC
4 ACBC ABAA
5 ACAAC ABBAA
6 ACBBCC BCBAAB
7 ABCABCB BACABCB
8 BACCABAA BBAABBAA
9 ABCABCABC ABCBABAAA
10 ABCBCABBCA BACBABBAAA

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

[入力例]

3 ABC ABC

1 C B

1 B C

2 AB BA

2 BA AB

3 CCB ABA

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 ABABA BABAB

5 ABCBC BBABA

5 CCCCC CBABC

5 BBAAA AAABB

5 AAABB BBAAA

5 ACACB BAACB

5 ACACB BBACA

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 C B

2 AB BA

3 ACB ACC

4 ACBC ABAA

5 ACAAC ABBAA

6 ACBBCC BCBAAB

7 ABCABCB BACABCB

8 BACCABAA BBAABBAA

9 ABCABCABC ABCBABAAA

10 ABCBCABBCA BACBABBAAA

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc166/editorial/7183
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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 INF = 2e18;
LL A[202020], dp[202020][8];

int main(){
    
    // 1. 入力情報.
    int N;
    LL a, b, c;
    scanf("%d %lld %lld %lld", &N, &a, &b, &c);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. 事前準備.
    LL gAB = __gcd(a, b);
    LL gBC = __gcd(b, c);
    LL gCA = __gcd(c, a);
    LL gABC = __gcd(gAB, c);
    LL lAB = a / gAB * b;
    LL lBC = b / gBC * c;
    LL lCA = c / gCA * a;
    LL lABC = lAB / __gcd(lAB, lBC) * lBC;
    
    // 3. 倍数チェック.
    auto f = [&](LL n, LL a, LL b, LL c) -> int {
        int ret = 0;
        if(n % a == 0) ret |= 1;
        if(n % b == 0) ret |= 2;
        if(n % c == 0) ret |= 4;
        return ret;
    };
    
    // 4. dp更新.
    // -> 第二成分は, 以下のルールを, ORでとった結果をインデックスに指定.
    // a の 倍数 => 1
    // b の 倍数 => 2
    // c の 倍数 => 4
    rep(i, N + 1) rep(j, 8) dp[i][j] = INF;
    dp[0][0] = 0;
    rep(i, N){
        // 何もしない.
        vl op;
        op.pb(A[i]);
        
        // a の倍数.
        op.pb((A[i] + a - 1) / a * a);
        
        // b の倍数.
        op.pb((A[i] + b - 1) / b * b);
        
        // c の倍数.
        op.pb((A[i] + c - 1) / c * c);
        
        // lcm(a, b) の倍数.
        op.pb((A[i] + lAB - 1) / lAB * lAB);
        
        // lcm(b, c) の倍数.
        op.pb((A[i] + lBC - 1) / lBC * lBC);
        
        // lcm(c, a) の倍数.
        op.pb((A[i] + lCA - 1) / lCA * lCA);
        
        // lcm(a, b, c) の倍数.
        op.pb((A[i] + lABC - 1) / lABC * lABC);
        
        // 4-2. 各状態ごとに, dp更新.
        rep(j, 8){
            // 状態.
            int s = f(op[j], a, b, c);
            
            // 遷移(状態 k からの遷移先は, 状態 (s | k)).
            rep(k, 8){
                //  状態 s が 状態 k の 部分集合の場合.
                if((k & s) == s){
                    dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k]);
                    continue;
                }
                
                //  状態 s が 状態 k の 部分集合でない場合.
                // -> 操作回数(op[j] - A[i]) を 考慮する必要がある.
                dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k] + op[j] - A[i]);
            }
        }
    }
    
    // 5. 出力.
    printf("%lld\n", dp[N][7]);
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc166/editorial/7183

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

#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 INF = 2e18;

LL A[202020], dp[202020][8];

int main(){

// 1. 入力情報.

int N;

LL a, b, c;

scanf("%d %lld %lld %lld", &N, &a, &b, &c);

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

// 2. 事前準備.

LL gAB = __gcd(a, b);

LL gBC = __gcd(b, c);

LL gCA = __gcd(c, a);

LL gABC = __gcd(gAB, c);

LL lAB = a / gAB * b;

LL lBC = b / gBC * c;

LL lCA = c / gCA * a;

LL lABC = lAB / __gcd(lAB, lBC) * lBC;

// 3. 倍数チェック.

auto f = [&](LL n, LL a, LL b, LL c) -> int {

int ret = 0;

if(n % a == 0) ret |= 1;

if(n % b == 0) ret |= 2;

if(n % c == 0) ret |= 4;

return ret;

};

// 4. dp更新.

// -> 第二成分は, 以下のルールを, ORでとった結果をインデックスに指定.

// a の倍数 => 1

// b の倍数 => 2

// c の倍数 => 4

rep(i, N + 1) rep(j, 8) dp[i][j] = INF;

dp[0][0] = 0;

rep(i, N){

// 何もしない.

vl op;

op.pb(A[i]);

// a の倍数.

op.pb((A[i] + a - 1) / a * a);

// b の倍数.

op.pb((A[i] + b - 1) / b * b);

// c の倍数.

op.pb((A[i] + c - 1) / c * c);

// lcm(a, b) の倍数.

op.pb((A[i] + lAB - 1) / lAB * lAB);

// lcm(b, c) の倍数.

op.pb((A[i] + lBC - 1) / lBC * lBC);

// lcm(c, a) の倍数.

op.pb((A[i] + lCA - 1) / lCA * lCA);

// lcm(a, b, c) の倍数.

op.pb((A[i] + lABC - 1) / lABC * lABC);

// 4-2. 各状態ごとに, dp更新.

rep(j, 8){

// 状態.

int s = f(op[j], a, b, c);

// 遷移(状態 k からの遷移先は, 状態 (s | k)).

rep(k, 8){

// 状態 s が状態 k の部分集合の場合.

if((k & s) == s){

dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k]);

continue;

}

// 状態 s が状態 k の部分集合でない場合.

// -> 操作回数(op[j] - A[i]) を考慮する必要がある.

dp[i + 1][s | k] = min(dp[i + 1][s | k], dp[i][k] + op[j] - A[i]);

}

// 5. 出力.

printf("%lld\n", dp[N][7]);

return 0;

}

[入力例]
3 3 4 5
8 9 11

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

[入力例]
3 3 4 5
14 11 59

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

[入力例]
6 10 20 30
8 17 5 28 39 13

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

[入力例]
1 999997 999998 999999
123456789123456789

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

[入力例]
5 3 5 12
79 83 59 111 98

[出力例]
1

[入力例]
10 7 13 31
79 54 3 65 88 51 38 73 123 78

[出力例]
3

[入力例]
100 2022 2023 2024
2981 4736 3411 8068 10584 389 2608 9985 684 11830 172 7465 1191 11411 5304 7646 1078 2925 6130 5694 411 6933 11928 3835 2154 8225 5906 3628 2216 10621 3409 7540 10503 11075 10477 2243 6708 412 11670 4915 11346 2017 5480 12087 9548 8264 7241 1148 509 4393 4078 9366 11422 6376 9437 5159 2238 5775 6517 3782 9302 7383 2867 3699 8125 2688 3944 6273 9013 7226 2275 5231 804 5789 5393 5683 10756 2671 6203 233 4354 7395 12073 3130 8366 995 5174 387 10195 393 11277 4502 7461 10823 10032 9122 3627 3388 6191 2374

[出力例]
76

[入力例]
300 31415 92653 58979
95878 11042 74842 71977 8434 71909 4719 71599 5217 115259 40165 40023 73330 14444 43158 40431 69014 46069 3575 48234 111675 76805 119595 120108 48976 99043 115430 73364 68890 45442 46584 42696 16106 39204 56507 87346 71220 65320 28459 22532 120425 51503 123041 104636 86123 24584 31166 49145 51897 85658 112667 16456 46553 31285 40940 96766 112717 15172 82933 96285 35222 84816 105328 123100 98971 70784 81388 25100 35509 26758 84449 96854 115706 47557 93362 2091 50288 17447 119007 23813 56200 69886 28646 51117 69959 80929 48759 115929 102536 33102 101192 98958 33201 17629 31347 83487 100317 3081 115347 37719 97540 92178 110187 22675 88385 9638 93384 46722 69302 64303 84737 29052 109422 114147 67049 54142 89624 41003 63736 40848 44403 69120 74396 32825 31020 20000 13853 42940 110681 105457 122320 65108 27384 30617 53446 86286 39140 58644 33762 55193 110992 51746 73785 34559 13628 59067 56068 34389 108449 22996 3143 100820 85122 11175 85321 113463 31329 86003 114600 80049 78543 95285 70209 21235 79741 104283 404 102283 38151 97825 12259 8721 9886 111445 116702 94793 18335 72040 76328 26314 43995 109237 120473 110066 50128 118544 30007 93924 20116 119344 59713 118653 61229 5823 106022 58536 12814 110755 14807 82060 11455 31816 55103 44137 109484 73331 65863 97384 93461 70888 83773 78645 91691 26985 19185 26087 53981 43703 43333 101604 69706 18417 85362 64956 34082 117355 28363 92691 118224 79433 52262 19876 12428 89844 65977 57152 43797 73580 13914 108756 18039 24535 21199 64947 9724 121639 88604 64034 101861 55770 27244 6891 74806 113840 68011 76634 51062 13570 106890 121794 89934 32532 45758 17043 111584 31058 60756 36975 62134 98955 93366 56236 45379 119759 97802 75866 58850 30659 90726 21983 3572 3959 14085 85735 64424 112289 36558 10951 19387 53368 58845 11335 106045 93872 13491 18563 42606 84514 99811 10140

[出力例]
672

[入力例]

3 3 4 5

8 9 11

[出力例]

※AtCoderのテストケースより

[入力例]

3 3 4 5

14 11 59

[出力例]

※AtCoderのテストケースより

[入力例]

6 10 20 30

8 17 5 28 39 13

[出力例]

※AtCoderのテストケースより

[入力例]

1 999997 999998 999999

123456789123456789

[出力例]

876537210887543205

※AtCoderのテストケースより

[入力例]

5 3 5 12

79 83 59 111 98

[出力例]

[入力例]

10 7 13 31

79 54 3 65 88 51 38 73 123 78

[出力例]

[入力例]

100 2022 2023 2024

2981 4736 3411 8068 10584 389 2608 9985 684 11830 172 7465 1191 11411 5304 7646 1078 2925 6130 5694 411 6933 11928 3835 2154 8225 5906 3628 2216 10621 3409 7540 10503 11075 10477 2243 6708 412 11670 4915 11346 2017 5480 12087 9548 8264 7241 1148 509 4393 4078 9366 11422 6376 9437 5159 2238 5775 6517 3782 9302 7383 2867 3699 8125 2688 3944 6273 9013 7226 2275 5231 804 5789 5393 5683 10756 2671 6203 233 4354 7395 12073 3130 8366 995 5174 387 10195 393 11277 4502 7461 10823 10032 9122 3627 3388 6191 2374

[出力例]

[入力例]

300 31415 92653 58979

95878 11042 74842 71977 8434 71909 4719 71599 5217 115259 40165 40023 73330 14444 43158 40431 69014 46069 3575 48234 111675 76805 119595 120108 48976 99043 115430 73364 68890 45442 46584 42696 16106 39204 56507 87346 71220 65320 28459 22532 120425 51503 123041 104636 86123 24584 31166 49145 51897 85658 112667 16456 46553 31285 40940 96766 112717 15172 82933 96285 35222 84816 105328 123100 98971 70784 81388 25100 35509 26758 84449 96854 115706 47557 93362 2091 50288 17447 119007 23813 56200 69886 28646 51117 69959 80929 48759 115929 102536 33102 101192 98958 33201 17629 31347 83487 100317 3081 115347 37719 97540 92178 110187 22675 88385 9638 93384 46722 69302 64303 84737 29052 109422 114147 67049 54142 89624 41003 63736 40848 44403 69120 74396 32825 31020 20000 13853 42940 110681 105457 122320 65108 27384 30617 53446 86286 39140 58644 33762 55193 110992 51746 73785 34559 13628 59067 56068 34389 108449 22996 3143 100820 85122 11175 85321 113463 31329 86003 114600 80049 78543 95285 70209 21235 79741 104283 404 102283 38151 97825 12259 8721 9886 111445 116702 94793 18335 72040 76328 26314 43995 109237 120473 110066 50128 118544 30007 93924 20116 119344 59713 118653 61229 5823 106022 58536 12814 110755 14807 82060 11455 31816 55103 44137 109484 73331 65863 97384 93461 70888 83773 78645 91691 26985 19185 26087 53981 43703 43333 101604 69706 18417 85362 64956 34082 117355 28363 92691 118224 79433 52262 19876 12428 89844 65977 57152 43797 73580 13914 108756 18039 24535 21199 64947 9724 121639 88604 64034 101861 55770 27244 6891 74806 113840 68011 76634 51062 13570 106890 121794 89934 32532 45758 17043 111584 31058 60756 36975 62134 98955 93366 56236 45379 119759 97802 75866 58850 30659 90726 21983 3572 3959 14085 85735 64424 112289 36558 10951 19387 53368 58845 11335 106045 93872 13491 18563 42606 84514 99811 10140

[出力例]

672

■参照サイト
AtCoder Regular Contest 166

2023年10月17日

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

C++の練習を兼ねて, AtCoder Grand Contest 045 の問題B (01 Unbalanced) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 個人的には, 解説のロジックで, 計算可能であることが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc045/editorial.pdf
// C++20(GCC 12.2)
#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--)
const int INF = 2020202020;
int cum[1010101], rMaxCum[1010101], u1[1010101], u1Cum[1010101], u2[1010101], u2Cum[1010101];

int main(){
    
    // 1. 入力情報.
    char c[1010101];
    scanf("%s", c);
    string s(c);
    int n = s.size();
    
    // 2. 事前準備(以降, 解説通り).
    // 2-1. 初期化.
    rep(i, n) u1[i] = u2[i] = (s[i] == '1') ? +1 : -1;
    
    // 2-2. 累積和(左から計算).
    // -> cum[0] = 0 も 考慮する.
    rep(i, n) cum[i + 1] = (s[i] == '1') ? cum[i] + 1 : cum[i] - 1;
    
    // 2-3. 累積和の最大値(右から計算).
    rep(i, 1010101) rMaxCum[i] = -INF;
    repr(i, n, 0) rMaxCum[i] = max(rMaxCum[i + 1], cum[i]);
    
    // 3. z.
    int z = -INF;
    rep(i, n + 1) z = max(z, cum[i]);
    
    // 4. 貪欲アルゴリズム.
    // 4-1. z 基準.
    int cnt = 0;
    rep(i, n){
        // 次へ.
        if(s[i] != '?') continue;
        
        // '?' を '1' に 変更できるか？
        // 累積和(左側).
        if(cum[i + 1] + 2 * (cnt + 1) > z) continue;
        
        // 累積和(右側).
        if(rMaxCum[i + 1] + 2 * (cnt + 1) > z) continue;
        
        // '?' を '1' に 変更.
        u1[i] = +1;
        
        // インクリメント.
        ++cnt;
    }
    
    // 4-2. (z + 1) 基準.
    cnt = 0;
    rep(i, n){
        // 次へ.
        if(s[i] != '?') continue;
        
        // '?' を '1' に 変更できるか？
        // 累積和(左側).
        if(cum[i + 1] + 2 * (cnt + 1) > z + 1) continue;
        
        // 累積和(右側).
        if(rMaxCum[i + 1] + 2 * (cnt + 1) > z + 1) continue;
        
        // '?' を '1' に 変更.
        u2[i] = +1;
        
        // インクリメント.
        ++cnt;
    }
    
    // 5. 計算準備(アンバランス度).
    // 5-1. f(z).
    int f1 = INF;
    rep(i, n) u1Cum[i + 1] = u1Cum[i] + u1[i];
    rep(i, n + 1) f1 = min(f1, u1Cum[i]);
    
    // 5-2. f(z + 1).
    int f2 = INF;
    rep(i, n) u2Cum[i + 1] = u2Cum[i] + u2[i];
    rep(i, n + 1) f2 = min(f2, u2Cum[i]);
    
    // 6. 出力.
    printf("%d\n", min(z - f1, z + 1 - f2));
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/agc045/editorial.pdf

// C++20(GCC 12.2)

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

const int INF = 2020202020;

int cum[1010101], rMaxCum[1010101], u1[1010101], u1Cum[1010101], u2[1010101], u2Cum[1010101];

int main(){

// 1. 入力情報.

char c[1010101];

scanf("%s", c);

string s(c);

int n = s.size();

// 2. 事前準備(以降, 解説通り).

// 2-1. 初期化.

rep(i, n) u1[i] = u2[i] = (s[i] == '1') ? +1 : -1;

// 2-2. 累積和(左から計算).

// -> cum[0] = 0 も考慮する.

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

// 2-3. 累積和の最大値(右から計算).

rep(i, 1010101) rMaxCum[i] = -INF;

repr(i, n, 0) rMaxCum[i] = max(rMaxCum[i + 1], cum[i]);

// 3. z.

int z = -INF;

rep(i, n + 1) z = max(z, cum[i]);

// 4. 貪欲アルゴリズム.

// 4-1. z 基準.

int cnt = 0;

rep(i, n){

// 次へ.

if(s[i] != '?') continue;

// '?' を '1' に変更できるか？

// 累積和(左側).

if(cum[i + 1] + 2 * (cnt + 1) > z) continue;

// 累積和(右側).

if(rMaxCum[i + 1] + 2 * (cnt + 1) > z) continue;

// '?' を '1' に変更.

u1[i] = +1;

// インクリメント.

++cnt;

}

// 4-2. (z + 1) 基準.

cnt = 0;

rep(i, n){

// 次へ.

if(s[i] != '?') continue;

// '?' を '1' に変更できるか？

// 累積和(左側).

if(cum[i + 1] + 2 * (cnt + 1) > z + 1) continue;

// 累積和(右側).

if(rMaxCum[i + 1] + 2 * (cnt + 1) > z + 1) continue;

// '?' を '1' に変更.

u2[i] = +1;

// インクリメント.

++cnt;

}

// 5. 計算準備(アンバランス度).

// 5-1. f(z).

int f1 = INF;

rep(i, n) u1Cum[i + 1] = u1Cum[i] + u1[i];

rep(i, n + 1) f1 = min(f1, u1Cum[i]);

// 5-2. f(z + 1).

int f2 = INF;

rep(i, n) u2Cum[i + 1] = u2Cum[i] + u2[i];

rep(i, n + 1) f2 = min(f2, u2Cum[i]);

// 6. 出力.

printf("%d\n", min(z - f1, z + 1 - f2));

return 0;

}

[入力例]
0??

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

[入力例]
0??0

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

[入力例]
??00????0??0????0?0??00??1???11?1?1???1?11?111???1

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

[入力例]
01??10?1?0

[出力例]
2

[入力例]
10?0??101??

[出力例]
1

[入力例]
0010??0???01010?00110?101011?0?101111?0??0?111?010

[出力例]
4

[入力例]
??111110100000000???1100??0???11110???0000??1100111110000111??11??1110111111??001111?111100111110000

[出力例]
16

[入力例]
00?11??011111?0101000??11???01??10?10??0?1?0011??1?00?00???10?0011?0?1001011?110000??0010?001010?1??1110?01011?00111?10?1?1??00?10?00??111?000?11?001?01??11?0100?00111???1???????1?001011011?0?0?1?0?0?

[出力例]
5

[入力例]
010?00??10?001????1111??0110111?101?0111001?1?10?11?1??1?01?10?0100000001?101??1?1?????00????1?1??00?0111?1?11?000?011????0000100001010?110?0??100110?0001100???100?000111?00?110?0?10011?011010??01?0001?01??1001010??1???1?00110?10000?0100????1001?110101?1?11000?000011010101?????01?01110???1?010110011101?000??1?010110100?0?1?10101001?01???11100?110100110?11?11100100101?101110?11110?010?1??0?00??0010001?010??10?1000?01?1010???00000?111?1??101??00100??0???1???0001011001101010?0011?1111?0??1001110?0?1?1?1?1??00?0??100?001011??10??10010???1??100?0?0?0?1110?00?111??101???11011000001?100?1??1000?111?1?01110101101?1?1??011?010?1?01011?11??001?110?10?10?1011?0?1?10????110?100100100100?0??00101???111000?10?011?0?0?????1?1010??0011000??0???01?10?1?1001?00??0??0?011011?00??10?011??1?100110?1??011010?101?1??10011?111100??111101111?1???1?101?1?110?1?01101?1???1011101?111001?0????0??011?0?000???01?11?001?011?0?11001001101?0??0??0?1011?1111???101100?1?01??0110101011?1??10?1????00???01?1?11000100?10?0??

[出力例]
8

[入力例]

0??

[出力例]

※AtCoderのテストケースより

[入力例]

0??0

[出力例]

※AtCoderのテストケースより

[入力例]

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

[出力例]

※AtCoderのテストケースより

[入力例]

01??10?1?0

[出力例]

[入力例]

10?0??101??

[出力例]

[入力例]

0010??0???01010?00110?101011?0?101111?0??0?111?010

[出力例]

[入力例]

??111110100000000???1100??0???11110???0000??1100111110000111??11??1110111111??001111?111100111110000

[出力例]

[入力例]

00?11??011111?0101000??11???01??10?10??0?1?0011??1?00?00???10?0011?0?1001011?110000??0010?001010?1??1110?01011?00111?10?1?1??00?10?00??111?000?11?001?01??11?0100?00111???1???????1?001011011?0?0?1?0?0?

[出力例]

[入力例]

010?00??10?001????1111??0110111?101?0111001?1?10?11?1??1?01?10?0100000001?101??1?1?????00????1?1??00?0111?1?11?000?011????0000100001010?110?0??100110?0001100???100?000111?00?110?0?10011?011010??01?0001?01??1001010??1???1?00110?10000?0100????1001?110101?1?11000?000011010101?????01?01110???1?010110011101?000??1?010110100?0?1?10101001?01???11100?110100110?11?11100100101?101110?11110?010?1??0?00??0010001?010??10?1000?01?1010???00000?111?1??101??00100??0???1???0001011001101010?0011?1111?0??1001110?0?1?1?1?1??00?0??100?001011??10??10010???1??100?0?0?0?1110?00?111??101???11011000001?100?1??1000?111?1?01110101101?1?1??011?010?1?01011?11??001?110?10?10?1011?0?1?10????110?100100100100?0??00101???111000?10?011?0?0?????1?1010??0011000??0???01?10?1?1001?00??0??0?011011?00??10?011??1?100110?1??011010?101?1??10011?111100??111101111?1???1?101?1?110?1?01101?1???1011101?111001?0????0??011?0?000???01?11?001?011?0?11001001101?0??0??0?1011?1111???101100?1?01??0110101011?1??10?1????00???01?1?11000100?10?0??

[出力例]

■参照サイト
AtCoder Grand Contest 045

2023年10月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 321 の問題C (321-like Searcher) ～問題D (Set Menu) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題C で, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++20(GCC 12.2)
#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--)

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    set<LL> st;
    auto dfs = [&](auto&& self, LL d){
        // 2-1. 保存.
        st.insert(d);
        
        // 2-2. 終了条件.
        int r = d % 10;
        if(r == 0) return;
        
        // 2-3. 追加(1 の 位).
        rep(i, r) self(self, 10 * d + i);
    };
    
    // 3. 321-like Number 生成(1022個).
    repx(i, 1, 10) dfs(dfs, i);
    // printf("st.size()=%d\n", st.size());
    
    // 4. K 番目は？
    LL ans = 0;
    for(auto &x : st){
        ans = x;
        if(--K == 0) break;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

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

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. dfs.

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

set<LL> st;

auto dfs = [&](auto&& self, LL d){

// 2-1. 保存.

st.insert(d);

// 2-2. 終了条件.

int r = d % 10;

if(r == 0) return;

// 2-3. 追加(1 の位).

rep(i, r) self(self, 10 * d + i);

};

// 3. 321-like Number 生成(1022個).

repx(i, 1, 10) dfs(dfs, i);

// printf("st.size()=%d\n", st.size());

// 4. K 番目は？

LL ans = 0;

for(auto &x : st){

ans = x;

if(--K == 0) break;

}

// 5. 出力.

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

return 0;

}

[入力例]
15

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

[入力例]
321

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

[入力例]
777

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

[入力例]
20

[出力例]
50

[入力例]
100

[出力例]
750

[入力例]
753

[出力例]
975421

[入力例]
1022

[出力例]
9876543210

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

321

[出力例]

9610

※AtCoderテストケースより

[入力例]

777

[出力例]

983210

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

100

[出力例]

750

[入力例]

753

[出力例]

975421

[入力例]

1022

[出力例]

9876543210

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#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()

int main(){
    
    // 1. 入力情報.
    int N, M, P;
    scanf("%d %d %d", &N, &M, &P);
    vl a(N), b(M);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, M) scanf("%lld", &b[i]);
    
    // 2. sort.
    sort(all(a));
    sort(all(b));
    
    // 3. 累積和.
    vl bCum(M + 1, 0);
    rep(i, M) bCum[i + 1] = bCum[i] + b[i];
    
    // 4. 定食の価格の総和.
    LL ans = 0;
    rep(i, N){
        int at = lower_bound(all(b), P - a[i]) - b.begin();
        ans += bCum[at] + a[i] * at;
        ans += (LL)P * (LL)(M - at);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

int main(){

// 1. 入力情報.

int N, M, P;

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

vl a(N), b(M);

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

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

// 2. sort.

sort(all(a));

sort(all(b));

// 3. 累積和.

vl bCum(M + 1, 0);

rep(i, M) bCum[i + 1] = bCum[i] + b[i];

// 4. 定食の価格の総和.

LL ans = 0;

rep(i, N){

int at = lower_bound(all(b), P - a[i]) - b.begin();

ans += bCum[at] + a[i] * at;

ans += (LL)P * (LL)(M - at);

}

// 5. 出力.

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

return 0;

}

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

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

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

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

[入力例]
7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

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

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

[出力例]
150

[入力例]
5 3 10
11 12 13 14 15
16 17 18

[出力例]
150

[入力例]
12 15 100000
64871 99252 11934 88203 110776 8275 1116 81869 16238 6552 17514 71649
47327 17873 111561 24780 17782 18870 51552 44546 113673 91382 32723 10999 103361 53973 64043

[出力例]
14227081

[入力例]
30 50 2500
2453 1367 2387 1093 613 1649 1990 910 101 913 1745 1644 2016 1796 1518 2112 2492 1139 2145 703 2225 959 2408 691 1529 864 821 951 2030 2364
1319 857 921 1939 2203 1884 1799 565 2018 1595 12 1638 996 1197 740 1038 2449 1073 1580 2449 1871 870 111 1576 2410 769 1711 2475 1634 2354 1884 1919 943 446 385 803 1618 348 358 1904 2045 2310 1782 1419 1126 1067 1535 64 2161 121

[出力例]
3402202

[入力例]
100 120 33333
14021 11206 4523 11383 704 21471 18313 12778 19149 10164 17165 10474 9934 2338 7657 12326 24422 6017 7482 7051 11148 13353 9444 16507 22077 21448 71255 20038 11640 17509 20149 7140 11280 327 22036 7580 8152 8686 15626 2617 21718 24964 9124 2813 13294 7855 24045 33238 13222 17043 13099 13126 18103 11068 22719 18441 1408 3640 7297 17074 4026 19471 20520 16667 10446 10834 12555 23445 1400 9644 24859 5472 222 23622 5946 23745 1440 1177 11130 8323 6627 24306 2669 229 18585 22270 5108 3641 4965 7130 11704 12396 19223 20115 17845 15612 10896 28 16299 12696
5280 16707 19516 17340 17379 56449 5037 11102 13189 13580 21477 22974 4607 17792 23474 23608 13913 18909 16060 3294 24606 6395 10719 10251 5608 22507 468 14804 8974 1357 4676 2748 111 18762 22817 9519 22569 14121 2198 13482 8642 4809 12622 23327 21821 6910 7153 19971 88783 4436 2067 20006 24267 9989 12288 2916 897 13812 205 14842 3604 6621 13595 932 11239 2238 176 20816 52247 12707 12895 71897 23032 8565 158 11641 21871 15146 6251 14621 2671 19909 21476 15272 5099 18902 16681 12731 3174 3155 4544 11628 23976 18968 3208 4721 24082 13040 4900 5015 5437 133 23114 20152 24286 8952 7540 11692 19253 20774 22949 20821 21565 3656 12576 6234 2845 1739 6693 728

[出力例]
282120162

[入力例]

2 2 7

3 5

6 1

[出力例]

※AtCoderテストケースより

[入力例]

1 3 2

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

7 12 25514963

2436426 24979445 61648772 23690081 33933447 76190629 62703497

11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

[出力例]

2115597124

※AtCoderテストケースより

[入力例]

5 3 123

1 2 3 4 5

6 7 8

[出力例]

150

[入力例]

5 3 10

11 12 13 14 15

16 17 18

[出力例]

150

[入力例]

12 15 100000

64871 99252 11934 88203 110776 8275 1116 81869 16238 6552 17514 71649

47327 17873 111561 24780 17782 18870 51552 44546 113673 91382 32723 10999 103361 53973 64043

[出力例]

14227081

[入力例]

30 50 2500

2453 1367 2387 1093 613 1649 1990 910 101 913 1745 1644 2016 1796 1518 2112 2492 1139 2145 703 2225 959 2408 691 1529 864 821 951 2030 2364

1319 857 921 1939 2203 1884 1799 565 2018 1595 12 1638 996 1197 740 1038 2449 1073 1580 2449 1871 870 111 1576 2410 769 1711 2475 1634 2354 1884 1919 943 446 385 803 1618 348 358 1904 2045 2310 1782 1419 1126 1067 1535 64 2161 121

[出力例]

3402202

[入力例]

100 120 33333

14021 11206 4523 11383 704 21471 18313 12778 19149 10164 17165 10474 9934 2338 7657 12326 24422 6017 7482 7051 11148 13353 9444 16507 22077 21448 71255 20038 11640 17509 20149 7140 11280 327 22036 7580 8152 8686 15626 2617 21718 24964 9124 2813 13294 7855 24045 33238 13222 17043 13099 13126 18103 11068 22719 18441 1408 3640 7297 17074 4026 19471 20520 16667 10446 10834 12555 23445 1400 9644 24859 5472 222 23622 5946 23745 1440 1177 11130 8323 6627 24306 2669 229 18585 22270 5108 3641 4965 7130 11704 12396 19223 20115 17845 15612 10896 28 16299 12696

5280 16707 19516 17340 17379 56449 5037 11102 13189 13580 21477 22974 4607 17792 23474 23608 13913 18909 16060 3294 24606 6395 10719 10251 5608 22507 468 14804 8974 1357 4676 2748 111 18762 22817 9519 22569 14121 2198 13482 8642 4809 12622 23327 21821 6910 7153 19971 88783 4436 2067 20006 24267 9989 12288 2916 897 13812 205 14842 3604 6621 13595 932 11239 2238 176 20816 52247 12707 12895 71897 23032 8565 158 11641 21871 15146 6251 14621 2671 19909 21476 15272 5099 18902 16681 12731 3174 3155 4544 11628 23976 18968 3208 4721 24082 13040 4900 5015 5437 133 23114 20152 24286 8952 7540 11692 19253 20774 22949 20821 21565 3656 12576 6234 2845 1739 6693 728

[出力例]

282120162

■参照サイト
サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）

2023年10月9日2023年10月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 323 の問題C (World Tour Finals) ～問題D (Merge Slimes) を解いてみた.

■感想.
1. 問題C, Dは, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, スライム合成の繰り返す処理が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
#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 main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vi a(M);
    rep(i, M) scanf("%d", &a[i]);
    vs s(N);
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string b(c);
        s[i] = b;
    }
    
    // 2. 各プレイヤーの現在の総合得点は？
    vi scores(N, 0);
    rep(i, N){
        scores[i] = i + 1;
        rep(j, M) scores[i] += a[j] * (s[i][j] == 'o');
    }
    
    // 3. 各プレイヤーが解いてない問題の各得点は？
    vvi notSolved(N);
    rep(i, N){
        rep(j, M) if(s[i][j] == 'x') notSolved[i].pb(a[j]);
        sort(all(notSolved[i]));
        reverse(all(notSolved[i]));
    }
    
    // 4. 他プレイヤーの現在の総合得点の最大値は？
    vi maxScoreOnOtherPlayers(N, 0);
    rep(i, N){
        int maxScore = 0;
        rep(j, N) if(i != j) maxScore = max(maxScore, scores[j]);
        maxScoreOnOtherPlayers[i] = maxScore;
    }
    
    // 5. 出力.
    rep(i, N){
        int ans = 0;
        int cur = scores[i];
        for(auto &p : notSolved[i]){
            if(maxScoreOnOtherPlayers[i] >= cur){
                ++ans;
                cur += p;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using vs = vector<string>;

#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 main(){

// 1. 入力情報.

int N, M;

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

vi a(M);

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

vs s(N);

rep(i, N){

char c[202];

scanf("%s", c);

string b(c);

s[i] = b;

}

// 2. 各プレイヤーの現在の総合得点は？

vi scores(N, 0);

rep(i, N){

scores[i] = i + 1;

rep(j, M) scores[i] += a[j] * (s[i][j] == 'o');

}

// 3. 各プレイヤーが解いてない問題の各得点は？

vvi notSolved(N);

rep(i, N){

rep(j, M) if(s[i][j] == 'x') notSolved[i].pb(a[j]);

sort(all(notSolved[i]));

reverse(all(notSolved[i]));

}

// 4. 他プレイヤーの現在の総合得点の最大値は？

vi maxScoreOnOtherPlayers(N, 0);

rep(i, N){

int maxScore = 0;

rep(j, N) if(i != j) maxScore = max(maxScore, scores[j]);

maxScoreOnOtherPlayers[i] = maxScore;

}

// 5. 出力.

rep(i, N){

int ans = 0;

int cur = scores[i];

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

if(maxScoreOnOtherPlayers[i] >= cur){

++ans;

cur += p;

}

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

}

return 0;

}

[入力例]
3 4
1000 500 700 2000
xxxo
ooxx
oxox

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

[入力例]
5 5
1000 1500 2000 2000 2500
xxxxx
oxxxx
xxxxx
oxxxx
oxxxx

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

[入力例]
7 8
500 500 500 500 500 500 500 500
xxxxxxxx
oxxxxxxx
ooxxxxxx
oooxxxxx
ooooxxxx
oooooxxx
ooooooxx

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

[入力例]
3 5
500 500 1000 1000 2500
xxxxo
xxxox
xooxx

[出力例]
0
1
1

[入力例]
5 7
500 500 500 500 1000 1000 1500
ooxooxx
xoxxxxx
xxxxxxx
xxooxox
ooxxoxo

[出力例]
1
3
4
2
0

[入力例]

3 4

1000 500 700 2000

xxxo

ooxx

oxox

[出力例]

※AtCoderテストケースより

[入力例]

5 5

1000 1500 2000 2000 2500

xxxxx

oxxxx

xxxxx

oxxxx

[出力例]

※AtCoderテストケースより

[入力例]

7 8

500 500 500 500 500 500 500 500

xxxxxxxx

oxxxxxxx

ooxxxxxx

oooxxxxx

ooooxxxx

oooooxxx

ooooooxx

[出力例]

※AtCoderテストケースより

[入力例]

3 5

500 500 1000 1000 2500

xxxxo

xxxox

xooxx

[出力例]

[入力例]

5 7

500 500 500 500 1000 1000 1500

ooxooxx

xoxxxxx

xxxxxxx

xxooxox

ooxxoxo

[出力例]

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

// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using P = pair<LL, LL>;
using vp = vector<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 all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp slimes(N);
    rep(i, N) scanf("%lld %lld", &slimes[i].a, &slimes[i].b);
    
    // 2. sort.
    sort(all(slimes));
    
    // 3. スライムの合成.
    map<LL, LL> m;
    rep(i, N){
        // 初期化(スライムのサイズ, 匹数).
        LL slimeSize = slimes[i].a;
        LL slimeCount = slimes[i].b;
        
        // 前回以前を反映.
        if(m.count(slimes[i].a)) slimeCount += m[slimes[i].a];
        else                     m[slimes[i].a] = slimes[i].b;
        
        // 合成対象のスライム匹数が, 0匹になるまで, 繰り返し.
        while(slimeCount){
            // スライム出現.
            m[slimeSize * 2] += slimeCount / 2;
            
            // スライム消滅.
            m[slimeSize] = slimeCount % 2;
            
            // 更新(スライムのサイズ, 匹数).
            slimeSize *= 2;
            slimeCount = m[slimeSize];
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    for(auto &x : m) ans += x.b;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using P = pair<LL, LL>;

using vp = vector<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 all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp slimes(N);

rep(i, N) scanf("%lld %lld", &slimes[i].a, &slimes[i].b);

// 2. sort.

sort(all(slimes));

// 3. スライムの合成.

map<LL, LL> m;

rep(i, N){

// 初期化(スライムのサイズ, 匹数).

LL slimeSize = slimes[i].a;

LL slimeCount = slimes[i].b;

// 前回以前を反映.

if(m.count(slimes[i].a)) slimeCount += m[slimes[i].a];

else m[slimes[i].a] = slimes[i].b;

// 合成対象のスライム匹数が, 0匹になるまで, 繰り返し.

while(slimeCount){

// スライム出現.

m[slimeSize * 2] += slimeCount / 2;

// スライム消滅.

m[slimeSize] = slimeCount % 2;

// 更新(スライムのサイズ, 匹数).

slimeSize *= 2;

slimeCount = m[slimeSize];

}

// 4. 集計.

LL ans = 0;

for(auto &x : m) ans += x.b;

// 5. 出力.

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

return 0;

}

[入力例]
3
3 3
5 1
6 1

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

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

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

[入力例]
1
1000000000 1000000000

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

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

[出力例]
5

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

[出力例]
15

[入力例]
20
19 81
8 52
7 104
3 94
14 26
16 47
1 46
6 108
11 113
20 52
5 105
15 5
18 95
17 20
10 121
4 53
12 65
9 14
2 15
13 96

[出力例]
36

[入力例]
30
14 929755
10 812758
26 405849
5 775226
19 916477
13 786895
17 119046
30 492339
7 429931
1 267396
11 892144
24 812785
20 480207
2 516830
25 749069
18 430046
6 653612
22 1122701
28 336222
29 1020713
27 203310
12 441113
21 729150
9 414670
8 432888
23 510440
15 250019
4 956264
16 239998
3 783368

[出力例]
157

[入力例]
100
63 802
2 1186
54 547
22 466
95 387
41 615
90 1071
76 1087
74 1017
27 877
30 704
86 1126
82 286
68 348
37 30
11 128
100 824
48 720
1 870
9 794
38 188
17 646
24 844
99 8
23 1017
18 209
8 661
83 243
50 766
87 1030
65 406
66 632
53 299
69 843
4 232
29 152
81 819
85 1064
97 80
14 526
71 470
75 816
13 22
42 217
33 188
93 898
10 721
40 780
44 1078
84 31
98 468
60 816
45 585
91 404
61 1176
28 389
36 913
51 472
94 1203
88 472
57 1130
73 1183
12 788
62 691
5 1056
43 330
46 406
19 708
67 1213
55 983
96 30
52 817
21 1049
32 1178
92 1202
70 19
6 373
35 450
25 112
15 434
72 858
3 706
79 238
26 312
34 521
49 112
56 51
7 474
78 631
31 242
59 231
20 1049
80 678
64 906
39 286
58 106
77 473
89 233
16 1168
47 591

[出力例]
278

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

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

[入力例]

3 3

5 1

6 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

2 1

3 1

[出力例]

※AtCoderテストケースより

[入力例]

1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

1 3

2 2

3 1

4 5

8 2

[出力例]

[入力例]

11 4

3 1

12 9

2 10

10 10

5 2

7 6

15 2

24 3

8 1

[出力例]

[入力例]

19 81

8 52

7 104

3 94

14 26

16 47

1 46

6 108

11 113

20 52

5 105

15 5

18 95

17 20

10 121

4 53

12 65

9 14

2 15

13 96

[出力例]

[入力例]

14 929755

10 812758

26 405849

5 775226

19 916477

13 786895

17 119046

30 492339

7 429931

1 267396

11 892144

24 812785

20 480207

2 516830

25 749069

18 430046

6 653612

22 1122701

28 336222

29 1020713

27 203310

12 441113

21 729150

9 414670

8 432888

23 510440

15 250019

4 956264

16 239998

3 783368

[出力例]

157

[入力例]

100

63 802

2 1186

54 547

22 466

95 387

41 615

90 1071

76 1087

74 1017

27 877

30 704

86 1126

82 286

68 348

37 30

11 128

100 824

48 720

1 870

9 794

38 188

17 646

24 844

99 8

23 1017

18 209

8 661

83 243

50 766

87 1030

65 406

66 632

53 299

69 843

4 232

29 152

81 819

85 1064

97 80

14 526

71 470

75 816

13 22

42 217

33 188

93 898

10 721

40 780

44 1078

84 31

98 468

60 816

45 585

91 404

61 1176

28 389

36 913

51 472

94 1203

88 472

57 1130

73 1183

12 788

62 691

5 1056

43 330

46 406

19 708

67 1213

55 983

96 30

52 817

21 1049

32 1178

92 1202

70 19

6 373

35 450

25 112

15 434

72 858

3 706

79 238

26 312

34 521

49 112

56 51

7 474

78 631

31 242

59 231

20 1049

80 678

64 906

39 286

58 106

77 473

89 233

16 1168

47 591

[出力例]

278

■参照サイト
ユニークビジョンプログラミングコンテスト2023 秋 (AtCoder Beginner Contest 323)

2023年10月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題D (Sum of SCC) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6696
// 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 C[33][33], dp[33][33][33 * 33];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. パスカルの三角形.
    C[0][0] = 1;
    repx(i, 1, 33){
        rep(j, 33){
            C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= MOD;
        }
    }
    
    // 3. dp更新.
    dp[0][0][0] = 1;
    rep(n, N){
        rep(i, n + 1){
            rep(j, M + 1){
                // 3-1. 頂点 n + 1 を A に 追加.
                rep(k, i + 1){
                    dp[n + 1][i + 1][j + k] += dp[n][i][j] * C[i][k];
                    dp[n + 1][i + 1][j + k] %= MOD;
                }
                
                // 3-2. 頂点 n + 1 を B に 追加.
                rep(k, n - i + 1){
                    dp[n + 1][i][j + i + k] += dp[n][i][j] * C[n - i][k];
                    dp[n + 1][i][j + i + k] %= MOD;
                }
            }
        }
    }
    
    // 4. 集計.
    LL ans = 0;
    repx(i, 1, N + 1){
        ans += dp[N][i][M];
        ans %= MOD;
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6696

// 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 C[33][33], dp[33][33][33 * 33];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. パスカルの三角形.

C[0][0] = 1;

repx(i, 1, 33){

rep(j, 33){

C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];

C[i][j] %= MOD;

}

// 3. dp更新.

dp[0][0][0] = 1;

rep(n, N){

rep(i, n + 1){

rep(j, M + 1){

// 3-1. 頂点 n + 1 を A に追加.

rep(k, i + 1){

dp[n + 1][i + 1][j + k] += dp[n][i][j] * C[i][k];

dp[n + 1][i + 1][j + k] %= MOD;

}

// 3-2. 頂点 n + 1 を B に追加.

rep(k, n - i + 1){

dp[n + 1][i][j + i + k] += dp[n][i][j] * C[n - i][k];

dp[n + 1][i][j + i + k] %= MOD;

}

// 4. 集計.

LL ans = 0;

repx(i, 1, N + 1){

ans += dp[N][i][M];

ans %= MOD;

}

// 5. 出力.

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

return 0;

}

[入力例]
3 1

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

[入力例]
6 2

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

[入力例]
25 156

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

[入力例]
1 0

[出力例]
1

[入力例]
2 1

[出力例]
2

[入力例]
5 1

[出力例]
34

[入力例]
7 5

[出力例]
33909

[入力例]
10 15

[出力例]
754406117

[入力例]
20 100

[出力例]
979610315

[入力例]
30 345

[出力例]
807062684

[入力例]

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

6 2

[出力例]

300

※AtCoderのテストケースより

[入力例]

25 156

[出力例]

902739687

※AtCoderのテストケースより

[入力例]

1 0

[出力例]

[入力例]

2 1

[出力例]

[入力例]

5 1

[出力例]

[入力例]

7 5

[出力例]

33909

[入力例]

10 15

[出力例]

754406117

[入力例]

20 100

[出力例]

979610315

[入力例]

30 345

[出力例]

807062684

■参照サイト
AtCoder Regular Contest 163

2023年9月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題C (Harmonic Mean) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 解説のロジックで, 解けることが興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6695
// C++20(GCC 12.2)
#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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. N = k * (k - 1) のパターンは？
    set<int> st;
    repx(i, 1, 23) st.insert(i * (i + 1));
    
    // 3. 各テストケース.
    rep(i, T){
        // 3-1. テストケース入力情報.
        int N;
        scanf("%d", &N);
        
        // 3-2. N = 1.
        if(N == 1) puts("Yes\n1");
        
        // 3-3. N = 2.
        if(N == 2){
            puts("No");
        }
        
        // 3-4. N >= 3.
        if(N >= 3){
            // N = k * (k - 1) のパターン.
            vi ans;
            if(st.count(N)){
                ans.pb(2);
                repx(j, 1, N - 1) ans.pb(2 * j * (j + 1));
                ans.pb(2 * (N - 1));
            }
            
            // 上記以外.
            if(!st.count(N)){
                repx(j, 1, N) ans.pb(j * (j + 1));
                ans.pb(N);
            }
            
            // 出力.
            puts("Yes");
            rep(j, N) printf("%d%s", ans[j], (j < N - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6695

// C++20(GCC 12.2)

#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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. N = k * (k - 1) のパターンは？

set<int> st;

repx(i, 1, 23) st.insert(i * (i + 1));

// 3. 各テストケース.

rep(i, T){

// 3-1. テストケース入力情報.

int N;

scanf("%d", &N);

// 3-2. N = 1.

if(N == 1) puts("Yes\n1");

// 3-3. N = 2.

if(N == 2){

puts("No");

}

// 3-4. N >= 3.

if(N >= 3){

// N = k * (k - 1) のパターン.

vi ans;

if(st.count(N)){

ans.pb(2);

repx(j, 1, N - 1) ans.pb(2 * j * (j + 1));

ans.pb(2 * (N - 1));

}

// 上記以外.

if(!st.count(N)){

repx(j, 1, N) ans.pb(j * (j + 1));

ans.pb(N);

}

// 出力.

puts("Yes");

rep(j, N) printf("%d%s", ans[j], (j < N - 1) ? " " : "\n");

}

return 0;

}

[入力例]
2
3
5

[出力例]
Yes
2 3 6 
Yes
3 4 5 6 20 
※AtCoderのテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
2 6 3
Yes
2 6 12 20 5

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

[出力例]
Yes
1
No
Yes
2 6 3
Yes
2 6 12 4
Yes
2 6 12 20 5
Yes
2 4 12 24 40 10
Yes
2 6 12 20 30 42 7
Yes
2 6 12 20 30 42 56 8
Yes
2 6 12 20 30 42 56 72 9
Yes
2 6 12 20 30 42 56 72 90 10

[入力例]
20
11
12
18
24
30
55
72
77
99
100
111
132
125
200
222
240
333
345
462
500

[出力例]
Yes
2 6 12 20 30 42 56 72 90 110 11
Yes
2 4 12 24 40 60 84 112 144 180 220 22
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 18
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 24
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 58
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 55
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 142
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 77
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 99
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 100
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 111
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 262
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 125
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 200
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 222
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 478
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 333
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 345
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 114720 115680 116644 117612 118584 119560 120540 121524 122512 123504 124500 125500 126504 127512 128524 129540 130560 131584 132612 133644 134680 135720 136764 137812 138864 139920 140980 142044 143112 144184 145260 146340 147424 148512 149604 150700 151800 152904 154012 155124 156240 157360 158484 159612 160744 161880 163020 164164 165312 166464 167620 168780 169944 171112 172284 173460 174640 175824 177012 178204 179400 180600 181804 183012 184224 185440 186660 187884 189112 190344 191580 192820 194064 195312 196564 197820 199080 200344 201612 202884 204160 205440 206724 208012 209304 210600 211900 213204 214512 215824 217140 218460 219784 221112 222444 223780 225120 226464 227812 229164 230520 231880 233244 234612 235984 237360 238740 240124 241512 242904 244300 245700 247104 248512 249924 251340 252760 254184 255612 257044 258480 259920 261364 262812 264264 265720 267180 268644 270112 271584 273060 274540 276024 277512 279004 280500 282000 283504 285012 286524 288040 289560 291084 292612 294144 295680 297220 298764 300312 301864 303420 304980 306544 308112 309684 311260 312840 314424 316012 317604 319200 320800 322404 324012 325624 327240 328860 330484 332112 333744 335380 337020 338664 340312 341964 343620 345280 346944 348612 350284 351960 353640 355324 357012 358704 360400 362100 363804 365512 367224 368940 370660 372384 374112 375844 377580 379320 381064 382812 384564 386320 388080 389844 391612 393384 395160 396940 398724 400512 402304 404100 405900 407704 409512 411324 413140 414960 416784 418612 420444 422280 424120 922
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 119370 120062 120756 121452 122150 122850 123552 124256 124962 125670 126380 127092 127806 128522 129240 129960 130682 131406 132132 132860 133590 134322 135056 135792 136530 137270 138012 138756 139502 140250 141000 141752 142506 143262 144020 144780 145542 146306 147072 147840 148610 149382 150156 150932 151710 152490 153272 154056 154842 155630 156420 157212 158006 158802 159600 160400 161202 162006 162812 163620 164430 165242 166056 166872 167690 168510 169332 170156 170982 171810 172640 173472 174306 175142 175980 176820 177662 178506 179352 180200 181050 181902 182756 183612 184470 185330 186192 187056 187922 188790 189660 190532 191406 192282 193160 194040 194922 195806 196692 197580 198470 199362 200256 201152 202050 202950 203852 204756 205662 206570 207480 208392 209306 210222 211140 212060 212982 213906 214832 215760 216690 217622 218556 219492 220430 221370 222312 223256 224202 225150 226100 227052 228006 228962 229920 230880 231842 232806 233772 234740 235710 236682 237656 238632 239610 240590 241572 242556 243542 244530 245520 246512 247506 248502 249500 500

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

[出力例]

Yes

2 3 6

Yes

3 4 5 6 20

※AtCoderのテストケースより

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

Yes

2 6 3

Yes

2 6 12 20 5

[入力例]

[出力例]

Yes

2 6 3

Yes

2 6 12 4

Yes

2 6 12 20 5

Yes

2 4 12 24 40 10

Yes

2 6 12 20 30 42 7

Yes

2 6 12 20 30 42 56 8

Yes

2 6 12 20 30 42 56 72 9

Yes

2 6 12 20 30 42 56 72 90 10

[入力例]

100

111

132

125

200

222

240

333

345

462

500

[出力例]

Yes

2 6 12 20 30 42 56 72 90 110 11

Yes

2 4 12 24 40 60 84 112 144 180 220 22

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 18

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 24

Yes

2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 58

Yes

2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 114720 115680 116644 117612 118584 119560 120540 121524 122512 123504 124500 125500 126504 127512 128524 129540 130560 131584 132612 133644 134680 135720 136764 137812 138864 139920 140980 142044 143112 144184 145260 146340 147424 148512 149604 150700 151800 152904 154012 155124 156240 157360 158484 159612 160744 161880 163020 164164 165312 166464 167620 168780 169944 171112 172284 173460 174640 175824 177012 178204 179400 180600 181804 183012 184224 185440 186660 187884 189112 190344 191580 192820 194064 195312 196564 197820 199080 200344 201612 202884 204160 205440 206724 208012 209304 210600 211900 213204 214512 215824 217140 218460 219784 221112 222444 223780 225120 226464 227812 229164 230520 231880 233244 234612 235984 237360 238740 240124 241512 242904 244300 245700 247104 248512 249924 251340 252760 254184 255612 257044 258480 259920 261364 262812 264264 265720 267180 268644 270112 271584 273060 274540 276024 277512 279004 280500 282000 283504 285012 286524 288040 289560 291084 292612 294144 295680 297220 298764 300312 301864 303420 304980 306544 308112 309684 311260 312840 314424 316012 317604 319200 320800 322404 324012 325624 327240 328860 330484 332112 333744 335380 337020 338664 340312 341964 343620 345280 346944 348612 350284 351960 353640 355324 357012 358704 360400 362100 363804 365512 367224 368940 370660 372384 374112 375844 377580 379320 381064 382812 384564 386320 388080 389844 391612 393384 395160 396940 398724 400512 402304 404100 405900 407704 409512 411324 413140 414960 416784 418612 420444 422280 424120 922

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 119370 120062 120756 121452 122150 122850 123552 124256 124962 125670 126380 127092 127806 128522 129240 129960 130682 131406 132132 132860 133590 134322 135056 135792 136530 137270 138012 138756 139502 140250 141000 141752 142506 143262 144020 144780 145542 146306 147072 147840 148610 149382 150156 150932 151710 152490 153272 154056 154842 155630 156420 157212 158006 158802 159600 160400 161202 162006 162812 163620 164430 165242 166056 166872 167690 168510 169332 170156 170982 171810 172640 173472 174306 175142 175980 176820 177662 178506 179352 180200 181050 181902 182756 183612 184470 185330 186192 187056 187922 188790 189660 190532 191406 192282 193160 194040 194922 195806 196692 197580 198470 199362 200256 201152 202050 202950 203852 204756 205662 206570 207480 208392 209306 210222 211140 212060 212982 213906 214832 215760 216690 217622 218556 219492 220430 221370 222312 223256 224202 225150 226100 227052 228006 228962 229920 230880 231842 232806 233772 234740 235710 236682 237656 238632 239610 240590 241572 242556 243542 244530 245520 246512 247506 248502 249500 500

■参照サイト
AtCoder Regular Contest 163

2023年9月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題A (Divide String) ～問題B (Favorite Game) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 両問とも, 解説のロジックで, 解けることが興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6693
// C++20(GCC 12.2)
#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--)

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        char c[2020];
        scanf("%d %s", &N, c);
        string s(c);
        
        // 2-2. 長さ 2 の分割方法が存在するか？
        bool ok = false;
        rep(i, N - 1){
            string l = s.substr(0, i + 1);
            string r = s.substr(i + 1, N - i - 1);
            // printf("l=%s r=%s\n", l.c_str(), r.c_str());
            // 狭義単調増加に注意(等号は含めない).
            if(l < r){
                ok = true;
                break;
            }
        }
        
        // 2-3. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6693

// C++20(GCC 12.2)

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

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 2-1. 各テストケース.

int N;

char c[2020];

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

string s(c);

// 2-2. 長さ 2 の分割方法が存在するか？

bool ok = false;

rep(i, N - 1){

string l = s.substr(0, i + 1);

string r = s.substr(i + 1, N - i - 1);

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

// 狭義単調増加に注意(等号は含めない).

if(l < r){

ok = true;

break;

}

// 2-3. 出力.

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

}

return 0;

}

[入力例]
5
4
abac
3
cac
2
ab
12
abababababab
5
edcba

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

[入力例]
9
2
aa
3
aba
4
zyyx
5
qqqqp
6
zyxwvx
7
pqrsqrp
8
zyxzxyzy
9
pqrpqrpqr
10
srqposrqpo

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

[入力例]

abac

cac

abababababab

edcba

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

aba

zyyx

qqqqp

zyxwvx

pqrsqrp

zyxzxyzy

pqrpqrpqr

srqposrqpo

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6699
// C++20(GCC 12.2)
#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 a[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 数列 B.
    sort(a + 2, a + N);
    
    // 3. 全探索.
    LL ans = 202020202020202020;
    repx(i, 2, N - M + 1){
        // 左端, 右端.
        LL l = a[i];
        LL r = a[i + M - 1];
        
        // 操作回数.
        LL op = 0;
        op += max(0LL, a[0] - l);
        op += max(0LL, r - a[1]);
        
        // 最小値更新.
        ans = min(ans, op);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6699

// C++20(GCC 12.2)

#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 a[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 数列 B.

sort(a + 2, a + N);

// 3. 全探索.

LL ans = 202020202020202020;

repx(i, 2, N - M + 1){

// 左端, 右端.

LL l = a[i];

LL r = a[i + M - 1];

// 操作回数.

LL op = 0;

op += max(0LL, a[0] - l);

op += max(0LL, r - a[1]);

// 最小値更新.

ans = min(ans, op);

}

// 4. 出力.

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

return 0;

}

[入力例]
3 1
2 3 5

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

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

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

[入力例]
8 5
15 59 64 96 31 17 88 9

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

[入力例]
7 5
31 14 91 40 16 56 99

[出力例]
100

[入力例]
20 12
81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51

[出力例]
105

[入力例]
30 15
830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776

[出力例]
525

[入力例]

3 1

2 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

5 2

1 4 2 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

8 5

15 59 64 96 31 17 88 9

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

31 14 91 40 16 56 99

[出力例]

100

[入力例]

20 12

81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51

[出力例]

105

[入力例]

30 15

830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776

[出力例]

525

■参照サイト
AtCoder Regular Contest 163

2023年9月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題E (Count Simple Paths) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 訪問済みフラグ(往路, 復路)を活用して, 数え上げできるロジックが, 興味深く思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc284/editorial/5494
// C++20(GCC 12.2)
#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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int ans = 0;
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m) -> void {
        // 終了条件.
        if(m[cur]) return;
        
        // 終了条件(TLE回避のため, ロジック追加).
        // -> 対象のテストケースは, 02_random_00.txt ～ 02_random_03.txt.
        if(ans == 1000000) return;
        
        // 訪問済みフラグ(往路).
        ++m[cur];
        ans = min(++ans, 1000000);
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            self(self, G, nex, cur, m);
        }
        
        // 訪問済みフラグ(復路).
        --m[cur];
    };
    int memo[N];
    rep(i, N) memo[i] = 0;
    dfs(dfs, G, 0, -1, memo);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc284/editorial/5494

// C++20(GCC 12.2)

#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

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, M){

int u, v;

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

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dfs.

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

int ans = 0;

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m) -> void {

// 終了条件.

if(m[cur]) return;

// 終了条件(TLE回避のため, ロジック追加).

// -> 対象のテストケースは, 02_random_00.txt ～ 02_random_03.txt.

if(ans == 1000000) return;

// 訪問済みフラグ(往路).

++m[cur];

ans = min(++ans, 1000000);

// 隣接頂点.

for(auto &nex : G[cur]){

if(nex == bef) continue;

self(self, G, nex, cur, m);

}

// 訪問済みフラグ(復路).

--m[cur];

};

int memo[N];

rep(i, N) memo[i] = 0;

dfs(dfs, G, 0, -1, memo);

// 3. 出力.

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

return 0;

}

[入力例]
4 2
1 2
2 3

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

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

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

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

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

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

[出力例]
3

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

[出力例]
10

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

[出力例]
26

[入力例]

4 2

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2

1 3

1 4

2 3

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

8 21

2 6

1 3

5 6

3 8

3 6

4 7

4 6

3 4

1 5

2 4

1 2

2 7

1 4

3 5

2 5

2 3

4 5

3 7

6 7

5 7

2 8

[出力例]

2023

※AtCoderテストケースより

[入力例]

5 3

1 2

2 3

4 5

[出力例]

[入力例]

10 9

1 2

2 3

2 4

1 5

5 6

5 7

7 8

7 9

7 10

[出力例]

[入力例]

18 20

1 2

2 3

3 4

4 5

5 3

1 6

6 8

6 9

9 8

9 10

11 9

7 1

7 12

18 7

12 13

12 14

12 15

13 16

16 17

17 13

[出力例]

■参照サイト
AtCoder Beginner Contest 284

C++の練習を兼ねて, AtCoder Beginner Contest 324 の 問題E (Joint Two Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の 問題C (Error Correction) ～ 問題D (Square Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 166 の 問題A (Replace C or Swap AB) ～ 問題B (Make Multiples) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 045 の 問題B (01 Unbalanced) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 321 の 問題C (321-like Searcher) ～ 問題D (Set Menu) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 323 の 問題C (World Tour Finals) ～ 問題D (Merge Slimes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題D (Sum of SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題C (Harmonic Mean) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題A (Divide String) ～ 問題B (Favorite Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の 問題E (Count Simple Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題E (Joint Two Strings) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 324 の問題C (Error Correction) ～問題D (Square Permutation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 166 の問題A (Replace C or Swap AB) ～問題B (Make Multiples) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 045 の問題B (01 Unbalanced) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 321 の問題C (321-like Searcher) ～問題D (Set Menu) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 323 の問題C (World Tour Finals) ～問題D (Merge Slimes) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題D (Sum of SCC) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題C (Harmonic Mean) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題A (Divide String) ～問題B (Favorite Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題E (Count Simple Paths) を解いてみた.