個人用メモ帳

2021年9月22日2021年9月22日

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;

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 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 &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）

2021年9月20日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2666
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int main(){
    
    // 1. 入力情報.
    string board = "";
    rep(i, 4){
        string s = "";
        rep(j, 4){
            int c;
            scanf("%d", &c);
            s.pb(c + '0');
        }
        // 村情報.
        board += s;
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](string &G, int s, int H, int W, int* c, int l, char f) -> void{
        // 空のキュー.
        queue<int> q;
        
        // 訪問済みフラグ設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int v = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n;
            int cx = v % W , cy = v / W;
            rep(i, 4){
                nx = cx + dx[i];
                ny = cy + dy[i];
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                
                // 訪問先のマスで, 訪問可能 かつ 未訪問 であれば, 連結成分を設定.
                if(G[n] == f && !c[n]) c[n] = l, q.push(n);
            }
        }
        return;
    };
    
    // 3. 全探索.
    int ans = 0;
    repx(i, 1, 1 << 16){
        // 2進数値(16桁)で, '1' を 村, '0' を 平野 と見做して, お堀を作成.
        string g = "";
        rep(j, 16){
            if(i & (1 << (15 - j))) g.pb('1');
            else                    g.pb('0');
        }
        
        // 連結成分チェック(村を含む側).
        int cIn[16], idx = 0;
        rep(j, 16) cIn[j] = 0;
        rep(j, 16) if(!cIn[j] && g[j] == '1') bfs(g, j, 4, 4, cIn, ++idx, '1');
        
        // 連結成分(村を含む側)の個数が, 1 より大きい場合.
        if(idx > 1) continue;
        
        // 例外パターン.
        // 村を含まない側について, お堀に, 四方を囲まれた領域があるか？
        // -> 以下のロジックは, 正しく動作しない.
        // ex.
        // i = 60223 が, 反例の一つ.
        // 1110
        // 1011
        // 0011
        // 1111
        // -> r = 1, c = 1 で, one = 4 となるが, 入力例 1 では, 除外してはならないパターン.
        /*
        bool ok = true;
        vs a;
        a.pb(g.substr(0, 4));
        a.pb(g.substr(4, 4));
        a.pb(g.substr(8, 4));
        a.pb(g.substr(12, 4));
        rep(r, 4){
            rep(c, 4){
                // 基準とする領域.
                if(a[r][c] == '0'){
                    int one = 0;
                    
                    // 左方向.
                    repr(p, c - 1, 0){
                        if(a[r][p] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 右方向.
                    repx(p, c + 1, 4){
                        if(a[r][p] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 上方向.
                    repr(p, r - 1, 0){
                        if(a[p][c] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 下方向.
                    repx(p, r + 1, 4){
                        if(a[p][c] == '1'){
                            one++;
                            break;
                        }
                    }
                    
                    // 判定.
                    if(one == 4) ok = false;
                    
                    // ex.
                    // i = 59863
                    // 1110
                    // 1001
                    // 1101
                    // 0111
                    // -> r = 1, c = 1 で, one = 4 となるはず.
                    // if(i == 59863) printf("r=%d c=%d one=%d\n", r, c, one);
                }
                if(!ok) break;
            }
            if(!ok) break;
        }
        
        // お堀に, 四方を囲まれた領域があった場合.
        if(!ok) continue;
        */
        
        // 作成したお堀が, 条件を満たすか？
        // 自己交差を含むか.
        // -> (r, c) = '1' について, 常に, 右下, 左下 を チェック(※以下の二パターン).
        // 10
        // 01
        // 
        // 01
        // 10
        bool ok = true;
        vs a;
        a.pb(g.substr(0, 4));
        a.pb(g.substr(4, 4));
        a.pb(g.substr(8, 4));
        a.pb(g.substr(12, 4));
        rep(r, 3){
            rep(c, 3){
                if(a[r][c] == '1'){
                    // 右下.
                    if(a[r][c + 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c + 1] == '1') ok = false;
                    
                    // 左下.
                    if(c > 0 && a[r][c - 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c - 1] == '1') ok = false;
                }
            }
        }
        
        // 内部に, 空洞があるか.
        // -> 以下のロジックは, 正しく動作しない(入力例 1 で, 1307 となり, 1272 にならない).
        /*
        // 空洞のパターン(その1).
        // 1110
        // 1010
        // 1110
        // 0000
        // -> 1110101011100000, 0111010101110000, 0000111010101110, 0000011101010111 と照合.
        bitset<16> bsg(g);
        bitset<16> bs01("1110101011100000");
        bitset<16> bs02("0111010101110000");
        bitset<16> bs03("0000111010101110");
        bitset<16> bs04("0000011101010111");
        if((bsg & bs01).count() == 8 && g[5] == '0')  ok = false;
        if((bsg & bs02).count() == 8 && g[6] == '0')  ok = false;
        if((bsg & bs03).count() == 8 && g[9] == '0')  ok = false;
        if((bsg & bs04).count() == 8 && g[10] == '0') ok = false;
        
        // 空洞のパターン(その2).
        // 1111
        // 1001
        // 1111
        // 0000
        // -> 1111100111110000, 0000111110011111 と照合.
        bitset<16> bs11("1111100111110000");
        bitset<16> bs12("0000111110011111");
        if((bsg & bs11).count() == 10 && (g[5] == '0' || g[6] == '0'))  ok = false;
        if((bsg & bs12).count() == 10 && (g[9] == '0' || g[10] == '0')) ok = false;
        
        // 空洞のパターン(その3).
        // 1110
        // 1010
        // 1010
        // 1110
        // -> 1110101010101110, 0111010101010111 と 照合.
        bitset<16> bs21("1110101010101110");
        bitset<16> bs22("0111010101010111");
        if((bsg & bs21).count() == 10 && (g[5] == '0' || g[9] == '0'))  ok = false;
        if((bsg & bs22).count() == 10 && (g[6] == '0' || g[10] == '0')) ok = false;
        
        // 空洞のパターン(その4).
        // 1111
        // 1001
        // 1001
        // 1111
        // -> 1111100110011111 と 照合.
        bitset<16> bs31("1111100110011111");
        if((bsg & bs31).count() == 12){
            if(g[5] == '0' || g[6] == '0' || g[9] == '0' || g[10] == '0') ok = false;
        }
        */
        
        // 内部に, 空洞があるか(※実装をやり直す).
        // -> 6 × 6 のエリアで確認する方法(解説通り).
        // 2進数値(36桁)で, '1' を 村, '0' を 平野 と見做して, (拡張した)お堀を作成.
        string h = "000000";
        rep(j, 16){
            if(j % 4 == 0) h.pb('0');
            if(i & (1 << (15 - j))) h.pb('1');
            else                    h.pb('0');
            if(j % 4 == 3) h.pb('0');
        }
        h += "000000";
        
        // 連結成分チェック(村を含まない側).
        idx = 0;
        int cOut[36];
        rep(j, 36) cOut[j] = 0;
        rep(j, 36) if(!cOut[j] && h[j] == '0') bfs(h, j, 6, 6, cOut, ++idx, '0');
        // if(i == 59863) printf("%s\n%s\n", g.c_str(), h.c_str());
        
        // 連結成分(村を含まない側)の個数が, 1 より大きい場合.
        if(idx > 1) continue;
        
        // 村を全て含むか.
        rep(j, 16){
            if(board[j] == '1' && g[j] == '0'){
                ok = false;
                break;
            }
        }
        
        // カウントアップ.
        if(ok) ans++;
    }
    
    // 4. 出力.
    printf("%d\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

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

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};

