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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題F (Cleaning Robot) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ AC版に到達できた.
2. 実装に, 非常に苦労したものの, いろいろ参考になった知識が多く, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2654
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
using vp = vector<P>;
using vvp = vector<vp>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
#define all(x) x.begin(), x.end()
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    char c[202020];
    LL K;
    scanf("%s %lld", c, &K);
    string s(c);
    
    // 2. ロボットの位置(文字列 S を 1回分).
    set<P> v;
    P cur, bef = {0, 0};
    v.insert({0, 0});
    rep(i, s.size()){
        // 今回分更新.
        // 下.
        if(s[i] == 'L'){
            cur.a = bef.a - 1;
            cur.b = bef.b;
        }
        
        // 右.
        if(s[i] == 'R'){
            cur.a = bef.a + 1;
            cur.b = bef.b;
        }
        
        // 上.
        if(s[i] == 'U'){
            cur.a = bef.a;
            cur.b = bef.b - 1;
        }
        
        // 下.
        if(s[i] == 'D'){
            cur.a = bef.a;
            cur.b = bef.b + 1;
        }
        
        // 保存.
        v.insert(cur);
        
        // 前回分更新.
        bef = cur;
    }
    LL a = cur.a, b = cur.b;
    
    // 3. d を 計算(※解説通り).
    // a が 0 で無い場合は, q = x / a を ベースに考える.
    // b が 0 で無い場合は, q = y / b を ベースに考える.
    auto f = [](set<P> &v, int N, LL a, LL b, LL* d) -> void{
        map<P, int> m;
        vvp qs(N);
        int i = -1;
        for(auto &p : v){
            // q, s, t を 計算
            LL x = p.a, y = p.b;
            LL q = INF, r = INF;
            
            // テストケース 046.txt, 047.txt で, WA版となったので修正.
            // -> 符号に応じて, 計算式が変動するかをチェック.
            // -> 余りが, 常に, 0 以上になるように寄せる必要がありそう.
            // ex.
            // (-11) % (-3) = -2, (-11) / (-3) =  3 -> 余りを, 1 として, 商を, 4 とする.
            // (+11) % (-3) = +2, (+11) / (-3) = -3
            // (-11) % (+3) = -2, (-11) / (+3) = -3 -> 余りを, 1 として, 商を, -4 とする.
            // (+11) % (+3) = +2, (+11) / (+3) =  3
            if(a != 0){
                r = x % a;
                q = x / a;
                if(r < 0 && x < 0){
                    r += abs(a);
                    q = (x - r) / a;
                }
            }else{
                r = y % b;
                q = y / b;
                if(r < 0 && y < 0){
                    r += abs(b);
                    q = (y - r) / b;
                }
            }
            LL s = x - q * a;
            LL t = y - q * b;
            ++i;
            
            // (s, t)ごとに保存.
            P g = {s, t};
            P h = {q, i};
            
            // 前回以前で, 出現済の場合.
            if(m.count(g) > 0){
                int j = m[g];
                qs[j].pb(h);
                continue;
            }
            
            // 初回出現した場合.
            if(m.count(g) == 0){
                m[g] = m.size();
                int j = m[g];
                qs[j].pb(h);
            }
        }
        
        // sort.
        rep(j, m.size()) sort(all(qs[j]));
        
        // d を 保存.
        rep(j, m.size()){
            rep(k, qs[j].size() - 1){
                LL qDiff = qs[j][k + 1].a - qs[j][k].a;
                int at = qs[j][k].b;
                d[at] = qDiff;
            }
        }
        
        // 終了.
        return;
    };
    
    // 4. 場合分け.
    int N = v.size();
    LL d[N];
    rep(i, N) d[i] = INF;
    if(a == 0 && b == 0) rep(i, N) d[i] = 1;
    else                 f(v, N, a, b, d);
    
    // 5. 集計.
    LL ans = 0;
    rep(i, N) ans += min(K, d[i]);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

// 解き直し.

// https://atcoder.jp/contests/abc219/editorial/2654

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector<P>;

using vvp = vector<vp>;

#define repex(i, a, b, c) for(int i = a; i < b; i += c)

#define repx(i, a, b) repex(i, a, b, 1)

#define rep(i, n) repx(i, 0, n)

#define repr(i, a, b) for(int i = a; i >= b; i--)

#define pb push_back

#define a first

#define b second

#define all(x) x.begin(), x.end()

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

char c[202020];

LL K;

scanf("%s %lld", c, &K);

string s(c);

// 2. ロボットの位置(文字列 S を 1回分).

