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

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題E (Divisible Substring) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったため, 解説を参考に, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc158/editorial.pdf
// 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--)

int main(){
    
    // 1. 入力情報.
    int N, P;
    char c[202020];
    scanf("%d %d %s", &N, &P, c);
    string s(c);
    int ns = s.size();
    LL ans = 0;
    
    // 2. P = 2, 5 の 場合.
    if(P == 2 || P == 5){
        // 2-1. 右端が, P の 倍数か？
        repr(i, ns - 1, 0) if((s[i] - '0') % P == 0) ans += (LL)(i + 1);
        
        // 2-2. 出力.
        printf("%lld\n", ans);
        return 0;
    }
    
    // 3. 上記以外.
    // 3-1. 10 の べき乗.
    int mPow10[ns];
    mPow10[ns - 1] = 1;
    repr(i, ns - 2, 0) mPow10[i] = mPow10[i + 1] * 10 % P;
    
    // 3-2. U[i] (mod P) の 個数は？
    map<int, int> uCount;
    int u = 0;
    repr(i, ns - 1, 0){
        u += mPow10[i] * (s[i] - '0');
        u %= P;
        ++uCount[u];
    }
    
    // 3-3. 集計.
    map<int, int> xCount;
    int x = 0;
    repr(i, ns - 1, 0){
        x += mPow10[i] * (s[i] - '0');
        x %= P;
        ++xCount[x];
        
        // x が 0 は, 自分自身もカウント対象なので, 注意.
        // ex.
        // N = 6 P = 7 S = 728105 の場合, 
        //      5 -> 7 の 倍数 でない -> 05 - 5 = 0 が 7 の倍数となるので, 1 を 加算.
        //     05 -> 7 の 倍数 でない -> 05 は 7 の倍数でないので, 0 を 加算.
        //    105 -> 7 の 倍数 である -> 728105, 28105, 105(自分自身) から, 
        //                              それぞれ 105 を 減算したものが 7 の 倍数なので, 3 を 加算.
        //   8105 -> 7 の 倍数 でない -> 8105 は 7 の倍数でないので, 0 を 加算.
        //  28105 -> 7 の 倍数 である -> 728105, 28105(自分自身) から, 
        //                              それぞれ 28105 を 減算したものが 7 の 倍数なので, 2 を 加算.
        // 728105 -> 7 の 倍数 である -> 728105(自分自身) から, 
        //                              それぞれ 728105 を 減算したものが 7 の 倍数なので, 1 を 加算.
        // 上記合計 7 (= 1 + 3 + 2 + 1) が 集計結果のはず.
        ans += (LL)(uCount[x] - xCount[x] + (x == 0));
    }
    
    // 3-4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

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

int main(){

// 1. 入力情報.

int N, P;

char c[202020];

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

string s(c);

int ns = s.size();

LL ans = 0;

// 2. P = 2, 5 の場合.

if(P == 2 || P == 5){

// 2-1. 右端が, P の倍数か？

repr(i, ns - 1, 0) if((s[i] - '0') % P == 0) ans += (LL)(i + 1);

// 2-2. 出力.

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

return 0;

}

// 3. 上記以外.

// 3-1. 10 のべき乗.

int mPow10[ns];

mPow10[ns - 1] = 1;

repr(i, ns - 2, 0) mPow10[i] = mPow10[i + 1] * 10 % P;

// 3-2. U[i] (mod P) の個数は？

map<int, int> uCount;

int u = 0;

repr(i, ns - 1, 0){

u += mPow10[i] * (s[i] - '0');

u %= P;

++uCount[u];

}

// 3-3. 集計.

map<int, int> xCount;

int x = 0;

repr(i, ns - 1, 0){

x += mPow10[i] * (s[i] - '0');

x %= P;

++xCount[x];

// x が 0 は, 自分自身もカウント対象なので, 注意.

// ex.

// N = 6 P = 7 S = 728105 の場合,

// 5 -> 7 の倍数でない -> 05 - 5 = 0 が 7 の倍数となるので, 1 を加算.

// 05 -> 7 の倍数でない -> 05 は 7 の倍数でないので, 0 を加算.

// 105 -> 7 の倍数である -> 728105, 28105, 105(自分自身) から,

// それぞれ 105 を減算したものが 7 の倍数なので, 3 を加算.

// 8105 -> 7 の倍数でない -> 8105 は 7 の倍数でないので, 0 を加算.

// 28105 -> 7 の倍数である -> 728105, 28105(自分自身) から,

// それぞれ 28105 を減算したものが 7 の倍数なので, 2 を加算.

// 728105 -> 7 の倍数である -> 728105(自分自身) から,

// それぞれ 728105 を減算したものが 7 の倍数なので, 1 を加算.

// 上記合計 7 (= 1 + 3 + 2 + 1) が集計結果のはず.

ans += (LL)(uCount[x] - xCount[x] + (x == 0));

}

// 3-4. 出力.

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

return 0;

}

[入力例]
4 3
3543

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

[入力例]
4 2
2020

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

[入力例]
20 11
33883322005544116655

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

[入力例]
6 7
728105

[出力例]
7

[入力例]
8 2
20220624

[出力例]
36

[入力例]
12 5
202003072240

[出力例]
30

[入力例]
100 123
6872267760531042464119518350821166892127405932097676518321338765887563671699117552972989237935232870

[出力例]
43

[入力例]
500 31415
19827912619128213155324311431340676818881586771968486313913880031802243688276451376203819426630356973924068276151752054138722949743845433174772642870341335136341653840978780047251625547015001037931570908172412415966038163714662909499827012269549282246479667761400616079763785738707691959444312832666207128504468482429462634779225762390883765639589187652951246319470816174745539828792627999850115408217855959299618176113149651198371207914448214824113154122258866645535483442753629014046055718878658164

[出力例]
56

[入力例]
1000 2022
2050746112373639485356489833822371389761990747934841841265597655258830232297968397489207690233496298133426293410768896915523812766755705073823818586409515760897930782894751029665097634226112753987009332271329102783102474625096233249280891692991693597633568639895819920959422459379571442123896088337866984489421595649580969796285426754644632567315800335271368050999071714673857927670715182746888815581432466171292295492131794475868801461733656763305977528429343286060721957075107528065898455564711323607055890311868877628618909133146693166860023145095450109292930544534876119895283488561564114642504547807421167248323016039488901561535793585700349466310737594859928780026542295538555515350355620916753933481763278124757373272127214451484549647938952706423163558530974157549181711513258840177446645005648016782019516724730986996393453592778311173619130217005658774305107670115722832986813548915716074625354172299675322194502546799298436785198907858447467803448790926043797899845966937419584694318042712

[出力例]
568

[入力例]
3000 20220307
596214249853483225097693315388909224384489458359826431372736370050820603971963623887223374916230451032952080616398933184251535026230270724401835890958546743454624434891513179796364363818613684299745813048992821012775776182603274217611727698315108854249194305571011714789573157968383474519210375548761883910648845714429491574215927967709529586597429267623637097712094874502528637589735259356521011987313487531114622639634280895531314472288317567241924124525374520626380053203654966374814948435836589081101098669761100669044658065687596533021109001359272974337164913032035249760410975011064653792396282333036217955719298828194573458829930219324512386017241443762438470885612043869536406611407681095560972777468453531916866773859101030929635813816830251144742068739585983959899577090196410233902164796886451593744927354893343913356858966924015231123951425230217457267923084875035706239757292110054735757720086630271101268691864803947406905179497668152325101570480106285035326410169587797498380392931595402548509074625534910183494355558852211413021128648117649900899014169715046066938106607928463353582556945561703118313686961815834149389505115465789809090890212540837188891715090834795472118703882181590227429467403212542982180674875675033516437035242158029597291351551040676003812134976183481144271558828702957427471354270949454780890810664406648785857395292896935628252928596982336870833981830324741464515604511843205181063341575739040518666255058327080389585965186610896654696065438411142665435271504129640043328572627654592179256255998025566103548660638942322143384677507961636075308992340792680254033645422068246686361691158623570075069431018321294545922421021636389297080337921588663982357977229526909116470321114915822673139914674472409576525020826191261709718690585036734121329540440957161361075738430823928138503133266943441005162406670170916574939298499893570061282038478026906288854595326694851351613865867391128213501468341263222274248107637114390405173134592468888519410941707681906904200754225523509190205865290605683971994577025051344857027083921022685954654893216083835686869098933948840609643556421123794591700725195710399020043544330293227662378282784174622758179743232409877655255045476605887615189866917175127208582069784212405656661186614031757797931490384710033497512237081906460780325753339042238740671828300928523312109224528224759099737242272565258627768278828066694562802209146872750725148590822945224260010532206995105321255181059324710839633727858809587370076767850668306926873691694429616371742926924403392061260046164734364664045255997895823394969579011070406439847192915118769193956704674278360413560579461109790715768935197207081728188375678386794199954373694666726071455324418062658727966723489352678898548319161293224216340382739015335474768790942239571225028961503326144288659244262210157158502728534527947520526957552280442455094734146572080410264728865088794877026515299468446838590500231888330601026317311155564146863595555475196625646824815420202458726192347289235

[出力例]
313

[入力例]

4 3

3543

[出力例]

※AtCoderのテストケースより

[入力例]

4 2

2020

[出力例]

※AtCoderのテストケースより

[入力例]

20 11

33883322005544116655

[出力例]

※AtCoderのテストケースより

[入力例]

6 7

728105

[出力例]

[入力例]

8 2

20220624

[出力例]

[入力例]

12 5

202003072240

[出力例]

[入力例]

100 123

6872267760531042464119518350821166892127405932097676518321338765887563671699117552972989237935232870

[出力例]

[入力例]

500 31415

19827912619128213155324311431340676818881586771968486313913880031802243688276451376203819426630356973924068276151752054138722949743845433174772642870341335136341653840978780047251625547015001037931570908172412415966038163714662909499827012269549282246479667761400616079763785738707691959444312832666207128504468482429462634779225762390883765639589187652951246319470816174745539828792627999850115408217855959299618176113149651198371207914448214824113154122258866645535483442753629014046055718878658164

[出力例]

[入力例]

1000 2022

2050746112373639485356489833822371389761990747934841841265597655258830232297968397489207690233496298133426293410768896915523812766755705073823818586409515760897930782894751029665097634226112753987009332271329102783102474625096233249280891692991693597633568639895819920959422459379571442123896088337866984489421595649580969796285426754644632567315800335271368050999071714673857927670715182746888815581432466171292295492131794475868801461733656763305977528429343286060721957075107528065898455564711323607055890311868877628618909133146693166860023145095450109292930544534876119895283488561564114642504547807421167248323016039488901561535793585700349466310737594859928780026542295538555515350355620916753933481763278124757373272127214451484549647938952706423163558530974157549181711513258840177446645005648016782019516724730986996393453592778311173619130217005658774305107670115722832986813548915716074625354172299675322194502546799298436785198907858447467803448790926043797899845966937419584694318042712

[出力例]

568

[入力例]

3000 20220307

596214249853483225097693315388909224384489458359826431372736370050820603971963623887223374916230451032952080616398933184251535026230270724401835890958546743454624434891513179796364363818613684299745813048992821012775776182603274217611727698315108854249194305571011714789573157968383474519210375548761883910648845714429491574215927967709529586597429267623637097712094874502528637589735259356521011987313487531114622639634280895531314472288317567241924124525374520626380053203654966374814948435836589081101098669761100669044658065687596533021109001359272974337164913032035249760410975011064653792396282333036217955719298828194573458829930219324512386017241443762438470885612043869536406611407681095560972777468453531916866773859101030929635813816830251144742068739585983959899577090196410233902164796886451593744927354893343913356858966924015231123951425230217457267923084875035706239757292110054735757720086630271101268691864803947406905179497668152325101570480106285035326410169587797498380392931595402548509074625534910183494355558852211413021128648117649900899014169715046066938106607928463353582556945561703118313686961815834149389505115465789809090890212540837188891715090834795472118703882181590227429467403212542982180674875675033516437035242158029597291351551040676003812134976183481144271558828702957427471354270949454780890810664406648785857395292896935628252928596982336870833981830324741464515604511843205181063341575739040518666255058327080389585965186610896654696065438411142665435271504129640043328572627654592179256255998025566103548660638942322143384677507961636075308992340792680254033645422068246686361691158623570075069431018321294545922421021636389297080337921588663982357977229526909116470321114915822673139914674472409576525020826191261709718690585036734121329540440957161361075738430823928138503133266943441005162406670170916574939298499893570061282038478026906288854595326694851351613865867391128213501468341263222274248107637114390405173134592468888519410941707681906904200754225523509190205865290605683971994577025051344857027083921022685954654893216083835686869098933948840609643556421123794591700725195710399020043544330293227662378282784174622758179743232409877655255045476605887615189866917175127208582069784212405656661186614031757797931490384710033497512237081906460780325753339042238740671828300928523312109224528224759099737242272565258627768278828066694562802209146872750725148590822945224260010532206995105321255181059324710839633727858809587370076767850668306926873691694429616371742926924403392061260046164734364664045255997895823394969579011070406439847192915118769193956704674278360413560579461109790715768935197207081728188375678386794199954373694666726071455324418062658727966723489352678898548319161293224216340382739015335474768790942239571225028961503326144288659244262210157158502728534527947520526957552280442455094734146572080410264728865088794877026515299468446838590500231888330601026317311155564146863595555475196625646824815420202458726192347289235

[出力例]

313

■参照サイト
AtCoder Beginner Contest 158

C++の練習を兼ねて, AtCoder Beginner Contest 158 の 問題E (Divisible Substring) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 158 の問題E (Divisible Substring) を解いてみた.

コメントを残すコメントをキャンセル