int main(){

// 1. 入力情報.

string board = "";

rep(i, 4){

string s = "";

rep(j, 4){

int c;

scanf("%d", &c);

s.pb(c + '0');

}

// 村情報.

board += s;

}

// 2. bfs.

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

auto bfs = [&](string &G, int s, int H, int W, int* c, int l, char f) -> void{

// 空のキュー.

queue<int> q;

// 訪問済みフラグ設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

// x: 列方向, y: 行方向で考える.

int nx, ny, n;

int cx = v % W , cy = v / W;

rep(i, 4){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * W;

// 訪問不可能なマスであれば, 処理をスキップ.

if(nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

// 訪問先のマスで, 訪問可能かつ未訪問であれば, 連結成分を設定.

if(G[n] == f && !c[n]) c[n] = l, q.push(n);

}

return;

};

// 3. 全探索.

int ans = 0;

repx(i, 1, 1 << 16){

// 2進数値(16桁)で, '1' を村, '0' を平野と見做して, お堀を作成.

string g = "";

rep(j, 16){

if(i & (1 << (15 - j))) g.pb('1');

else g.pb('0');

}

// 連結成分チェック(村を含む側).

int cIn[16], idx = 0;

rep(j, 16) cIn[j] = 0;

rep(j, 16) if(!cIn[j] && g[j] == '1') bfs(g, j, 4, 4, cIn, ++idx, '1');

// 連結成分(村を含む側)の個数が, 1 より大きい場合.

if(idx > 1) continue;

// 例外パターン.

// 村を含まない側について, お堀に, 四方を囲まれた領域があるか？

// -> 以下のロジックは, 正しく動作しない.

// ex.

// i = 60223 が, 反例の一つ.

// 1110

// 1011

// 0011

// 1111

// -> r = 1, c = 1 で, one = 4 となるが, 入力例 1 では, 除外してはならないパターン.

bool ok = true;

vs a;

a.pb(g.substr(0, 4));

a.pb(g.substr(4, 4));

a.pb(g.substr(8, 4));

a.pb(g.substr(12, 4));

rep(r, 4){

rep(c, 4){

// 基準とする領域.

if(a[r][c] == '0'){

int one = 0;

// 左方向.

repr(p, c - 1, 0){

if(a[r][p] == '1'){

one++;

break;

}

// 右方向.

repx(p, c + 1, 4){

if(a[r][p] == '1'){

one++;

break;

}

// 上方向.

repr(p, r - 1, 0){

if(a[p][c] == '1'){

one++;

break;

}

// 下方向.

repx(p, r + 1, 4){

if(a[p][c] == '1'){

one++;

break;

}

// 判定.

if(one == 4) ok = false;

// ex.

// i = 59863

// 1110

// 1001

// 1101

// 0111

// -> r = 1, c = 1 で, one = 4 となるはず.

// if(i == 59863) printf("r=%d c=%d one=%d\n", r, c, one);

}

if(!ok) break;

}

if(!ok) break;

}

// お堀に, 四方を囲まれた領域があった場合.

if(!ok) continue;

// 作成したお堀が, 条件を満たすか？

// 自己交差を含むか.

// -> (r, c) = '1' について, 常に, 右下, 左下をチェック(※以下の二パターン).

// 10

// 01

// 10

bool ok = true;

vs a;

a.pb(g.substr(0, 4));

a.pb(g.substr(4, 4));

a.pb(g.substr(8, 4));

a.pb(g.substr(12, 4));

rep(r, 3){

rep(c, 3){

if(a[r][c] == '1'){

// 右下.

if(a[r][c + 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c + 1] == '1') ok = false;

// 左下.

if(c > 0 && a[r][c - 1] == '0' && a[r + 1][c] == '0' && a[r + 1][c - 1] == '1') ok = false;

}

// 内部に, 空洞があるか.

// -> 以下のロジックは, 正しく動作しない(入力例 1 で, 1307 となり, 1272 にならない).

// 空洞のパターン(その1).

// 1110

// 1010

// 1110

// 0000

// -> 1110101011100000, 0111010101110000, 0000111010101110, 0000011101010111 と照合.

bitset<16> bsg(g);

bitset<16> bs01("1110101011100000");

bitset<16> bs02("0111010101110000");

bitset<16> bs03("0000111010101110");

bitset<16> bs04("0000011101010111");

if((bsg & bs01).count() == 8 && g[5] == '0') ok = false;

if((bsg & bs02).count() == 8 && g[6] == '0') ok = false;

if((bsg & bs03).count() == 8 && g[9] == '0') ok = false;

if((bsg & bs04).count() == 8 && g[10] == '0') ok = false;

// 空洞のパターン(その2).

// 1111

// 1001

// 1111

// 0000

// -> 1111100111110000, 0000111110011111 と照合.

bitset<16> bs11("1111100111110000");

bitset<16> bs12("0000111110011111");

if((bsg & bs11).count() == 10 && (g[5] == '0' || g[6] == '0')) ok = false;

if((bsg & bs12).count() == 10 && (g[9] == '0' || g[10] == '0')) ok = false;

// 空洞のパターン(その3).

// 1110

// 1010

// 1110

// -> 1110101010101110, 0111010101010111 と照合.

bitset<16> bs21("1110101010101110");

bitset<16> bs22("0111010101010111");

if((bsg & bs21).count() == 10 && (g[5] == '0' || g[9] == '0')) ok = false;

if((bsg & bs22).count() == 10 && (g[6] == '0' || g[10] == '0')) ok = false;

// 空洞のパターン(その4).

// 1111

// 1001

// 1111

// -> 1111100110011111 と照合.

bitset<16> bs31("1111100110011111");

if((bsg & bs31).count() == 12){

if(g[5] == '0' || g[6] == '0' || g[9] == '0' || g[10] == '0') ok = false;

}

// 内部に, 空洞があるか(※実装をやり直す).

// -> 6 × 6 のエリアで確認する方法(解説通り).

// 2進数値(36桁)で, '1' を村, '0' を平野と見做して, (拡張した)お堀を作成.

string h = "000000";

rep(j, 16){

if(j % 4 == 0) h.pb('0');

if(i & (1 << (15 - j))) h.pb('1');

else h.pb('0');

if(j % 4 == 3) h.pb('0');

}

h += "000000";

// 連結成分チェック(村を含まない側).

idx = 0;

int cOut[36];

rep(j, 36) cOut[j] = 0;

rep(j, 36) if(!cOut[j] && h[j] == '0') bfs(h, j, 6, 6, cOut, ++idx, '0');

// if(i == 59863) printf("%s\n%s\n", g.c_str(), h.c_str());

// 連結成分(村を含まない側)の個数が, 1 より大きい場合.

if(idx > 1) continue;

// 村を全て含むか.

rep(j, 16){

if(board[j] == '1' && g[j] == '0'){

ok = false;

break;

}

// カウントアップ.

if(ok) ans++;

}

// 4. 出力.

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

return 0;

}

[入力例]
1 0 0 0
0 0 1 0
0 0 0 0
1 0 0 0

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

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

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

[入力例]
1 0 0 1
0 0 1 0
0 1 0 0
1 0 0 1

[出力例]
153

[入力例]
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1

[出力例]
373

[入力例]
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0

[出力例]
696

[入力例]
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

[出力例]
2401

[入力例]
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

[出力例]
4111

[入力例]

1 0 0 0

0 0 1 0

0 0 0 0

1 0 0 0

[出力例]

1272

※AtCoderテストケースより

[入力例]

1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

1 0 0 1

0 0 1 0

0 1 0 0

1 0 0 1

[出力例]

153

[入力例]

1 0 0 1

0 0 0 0

1 0 0 1

[出力例]

373

[入力例]

0 1 0 0

0 0 0 1

1 0 0 0

0 0 1 0

[出力例]

696

[入力例]

0 0 0 0

0 1 1 0

0 0 0 0

[出力例]

2401

[入力例]

1 0 0 0

0 0 0 0

[出力例]

4111

■参照サイト
AtCoder Beginner Contest 219

2021年9月20日

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題C (Neo-lexicographic Ordering) ～問題D (Strange Lunchbox) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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. 入力情報.
    char x[33];
    scanf("%s", x);
    
    // 2. 対応表作成.
    string X(x);
    map<char, char> ix, ox;
    rep(i, X.size()){
        ix['a' + i] = X[i];
        ox[X[i]]    = 'a' + i;
    }
    
    // 3. 並べ替え対象の文字列情報.
    int N;
    scanf("%d", &N);
    vs v;
    rep(i, N){
        char c[22];
        scanf("%s", c);
        string s(c);
        rep(j, s.size()) s[j] = ox[s[j]];
        v.pb(s);
    }
    
    // 4. sort.
    sort(all(v));
    
    // 5. 出力.
    for(auto &p : v){
        string ans = p;
        rep(i, ans.size()) ans[i] = ix[ans[i]];
        printf("%s\n", ans.c_str());
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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. 入力情報.

char x[33];

scanf("%s", x);

// 2. 対応表作成.

string X(x);

map<char, char> ix, ox;

rep(i, X.size()){

ix['a' + i] = X[i];

ox[X[i]] = 'a' + i;

}

// 3. 並べ替え対象の文字列情報.

int N;

scanf("%d", &N);

vs v;

rep(i, N){

char c[22];

scanf("%s", c);

string s(c);

rep(j, s.size()) s[j] = ox[s[j]];

v.pb(s);

}

// 4. sort.

sort(all(v));

// 5. 出力.

for(auto &p : v){

string ans = p;

rep(i, ans.size()) ans[i] = ix[ans[i]];

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

}

return 0;

}

[入力例]
bacdefghijklmnopqrstuvwxzy
4
abx
bzz
bzy
caa

[出力例]
bzz
bzy
abx
caa
※AtCoderテストケースより

[入力例]
zyxwvutsrqponmlkjihgfedcba
5
a
ab
abc
ac
b

[出力例]
b
a
ac
ab
abc
※AtCoderテストケースより

[入力例]
rqpoihgfnmlwvutzyedcbaxskj
10
nvtyqh
coqnne
lgvixt
erswhk
dnfzdv
zjsxzq
sjcveg
orxzqy
ougfli
doronj

[出力例]
orxzqy
ougfli
nvtyqh
lgvixt
zjsxzq
erswhk
doronj
dnfzdv
coqnne
sjcveg

[入力例]
dcpxskjhgfnoiwvutzybamlrqe
15
sndgxatct
owgwzag
qdduk
xtajce
oajsn
ysllcgo
mzaqdh
llobul
fahfo
had
ompyn
ssmiwhgz
iazoaqa
dykdyhe
sbmrqnze

[出力例]
dykdyhe
xtajce
ssmiwhgz
sndgxatct
sbmrqnze
had
fahfo
owgwzag
oajsn
ompyn
iazoaqa
ysllcgo
mzaqdh
llobul
qdduk

[入力例]

bacdefghijklmnopqrstuvwxzy

abx

bzz

bzy

caa

[出力例]

bzz

bzy

abx

caa

※AtCoderテストケースより

[入力例]

zyxwvutsrqponmlkjihgfedcba

abc

[出力例]

abc

※AtCoderテストケースより

[入力例]

rqpoihgfnmlwvutzyedcbaxskj

nvtyqh

coqnne

lgvixt

erswhk

dnfzdv

zjsxzq

sjcveg

orxzqy

ougfli

doronj

[出力例]

orxzqy

ougfli

nvtyqh

lgvixt

zjsxzq

erswhk

doronj

dnfzdv

coqnne

sjcveg

[入力例]

dcpxskjhgfnoiwvutzybamlrqe

sndgxatct

owgwzag

qdduk

xtajce

oajsn

ysllcgo

mzaqdh

llobul

fahfo

had

ompyn

ssmiwhgz

iazoaqa

dykdyhe

sbmrqnze

[出力例]

dykdyhe

xtajce

ssmiwhgz

sndgxatct

sbmrqnze

had

fahfo

owgwzag

oajsn

ompyn

iazoaqa

ysllcgo

mzaqdh

llobul

qdduk

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

// 解き直し.
// https://atcoder.jp/contests/abc219/editorial/2651
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int INF = 2020202020;
int a[303], b[303], dp[303][303][303];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    rep(i, N) scanf("%d %d", &a[i], &b[i]);
    
    // 2. dp更新.
    rep(i, N + 1) rep(j, X + 1) rep(k, Y + 1) dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    repx(i, 1, N + 1){
        rep(j, X + 1){
            int p = min(j + a[i - 1], X);
            rep(k, Y + 1){
                // 弁当を購入する.
                int q = min(k + b[i - 1], Y);
                dp[i][p][q] = min(dp[i][p][q], dp[i - 1][j][k] + 1);
                
                // 弁当を購入しない.
                dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", (dp[N][X][Y] == INF) ? -1 : dp[N][X][Y]);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

const int INF = 2020202020;

int a[303], b[303], dp[303][303][303];

int main(){

// 1. 入力情報.

int N, X, Y;

scanf("%d %d %d", &N, &X, &Y);

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

// 2. dp更新.

rep(i, N + 1) rep(j, X + 1) rep(k, Y + 1) dp[i][j][k] = INF;

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

repx(i, 1, N + 1){

rep(j, X + 1){

int p = min(j + a[i - 1], X);

rep(k, Y + 1){

// 弁当を購入する.

int q = min(k + b[i - 1], Y);

dp[i][p][q] = min(dp[i][p][q], dp[i - 1][j][k] + 1);

// 弁当を購入しない.

dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);

}

// 3. 出力.

printf("%d\n", (dp[N][X][Y] == INF) ? -1 : dp[N][X][Y]);

return 0;

}

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

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

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

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

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

[出力例]
5

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

[出力例]
10

[入力例]

5 6

2 1

3 4

2 3

[出力例]

※AtCoderテストケースより

[入力例]

8 8

3 4

2 3

2 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

13 18

1 3

2 1

3 2

5 4

3 8

5 2

3 1

[出力例]

[入力例]

77 88

2 2

5 9

10 6

3 1

12 5

2 9

3 6

4 7

11 5

1 10

9 5

5 7

11 3

8 11

4 9

9 2

4 9

6 5

6 11

7 2

5 4

5 12

10 8

2 2

12 2

12 8

5 8

5 9

2 6

6 2

[出力例]

■参照サイト
AtCoder Beginner Contest 219

2021年9月19日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題G (Game on Tree 2) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説(プログラム)を参考に実装して, AC版に持って行く方針を取った.
2. 苦手な動的計画法(木dp)の訓練を積めたので, 非常に良かったと思う.
3. いったん自力で実装してみたものの, AC版に到達できなかった.
-> 原因としては, 二つの multiset の個数調整で, 実装が正しくなかったこと, dpへの中央値設定(のタイミング, 更新条件)などがあげられると推測する.
いずれにしても, dfsの実装を正しく行うことは, 相変わらず, 直観的に分かりづらく, 難しく感じる(※)ため, 継続して, 今後の課題になっていくと思う.
※dfsの終了条件, dp更新(条件, タイミング)などが, 難しく感じる原因の一つと推測する.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解答不能.
// https://atcoder.jp/contests/abc218/editorial/2607
// -> dfs の 実装パターン を 暗記すること(特に, 終了条件, multiset の 利用方法など).
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
int a[101010], dp[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    vvi G(N);
    rep(i, N - 1){
        int u, v;
        scanf("%d %d", &u, &v);
        u--, v--;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. 中央値.
    auto f = [&](multiset<int> &l, multiset<int> &r) -> int{
        int m = -1;
        if(l.size() == r.size() + 1){
            auto it = l.end();
            m = *(--it);
        }else{
            auto it1 = l.end();
            auto it2 = r.begin();
            m = (*(--it1) + *it2) / 2;
        }
        return m;
    };
    
    // 3. 個数調整.
    auto g = [&](multiset<int> &l, multiset<int> &r) -> void{
        // 左側の最大値を, 右側に移動.
        if(l.size()){
            auto itr = l.end();
            --itr;
            r.insert(*itr);
            l.erase(itr);
        }
        
        // 左側, 右側のサイズを調整.
        while(l.size() < r.size()){
            l.insert(*r.begin());
            r.erase(r.begin());
        }
        return;
    };
    
    // 4. 削除.
    auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{
        auto itr = l.end();
        --itr;
        if(*itr < x) r.erase(r.lower_bound(x));
        else         l.erase(l.lower_bound(x));
        return;
    };
    
    // 5. dfs.
    multiset<int> l, r;
    auto dfs = [&](auto self, int cur, int bef, int d) -> void{
        // 多重集合に, 要素を追加.
        l.insert(a[cur]);
        g(l, r);
        
        // dp更新.
        int mMin = 2020202020;
        int mMax = 0;
        for(int nex : G[cur]){
            if(nex != bef){
                self(self, nex, cur, d + 1);
                mMin = min(mMin, dp[nex]);
                mMax = max(mMax, dp[nex]);
            }
        }
        
        // 中央値設定など.
        if(mMax == 0)  dp[cur] = f(l, r);
        else if(d & 1) dp[cur] = mMin;
        else           dp[cur] = mMax;
        
        // 多重集合から, 要素を削除.
        h(l, r, a[cur]);
        g(l, r);
        
        // 終了.
        return;
    };
    
    // 6. 木dp.
    dfs(dfs, 0, -1, 0);
    
    // 7. 出力.
    printf("%d\n", dp[0]);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解答不能.

// https://atcoder.jp/contests/abc218/editorial/2607

// -> dfs の実装パターンを暗記すること(特に, 終了条件, multiset の利用方法など).

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int a[101010], dp[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

vvi G(N);

rep(i, N - 1){

int u, v;

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

u--, v--;

G[u].pb(v);

G[v].pb(u);

}

// 2. 中央値.

auto f = [&](multiset<int> &l, multiset<int> &r) -> int{

int m = -1;

if(l.size() == r.size() + 1){

auto it = l.end();

m = *(--it);

}else{

auto it1 = l.end();

auto it2 = r.begin();

m = (*(--it1) + *it2) / 2;

}

return m;

};

// 3. 個数調整.

auto g = [&](multiset<int> &l, multiset<int> &r) -> void{

// 左側の最大値を, 右側に移動.

if(l.size()){

auto itr = l.end();

--itr;

r.insert(*itr);

l.erase(itr);

}

// 左側, 右側のサイズを調整.

while(l.size() < r.size()){

l.insert(*r.begin());

r.erase(r.begin());

}

return;

};

// 4. 削除.

auto h = [&](multiset<int> &l, multiset<int> &r, int x) -> void{

auto itr = l.end();

--itr;

if(*itr < x) r.erase(r.lower_bound(x));

else l.erase(l.lower_bound(x));

return;

};

// 5. dfs.

multiset<int> l, r;

auto dfs = [&](auto self, int cur, int bef, int d) -> void{

// 多重集合に, 要素を追加.

l.insert(a[cur]);

g(l, r);

// dp更新.

int mMin = 2020202020;

int mMax = 0;

for(int nex : G[cur]){

if(nex != bef){

self(self, nex, cur, d + 1);

mMin = min(mMin, dp[nex]);

mMax = max(mMax, dp[nex]);

}

// 中央値設定など.

if(mMax == 0) dp[cur] = f(l, r);

else if(d & 1) dp[cur] = mMin;

else dp[cur] = mMax;

// 多重集合から, 要素を削除.

h(l, r, a[cur]);

g(l, r);

// 終了.

return;

};

// 6. 木dp.

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

// 7. 出力.

printf("%d\n", dp[0]);

return 0;

}

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

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

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

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

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

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

[入力例]
2
6 18
1 2

[出力例]
12

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

[出力例]
6

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

[出力例]
5

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

[出力例]
10

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

[出力例]
15

100

101

102

[入力例]

2 4 6 8 10

4 5

3 4

1 5

2 4

[出力例]

※AtCoderテストケースより

[入力例]

6 4 6 10 8

1 4

1 2

1 5

1 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 6 4 6 6

1 2

2 3

4 6

2 5

2 6

[出力例]

※AtCoderテストケースより

[入力例]

6 18

1 2

[出力例]

[入力例]

6 8 2

1 2

2 3

[出力例]

[入力例]

6 2 8 12 4 2

1 2

1 6

6 3

6 4

4 5

[出力例]

[入力例]

8 2 10 12 16 2 4 20 18 14 12 6 4 8 10 6

1 2

1 3

2 4

2 5

4 8

4 9

5 10

5 11

3 6

3 7

6 12

6 13

7 14

7 15

7 16

[出力例]

[入力例]

18 2 4 18 24 12 8 14 12

1 2

1 3

2 4

2 5

5 6

5 7

7 8

7 9

[出力例]

■参照サイト
AtCoder Beginner Contest 218

2021年9月17日2021年9月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題F (Blocked Roads) を解いてみた.

■感想.
1. 問題F は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2606
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vs = vector<set<int>>;
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 pb push_back
#define a first
#define b second
int info[404][404]; // 最短経路を構成する辺情報.
int memo[404][404]; // 最短経路上の辺情報.

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vs OG(N), RG(N);
    vp edges;
    rep(i, M){
        int s, t;
        scanf("%d %d", &s, &t);
        s--, t--;
        OG[s].insert(t);  // 有向グラフ.
        RG[t].insert(s);  // 有向グラフ(逆向き).
        edges.pb({s, t}); // 有向辺.
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 訪問済であれば, 処理をスキップ.
                if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
            }
        }
        return;
    };
    
    // 3. 最短距離(グラフの有向辺が, 全てそろっている場合).
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(OG, 0, d);
    
    // 4. 最短経路を取得.
    // -> 到達可能な場合に, 最短経路を取得(ゴールから逆算).
    auto f = [&](vs &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]){
                // 距離 が 1 小さい場合に, 最短経路として保存.
                if(d[e] == d[u] - 1){
                    info[e][u]++;
                    q.push(e);
                    break;
                }
            }
        }
        return;
    };
    int D = d[N - 1];
    if(D) f(RG, N - 1, d);
    
    // 5. クエリ回答.
    for(auto &e : edges){
        // 辺情報.
        int u = e.a; // 始点.
        int v = e.b; // 終点.
        
        // 到達不可能な場合.
        if(!D) puts("-1");
        
        // 到達可能な場合.
        if(D){
            // 辺(u, v) が, 最短経路上に無い場合.
            if(!info[u][v]) printf("%d\n", D);
            
            // 辺(u, v) が, 最短経路上に有る場合.
            if(info[u][v]){
                // 探索済みの場合.
                if(memo[u][v] != 0) printf("%d\n", memo[u][v]);
                
                // 探索済みでない場合.
                if(memo[u][v] == 0){
                    // グラフから, 辺を削除.
                    OG[u].erase(v);
                    
                    // bfs.
                    int duv[N];
                    rep(i, N) duv[i] = 0;
                    bfs(OG, 0, duv);
                    
                    // 探索結果を保存.
                    memo[u][v] = duv[N - 1] ? duv[N - 1] : -1;
                    
                    // グラフに, 辺を戻す.
                    OG[u].insert(v);
                    
                    // 出力.
                    printf("%d\n", memo[u][v]);
                }
            }
        }
    }
    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

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2606

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vs = vector<set<int>>;

using vp = vector;

#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

int info[404][404]; // 最短経路を構成する辺情報.

int memo[404][404]; // 最短経路上の辺情報.

int main(){

// 1. 入力情報.

int N, M;

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

vs OG(N), RG(N);

vp edges;

rep(i, M){

int s, t;

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

s--, t--;

OG[s].insert(t); // 有向グラフ.

RG[t].insert(s); // 有向グラフ(逆向き).

edges.pb({s, t}); // 有向辺.

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 訪問済であれば, 処理をスキップ.

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

}

return;

};

// 3. 最短距離(グラフの有向辺が, 全てそろっている場合).

int d[N];

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

bfs(OG, 0, d);

// 4. 最短経路を取得.

// -> 到達可能な場合に, 最短経路を取得(ゴールから逆算).

auto f = [&](vs &G, int s, int* d){

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

// 距離が 1 小さい場合に, 最短経路として保存.

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

info[e][u]++;

q.push(e);

break;

}

return;

};

int D = d[N - 1];

if(D) f(RG, N - 1, d);

// 5. クエリ回答.

for(auto &e : edges){

// 辺情報.

int u = e.a; // 始点.

int v = e.b; // 終点.

// 到達不可能な場合.

if(!D) puts("-1");

// 到達可能な場合.

if(D){

// 辺(u, v) が, 最短経路上に無い場合.

if(!info[u][v]) printf("%d\n", D);

// 辺(u, v) が, 最短経路上に有る場合.

if(info[u][v]){

// 探索済みの場合.

if(memo[u][v] != 0) printf("%d\n", memo[u][v]);

// 探索済みでない場合.

if(memo[u][v] == 0){

// グラフから, 辺を削除.

OG[u].erase(v);

// bfs.

int duv[N];

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

bfs(OG, 0, duv);

// 探索結果を保存.

memo[u][v] = duv[N - 1] ? duv[N - 1] : -1;

// グラフに, 辺を戻す.

OG[u].insert(v);

// 出力.

printf("%d\n", memo[u][v]);

}

return 0;

}

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

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

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

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

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

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

[入力例]
4 1
1 2

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

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

[出力例]
-1
-1
-1

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

[出力例]
3
3
4
-1
3
3
3
3
5

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

[出力例]
7
5
5
8
5
5
5
5
-1
5
5
6
5
5
5
7
5
5
5
5
5
5
5
5

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

[入力例]

3 3

1 2

1 3

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 2

2 3

2 4

3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 10

1 2

1 4

1 5

2 1

2 3

3 1

3 2

3 5

4 2

4 3

[出力例]

※AtCoderテストケースより

[入力例]

4 1

1 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

5 3

1 2

3 4

3 5

[出力例]

-1

[入力例]

7 9

1 3

3 4

1 4

4 2

7 4

2 5

5 6

6 7

2 7

[出力例]

-1

[入力例]

18 24

1 2

1 3

3 6

2 5

6 2

6 7

7 4

4 5

5 8

8 4

8 9

8 10

9 10

10 11

10 17

10 18

10 12

12 15

12 13

12 14

13 14

14 16

13 18

18 14

[出力例]

-1

■参照サイト
AtCoder Beginner Contest 218

2021年9月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 210 の問題E (Ring MST) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 解説にあるように, 最小全域木(Kruskal’s Algorithm) の性質を使って, 最終的に, 数式まで落とし込んでいくロジックが, 非常に面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc210/editorial/2299
// 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>;
#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()
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int M;
    LL N;
    scanf("%lld %d", &N, &M);
    vp v;
    rep(i, M){
        LL a, c;
        scanf("%lld %lld", &a, &c);
        v.pb({c, a});
    }
    
    // 2. sort.
    // -> 解説にある通り, 最小全域木(Kruskal's Algorithm) を ベースに考えるため必要.
    sort(all(v));
    
    // 3. コストの最小値は？
    LL ans = 0, bef = N, cur;
    for(auto &p : v){
        // 今回分更新.
        cur = __gcd(bef, p.b);
        
        // 集計.
        ans += p.a * (bef - cur);
        
        // 前回分更新.
        bef = cur;
    }
    
    // 4. 全域木が無い場合.
    if(cur > 1) ans = -1;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc210/editorial/2299

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector;

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int M;

LL N;

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

vp v;

rep(i, M){

LL a, c;

scanf("%lld %lld", &a, &c);

v.pb({c, a});

}

// 2. sort.

// -> 解説にある通り, 最小全域木(Kruskal's Algorithm) をベースに考えるため必要.

sort(all(v));

// 3. コストの最小値は？

LL ans = 0, bef = N, cur;

for(auto &p : v){

// 今回分更新.

cur = __gcd(bef, p.b);

// 集計.

ans += p.a * (bef - cur);

// 前回分更新.

bef = cur;

}

// 4. 全域木が無い場合.

if(cur > 1) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
4 2
2 3
3 5

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

[入力例]
6 1
3 4

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

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

[出力例]
-1

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

[出力例]
9

[入力例]
32 10
12 5
16 1
22 13
31 10
1 7
19 3
21 8
3 17
17 5
26 10

[出力例]
61

[入力例]
33333 22
19002 32181
25701 58593
18097 46854
383 94737
14074 64088
5079 170351
17624 152448
21230 18133
1601 73981
31329 28493
22453 10214
3365 132535
9035 127417
28030 170783
14237 68665
13917 179105
21643 104707
6672 65054
30083 196465
31715 98708
19864 154275
25748 53992

[出力例]
340453048

[入力例]

4 2

2 3

3 5

[出力例]

※AtCoderテストケースより

[入力例]

6 1

3 4

[出力例]

-1

※AtCoderテストケースより

[入力例]

8 3

2 1

4 2

6 3

[出力例]

-1

[入力例]

10 9

1 9

2 8

3 7

4 6

5 5

6 4

7 3

8 2

9 1

[出力例]

[入力例]

32 10

12 5

16 1

22 13

31 10

1 7

19 3

21 8

3 17

17 5

26 10

[出力例]

[入力例]

33333 22

19002 32181

25701 58593

18097 46854

383 94737

14074 64088

5079 170351

17624 152448

21230 18133

1601 73981

31329 28493

22453 10214

3365 132535

9035 127417

28030 170783

14237 68665

13917 179105

21643 104707

6672 65054

30083 196465

31715 98708

19864 154275

25748 53992

[出力例]

340453048

■参照サイト
AtCoder Beginner Contest 210

2021年9月15日

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

C++の練習を兼ねて, AtCoder Beginner Contest 210 の問題C (Colorful Candies) ～問題D (National Railway) を解いてみた.

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

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int c[303030];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    map<int, int> m;
    int ans = 0;
    rep(i, N){
        scanf("%d", &c[i]);
        // K番目まで.
        if(i < K){
            m[c[i]]++;
            ans = m.size();
        }
        
        // (K + 1)番目以降.
        if(i >= K){
            // (i - K)番目を除外.
            m[c[i - K]]--;
            if(m[c[i - K]] == 0) m.erase(c[i - K]);
            
            // i番目を追加.
            m[c[i]]++;
            
            // 最大値更新.
            ans = max(ans, (int)m.size());
        }
    }
    
    // 2. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int c[303030];

int main(){

// 1. 入力情報.

int N, K;

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

map<int, int> m;

int ans = 0;

rep(i, N){

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

// K番目まで.

if(i < K){

m[c[i]]++;

ans = m.size();

}

// (K + 1)番目以降.

if(i >= K){

// (i - K)番目を除外.

m[c[i - K]]--;

if(m[c[i - K]] == 0) m.erase(c[i - K]);

// i番目を追加.

m[c[i]]++;

// 最大値更新.

ans = max(ans, (int)m.size());

}

// 2. 出力.

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

return 0;

}

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

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

[入力例]
5 5
4 4 4 4 4

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

[入力例]
10 6
304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

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

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

[出力例]
3

[入力例]
100 11
1 2 1 2 2 2 1 3 2 1 2 1 1 1 2 2 3 3 3 4 4 4 1 1 4 1 3 2 4 2 4 4 1 3 3 2 2 1 2 1 1 1 1 3 2 3 3 2 1 2 3 1 3 2 1 1 3 1 1 3 2 5 3 2 4 4 6 4 1 1 6 5 1 4 1 2 6 5 5 5 6 2 1 4 6 6 2 5 3 3 2 3 3 3 1 4 3 2 3 4

[出力例]
6

[入力例]

7 3

1 2 1 2 3 3 1

[出力例]

※AtCoderテストケースより

[入力例]

5 5

4 4 4 4 4

[出力例]

※AtCoderテストケースより

[入力例]

10 6

304621362 506696497 304621362 506696497 834022578 304621362 414720753 304621362 304621362 414720753

[出力例]

※AtCoderテストケースより

[入力例]

30 7

2 1 5 1 2 1 2 2 2 1 1 3 1 1 1 4 3 3 4 1 1 3 3 3 1 1 5 3 5 1

[出力例]

[入力例]

100 11

1 2 1 2 2 2 1 3 2 1 2 1 1 1 2 2 3 3 3 4 4 4 1 1 4 1 3 2 4 2 4 4 1 3 3 2 2 1 2 1 1 1 1 3 2 3 3 2 1 2 3 1 3 2 1 1 3 1 1 3 2 5 3 2 4 4 6 4 1 1 6 5 1 4 1 2 6 5 5 5 6 2 1 4 6 6 2 5 3 3 2 3 3 3 1 4 3 2 3 4

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc210/editorial/2298
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
using vvl = vector<vl>;
#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()
const LL INF = 202020202020202020;

int main(){
    
    // 1. 入力情報.
    int H, W;
    LL C;
    scanf("%d %d %lld", &H, &W, &C);
    vvl o, r;
    rep(i, H){
        vl x;
        rep(j, W){
            LL a;
            scanf("%lld", &a);
            x.pb(a);
        }
        o.pb(x);
        
        // グリッド(左右反転版).
        reverse(all(x));
        r.pb(x);
    }
    
    // 2. 最小コスト計算.
    auto f = [&](vvl &a) -> LL{
        // 2-1. dp初期化.
        LL dp[H + 1][W + 1], pd[H + 1][W + 1];
        rep(i, H + 1){
            rep(j, W + 1){
                // 解説通り.
                dp[i][j] = 0;
                pd[i][j] = 0;
                if(i == 0 || j == 0) dp[i][j] = INF;
            }
        }
        
        // 2-2. dp更新.
        repx(i, 1, H + 1){
            repx(j, 1, W + 1){
                dp[i][j] = min({a[i - 1][j - 1], dp[i - 1][j] + C, dp[i][j - 1] + C});
            }
        }
        
        // 2-3. pd更新.
        repx(i, 1, H + 1){
            repx(j, 1, W + 1){
                pd[i][j] = min(dp[i - 1][j] + C + a[i - 1][j - 1], dp[i][j - 1] + C + a[i - 1][j - 1]);
            }
        }
        
        // 2-4. 最小コストは？
        LL ret = INF;
        repx(i, 1, H + 1) repx(j, 1, W + 1) ret = min(ret, pd[i][j]);
        
        // 2-5. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%lld\n", min(f(o), f(r)));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc210/editorial/2298

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

const LL INF = 202020202020202020;

int main(){

// 1. 入力情報.

int H, W;

LL C;

scanf("%d %d %lld", &H, &W, &C);

vvl o, r;

rep(i, H){

vl x;

rep(j, W){

LL a;

scanf("%lld", &a);

x.pb(a);

}

o.pb(x);

// グリッド(左右反転版).

reverse(all(x));

r.pb(x);

}

// 2. 最小コスト計算.

auto f = [&](vvl &a) -> LL{

// 2-1. dp初期化.

LL dp[H + 1][W + 1], pd[H + 1][W + 1];

rep(i, H + 1){

rep(j, W + 1){

// 解説通り.

dp[i][j] = 0;

pd[i][j] = 0;

if(i == 0 || j == 0) dp[i][j] = INF;

}

// 2-2. dp更新.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

dp[i][j] = min({a[i - 1][j - 1], dp[i - 1][j] + C, dp[i][j - 1] + C});

}

// 2-3. pd更新.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

pd[i][j] = min(dp[i - 1][j] + C + a[i - 1][j - 1], dp[i][j - 1] + C + a[i - 1][j - 1]);

}

// 2-4. 最小コストは？

LL ret = INF;

repx(i, 1, H + 1) repx(j, 1, W + 1) ret = min(ret, pd[i][j]);

// 2-5. 返却.

return ret;

};

// 3. 出力.

printf("%lld\n", min(f(o), f(r)));

return 0;

}

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

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

[入力例]
3 3 1000000000
1000000 1000000 1
1000000 1000000 1000000
1 1000000 1000000

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

[入力例]
7 10 15
700 485 632 445 516 312 402 613 610 623
481 512 264 601 556 586 218 531 448 360
235 660 602 112 448 511 643 621 518 290
475 552 506 466 346 266 507 595 467 477
416 320 522 565 232 489 654 685 360 280
598 357 598 695 532 455 300 286 101 580
227 366 520 671 247 611 376 387 292 674

[出力例]
333

[入力例]
20 15 1111
69063 33529 70578 50473 33471 52692 59471 57207 41725 73815 75990 58995 39558 34738 49390
47707 78277 43559 38292 55222 31209 41636 54607 61137 68448 36770 59629 42720 78848 37025
31609 57109 52053 64466 34145 76388 54801 69362 53657 43378 78784 43989 58151 69935 75943
67146 71389 89098 48517 49145 40974 77705 48244 74143 45828 48442 41498 42878 78315 58550
72032 61268 54425 74660 35074 79791 34745 34377 57131 48088 33329 67736 53202 48549 67432
69402 54219 46534 34541 71061 63496 78626 69645 30327 35236 35039 56727 68706 76467 39552
42314 77814 38446 51468 66049 76406 68834 71865 63726 37778 60911 61255 53232 58945 62656
59630 41382 33943 72670 39640 77778 54823 62697 59889 67380 69919 55597 79104 53231 42149
66203 43153 64211 74574 60586 23900 53138 58149 72500 42190 40920 76979 67916 64220 78405
52320 59411 67566 76096 61546 65448 44318 33146 77883 65354 61381 66288 57002 62162 66443
57886 71760 33859 68348 76774 76808 74974 79765 55667 44448 58907 77074 50676 52163 51846
50856 55845 35800 70185 71215 73791 54767 77859 54498 74996 63781 73995 77765 45745 62157
75593 68722 31381 62576 71971 72569 62767 39665 48665 68091 53402 66721 53620 55335 56359
78114 49803 63406 41829 69565 73215 60739 69744 79310 61955 55631 68519 41628 70338 71592
53919 45273 47108 70105 79995 41198 65080 52365 39594 50123 63601 70300 52884 57012 67253
73311 53015 51435 77753 71262 57758 69687 68265 69790 50121 71519 59045 71228 68859 64313
79813 44042 59482 41806 67679 39375 51816 77314 78514 79956 51152 46028 53674 49413 71485
37928 73924 60817 41926 77080 44004 65161 54692 48732 59836 71124 45275 72694 12768 57388
47231 73723 54306 34425 77777 66795 61515 54203 69957 57813 49482 58912 62337 73125 54917
72717 32344 75565 33948 51856 64994 62686 76308 67035 41810 68473 45145 48847 74636 44683

[出力例]
55555

[入力例]

3 4 2

1 7 7 9

9 6 3 7

7 8 6 4

[出力例]

※AtCoderテストケースより

[入力例]

3 3 1000000000

1000000 1000000 1

1000000 1000000 1000000

1 1000000 1000000

[出力例]

1001000001

※AtCoderテストケースより

[入力例]

7 10 15

700 485 632 445 516 312 402 613 610 623

481 512 264 601 556 586 218 531 448 360

235 660 602 112 448 511 643 621 518 290

475 552 506 466 346 266 507 595 467 477

416 320 522 565 232 489 654 685 360 280

598 357 598 695 532 455 300 286 101 580

227 366 520 671 247 611 376 387 292 674

[出力例]

333

[入力例]

20 15 1111

69063 33529 70578 50473 33471 52692 59471 57207 41725 73815 75990 58995 39558 34738 49390

47707 78277 43559 38292 55222 31209 41636 54607 61137 68448 36770 59629 42720 78848 37025

31609 57109 52053 64466 34145 76388 54801 69362 53657 43378 78784 43989 58151 69935 75943

67146 71389 89098 48517 49145 40974 77705 48244 74143 45828 48442 41498 42878 78315 58550

72032 61268 54425 74660 35074 79791 34745 34377 57131 48088 33329 67736 53202 48549 67432

69402 54219 46534 34541 71061 63496 78626 69645 30327 35236 35039 56727 68706 76467 39552

42314 77814 38446 51468 66049 76406 68834 71865 63726 37778 60911 61255 53232 58945 62656

59630 41382 33943 72670 39640 77778 54823 62697 59889 67380 69919 55597 79104 53231 42149

66203 43153 64211 74574 60586 23900 53138 58149 72500 42190 40920 76979 67916 64220 78405

52320 59411 67566 76096 61546 65448 44318 33146 77883 65354 61381 66288 57002 62162 66443

57886 71760 33859 68348 76774 76808 74974 79765 55667 44448 58907 77074 50676 52163 51846

50856 55845 35800 70185 71215 73791 54767 77859 54498 74996 63781 73995 77765 45745 62157

75593 68722 31381 62576 71971 72569 62767 39665 48665 68091 53402 66721 53620 55335 56359

78114 49803 63406 41829 69565 73215 60739 69744 79310 61955 55631 68519 41628 70338 71592

53919 45273 47108 70105 79995 41198 65080 52365 39594 50123 63601 70300 52884 57012 67253

73311 53015 51435 77753 71262 57758 69687 68265 69790 50121 71519 59045 71228 68859 64313

79813 44042 59482 41806 67679 39375 51816 77314 78514 79956 51152 46028 53674 49413 71485

37928 73924 60817 41926 77080 44004 65161 54692 48732 59836 71124 45275 72694 12768 57388

47231 73723 54306 34425 77777 66795 61515 54203 69957 57813 49482 58912 62337 73125 54917

72717 32344 75565 33948 51856 64994 62686 76308 67035 41810 68473 45145 48847 74636 44683

[出力例]

55555

■参照サイト
AtCoder Beginner Contest 210

2021年9月14日

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

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

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. Union-Find木, 最小全域木(Kruskal’s Algorithm) の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2580
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vl = vector<LL>;
using T3 = tuple<LL, int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
LL c[202020];
int a[202020], b[202020];

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL cTotal = 0;
    rep(i, M){
        scanf("%d %d %lld", &a[i], &b[i], &c[i]);
        a[i]--;
        b[i]--;
        cTotal += c[i]; // コスト合計.
    }
    
    // 2. sort.
    vector<T3> t;
    rep(i, M) t.emplace_back(c[i], a[i], b[i]);
    sort(all(t));
    
    // 3. 最小全域木(Kruskal's Algorithm)を計算.
    // 競プロ典型 90 問 (049 - Flip Digits 2)
    // https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp
    LL cSum = 0;
    UnionFind uf(N + 2);
    rep(i, t.size()){
        // 3-1. グラフ情報.
        int u = get<1>(t[i]);
        int v = get<2>(t[i]);
        LL cost = get<0>(t[i]);
        
        // 3-2. コストが負.
        // -> 必ず, 辺を追加.
        if(cost < 0){
            uf.unite(u, v);
            cSum += cost;
        }
        
        // 3-3. コストがゼロ以上.
        // -> 最小全域木に必要な場合に, 追加.
        if(cost >= 0){
            if(!uf.same(u, v)){
                uf.unite(u, v);
                cSum += cost;
            }
        }
    }
    
    // 4. 出力.
    printf("%lld\n", cTotal - cSum);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2580

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vl = vector<LL>;

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

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

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

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

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

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

LL c[202020];

int a[202020], b[202020];

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, M;

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

LL cTotal = 0;

rep(i, M){

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

a[i]--;

b[i]--;

cTotal += c[i]; // コスト合計.

}

// 2. sort.

vector<T3> t;

rep(i, M) t.emplace_back(c[i], a[i], b[i]);

sort(all(t));

// 3. 最小全域木(Kruskal's Algorithm)を計算.

// 競プロ典型 90 問 (049 - Flip Digits 2)

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/049.cpp

LL cSum = 0;

UnionFind uf(N + 2);

rep(i, t.size()){

// 3-1. グラフ情報.

int u = get<1>(t[i]);

int v = get<2>(t[i]);

LL cost = get<0>(t[i]);

// 3-2. コストが負.

// -> 必ず, 辺を追加.

if(cost < 0){

uf.unite(u, v);

cSum += cost;

}

// 3-3. コストがゼロ以上.

// -> 最小全域木に必要な場合に, 追加.

if(cost >= 0){

if(!uf.same(u, v)){

uf.unite(u, v);

cSum += cost;

}

// 4. 出力.

printf("%lld\n", cTotal - cSum);

return 0;

}

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

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

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

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

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

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

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

[出力例]
13

※実際, 辺 1, 4, 5 を 取り除いて, 合計 4 + 3 + 6 = 13 の 報酬となる.

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

[出力例]
49

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を 取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の 報酬となる.

[入力例]

4 5

1 2 1

1 3 1

1 4 1

3 2 2

4 2 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2 1

2 3 0

3 1 -1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 2 -1

1 2 2

1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 7

1 3 4

3 4 3

1 2 -1

2 5 3

2 5 6

2 4 2

5 4 -2

[出力例]

※実際, 辺 1, 4, 5 を取り除いて, 合計 4 + 3 + 6 = 13 の報酬となる.

[入力例]

10 16

1 3 -4

7 1 3

5 3 2

3 6 -1

5 6 3

5 2 7

5 7 6

7 9 7

4 9 -3

8 9 11

4 8 4

4 2 5

2 8 6

2 10 2

6 10 7

8 10 9

[出力例]

※実際, 辺 5, 7, 8, 10, 13, 15, 16 を取り除いて, 合計 3 + 6 + 7 + 11 + 6 + 7 + 9 = 49 の報酬となる.

■参照サイト
AtCoder Beginner Contest 218
Union-Find木
 競プロ典型 90 問の問題049

2021年9月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題C (Shapes) ～問題D (Rectangles) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. 問題D の解説で, 全探索で数え上げていく方針が, なるほどと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vs S, T000;
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string s(c);
        S.pb(s);
    }
    rep(i, N){
        char c[202];
        scanf("%s", c);
        string s(c);
        T000.pb(s);
    }
    
    // 2. T を 90度, 180度, 270度回転させる.
    vs T090, T180, T270;
    string x(N, '.');
    rep(i, N){
        T090.pb(x);
        T180.pb(x);
        T270.pb(x);
    }
    rep(i, N) rep(j, N) T090[N - 1 - j][i] = T000[i][j];
    rep(i, N) rep(j, N) T180[N - 1 - j][i] = T090[i][j];
    rep(i, N) rep(j, N) T270[N - 1 - j][i] = T180[i][j];
    
    // 3. 図形 について, # の 位置関係を取得.
    auto f = [&](vs &s) -> set<P> {
        // 3-1. 基準となる場所を取得.
        set<P> ret;
        int sx = -1, sy = -1;
        rep(i, N){
            bool ok = false;
            rep(j, N){
                if(s[i][j] == '#'){
                    sx = i;
                    sy = j;
                    ok = true;
                    break;
                }
            }
            if(ok) break;
        }
        
        // 3-2. 位置関係を取得.
        rep(i, N) rep(j, N) if(s[i][j] == '#') ret.insert({i - sx, j - sy});
        
        // 3-3. 返却.
        return ret;
    };
    
    // 4. 各図形 について, # の 位置関係を保存.
    set<P> q0 = f(S);
    set<P> q1 = f(T000);
    set<P> q2 = f(T090);
    set<P> q3 = f(T180);
    set<P> q4 = f(T270);
    
    // 5. 出力.
    bool ans = false;
    if(q0 == q1 || q0 == q2 || q0 == q3 || q0 == q4) ans = true;
    printf("%s\n", ans ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vs S, T000;

rep(i, N){

char c[202];

scanf("%s", c);

string s(c);

S.pb(s);

}

rep(i, N){

char c[202];

scanf("%s", c);

string s(c);

T000.pb(s);

}

// 2. T を 90度, 180度, 270度回転させる.

vs T090, T180, T270;

string x(N, '.');

rep(i, N){

T090.pb(x);

T180.pb(x);

T270.pb(x);

}

rep(i, N) rep(j, N) T090[N - 1 - j][i] = T000[i][j];

rep(i, N) rep(j, N) T180[N - 1 - j][i] = T090[i][j];

rep(i, N) rep(j, N) T270[N - 1 - j][i] = T180[i][j];

// 3. 図形について, # の位置関係を取得.

auto f = [&](vs &s) -> set {

// 3-1. 基準となる場所を取得.

set ret;

int sx = -1, sy = -1;

rep(i, N){

bool ok = false;

rep(j, N){

if(s[i][j] == '#'){

sx = i;

sy = j;

ok = true;

break;

}

if(ok) break;

}

// 3-2. 位置関係を取得.

rep(i, N) rep(j, N) if(s[i][j] == '#') ret.insert({i - sx, j - sy});

// 3-3. 返却.

return ret;

};

// 4. 各図形について, # の位置関係を保存.

set q0 = f(S);

set q1 = f(T000);

set q2 = f(T090);

set q3 = f(T180);

set q4 = f(T270);

// 5. 出力.

bool ans = false;

if(q0 == q1 || q0 == q2 || q0 == q3 || q0 == q4) ans = true;

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

return 0;

}

[入力例]
5
.....
..#..
.###.
.....
.....
.....
.....
....#
...##
....#

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

[入力例]
5
#####
##..#
#..##
#####
.....
#####
#..##
##..#
#####
.....

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

[入力例]
4
#...
..#.
..#.
....
#...
#...
..#.
....

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

[入力例]
4
#...
.##.
..#.
....
##..
#...
..#.
....

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

[入力例]
3
#..
.#.
...
..#
.#.
...

[出力例]
Yes

[入力例]
5
..#..
.#.#.
.###.
#...#
#...#
...##
.##..
#.#..
.##..
...##

[出力例]
Yes

[入力例]
17
.................
...#...###...###.
..#.#..#..#.#....
..#.#..#..#.#....
..###..####.#....
.#...#.#..#.#....
.#...#.#..#.#....
.#...#.###...###.
.................
.####..##..#####.
....#...#..#...#.
....#...#..#...#.
.####...#..#####.
.#......#..#...#.
.#......#..#...#.
.####..###.#####.
.................
.................
.................
####..#.###......
#..#..#....###...
#..#..#....#..#..
#..####....###...
........###......
.................
#.....#.#######..
#######.#..#..#..
#.......#..#..#..
.........#####...
#######..........
#..#..#..#####...
#..#..#.#.....#..
#..#..#.#.....#..
#######.#.....#..

[出力例]
Yes

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

[入力例]

.....

..#..

.###.

.....

....#

...##

....#

[出力例]

Yes

※AtCoderテストケースより

[入力例]

#####

##..#

#..##

#####

.....

#####

#..##

##..#

#####

.....

[出力例]

※AtCoderテストケースより

[入力例]

#...

..#.

....

#...

..#.

....

[出力例]

Yes

※AtCoderテストケースより

[入力例]

#...

.##.

..#.

....

##..

#...

..#.

....

[出力例]

※AtCoderテストケースより

[入力例]

#..

.#.

...

..#

.#.

...

[出力例]

Yes

[入力例]

..#..

.#.#.

.###.

#...#

...##

.##..

#.#..

.##..

...##

[出力例]

Yes

[入力例]

.................

...#...###...###.

..#.#..#..#.#....

..###..####.#....

.#...#.#..#.#....

.#...#.###...###.

.................

.####..##..#####.

....#...#..#...#.

.####...#..#####.

.#......#..#...#.

.####..###.#####.

.................

####..#.###......

#..#..#....###...

#..#..#....#..#..

#..####....###...

........###......

.................

#.....#.#######..

#######.#..#..#..

#.......#..#..#..

.........#####...

#######..........

#..#..#..#####...

#..#..#.#.....#..

#######.#.....#..

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc218/editorial/2605
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<P> st;
    rep(i, N){
        int x, y;
        scanf("%d %d", &x, &y);
        st.insert({x, y});
    }
    
    // 2. 全探索.
    int ans = 0;
    for(auto &p : st){
        // 左下.
        int ldX = p.a;
        int ldY = p.b;
        for(auto &q : st){
            // 右上.
            int ruX = q.a;
            int ruY = q.b;
            
            // 条件を満たすかチェック.
            if(ruX <= ldX || ruY <= ldY) continue;
            
            // 左上 を 含むか？
            bool ok = true;
            if(st.count({ldX, ruY}) == 0) ok = false;
            
            // 右下 を 含むか？
            if(st.count({ruX, ldY}) == 0) ok = false;
            
            // カウント.
            if(ok) ans++;
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc218/editorial/2605

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set st;

rep(i, N){

int x, y;

scanf("%d %d", &x, &y);

st.insert({x, y});

}

// 2. 全探索.

int ans = 0;

for(auto &p : st){

// 左下.

int ldX = p.a;

int ldY = p.b;

for(auto &q : st){

// 右上.

int ruX = q.a;

int ruY = q.b;

// 条件を満たすかチェック.

if(ruX <= ldX || ruY <= ldY) continue;

// 左上を含むか？

bool ok = true;

if(st.count({ldX, ruY}) == 0) ok = false;

// 右下を含むか？

if(st.count({ruX, ldY}) == 0) ok = false;

// カウント.

if(ok) ans++;

}

// 3. 出力.

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

return 0;

}

[入力例]
6
0 0
0 1
1 0
1 1
2 0
2 1

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

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

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

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

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

[入力例]
12
3 2
3 7
3 11
5 4
5 7
5 11
7 2
7 4
7 7
7 11
9 7
9 11

[出力例]
10

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

[出力例]
22

[入力例]

0 0

0 1

1 0

1 1

2 0

2 1

[出力例]

※AtCoderテストケースより

[入力例]

0 1

1 2

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

0 1

1 0

2 0

2 1

2 2

3 0

3 2

[出力例]

※AtCoderテストケースより

[入力例]

3 2

3 7

3 11

5 4

5 7

5 11

7 2

7 4

7 7

7 11

9 7

9 11

[出力例]

[入力例]

1 0

1 5

1 8

0 5

0 9

0 12

3 0

3 2

3 5

3 8

2 3

2 9

10 8

10 9

10 11

2 7

5 8

5 11

5 2

5 3

2 12

9 8

9 11

4 3

4 9

6 0

6 5

7 0

7 2

7 3

7 5

7 7

7 9

[出力例]

■参照サイト
AtCoder Beginner Contest 218

2021年9月12日

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

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.

■感想.
1. 問題G は, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達出来た.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc216/editorial/2474
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL INF = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        int l, r, x;
        scanf("%d %d %d", &l, &r, &x);
        edge e;
        e.n = r;
        e.c = (LL)(r - l + 1 - x);
        G[l - 1].pb(e);
    }
    
    // 2. グラフに辺を追加.
    rep(i, N){
        edge e1;
        e1.n = i + 1;
        e1.c = 1LL;
        G[i].pb(e1);
        
        edge e2;
        e2.n = i;
        e2.c = 0LL;
        G[i + 1].pb(e2);
    }
    
    // 3. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 3-1. 初期化.
        priority_queue<edge> pq;
        
        // 3-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 3-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 3-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 3-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 3-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
        return;
    };
    
    // 4. 各頂点までの, 最短コストを求める.
    LL d[N + 1];     // 頂点 0 からの距離.
    int memo[N + 1]; // 訪問済みフラグ.
    rep(i, N + 1) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 5. 数列 A に含まれる 1 の 個数.
    LL a[N];
    rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);
    
    // 6. 出力.
    rep(i, N){
        printf("%lld", a[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc216/editorial/2474

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // コスト.

bool operator < (const edge &E) const{ return c > E.c; }

};

vector<edge> G[202020];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

int l, r, x;

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

edge e;

e.n = r;

e.c = (LL)(r - l + 1 - x);

G[l - 1].pb(e);

}

// 2. グラフに辺を追加.

rep(i, N){

edge e1;

e1.n = i + 1;

e1.c = 1LL;

G[i].pb(e1);

edge e2;

e2.n = i;

e2.c = 0LL;

G[i + 1].pb(e2);

}

// 3. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s, LL* d, int* memo){

// 3-1. 初期化.

priority_queue<edge> pq;

// 3-2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 3-3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 3-4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 3-5. 訪問済みフラグ設定.

if(memo[cn]) continue;

memo[cn]++;

// 3-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

return;

};

// 4. 各頂点までの, 最短コストを求める.

LL d[N + 1]; // 頂点 0 からの距離.

int memo[N + 1]; // 訪問済みフラグ.

rep(i, N + 1) d[i] = INF, memo[i] = 0;

dijkstra(0, d, memo);

// 5. 数列 A に含まれる 1 の個数.

LL a[N];

rep(i, N) a[i] = 1LL - (d[i + 1] - d[i]);

// 6. 出力.

rep(i, N){

printf("%lld", a[i]);

printf("%s", (i < N - 1) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

[出力例]
0 0 1 1 1 1 0 1 0 0

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

[出力例]
0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1

[入力例]

6 3

1 4 3

2 2 1

4 6 2

[出力例]

0 1 1 1 0 1

※AtCoderテストケースより

[入力例]

8 2

2 6 1

3 5 3

[出力例]

0 0 1 1 1 0 0 0

※AtCoderテストケースより

[入力例]

10 5

3 7 3

1 6 4

5 5 1

6 8 2

8 10 1

[出力例]

0 0 1 1 1 1 0 1 0 0

[入力例]

25 12

9 13 2

3 5 1

6 18 6

1 6 3

10 22 6

5 18 7

9 11 1

8 15 4

7 25 9

4 5 1

3 17 7

2 11 5

[出力例]

0 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 0 1 0 0 0 1 1 1 1

■参照サイト
AtCoder Beginner Contest 216

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の 問題C (Neo-lexicographic Ordering) ～ 問題D (Strange Lunchbox) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題G (Game on Tree 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題F (Blocked Roads) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 210 の 問題E (Ring MST) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 210 の 問題C (Colorful Candies) ～ 問題D (National Railway) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の 問題C (Shapes) ～ 問題D (Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の 問題G (01Sequence) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 219 の問題C (Neo-lexicographic Ordering) ～問題D (Strange Lunchbox) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題G (Game on Tree 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題F (Blocked Roads) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 210 の問題E (Ring MST) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 210 の問題C (Colorful Candies) ～問題D (National Railway) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 218 の問題C (Shapes) ～問題D (Rectangles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 216 の問題G (01Sequence) を解いてみた.