set<P> v;

P cur, bef = {0, 0};

v.insert({0, 0});

rep(i, s.size()){

// 今回分更新.

// 下.

if(s[i] == 'L'){

cur.a = bef.a - 1;

cur.b = bef.b;

}

// 右.

if(s[i] == 'R'){

cur.a = bef.a + 1;

cur.b = bef.b;

}

// 上.

if(s[i] == 'U'){

cur.a = bef.a;

cur.b = bef.b - 1;

}

// 下.

if(s[i] == 'D'){

cur.a = bef.a;

cur.b = bef.b + 1;

}

// 保存.

v.insert(cur);

// 前回分更新.

bef = cur;

}

LL a = cur.a, b = cur.b;

// 3. d を計算(※解説通り).

// a が 0 で無い場合は, q = x / a をベースに考える.

// b が 0 で無い場合は, q = y / b をベースに考える.

auto f = [](set<P> &v, int N, LL a, LL b, LL* d) -> void{

map<P, int> m;

vvp qs(N);

int i = -1;

for(auto &p : v){

// q, s, t を計算

LL x = p.a, y = p.b;

LL q = INF, r = INF;

// テストケース 046.txt, 047.txt で, WA版となったので修正.

// -> 符号に応じて, 計算式が変動するかをチェック.

// -> 余りが, 常に, 0 以上になるように寄せる必要がありそう.

// ex.

// (-11) % (-3) = -2, (-11) / (-3) = 3 -> 余りを, 1 として, 商を, 4 とする.

// (+11) % (-3) = +2, (+11) / (-3) = -3

// (-11) % (+3) = -2, (-11) / (+3) = -3 -> 余りを, 1 として, 商を, -4 とする.

// (+11) % (+3) = +2, (+11) / (+3) = 3

if(a != 0){

r = x % a;

q = x / a;

if(r < 0 && x < 0){

r += abs(a);

q = (x - r) / a;

}

}else{

r = y % b;

q = y / b;

if(r < 0 && y < 0){

r += abs(b);

q = (y - r) / b;

}

LL s = x - q * a;

LL t = y - q * b;

++i;

// (s, t)ごとに保存.

P g = {s, t};

P h = {q, i};

// 前回以前で, 出現済の場合.

if(m.count(g) > 0){

int j = m[g];

qs[j].pb(h);

continue;

}

// 初回出現した場合.

if(m.count(g) == 0){

m[g] = m.size();

int j = m[g];

qs[j].pb(h);

}

// sort.

rep(j, m.size()) sort(all(qs[j]));

// d を保存.

rep(j, m.size()){

rep(k, qs[j].size() - 1){

LL qDiff = qs[j][k + 1].a - qs[j][k].a;

int at = qs[j][k].b;

d[at] = qDiff;

}

// 終了.

return;

};

// 4. 場合分け.

int N = v.size();

LL d[N];

rep(i, N) d[i] = INF;

if(a == 0 && b == 0) rep(i, N) d[i] = 1;

else f(v, N, a, b, d);

// 5. 集計.

LL ans = 0;

rep(i, N) ans += min(K, d[i]);

// 6. 出力.

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

return 0;

}

[入力例]
RDRUL
2

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

[入力例]
LR
1000000000000

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

[入力例]
UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

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

[入力例]
R
1

[出力例]
2

[入力例]
RU
2

[出力例]
5

[入力例]
LDURU
3

[出力例]
8

[入力例]
LULRDRRLDULURRLRLRRUDRDLRULDDDDLDRUDDDLRDDLDDUDRLD
1732050807

[出力例]
45033320985

[入力例]
DLUDDLULLURRDRUULRLUDRDULURDDDUULLDLLDUUDUDUUURRRUUDRRURLRDLLDLLRULULLLUURLRDLLDULRLLDRDDLUDDURURLUL
223606797749

[出力例]
11627553482950

[入力例]
LUULLLDLDRRUDDDUDLRDRLDRURUULULRRDURLRDLURULLULLDDDLRLLDRDRRRLDRUDRRLRDLUUDLULUDRLUULLLRRLDDRRULRDLLULULDURULUDUDRUDLDDRDLLRUULRLLLDUUUDDUDLDDLRDDLUDDURUDRUDDUUDRULDLLDUDUDLURRUURURDRRURUURRRURRDRLRUURDDRLRUDLDRDULDLRDRRLRLRDDDDLUDDDLULURRULUDLDUDRRLURDDRLLLDRUURULURLLLRUULLLRURRRURLLDULLDDLDLUURRUULDRLRDRURRRDRDUURLDLURDURLLUDLDDRRRLUDRDDLURRLULUDRLLLDLRURUDDDLRRUUULRRLDLRDDURRLLRDUDRDLLLRDLRDLUUURRLLURDURDDLRULUULDRLRDLRLRRDDRULLLLLDURLUDDRUUUUDLRLUDLRLRLDRRLDDULDLLUUUDRLLLDDLRRLDLDUUULLDLLLRRUURDULDLULUUDRLDLDUUDRLLDLUURUUDDLULUURRLDUDLLDRRULRULRDRULLLUUURRRURULULDUDUDRUDDDDDDLRRLDDRLRDLDRRLLRDDRUUDDLLUDLLURDDLDUDDRDULDDURLDLLRDDRLDDDLLLRULLULRURUULULRDRDURUDULRDDUDLDRLRUUULRLUDDULRURRRLDLULLURUDRRLDDRURLDLRDLDULLRUDRLLRLRRRRLLRDLRLLRDURURLDLDDRLRUDRRRLLRDLLLLDLURUDULURURLDRDDURRUDDRDLDLDDULLRLLDURLRLDRUDLUUDLUDULURDLUDURRULDDULRLDLDDLDRLRRURURDRDRUURDRLLDULLLUULUDDLRDRLURDULUDRUURRUDDDRURLURLUDRDURDUDLURUUUULULRRUUDULLLULLUUUULDLUURDRDUDUDRULDLRRUDURDLRDULULDDRRRDURDRRUULRDULRLRLLR
120205690315

[出力例]
28488748604720

[入力例]
URLRDRDDLDLLRDUUUURDULLLRUUUULRLULULLLRDDLDDLDDLRRRDLULDDDUDRDULDDDUURLDUUDDRURRLLLDDUUDRRLULLDLRUUULRDDUDDUULDLDLDLDURUULUULDRLUDLLRDRRURRULRLDURLRRRRDLDLRRRLDLDRURLDUDLLDDURUDLUULDLULRRDDDLRRRUDRRRDRLRULRDLURLLRUULRDLDURUURLUUULDUDDDULURLLRRRRRDRLDRRDULDDDDDUULDDURLUDLURDURDDURRLDLDRLUDDUURRDURRRRLURURRDURDDLRDLRLLRDLULURLDUDLLURDDRRRULRLRURDLRURUURDUUULLRURDLLUDDLULLUURLLRURULRRURDLLRULLURRRRDUUDULULDLLRUURDRLRRRDLURURUUDRURDRURDRULRLLRUDURULDRRRUURUDLUULRRDLDLULRRRRLRDRULRULLUDRULLLDDULRUDUUDDRURRURDDDDDUDUUUURLRLLRDDLULDDRDLRRDLURDULDLRDRUULULRULURDRUDLLLURULLUUUUDLLDDLDURRLURLRLLDLDDRLDLRRDULLRDUUDUUDDURRRDUUULLRRDLLDDRRDUURUUDUUURDLULLRURULULRRLLLRLDLLDRUURUURLRRUDLDURRDRLUDDRULRLLDUDRLUDDURDUDDDLUDLLDDDRUDRRDULDUUURLRRLDRRRLURLUUDLURDDULRDRLLDLUDRLDULDLDDLRDLRULDDRUDUUDULRUUDRRLLDLDLURRRDURLRRDRULRRRRURLUUULLDULRDUDLRLDLRLLDLLUULUURDDRRLRULRLLUULRDURUDUUUDDDUDDLLRUDUDDLLLURDDURLURUUDLLRUURRUUUUULLLLRRDLLRRLURRLDDDRRRRUULLDRLULUDDLDRDLUUULLUDLLDLRLLULRRLRLURRULUUDDUUDDRLURLULURDLRLRLLDRURRURUUDLRLDDRURLDRLDRRDRDUUULULLUURRRRLLUDRDRDUURRLLURRRURUUDUDUUDRLDDLRLUURLLRLUURRUDDULDLDDUUULDUDRLURRDDRLDLRURRULURULRRRLDURULDUDRUDDRRLLRUURLRURLRUDLRRDUDUDULDUDDDDDLUDUUUDLRLRLUUUULLDLRRUDRRDDLDUDRDUULDULDDURURLDLDDRRUDRULRRULRDUDDLRLULDDULDRLULUDLDRRDLRRRUUDLRUDDLULDDRRLLUDDLDURRUUDURULLLLUDRRLDLLUDDURDLDLDURDDRLULRLLDLLRDDDURDUURRULDDUUDLRLDLRLRRDLRULLUULLDDUURULRDUDRURDRULLLDRRRLDRUUUURDDDDDLUULUDURDDRDDRUDLDRUULULLRRDLRRRRUDDRRRLUUDDUUDDLDLRUUURDLULULLDURRLLDDUUDRDLRDRLDRULDRUDLRURDRLUUDRLLLRULUURLUDLLUDULLRRUUDRLLRLLDLLRRUUUULLRRRDUUDUUUULRRRDDRUULLUDLLRUDDLRRDLLLURLRRUURRRUDULDDRRRUDRRDLURRLULRRLDUDLULUDURRLDDURDLDDDLRUUDDDDDUUUDULUUDRLURLDUDRLRRRDRLLRDLDRLLUURRRUURDRDULDLDLLRUULLUDLLURRRLRLDRRLDDURURDLRLRUUULLDDRUUDULRDLRRURLUDDRRDRDLUDDRULLUURLDLDUDDRUUURUULRRRRRRUDDRUURLURDLDRULDDLDRLLUULLRRDRLUUDURLDRLDDRRLDDRRLUDLLDUURLRUUDRRDDDULUURLDDLLURRDDRRRUULDRLDULLULDRULUUDLLLDLULLURLDUDLDUULULRLDLULURLRDRDDRLULLLURDLULDDUULLDDLURLDLRDLDRRDDRRRRLLDRRDDRRUUDLULRUDUDLRUD
670499185382

[出力例]
342625083730316

[入力例]

RDRUL

[出力例]

※AtCoderテストケースより

[入力例]

1000000000000

[出力例]

※AtCoderテストケースより

[入力例]

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU

31415926535

[出力例]

219911485785

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

LDURU

[出力例]

[入力例]

LULRDRRLDULURRLRLRRUDRDLRULDDDDLDRUDDDLRDDLDDUDRLD

1732050807

[出力例]

45033320985

[入力例]

DLUDDLULLURRDRUULRLUDRDULURDDDUULLDLLDUUDUDUUURRRUUDRRURLRDLLDLLRULULLLUURLRDLLDULRLLDRDDLUDDURURLUL

223606797749

[出力例]

11627553482950

[入力例]

LUULLLDLDRRUDDDUDLRDRLDRURUULULRRDURLRDLURULLULLDDDLRLLDRDRRRLDRUDRRLRDLUUDLULUDRLUULLLRRLDDRRULRDLLULULDURULUDUDRUDLDDRDLLRUULRLLLDUUUDDUDLDDLRDDLUDDURUDRUDDUUDRULDLLDUDUDLURRUURURDRRURUURRRURRDRLRUURDDRLRUDLDRDULDLRDRRLRLRDDDDLUDDDLULURRULUDLDUDRRLURDDRLLLDRUURULURLLLRUULLLRURRRURLLDULLDDLDLUURRUULDRLRDRURRRDRDUURLDLURDURLLUDLDDRRRLUDRDDLURRLULUDRLLLDLRURUDDDLRRUUULRRLDLRDDURRLLRDUDRDLLLRDLRDLUUURRLLURDURDDLRULUULDRLRDLRLRRDDRULLLLLDURLUDDRUUUUDLRLUDLRLRLDRRLDDULDLLUUUDRLLLDDLRRLDLDUUULLDLLLRRUURDULDLULUUDRLDLDUUDRLLDLUURUUDDLULUURRLDUDLLDRRULRULRDRULLLUUURRRURULULDUDUDRUDDDDDDLRRLDDRLRDLDRRLLRDDRUUDDLLUDLLURDDLDUDDRDULDDURLDLLRDDRLDDDLLLRULLULRURUULULRDRDURUDULRDDUDLDRLRUUULRLUDDULRURRRLDLULLURUDRRLDDRURLDLRDLDULLRUDRLLRLRRRRLLRDLRLLRDURURLDLDDRLRUDRRRLLRDLLLLDLURUDULURURLDRDDURRUDDRDLDLDDULLRLLDURLRLDRUDLUUDLUDULURDLUDURRULDDULRLDLDDLDRLRRURURDRDRUURDRLLDULLLUULUDDLRDRLURDULUDRUURRUDDDRURLURLUDRDURDUDLURUUUULULRRUUDULLLULLUUUULDLUURDRDUDUDRULDLRRUDURDLRDULULDDRRRDURDRRUULRDULRLRLLR

120205690315

[出力例]

28488748604720

[入力例]

URLRDRDDLDLLRDUUUURDULLLRUUUULRLULULLLRDDLDDLDDLRRRDLULDDDUDRDULDDDUURLDUUDDRURRLLLDDUUDRRLULLDLRUUULRDDUDDUULDLDLDLDURUULUULDRLUDLLRDRRURRULRLDURLRRRRDLDLRRRLDLDRURLDUDLLDDURUDLUULDLULRRDDDLRRRUDRRRDRLRULRDLURLLRUULRDLDURUURLUUULDUDDDULURLLRRRRRDRLDRRDULDDDDDUULDDURLUDLURDURDDURRLDLDRLUDDUURRDURRRRLURURRDURDDLRDLRLLRDLULURLDUDLLURDDRRRULRLRURDLRURUURDUUULLRURDLLUDDLULLUURLLRURULRRURDLLRULLURRRRDUUDULULDLLRUURDRLRRRDLURURUUDRURDRURDRULRLLRUDURULDRRRUURUDLUULRRDLDLULRRRRLRDRULRULLUDRULLLDDULRUDUUDDRURRURDDDDDUDUUUURLRLLRDDLULDDRDLRRDLURDULDLRDRUULULRULURDRUDLLLURULLUUUUDLLDDLDURRLURLRLLDLDDRLDLRRDULLRDUUDUUDDURRRDUUULLRRDLLDDRRDUURUUDUUURDLULLRURULULRRLLLRLDLLDRUURUURLRRUDLDURRDRLUDDRULRLLDUDRLUDDURDUDDDLUDLLDDDRUDRRDULDUUURLRRLDRRRLURLUUDLURDDULRDRLLDLUDRLDULDLDDLRDLRULDDRUDUUDULRUUDRRLLDLDLURRRDURLRRDRULRRRRURLUUULLDULRDUDLRLDLRLLDLLUULUURDDRRLRULRLLUULRDURUDUUUDDDUDDLLRUDUDDLLLURDDURLURUUDLLRUURRUUUUULLLLRRDLLRRLURRLDDDRRRRUULLDRLULUDDLDRDLUUULLUDLLDLRLLULRRLRLURRULUUDDUUDDRLURLULURDLRLRLLDRURRURUUDLRLDDRURLDRLDRRDRDUUULULLUURRRRLLUDRDRDUURRLLURRRURUUDUDUUDRLDDLRLUURLLRLUURRUDDULDLDDUUULDUDRLURRDDRLDLRURRULURULRRRLDURULDUDRUDDRRLLRUURLRURLRUDLRRDUDUDULDUDDDDDLUDUUUDLRLRLUUUULLDLRRUDRRDDLDUDRDUULDULDDURURLDLDDRRUDRULRRULRDUDDLRLULDDULDRLULUDLDRRDLRRRUUDLRUDDLULDDRRLLUDDLDURRUUDURULLLLUDRRLDLLUDDURDLDLDURDDRLULRLLDLLRDDDURDUURRULDDUUDLRLDLRLRRDLRULLUULLDDUURULRDUDRURDRULLLDRRRLDRUUUURDDDDDLUULUDURDDRDDRUDLDRUULULLRRDLRRRRUDDRRRLUUDDUUDDLDLRUUURDLULULLDURRLLDDUUDRDLRDRLDRULDRUDLRURDRLUUDRLLLRULUURLUDLLUDULLRRUUDRLLRLLDLLRRUUUULLRRRDUUDUUUULRRRDDRUULLUDLLRUDDLRRDLLLURLRRUURRRUDULDDRRRUDRRDLURRLULRRLDUDLULUDURRLDDURDLDDDLRUUDDDDDUUUDULUUDRLURLDUDRLRRRDRLLRDLDRLLUURRRUURDRDULDLDLLRUULLUDLLURRRLRLDRRLDDURURDLRLRUUULLDDRUUDULRDLRRURLUDDRRDRDLUDDRULLUURLDLDUDDRUUURUULRRRRRRUDDRUURLURDLDRULDDLDRLLUULLRRDRLUUDURLDRLDDRRLDDRRLUDLLDUURLRUUDRRDDDULUURLDDLLURRDDRRRUULDRLDULLULDRULUUDLLLDLULLURLDUDLDUULULRLDLULURLRDRDDRLULLLURDLULDDUULLDDLURLDLRDLDRRDDRRRRLLDRRDDRRUUDLULRUDUDLRUD

670499185382

[出力例]

342625083730316

■参照サイト
サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

C++の練習を兼ねて, AtCoder Beginner Contest 219 の 問題F (Cleaning Robot) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題F (Cleaning Robot) を解いてみた.

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