C++ | 個人用メモ帳

2021年12月14日2021年12月14日

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

C++の練習を兼ねて, JOI 2021/2022 二次予選過去問の問題C (国土分割 (Land Division)) を解いてみた.

■感想.
1. 問題Cは, 実装に苦労したものの, 解説を見る前に, AC版に到達できたので十分だと思う.
2. 二次元累積和の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);
    
    // 2. 二次元累積和.
    // -> (px, py) ～ (qx, qy) は, 以下で計算.
    // aCum[qx][qy] - aCum[qx][py - 1] - aCum[px - 1][qy] + aCum[px - 1][py - 1].
    repx(i, 1, H + 1){
        repx(j, 1, W + 1){
            aCum[i][j] = aCum[i - 1][j] + aCum[i][j - 1] - aCum[i - 1][j - 1] + a[i - 1][j - 1];
        }
    }
    
    // 3. 分割.
    // 3-1. 列方向の分割.
    vvi cDivisors;
    repx(j, 1, W){
        // 1列目 ～ j列目まで含む場合.
        vi v;
        v.pb(j);
        
        // 基準となる人口をベースに探索.
        // (1, 1) ～ (H, j) の 範囲.
        LL p = aCum[H][j] - aCum[H][0] - aCum[0][j] + aCum[0][0];
        int l = j, r = j + 1;
        while(1){
            // 分割の探索終了.
            if(r > W) break;
            
            // (1, l + 1) ～ (H, r) の 範囲.
            LL cur = aCum[H][r] - aCum[H][l] - aCum[0][r] + aCum[0][l];
            
            // 新たな境界線が見つかった.
            if(cur == p){
                v.pb(r);
                l = r;
                r = l + 1;
            }
            
            // 見つからなかった.
            if(cur != p) r++;
        }
        
        // 探索した分割方法を追加.
        if(v.back() == W) cDivisors.pb(v);
    }
    /*
    for(auto &cDiv : cDivisors){
        for(auto &p : cDiv) printf("%d ", p);
        puts("");
    }
    */
    
    // 3-2. 行方向の分割.
    vvi rDivisors;
    repx(i, 1, H){
        // 1行目 ～ i行目まで含む場合.
        vi v;
        v.pb(i);
        
        // 基準となる人口をベースに探索.
        // (1, 1) ～ (i, W) の 範囲.
        LL p = aCum[i][W] - aCum[i][0] - aCum[0][W] + aCum[0][0];
        int u = i, d = i + 1;
        while(1){
            // 分割の探索終了.
            if(d > H) break;
            
            // (u + 1, 1) ～ (d, W) の 範囲.
            LL cur = aCum[d][W] - aCum[d][0] - aCum[u][W] + aCum[u][0];
            
            // 新たな境界線が見つかった.
            if(cur == p){
                v.pb(d);
                u = d;
                d = u + 1;
            }
            
            // 見つからなかった.
            if(cur != p) d++;
        }
        
        // 探索した分割方法を追加.
        if(v.back() == H) rDivisors.pb(v);
    }
    /*
    for(auto &rDiv : rDivisors){
        for(auto &p : rDiv) printf("%d ", p);
        puts("");
    }
    */
    
    // 4. 分割 を 全探索.
    int ans = cDivisors.size() + rDivisors.size();
    for(auto &cDiv : cDivisors){
        for(auto &rDiv : rDivisors){
            // チェック.
            bool ok = true;
            
            // 範囲.
            LL p = 0;
            int cBef = 0, rBef = 0;
            for(int cCur : cDiv){
                for(int rCur : rDiv){
                    // (rBef, cBef) ～ (rCur, cCur) の 範囲.
                    LL n = aCum[rCur][cCur] - aCum[rCur][cBef] - aCum[rBef][cCur] + aCum[rBef][cBef];
                    
                    // 初回のみ更新.
                    if(p == 0) p = n;
                    
                    // 評価.
                    if(p && p != n){
                        ok = false;
                        break;
                    }
                    
                    // 前回分更新.
                    rBef = rCur;
                }
                
                // 前回分更新.
                cBef = cCur;
                
                // 初期化.
                rBef = 0;
                
                // 判定(false)が決まっている場合.
                if(!ok) break;
            }
            
            // 加算.
            if(ok) ans++;
        }
    }
    
    // 5. 出力.
    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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

LL a[55][55], aCum[55][55];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);

// 2. 二次元累積和.

// -> (px, py) ～ (qx, qy) は, 以下で計算.

// aCum[qx][qy] - aCum[qx][py - 1] - aCum[px - 1][qy] + aCum[px - 1][py - 1].

repx(i, 1, H + 1){

repx(j, 1, W + 1){

aCum[i][j] = aCum[i - 1][j] + aCum[i][j - 1] - aCum[i - 1][j - 1] + a[i - 1][j - 1];

}

// 3. 分割.

// 3-1. 列方向の分割.

vvi cDivisors;

repx(j, 1, W){

// 1列目～ j列目まで含む場合.

vi v;

v.pb(j);

// 基準となる人口をベースに探索.

// (1, 1) ～ (H, j) の範囲.

LL p = aCum[H][j] - aCum[H][0] - aCum[0][j] + aCum[0][0];

int l = j, r = j + 1;

while(1){

// 分割の探索終了.

if(r > W) break;

// (1, l + 1) ～ (H, r) の範囲.

LL cur = aCum[H][r] - aCum[H][l] - aCum[0][r] + aCum[0][l];

// 新たな境界線が見つかった.

if(cur == p){

v.pb(r);

l = r;

r = l + 1;

}

// 見つからなかった.

if(cur != p) r++;

}

// 探索した分割方法を追加.

if(v.back() == W) cDivisors.pb(v);

}

for(auto &cDiv : cDivisors){

for(auto &p : cDiv) printf("%d ", p);

puts("");

}

// 3-2. 行方向の分割.

vvi rDivisors;

repx(i, 1, H){

// 1行目～ i行目まで含む場合.

vi v;

v.pb(i);

// 基準となる人口をベースに探索.

// (1, 1) ～ (i, W) の範囲.

LL p = aCum[i][W] - aCum[i][0] - aCum[0][W] + aCum[0][0];

int u = i, d = i + 1;

while(1){

// 分割の探索終了.

if(d > H) break;

// (u + 1, 1) ～ (d, W) の範囲.

LL cur = aCum[d][W] - aCum[d][0] - aCum[u][W] + aCum[u][0];

// 新たな境界線が見つかった.

if(cur == p){

v.pb(d);

u = d;

d = u + 1;

}

// 見つからなかった.

if(cur != p) d++;

}

// 探索した分割方法を追加.

if(v.back() == H) rDivisors.pb(v);

}

for(auto &rDiv : rDivisors){

for(auto &p : rDiv) printf("%d ", p);

puts("");

}

// 4. 分割を全探索.

int ans = cDivisors.size() + rDivisors.size();

for(auto &cDiv : cDivisors){

for(auto &rDiv : rDivisors){

// チェック.

bool ok = true;

// 範囲.

LL p = 0;

int cBef = 0, rBef = 0;

for(int cCur : cDiv){

for(int rCur : rDiv){

// (rBef, cBef) ～ (rCur, cCur) の範囲.

LL n = aCum[rCur][cCur] - aCum[rCur][cBef] - aCum[rBef][cCur] + aCum[rBef][cBef];

// 初回のみ更新.

if(p == 0) p = n;

// 評価.

if(p && p != n){

ok = false;

break;

}

// 前回分更新.

rBef = rCur;

}

// 前回分更新.

cBef = cCur;

// 初期化.

rBef = 0;

// 判定(false)が決まっている場合.

if(!ok) break;

}

// 加算.

if(ok) ans++;

}

// 5. 出力.

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

return 0;

}

[入力例]
2 3
10 10 20
10 10 20

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

[入力例]
1 4
2 1 1 2

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

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

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

[入力例]
1 1
10000

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

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

[出力例]
5

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

[出力例]
11

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

[出力例]
7

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

[出力例]
19

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

[出力例]
99

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

[入力例]

2 3

10 10 20

[出力例]

※AtCoderテストケースより

[入力例]

1 4

2 1 1 2

[出力例]

※AtCoderテストケースより

[入力例]

3 3

2 9 4

7 5 3

6 1 8

[出力例]

※AtCoderテストケースより

[入力例]

1 1

10000

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 2 1 1

1 1 2 1

1 1 1 2

2 1 1 1

[出力例]

[入力例]

6 6

1 2 1 2 1 2

2 1 2 1 2 1

1 2 1 2 1 2

2 1 2 1 2 1

1 2 1 2 1 2

2 1 2 1 2 1

[出力例]

[入力例]

9 9

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

2 3 1 2 3 1 2 3 1

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

2 3 1 2 3 1 2 3 1

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

2 3 1 2 3 1 2 3 1

[出力例]

[入力例]

12 12

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

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

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

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

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

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

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

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

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

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

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

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

[出力例]

[入力例]

48 48

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

[出力例]

■参照サイト
JOI 2021/2022 二次予選過去問

2021年12月13日

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

C++の練習を兼ねて, AtCoder Regular Contest 054 の問題C (鯛焼き) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 行列の掃き出し法について復習出来たので, 非常に良かったと思う..
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト AtCoder Regular Contest 054 解説をご覧下さい.

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

// 解き直し.
// https://img.atcoder.jp/data/arc/054/editorial.pdf
// 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. 入力情報.
    int N;
    scanf("%d", &N);
    vs matrix;
    rep(i, N){
        char c[222];
        scanf("%s", c);
        string s(c);
        matrix.pb(s);
    }
    // puts("--- Matrix before update ---");
    // rep(i, N) printf("%s\n", matrix[i].c_str());
    
    // 2. 掃き出し法(mod2版).
    // https://ja.wikipedia.org/wiki/ガウスの消去法
    // 
    // ex.
    // [変更前行列]
    // 011001
    // 001001
    // 101011
    // 010110
    // 001100
    // 
    // [変更後行列]
    // 100001
    // 010000
    // 001001
    // 000101
    // 000011
    // 
    auto gauss = [&](vs &m, int N, int M) -> vs {
        // 2-1. 戻り値設定.
        vs ret = m;
        
        // 2-2. 各行を順次確認.
        rep(i, N){
            // 降順sort.
            sort(all(ret));
            reverse(all(ret));
            
            // 最初に, '1' となる位置.
            int at = M;
            rep(j, M){
                if(ret[i][j] == '1'){
                    at = j;
                    break;
                }
            }
            
            // 見つからなった場合.
            if(at == M) continue;
            
            // i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が 有れば, 掃き出す.
            rep(j, N){
                if(i != j && ret[j][at] == '1'){
                    // 操作対象を設定.
                    string o = ret[i]; // i行目.
                    string n = ret[j]; // j行目.
                    
                    // j行目の掃き出し.
                    rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));
                    
                    // j行目更新.
                    ret[j] = n;
                }
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    vs gMatrix = gauss(matrix, N, N);
    // puts("--- Matrix after update ---");
    // rep(i, N) printf("%s\n", gMatrix[i].c_str());
    
    // 3. 行列式.
    int ans = 1;
    rep(i, N) ans *= gMatrix[i][i] - '0';
    
    // 4. 出力.
    printf("%s\n", ans ? "Odd" : "Even");
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/data/arc/054/editorial.pdf

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

int N;

scanf("%d", &N);

vs matrix;

rep(i, N){

char c[222];

scanf("%s", c);

string s(c);

matrix.pb(s);

}

// puts("--- Matrix before update ---");

// rep(i, N) printf("%s\n", matrix[i].c_str());

// 2. 掃き出し法(mod2版).

// https://ja.wikipedia.org/wiki/ガウスの消去法

// ex.

// [変更前行列]

// 011001

// 001001

// 101011

// 010110

// 001100

// [変更後行列]

// 100001

// 010000

// 001001

// 000101

// 000011

auto gauss = [&](vs &m, int N, int M) -> vs {

// 2-1. 戻り値設定.

vs ret = m;

// 2-2. 各行を順次確認.

rep(i, N){

// 降順sort.

sort(all(ret));

reverse(all(ret));

// 最初に, '1' となる位置.

int at = M;

rep(j, M){

if(ret[i][j] == '1'){

at = j;

break;

}

// 見つからなった場合.

if(at == M) continue;

// i行目以外(j行目)と比較して, 前項で求めた位置(列)に, '1' が有れば, 掃き出す.

rep(j, N){

if(i != j && ret[j][at] == '1'){

// 操作対象を設定.

string o = ret[i]; // i行目.

string n = ret[j]; // j行目.

// j行目の掃き出し.

rep(k, M) n[k] = '0' + ((n[k] - '0') ^ (o[k] - '0'));

// j行目更新.

ret[j] = n;

}

// 2-3. 返却.

return ret;

};

vs gMatrix = gauss(matrix, N, N);

// puts("--- Matrix after update ---");

// rep(i, N) printf("%s\n", gMatrix[i].c_str());

// 3. 行列式.

int ans = 1;

rep(i, N) ans *= gMatrix[i][i] - '0';

// 4. 出力.

printf("%s\n", ans ? "Odd" : "Even");

return 0;

}

[入力例]
3
110
101
011

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

[入力例]
3
110
111
011

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

[入力例]
2
00
00

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

[入力例]
12
000000100000
011111111111
000000100000
000111111100
100100000100
100111111100
100100000100
100111111100
100100000100
100111111100
100000000000
111111111111

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

[入力例]
5
10001
01010
00100
10100
01001

[出力例]
Odd

[入力例]
7
0010100
1010001
0010110
0110100
0011101
1110100
0110110

[出力例]
Even

[入力例]
20
10101011001000001011
01101000100000101010
00101010100110101101
01100001100101001011
10111100110110111011
00111001101011001010
01100100100101001101
01101101001010010001
00011011011101011100
01100001111010010011
01001000111001101101
00100101010111100001
01010101101111000000
11011100011101001001
00101101000111100100
01100001110011100111
01000110110011011101
01101000110000100110
10100011100101001010
11001010110101010111

[出力例]
Odd

[入力例]
30
111000000000000000000000000000
010000000000000000000000000000
001001000000000100000000000000
000100000000000000000100000000
001010000000000100000000000000
000001000000000000000000000000
010000100000000000000000000000
000000010000000100000000000000
000100001000000000000100000000
001000000100000000000000000000
000001000010000000000000000000
000100000001000000000000000000
000000000000100000000000000000
001000000000010000000100000000
000000000000001000000000000000
000100000000000100000000000000
000001000000000010000000000000
000000000000000001000000000000
000100000000000000100000000000
000000000000000100010000000000
000000000000000000001000000000
000001000000000000000100000000
000000000000000000000010000000
000000000000000000000001000000
000000000000000000000000100000
000000000000000100000100010000
000000000000000000000000001000
000000000000000000000000000100
000000000000000100000100000010
000000000000000000000000000001

[出力例]
Odd

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

[入力例]

110

101

011

[出力例]

Even

※AtCoderのテストケースより

[入力例]

110

111

011

[出力例]

Odd

※AtCoderのテストケースより

[入力例]

[出力例]

Even

※AtCoderのテストケースより

[入力例]

000000100000

011111111111

000000100000

000111111100

100100000100

100111111100

100100000100

100111111100

100100000100

100111111100

100000000000

111111111111

[出力例]

Even

※AtCoderのテストケースより

[入力例]

10001

01010

00100

10100

01001

[出力例]

Odd

[入力例]

0010100

1010001

0010110

0110100

0011101

1110100

0110110

[出力例]

Even

[入力例]

10101011001000001011

01101000100000101010

00101010100110101101

01100001100101001011

10111100110110111011

00111001101011001010

01100100100101001101

01101101001010010001

00011011011101011100

01100001111010010011

01001000111001101101

00100101010111100001

01010101101111000000

11011100011101001001

00101101000111100100

01100001110011100111

01000110110011011101

01101000110000100110

10100011100101001010

11001010110101010111

[出力例]

Odd

[入力例]

111000000000000000000000000000

010000000000000000000000000000

001001000000000100000000000000

000100000000000000000100000000

001010000000000100000000000000

000001000000000000000000000000

010000100000000000000000000000

000000010000000100000000000000

000100001000000000000100000000

001000000100000000000000000000

000001000010000000000000000000

000100000001000000000000000000

000000000000100000000000000000

001000000000010000000100000000

000000000000001000000000000000

000100000000000100000000000000

000001000000000010000000000000

000000000000000001000000000000

000100000000000000100000000000

000000000000000100010000000000

000000000000000000001000000000

000001000000000000000100000000

000000000000000000000010000000

000000000000000000000001000000

000000000000000000000000100000

000000000000000100000100010000

000000000000000000000000001000

000000000000000000000000000100

000000000000000100000100000010

000000000000000000000000000001

[出力例]

Odd

■参照サイト
AtCoder Regular Contest 054

2021年12月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題D (Kth Excluded) を解いてみた.

■感想.
1. 問題Dは, 方針を決めることができたので, AC版に到達できたと思う.
2. 桁数オーバーフローに注意する必要があると感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vl = vector<LL>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    vl aCum, aMax;
    LL bef = 0, cur, aCount = 0;
    rep(i, N + 1){
        // 1-1. 今回分更新.
        if(i < N) scanf("%lld", &cur);
        else      cur = 2e18 + 1; // killer_00.txt, killer_01.txt の WA回避のため修正.
        
        // 1-2. 前回分 + 1 でない.
        if(cur != bef + 1){
            // 開始地点, 終了地点, 数列の長さ.
            LL s = bef + 1, g = cur - 1;
            aCount += (g - s + 1);
            
            // 数列の長さ.
            aCum.pb(aCount);
            
            // 終了地点.
            aMax.pb(g);
        }
        
        // 1-3. 前回分更新.
        bef = cur;
    }
    
    // 2. クエリ回答.
    rep(i, Q){
        // 2-1. 入力情報.
        LL k;
        scanf("%lld", &k);
        
        // 2-2. 対象区間は？
        int at = lower_bound(all(aCum), k) - aCum.begin();
        
        // 2-3. 出力.
        printf("%lld\n", aMax[at] - (aCum[at] - k));
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, Q;

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

vl aCum, aMax;

LL bef = 0, cur, aCount = 0;

rep(i, N + 1){

// 1-1. 今回分更新.

if(i < N) scanf("%lld", &cur);

else cur = 2e18 + 1; // killer_00.txt, killer_01.txt の WA回避のため修正.

// 1-2. 前回分 + 1 でない.

if(cur != bef + 1){

// 開始地点, 終了地点, 数列の長さ.

LL s = bef + 1, g = cur - 1;

aCount += (g - s + 1);

// 数列の長さ.

aCum.pb(aCount);

// 終了地点.

aMax.pb(g);

}

// 1-3. 前回分更新.

bef = cur;

}

// 2. クエリ回答.

rep(i, Q){

// 2-1. 入力情報.

LL k;

scanf("%lld", &k);

// 2-2. 対象区間は？

int at = lower_bound(all(aCum), k) - aCum.begin();

// 2-3. 出力.

printf("%lld\n", aMax[at] - (aCum[at] - k));

}

return 0;

}

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

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

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

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

[入力例]
25 10
6 12 13 14 15 18 19 20 21 30 31 33 34 36 38 39 50 52 53 61 62 63 70 75 76
6
12
18
23
31
38
45
52
62
72

[出力例]
7
17
27
37
47
57
67
77
87
97

[入力例]
100 23
9 10 11 17 18 19 28 30 33 35 36 37 45 46 49 52 53 54 62 64 65 66 73 75 76 82 87 89 91 95 100 103 104 106 109 112 115 116 121 123 127 132 134 135 137 138 143 145 146 147 148 150 151 152 155 159 164 167 171 175 180 181 184 189 194 198 203 204 209 210 211 215 218 221 226 230 231 232 253 254 255 297 298 299 310 311 330 331 332 353 354 355 380 381 497 498 499 502 503 504
21
54
43
46
900
3
18
83
72
17
592
93
56
651
93
50
495
25
9
34
49
421
921

[出力例]
27
79
61
68
1000
3
24
122
105
23
692
139
81
751
139
72
595
34
12
48
71
521
1021

[入力例]
250 50
746613 746614 746615 2683153 3233720 4204660 4652794 5883835 6422788 6953670 7636076 8563481 9178735 9489843 9899172 10335868 10653155 11792699 11925921 13046145 13808643 14855572 15487195 16627308 17744167 18234255 19053679 19337935 20030518 21024520 21745112 22629723 22653485 23431917 24663819 25323066 26145758 27013488 27353017 27383022 27974175 28107805 28650712 29447740 30007066 30431360 30431361 30431362 30431363 30431364 33706250 34343267 35348883 36527092 36704391 37624195 38595540 38843525 39469807 40677306 40867726 41413646 41450599 42443129 42673155 43814255 44319778 45367530 46051714 46214520 46409682 46649187 47848776 48041150 49107102 49549002 50471556 51196857 52387753 52743126 53268887 53290116 53836692 54096175 55128955 55430769 56299460 56845910 58074768 58505119 59035065 59636949 60072005 60398854 61581656 62082401 62706903 63721251 63979740 64183740 64886128 65887076 65973029 66567134 67234932 67647604 68263536 68830022 69145848 70197165 71431412 71904605 72507825 72847177 72847178 72847179 74293680 74464402 74561173 75279390 76465146 76914292 76918559 77562993 77872863 78589101 78886401 79034982 79279781 79865710 80239004 81047599 81940328 82004122 82614772 83791664 84743572 85403795 85516862 85942481 86512389 87493211 87609539 88046984 88476486 89576066 90624417 91719247 91802642 92034759 92705104 93924733 94470025 95300864 95503652 96171236 96557301 96611825 97630015 97783772 98356198 98773823 99506358 99942052 101118416 101695959 102003307 102740910 102740911 102740912 102740913 102740914 107236281 107793841 108421371 109063986 110174581 110430309 111209218 112411974 113512766 113826936 114503106 115484856 115653990 116273123 116291391 116817712 117420207 118217824 118417034 119483434 119831598 119872135 121017712 121170135 121415639 122565788 123553520 123853682 124201031 124509002 125578997 125927099 125927100 125927101 125927102 125927103 125927104 125927105 130086977 130649975 130649976 130649977 132762225 133842101 133925877 134897737 136126419 136135464 137035030 137935786 139155540 139237102 140013889 141037552 141990744 142347628 143451636 144240520 144799072 145606437 146038290 146147363 146202540 147406002 148238354 149030196 149349615 150543917 150913307 152123371 153166373 153975225 154195402 155052997 155052998 155052999 155053000 155053001
110251
688332
1853162
2241472
2302113
3394423
4113196
4897496
5629575
6030655
6203046
7355841
7941409
8860266
9915464
10475700
11295594
11611593
12341892
12382850
13535801
14596820
14945771
15212412
16050416
16556751
16952026
16982735
17404171
18360731
18404043
18566152
19717961
20534388
20942279
21892954
22344006
22615407
22884648
23243021
23868687
24210078
24529796
25214811
26154712
26222830
26723591
27744901
28976714
29989729

[出力例]
110251
688332
1853165
2241475
2302116
3394428
4113201
4897503
5629582
6030663
6203054
7355851
7941420
8860278
9915479
10475716
11295611
11611610
12341911
12382869
13535821
14596841
14945793
15212434
16050439
16556774
16952050
16982759
17404195
18360757
18404069
18566178
19717989
20534417
20942308
21892985
22344037
22615438
22884681
23243054
23868721
24210112
24529830
25214846
26154749
26222867
26723628
27744941
28976757
29989773

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

[入力例]

4 3

3 5 6 7

[出力例]

※AtCoderテストケースより

[入力例]

5 2

1 2 3 4 5

[出力例]

※AtCoderテストケースより

[入力例]

25 10

6 12 13 14 15 18 19 20 21 30 31 33 34 36 38 39 50 52 53 61 62 63 70 75 76

[出力例]

[入力例]

100 23

9 10 11 17 18 19 28 30 33 35 36 37 45 46 49 52 53 54 62 64 65 66 73 75 76 82 87 89 91 95 100 103 104 106 109 112 115 116 121 123 127 132 134 135 137 138 143 145 146 147 148 150 151 152 155 159 164 167 171 175 180 181 184 189 194 198 203 204 209 210 211 215 218 221 226 230 231 232 253 254 255 297 298 299 310 311 330 331 332 353 354 355 380 381 497 498 499 502 503 504

900

592

651

495

421

921

[出力例]

1000

122

105

692

139

751

139

595

521

1021

[入力例]

250 50

746613 746614 746615 2683153 3233720 4204660 4652794 5883835 6422788 6953670 7636076 8563481 9178735 9489843 9899172 10335868 10653155 11792699 11925921 13046145 13808643 14855572 15487195 16627308 17744167 18234255 19053679 19337935 20030518 21024520 21745112 22629723 22653485 23431917 24663819 25323066 26145758 27013488 27353017 27383022 27974175 28107805 28650712 29447740 30007066 30431360 30431361 30431362 30431363 30431364 33706250 34343267 35348883 36527092 36704391 37624195 38595540 38843525 39469807 40677306 40867726 41413646 41450599 42443129 42673155 43814255 44319778 45367530 46051714 46214520 46409682 46649187 47848776 48041150 49107102 49549002 50471556 51196857 52387753 52743126 53268887 53290116 53836692 54096175 55128955 55430769 56299460 56845910 58074768 58505119 59035065 59636949 60072005 60398854 61581656 62082401 62706903 63721251 63979740 64183740 64886128 65887076 65973029 66567134 67234932 67647604 68263536 68830022 69145848 70197165 71431412 71904605 72507825 72847177 72847178 72847179 74293680 74464402 74561173 75279390 76465146 76914292 76918559 77562993 77872863 78589101 78886401 79034982 79279781 79865710 80239004 81047599 81940328 82004122 82614772 83791664 84743572 85403795 85516862 85942481 86512389 87493211 87609539 88046984 88476486 89576066 90624417 91719247 91802642 92034759 92705104 93924733 94470025 95300864 95503652 96171236 96557301 96611825 97630015 97783772 98356198 98773823 99506358 99942052 101118416 101695959 102003307 102740910 102740911 102740912 102740913 102740914 107236281 107793841 108421371 109063986 110174581 110430309 111209218 112411974 113512766 113826936 114503106 115484856 115653990 116273123 116291391 116817712 117420207 118217824 118417034 119483434 119831598 119872135 121017712 121170135 121415639 122565788 123553520 123853682 124201031 124509002 125578997 125927099 125927100 125927101 125927102 125927103 125927104 125927105 130086977 130649975 130649976 130649977 132762225 133842101 133925877 134897737 136126419 136135464 137035030 137935786 139155540 139237102 140013889 141037552 141990744 142347628 143451636 144240520 144799072 145606437 146038290 146147363 146202540 147406002 148238354 149030196 149349615 150543917 150913307 152123371 153166373 153975225 154195402 155052997 155052998 155052999 155053000 155053001

110251

688332

1853162

2241472

2302113

3394423

4113196

4897496

5629575

6030655

6203046

7355841

7941409

8860266

9915464

10475700

11295594

11611593

12341892

12382850

13535801

14596820

14945771

15212412

16050416

16556751

16952026

16982735

17404171

18360731

18404043

18566152

19717961

20534388

20942279

21892954

22344006

22615407

22884648

23243021

23868687

24210078

24529796

25214811

26154712

26222830

26723591

27744901

28976714

29989729

[出力例]

110251

688332

1853165

2241475

2302116

3394428

4113201

4897503

5629582

6030663

6203054

7355851

7941420

8860278

9915479

10475716

11295611

11611610

12341911

12382869

13535821

14596841

14945793

15212434

16050439

16556774

16952050

16982759

17404195

18360757

18404069

18566178

19717989

20534417

20942308

21892985

22344037

22615438

22884681

23243054

23868721

24210112

24529830

25214846

26154749

26222867

26723628

27744941

28976757

29989773

■参照サイト
AtCoder Beginner Contest 205

2021年12月7日2021年12月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 199 の問題F (Graph Smoothing) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, 実装して, AC版に到達できたと思う.
2. 個人的には, 操作後の頂点に書かれている数の期待値が, 行列計算から, 算出できるというロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc199/editorial/1167
// 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 vvi = vector<vi>;
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
const LL MOD = 1e9 + 7;
LL a[111];

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

// 行列乗算を行う.
// @param a: 行列.
// @param b: 行列.
// @return:  計算結果(mod版).
vvl matrixMultiplication(vvl &a, vvl &b){
    int n = a.size();
    vvl ret(n, vl(n, 0LL));
    rep(i, n){
        rep(j, n){
            LL t = 0;
            rep(k, n){
                t += a[i][k] * b[k][j];
                t %= MOD;
            }
            ret[i][j] = t;
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL K;
    scanf("%d %d %lld", &N, &M, &K);
    rep(i, N) scanf("%lld", &a[i]);
    vvi G(N);
    rep(i, M){
        int x, y;
        scanf("%d %d", &x, &y);
        x--, y--;
        G[x].pb(y);
        G[y].pb(x);
    }
    
    // 2. 逆数.
    LL im = mPow((LL)M, MOD - 2);
    LL i2 = mPow(2LL, MOD - 2);
    
    // 3. 行列 m.
    vvl matrix(N, vl(N, 0LL));
    rep(i, N){
        // 3-1. 頂点 i の 次数.
        LL d = (LL)G[i].size();
        
        // 3-2. (i, i)成分.
        // -> 1 - (d / M) * (1 / 2) を 設定.
        matrix[i][i] = (1 + (MOD - d) * im % MOD * i2 % MOD) % MOD;
        
        // 3-3. 頂点 i の 隣接頂点.
        // -> (1 / M) * (1 / 2) を 設定.
        for(auto &p : G[i]) matrix[p][i] = im * i2 % MOD;
    }
    
    // 4. 行列のべき乗.
    auto f = [&](vvl &m, LL b) -> vvl {
        // 4-1. 単位行列.
        vvl t(N, vl(N, 0LL));
        rep(i, N) t[i][i] = 1;
        
        // 4-2. べき乗計算.
        vvl a = m;
        while(b){
            if(b & 1) t = matrixMultiplication(t, a);
            a = matrixMultiplication(a, a);
            b >>= 1;
        }
        
        // 4-3. 返却.
        return t;
    };
    
    // 5. 行列 m の K 乗.
    vvl kMatrix = f(matrix, K);
    
    // 6. 出力.
    rep(i, N){
        LL ans = 0;
        rep(j, N){
            ans += a[j] * kMatrix[j][i];
            ans %= MOD;
        }
        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

// 解き直し.

// https://atcoder.jp/contests/abc199/editorial/1167

// 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 vvi = vector<vi>;

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

const LL MOD = 1e9 + 7;

LL a[111];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

// 行列乗算を行う.

// @param a: 行列.

// @param b: 行列.

// @return: 計算結果(mod版).

vvl matrixMultiplication(vvl &a, vvl &b){

int n = a.size();

vvl ret(n, vl(n, 0LL));

rep(i, n){

rep(j, n){

LL t = 0;

rep(k, n){

t += a[i][k] * b[k][j];

t %= MOD;

}

ret[i][j] = t;

}

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

LL K;

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

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

vvi G(N);

rep(i, M){

int x, y;

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

x--, y--;

G[x].pb(y);

G[y].pb(x);

}

// 2. 逆数.

LL im = mPow((LL)M, MOD - 2);

LL i2 = mPow(2LL, MOD - 2);

// 3. 行列 m.

vvl matrix(N, vl(N, 0LL));

rep(i, N){

// 3-1. 頂点 i の次数.

LL d = (LL)G[i].size();

// 3-2. (i, i)成分.

// -> 1 - (d / M) * (1 / 2) を設定.

matrix[i][i] = (1 + (MOD - d) * im % MOD * i2 % MOD) % MOD;

// 3-3. 頂点 i の隣接頂点.

// -> (1 / M) * (1 / 2) を設定.

for(auto &p : G[i]) matrix[p][i] = im * i2 % MOD;

}

// 4. 行列のべき乗.

auto f = [&](vvl &m, LL b) -> vvl {

// 4-1. 単位行列.

vvl t(N, vl(N, 0LL));

rep(i, N) t[i][i] = 1;

// 4-2. べき乗計算.

vvl a = m;

while(b){

if(b & 1) t = matrixMultiplication(t, a);

a = matrixMultiplication(a, a);

b >>= 1;

}

// 4-3. 返却.

return t;

};

// 5. 行列 m の K 乗.

vvl kMatrix = f(matrix, K);

// 6. 出力.

rep(i, N){

LL ans = 0;

rep(j, N){

ans += a[j] * kMatrix[j][i];

ans %= MOD;

}

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

}

return 0;

}

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

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

[入力例]
3 2 2
12 48 36
1 2
1 3

[出力例]
750000036
36
250000031
※AtCoderテストケースより

[入力例]
4 5 1000
578 173 489 910
1 2
2 3
3 4
4 1
1 3

[出力例]
201113830
45921509
67803140
685163678
※AtCoderテストケースより

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

[出力例]
8
9
11

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

[出力例]
60105104
306664487
204426177
528008430
119334530
696618822
438064470
15348755
686133158
945296134

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

[出力例]
256833840
773912707
782215323
520721643
812754100
686558120
158488543
731923937
956199888
385308127
166469694
793620776
525611593
975959465
25353523
820154314
839516161
264137745
498907154
25353523

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

[入力例]

3 2 1

3 1 5

1 2

1 3

[出力例]

500000005

500000008

※AtCoderテストケースより

[入力例]

3 2 2

12 48 36

1 2

1 3

[出力例]

750000036

250000031

※AtCoderテストケースより

[入力例]

4 5 1000

578 173 489 910

1 2

2 3

3 4

4 1

1 3

[出力例]

201113830

45921509

67803140

685163678

※AtCoderテストケースより

[入力例]

3 3 2

4 8 16

1 2

2 3

3 1

[出力例]

[入力例]

10 12 15

3 1 4 1 5 9 2 6 5 3

1 2

2 3

3 1

4 5

5 6

6 4

7 8

8 9

9 7

2 10

4 10

9 10

[出力例]

60105104

306664487

204426177

528008430

119334530

696618822

438064470

15348755

686133158

945296134

[入力例]

20 25 123456789

1 2 5 9 9 2 1 0 4 9 8 9 4 8 7 3 1 6 4 7

1 2

2 3

3 4

4 5

5 1

6 1

7 2

8 3

9 4

10 5

6 11

11 16

16 6

7 12

12 17

17 7

8 13

13 18

18 8

9 14

14 19

19 9

10 15

15 20

20 10

[出力例]

256833840

773912707

782215323

520721643

812754100

686558120

158488543

731923937

956199888

385308127

166469694

793620776

525611593

975959465

25353523

820154314

839516161

264137745

498907154

25353523

■参照サイト
AtCoder Beginner Contest 199（Sponsored by Panasonic）

2021年12月6日2021年12月6日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説内容を実装する形で, AC版に到達できたと思う.
2. 苦手なdpの訓練(本問では, bitDP)を積めたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc199/editorial/1164
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int x[111], y[111], z[111];
LL dp[1 << 18];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, M){
        scanf("%d %d %d", &x[i], &y[i], &z[i]);
        
        // Y は, [1, N - 1] を [0, N - 2] に 読み替え.
        y[i]--;
    }
    
    // 2. dp更新.
    dp[0] = 1;
    rep(i, 1 << N){
        // 2-1. 累積和.
        int sCum[N + 1];
        rep(j, N + 1) sCum[j] = 0;
        rep(j, N) sCum[j + 1] = sCum[j] + ((i & (1 << j)) > 0);
        
        // 2-2. 要素数.
        int one = __builtin_popcount(i);
        
        // 2-3. i に 含まれない一要素を, 追加して, 遷移出来るか？
        // ex.
        // N = 6
        // i = 011001 (25 = {0, 3, 4}) から, (i または j) = 011011 (27 = {0, 1, 3, 4}) に 遷移出来るか？
        rep(j, N){
            // j が i の 要素 に 含まれる場合は, Skip.
            if(i & (1 << j)) continue;
            
            // 集合{S または x}(※ここでは, i と j の 和集合を考えた場合 の bit) が 条件を満たすかチェック(M通り).
            bool ok = true;
            rep(k, M){
                // 集合{S または x} の サイズ が, one + 1 で, 
                // かつ, 
                // 集合{S または x} に含まれる y[k]以下が, z[k]以下になっているかをチェック.
                if(one + 1 == x[k] && (sCum[y[k] + 1] + (j <= y[k]) > z[k])){
                    ok = false;
                    break;
                }
            }
            
            // 条件を満たす場合は, 加算.
            if(ok) dp[i | (1 << j)] += dp[i];
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[(1 << N) - 1]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc199/editorial/1164

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int x[111], y[111], z[111];

LL dp[1 << 18];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, M){

scanf("%d %d %d", &x[i], &y[i], &z[i]);

// Y は, [1, N - 1] を [0, N - 2] に読み替え.

y[i]--;

}

// 2. dp更新.

dp[0] = 1;

rep(i, 1 << N){

// 2-1. 累積和.

int sCum[N + 1];

rep(j, N + 1) sCum[j] = 0;

rep(j, N) sCum[j + 1] = sCum[j] + ((i & (1 << j)) > 0);

// 2-2. 要素数.

int one = __builtin_popcount(i);

// 2-3. i に含まれない一要素を, 追加して, 遷移出来るか？

// ex.

// N = 6

// i = 011001 (25 = {0, 3, 4}) から, (i または j) = 011011 (27 = {0, 1, 3, 4}) に遷移出来るか？

rep(j, N){

// j が i の要素に含まれる場合は, Skip.

if(i & (1 << j)) continue;

// 集合{S または x}(※ここでは, i と j の和集合を考えた場合の bit) が条件を満たすかチェック(M通り).

bool ok = true;

rep(k, M){

// 集合{S または x} のサイズが, one + 1 で,

// かつ,

// 集合{S または x} に含まれる y[k]以下が, z[k]以下になっているかをチェック.

if(one + 1 == x[k] && (sCum[y[k] + 1] + (j <= y[k]) > z[k])){

ok = false;

break;

}

// 条件を満たす場合は, 加算.

if(ok) dp[i | (1 << j)] += dp[i];

}

// 3. 出力.

printf("%lld\n", dp[(1 << N) - 1]);

return 0;

}

[入力例]
3 1
2 2 1

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

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

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

[入力例]
18 0

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

[入力例]
2 0

[出力例]
2

[入力例]
2 1
1 1 0

[出力例]
1

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

[出力例]
6

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

[出力例]
2088

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

[出力例]
107702784000

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

[出力例]
2519962970112000

[入力例]

3 1

2 2 1

[出力例]

※AtCoderテストケースより

[入力例]

5 2

3 3 2

4 4 3

[出力例]

※AtCoderテストケースより

[入力例]

18 0

[出力例]

6402373705728000

※AtCoderテストケースより

[入力例]

2 0

[出力例]

[入力例]

2 1

1 1 0

[出力例]

[入力例]

3 2

1 1 1

2 2 2

[出力例]

[入力例]

7 5

1 5 3

2 6 4

3 5 2

4 6 5

5 2 1

[出力例]

2088

[入力例]

15 10

3 5 9

7 6 2

3 12 6

4 8 1

5 9 6

6 8 9

1 12 3

4 5 0

2 14 9

14 6 6

[出力例]

107702784000

[入力例]

18 7

5 7 4

8 9 5

7 5 3

3 12 2

6 8 5

3 9 2

9 15 7

[出力例]

2519962970112000

■参照サイト
AtCoder Beginner Contest 199（Sponsored by Panasonic）

2021年12月5日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説内容を実装する形で, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 数列の性質を, 動的計画法に持ち込むことで, 操作後の数列の種類数がカウントできるロジックが, 面白いと感じた.
3. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 説き直し.
// https://atcoder.jp/contests/abc230/editorial/91
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 998244353;
LL a[202020], aCum[202020], dp[202020], dpCum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 累積和.
    // -> aCum[i + 1] = a[i] + a[i - 1] + ... + a[0]
    rep(i, N) aCum[i + 1] = aCum[i] + a[i];
    
    // 3. dp更新.
    map<LL, int> m; // {累積和, 最大index}
    m[0] = 0;
    dp[0] = 1;
    dpCum[0] = 0;
    repx(i, 1, N + 1){
        // 3-1. a[j] + a[j + 1] + ... + a[i] = 0 となる j があるか？
        int j = 0;
        if(m.count(aCum[i])) j = m[aCum[i]]; // 前回以前に, aCum[i + 1] が 出現している場合.
        
        // 3-2. 最大index を 更新.
        m[aCum[i]] = i;
        
        // 3-3. dpCum更新(dpCum[i] = dp[i - 1] + dp[i - 1] + ... + dp[0]).
        dpCum[i] = dpCum[i - 1] + dp[i - 1];
        dpCum[i] %= MOD;
        
        // 3-4. dp更新(dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[j] = dpCum[i] - dpCum[j] と 見る).
        dp[i] = dpCum[i] + MOD - dpCum[j];
        dp[i] %= MOD;
    }
    
    // 4. 集計(aCum[N] - aCum[k] = 0 となる dp[k]).
    LL ans = 0;
    repx(k, 1, N + 1) if(aCum[N] == aCum[k]) ans += dp[k], ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 説き直し.

// https://atcoder.jp/contests/abc230/editorial/91

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

LL a[202020], aCum[202020], dp[202020], dpCum[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 累積和.

// -> aCum[i + 1] = a[i] + a[i - 1] + ... + a[0]

rep(i, N) aCum[i + 1] = aCum[i] + a[i];

// 3. dp更新.

map<LL, int> m; // {累積和, 最大index}

m[0] = 0;

dp[0] = 1;

dpCum[0] = 0;

repx(i, 1, N + 1){

// 3-1. a[j] + a[j + 1] + ... + a[i] = 0 となる j があるか？

int j = 0;

if(m.count(aCum[i])) j = m[aCum[i]]; // 前回以前に, aCum[i + 1] が出現している場合.

// 3-2. 最大index を更新.

m[aCum[i]] = i;

// 3-3. dpCum更新(dpCum[i] = dp[i - 1] + dp[i - 1] + ... + dp[0]).

dpCum[i] = dpCum[i - 1] + dp[i - 1];

dpCum[i] %= MOD;

// 3-4. dp更新(dp[i] = dp[i - 1] + dp[i - 2] + ... + dp[j] = dpCum[i] - dpCum[j] と見る).

dp[i] = dpCum[i] + MOD - dpCum[j];

dp[i] %= MOD;

}

// 4. 集計(aCum[N] - aCum[k] = 0 となる dp[k]).

LL ans = 0;

repx(k, 1, N + 1) if(aCum[N] == aCum[k]) ans += dp[k], ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
3
1 -1 1

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

[入力例]
10
377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

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

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

[出力例]
16

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

[出力例]
928

[入力例]
15
-1 12 -3 9 -12 -3 0 -7 7 -1 5 17 -10 0 11

[出力例]
7680

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

[出力例]
19569121

[入力例]
50
3358 2443 9460 4339 -610 -3793 -15197 -10441 -5374 5738 10077 -9794 4846 8599 -3651 -367 2251 -5020 3168 3918 -625 3835 -2395 -9713 8180 8077 -1650 60 -4954 -8226 5051 9719 6910 -14987 563 5057 -7262 7238 393 -7147 -484 721 -2818 5914 -2261 -835 1032 1582 -1779 -1556

[出力例]
804371196

[入力例]

1 -1 1

[出力例]

※AtCoderテストケースより

[入力例]

377914575 -275478149 0 -444175904 719654053 -254224494 -123690081 377914575 -254224494 -21253655

[出力例]

321

※AtCoderテストケースより

[入力例]

3 -2 -1 5 -5

[出力例]

[入力例]

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

[出力例]

928

[入力例]

-1 12 -3 9 -12 -3 0 -7 7 -1 5 17 -10 0 11

[出力例]

7680

[入力例]

3 1 -4 1 -5 9 -2 -6 5 3 -5 8 -9 7 -9 3 2 -3 8 -4 6 -2 -6 4 3 -3 -8 3 2 7 -9 5 0

[出力例]

19569121

[入力例]

3358 2443 9460 4339 -610 -3793 -15197 -10441 -5374 5738 10077 -9794 4846 8599 -3651 -367 2251 -5020 3168 3918 -625 3835 -2395 -9713 8180 8077 -1650 60 -4954 -8226 5051 9719 6910 -14987 563 5057 -7262 7238 393 -7147 -484 721 -2818 5914 -2261 -835 1032 1582 -1779 -1556

[出力例]

804371196

■参照サイト
AtCoder Beginner Contest 230

2021年12月5日2021年12月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 230 の問題E (Fraction Floor Sum) を解いてみた.

■感想.
1. 問題Eは, 方針を決めることができたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. カウント.
    LL ans = 0, u = sqrt(N);
    repx(i, 1, (int)u + 1){
        // (N / i) を 集計.
        if((LL)i != (N / i)) ans += N / i;
        
        // i を 集計.
        ans += ((N / i) - N / (i + 1)) * i;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. カウント.

LL ans = 0, u = sqrt(N);

repx(i, 1, (int)u + 1){

// (N / i) を集計.

if((LL)i != (N / i)) ans += N / i;

// i を集計.

ans += ((N / i) - N / (i + 1)) * i;

}

// 3. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
10000000000

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

[入力例]
1

[出力例]
1

[入力例]
5

[出力例]
10

[入力例]
6

[出力例]
14

[入力例]
16

[出力例]
50

[入力例]
2021

[出力例]
15698

[入力例]
20211203

[出力例]
343108943

[入力例]
202112032240

[出力例]
5292610637212

[入力例]
1000000000000

[出力例]
27785452449086

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

10000000000

[出力例]

231802823220

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

2021

[出力例]

15698

[入力例]

20211203

[出力例]

343108943

[入力例]

202112032240

[出力例]

5292610637212

[入力例]

1000000000000

[出力例]

27785452449086

■参照サイト
AtCoder Beginner Contest 230

2021年12月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 230 の問題C (X drawing) ～問題D (Destroyer Takahashi) を解いてみた.

■感想.
1. 問題C, Dは, 方針を決めることができたので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N, A, B, P, Q, R, S;
    scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &A, &B, &P, &Q, &R, &S);
    
    // 2. 黒マス範囲.
    LL kMin1 = max(1 - A, 1 - B);
    LL kMax1 = min(N - A, N - B);
    LL kMin2 = max(1 - A, B - N);
    LL kMax2 = min(N - A, B - 1);
    
    // 3. 出力.
    LL a, b;
    rep(i, (int)(Q - P + 1)){
        rep(j, (int)(S - R + 1)){
            // 3-1. (A, B) からの移動距離.
            bool ok = false;
            a = (P + i) - A;
            b = (R + j) - B;
            
            // 3-2. 黒マスに該当するか？
            // パターン①.
            if(a == b && kMin1 <= a && a <= kMax1) ok = true;
            
            // パターン②.
            if(a + b == 0 && kMin2 <= a && a <= kMax2) ok = true;
            
            // 3-3. 出力.
            printf("%s", ok ? "#" : ".");
        }
        puts("");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL N, A, B, P, Q, R, S;

scanf("%lld %lld %lld %lld %lld %lld %lld", &N, &A, &B, &P, &Q, &R, &S);

// 2. 黒マス範囲.

LL kMin1 = max(1 - A, 1 - B);

LL kMax1 = min(N - A, N - B);

LL kMin2 = max(1 - A, B - N);

LL kMax2 = min(N - A, B - 1);

// 3. 出力.

LL a, b;

rep(i, (int)(Q - P + 1)){

rep(j, (int)(S - R + 1)){

// 3-1. (A, B) からの移動距離.

bool ok = false;

a = (P + i) - A;

b = (R + j) - B;

// 3-2. 黒マスに該当するか？

// パターン①.

if(a == b && kMin1 <= a && a <= kMax1) ok = true;

// パターン②.

if(a + b == 0 && kMin2 <= a && a <= kMax2) ok = true;

// 3-3. 出力.

printf("%s", ok ? "#" : ".");

}

puts("");

}

return 0;

}

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

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

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

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

[入力例]
1000000000000000000 999999999999999999 999999999999999999
999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

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

[入力例]
11 6 6
1 11 1 11

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

[入力例]
12345 2020 2021
2017 2023 2018 2024 

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

[入力例]

5 3 2

1 5 1 5

[出力例]

...#.

#.#..

.#...

#.#..

...#.

※AtCoderテストケースより

[入力例]

5 3 3

4 5 2 5

[出力例]

#.#.

...#

※AtCoderテストケースより

[入力例]

1000000000000000000 999999999999999999 999999999999999999

999999999999999998 1000000000000000000 999999999999999998 1000000000000000000

[出力例]

#.#

.#.

#.#

※AtCoderテストケースより

[入力例]

11 6 6

1 11 1 11

[出力例]

#.........#

.#.......#.

..#.....#..

...#...#...

....#.#....

.....#.....

....#.#....

...#...#...

..#.....#..

.#.......#.

#.........#

[入力例]

12345 2020 2021

2017 2023 2018 2024

[出力例]

#.....#

.#...#.

..#.#..

...#...

..#.#..

.#...#.

#.....#

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, 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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, D;
    scanf("%d %d", &N, &D);
    vp v;
    rep(i, N){
        int l, r;
        scanf("%d %d", &l, &r);
        v.pb({r, l});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. カウント.
    int ans = 0, minR = 1010101010;
    rep(i, N){
        // [l, r] が 衝撃波 の 範囲 [minR, minR + D - 1] に 含まれるか？
        if(minR > v[i].a || minR + D - 1 < v[i].b){
            minR = v[i].a;
            ans++;
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define b second

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, D;

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

vp v;

rep(i, N){

int l, r;

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

v.pb({r, l});

}

// 2. sort.

sort(all(v));

// 3. カウント.

int ans = 0, minR = 1010101010;

rep(i, N){

// [l, r] が衝撃波の範囲 [minR, minR + D - 1] に含まれるか？

if(minR > v[i].a || minR + D - 1 < v[i].b){

minR = v[i].a;

ans++;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

[入力例]
5 2
1 100
1 1000000000
101 1000
9982 44353
1000000000 1000000000

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

[入力例]
20 5
12 17
77 84
40 51
119 125
73 85
113 119
70 79
10 13
70 82
27 31
20 27
116 119
2 4
72 79
17 28
7 17
109 113
86 88
108 109
39 43

[出力例]
8

[入力例]
50 10
1810 1903
936 945
12230 12323
4750 4752
8500 8529
3950 4032
10872 10884
3282 3353
6205 6215
116 196
2626 2703
10009 10011
10514 10549
7577 7593
9689 9761
8984 9096
1390 1466
7835 7852
4756 4761
7967 8045
3417 3525
4265 4352
1356 1476
8978 9080
4481 4542
8305 8424
2887 2949
2499 2620
7262 7380
5083 5172
793 884
1855 1902
7775 7864
248 345
7239 7268
815 863
1407 1412
10147 10260
4915 4996
11488 11510
2003 2014
2955 3020
5099 5109
5846 5939
6037 6154
1253 1266
8425 8465
5863 5918
9449 9505
9882 9957

[出力例]
37

100

101

102

103

104

105

106

107

108

109

110

111

112

113

[入力例]

3 3

1 2

4 7

5 9

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 2

4 7

4 9

[出力例]

※AtCoderテストケースより

[入力例]

5 2

1 100

1 1000000000

101 1000

9982 44353

1000000000 1000000000

[出力例]

※AtCoderテストケースより

[入力例]

20 5

12 17

77 84

40 51

119 125

73 85

113 119

70 79

10 13

70 82

27 31

20 27

116 119

2 4

72 79

17 28

7 17

109 113

86 88

108 109

39 43

[出力例]

[入力例]

50 10

1810 1903

936 945

12230 12323

4750 4752

8500 8529

3950 4032

10872 10884

3282 3353

6205 6215

116 196

2626 2703

10009 10011

10514 10549

7577 7593

9689 9761

8984 9096

1390 1466

7835 7852

4756 4761

7967 8045

3417 3525

4265 4352

1356 1476

8978 9080

4481 4542

8305 8424

2887 2949

2499 2620

7262 7380

5083 5172

793 884

1855 1902

7775 7864

248 345

7239 7268

815 863

1407 1412

10147 10260

4915 4996

11488 11510

2003 2014

2955 3020

5099 5109

5846 5939

6037 6154

1253 1266

8425 8465

5863 5918

9449 9505

9882 9957

[出力例]

■参照サイト
AtCoder Beginner Contest 230

2021年12月1日2021年12月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 130 の問題C (Digit Sum Minimization) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装したところ, AC版に到達できたと思う.
2. 個人的には, 実装に苦労したものの, 非常に面白い問題に感じた.
3. 学習のために, 解説プログラムを確認後, 実際に桁和を評価するパターンを組み込んだ実装もしてみた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc130/editorial/2976
// 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--)
#define pb push_back
int aCount[10], bCount[10];

int main(){
    
    // 1. 入力情報.
    char s1[101010], s2[101010];
    scanf("%s %s", s1, s2);
    string sa(s1), sb(s2);
    
    // 2. a, b を 調整.
    bool aMinB = true;
    int al = sa.size(), bl = sb.size();
    if(al > bl){
        swap(sa, sb);
        aMinB = false;
    }
    
    // 3. 各桁の数字の出現回数.
    int lMax = max(al, bl), lMin = min(al, bl);
    rep(i, lMax){
        if(i < lMin) aCount[sa[i] - '0']++;
        bCount[sb[i] - '0']++;
    }
    aCount[0] += lMax - lMin;
    assert(bCount[0] == 0);
    // rep(i, 10) printf("%d ", aCount[i]);
    // puts("\n-----");
    // rep(i, 10) printf("%d ", bCount[i]);
    // puts("\n-----");
    
    // 4. 各桁の並び替え.
    int kMax = 0;
    string ans[2];
    ans[0] = sa;
    ans[1] = sb;
    repx(a0, 1, 10){
        // 4-1. 変数を準備.
        int k = 0;
        string t[2];
        t[0] = "";
        t[1] = "";
        int ca[10], cb[10];
        rep(i, 10){
            ca[i] = aCount[i];
            cb[i] = bCount[i];
        }
        
        // 4-2. a[0] + b[0] >= 10 となるものを探す.
        if(ca[a0]){
            repx(b0, 10 - a0, 10){
                // 見つかった場合は, 保存.
                if(cb[b0]){
                    t[0].pb(a0 + '0');
                    t[1].pb(b0 + '0');
                    ca[a0]--;
                    cb[b0]--;
                    k++;
                    break;
                }
            }
        }
        
        // 4-3. 見つからなかった場合.
        // printf("a0=%d t0=%s t1=%s\n", a0, t[0].c_str(), t[1].c_str());
        if(!k) continue;
        
        // 4-4. 見つかった場合.
        repx(a, 1, 10){
            repx(b, 9 - a, 10){
                if(ca[a]){
                    // 各数字の出現回数を更新.
                    int l = min(ca[a], cb[b]);
                    ca[a] -= l;
                    cb[b] -= l;
                    k += l;
                    
                    // 文字列作成.
                    string aStr(l, a + '0');
                    string bStr(l, b + '0');
                    
                    // 文字列追加.
                    t[0] = aStr + t[0];
                    t[1] = bStr + t[1];
                }
            }
        }
        
        // 4-5. 桁数以上(ゼロを考慮)の場合.
        if(ca[0]){
            if(cb[9]){
                // 該当する数字の出現回数を更新.
                int l = min(ca[0], cb[9]);
                ca[0] -= l;
                cb[9] -= l;
                k += l;
                
                // 文字列作成.
                string bStr(l, 9 + '0');
                
                // 文字列追加.
                t[1] = bStr + t[1];
            }
        }
        
        // 4-6. 残り.
        repx(a, 1, 10){
            if(ca[a]){
                string aStr(ca[a], a + '0');
                t[0] = aStr + t[0];
            }
        }
        repx(b, 1, 10){
            if(cb[b]){
                string bStr(cb[b], b + '0');
                t[1] = bStr + t[1];
            }
        }
        
        // 4-7. 最大値更新.
        if(k > kMax){
            kMax = k;
            ans[0] = t[0];
            ans[1] = t[1];
        }
    }
    
    // 5. 入れ替え.
    if(!aMinB) swap(ans[0], ans[1]);
    
    // 6. 出力.
    printf("%s\n%s\n", ans[0].c_str(), ans[1].c_str());
    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

// 解き直し.

// https://atcoder.jp/contests/arc130/editorial/2976

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

#define pb push_back

int aCount[10], bCount[10];

int main(){

// 1. 入力情報.

char s1[101010], s2[101010];

scanf("%s %s", s1, s2);

string sa(s1), sb(s2);

// 2. a, b を調整.

bool aMinB = true;

int al = sa.size(), bl = sb.size();

if(al > bl){

swap(sa, sb);

aMinB = false;

}

// 3. 各桁の数字の出現回数.

int lMax = max(al, bl), lMin = min(al, bl);

rep(i, lMax){

if(i < lMin) aCount[sa[i] - '0']++;

bCount[sb[i] - '0']++;

}

aCount[0] += lMax - lMin;

assert(bCount[0] == 0);

// rep(i, 10) printf("%d ", aCount[i]);

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

// rep(i, 10) printf("%d ", bCount[i]);

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

// 4. 各桁の並び替え.

int kMax = 0;

string ans[2];

ans[0] = sa;

ans[1] = sb;

repx(a0, 1, 10){

// 4-1. 変数を準備.

int k = 0;

string t[2];

t[0] = "";

t[1] = "";

int ca[10], cb[10];

rep(i, 10){

ca[i] = aCount[i];

cb[i] = bCount[i];

}

// 4-2. a[0] + b[0] >= 10 となるものを探す.

if(ca[a0]){

repx(b0, 10 - a0, 10){

// 見つかった場合は, 保存.

if(cb[b0]){

t[0].pb(a0 + '0');

t[1].pb(b0 + '0');

ca[a0]--;

cb[b0]--;

k++;

break;

}

// 4-3. 見つからなかった場合.

// printf("a0=%d t0=%s t1=%s\n", a0, t[0].c_str(), t[1].c_str());

if(!k) continue;

// 4-4. 見つかった場合.

repx(a, 1, 10){

repx(b, 9 - a, 10){

if(ca[a]){

// 各数字の出現回数を更新.

int l = min(ca[a], cb[b]);

ca[a] -= l;

cb[b] -= l;

k += l;

// 文字列作成.

string aStr(l, a + '0');

string bStr(l, b + '0');

// 文字列追加.

t[0] = aStr + t[0];

t[1] = bStr + t[1];

}

// 4-5. 桁数以上(ゼロを考慮)の場合.

if(ca[0]){

if(cb[9]){

// 該当する数字の出現回数を更新.

int l = min(ca[0], cb[9]);

ca[0] -= l;

cb[9] -= l;

k += l;

// 文字列作成.

string bStr(l, 9 + '0');

// 文字列追加.

t[1] = bStr + t[1];

}

// 4-6. 残り.

repx(a, 1, 10){

if(ca[a]){

string aStr(ca[a], a + '0');

t[0] = aStr + t[0];

}

repx(b, 1, 10){

if(cb[b]){

string bStr(cb[b], b + '0');

t[1] = bStr + t[1];

}

// 4-7. 最大値更新.

if(k > kMax){

kMax = k;

ans[0] = t[0];

ans[1] = t[1];

}

// 5. 入れ替え.

if(!aMinB) swap(ans[0], ans[1]);

// 6. 出力.

printf("%s\n%s\n", ans[0].c_str(), ans[1].c_str());

return 0;

}

[入力例]
253
286

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

[入力例]
345
556

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

[入力例]
123
987987

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

[入力例]
11111111111111111111
111111111111111111111111111111

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

[入力例]
33231965444
773455566

[出力例]
19233444563
766555437

[入力例]
13785194584316927589
361659282125285

[出力例]
55299111335446887789
988665553222211

[入力例]
64298525857766878472
985733285545756164339168335839

[出力例]
98888777766655544222
888666599955311333233354455778

[入力例]
31415926535897932384626433832795
28841971693993751

[出力例]
66555443333999933221122345678887
99998877654321113

[入力例]
22175444971457187528782565139685443474229549313625352752311829887254616176822621978974878462694157495375954615447899327541617489148111884227358232886286227889645557945726241681611891958772213477437515
551641763747245118646413653235781313233898374817931453544492522426656592511875353264755952631934534191775794555619912773366291621596845688541515236561

[出力例]
88877777777777522222222222222111199999999999999999111111111111111111111222222222222255555533333333333354444444444444444444444444455555555555555555776666666666666666677777777777778888888888888888888888
999999999999888888888777777777777766666666666666666655555555555555555555555555544444444444444444333333333333333333322222222222221111111111111111111112

[入力例]
596566292477225167124797689822712989922218287694224795251699134214547334585329464159544189788918151193737328351346297845156335816156298861219182734638377894728227668331283653624246257276377836811971862752912774484634753467867376249442665576297677263994726859927416957145424679534826171713328616357727
76564588753992977891167538419732544499251298849996481579385543316893495799434283729514832677617324997637168395535682693663371365536697733465595971514825885974222929187611533998246944634996939819275442

[出力例]
888888888888777777777777777777777777777666666666666555554444444433333399999999999999999999999999999932222222222222222222222111111111111111111111111111111122222222222222222222233333333333333333333344444444444444444444444455555555555555555555556666666666666666666666666777777777777777788888888888888888
99999999999999999999999999999999999888888888888888888877777777777777777777766666666666666666666655555555555555555555555544444444444444444444443333333333333333333333333222222222222222211111111111111112

[入力例]
175558784176642428478886852882855583716348823311266168351117565526517246563464474343713186378358445825842875688328468224747862347184328843234558524873384588623418676322736867374751213285481637258731113376141451225431247636868272855271286637444364837212345678899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911648254724172726886576212874999999999999999999999998761513785328536141681424618172454423262172768855338
798712575381827545576737899297923911446969182444192158293357571521113147117194441699283651197668998739383164988824344734982795349365355256562868136216491554917941957124319167153177952521376528156791156976544147951266159411376581323677263132625248786714518936274126888662385854877456875923693193179271447287133625556351996281293848629914671463858318958835174529758272731193423

[出力例]
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999988876543221111111111111111111111111111111111111122222222222222222222222222222222222222222223333333333333333333333333333333333333344444444444444444444444444444444444444444444555555555555555555555555555555555555666666666666666666666666666666666666666777777777777777777777777777777777777778888888888888888888888888888888888888888888888888888889
999999999999999999999999999999999999999999998888888888888888888888888888888888888877777777777777777777777777777777777777777776666666666666666666666666666666666666655555555555555555555555555555555555555555555444444444444444444444444444444444444333333333333333333333333333333333333333222222222222222222222222222222222222221111111111111111111111111111111111111111111111111111111

[入力例]

253

286

[出力例]

532

268

※AtCoderのテストケースより

[入力例]

345

556

[出力例]

435

565

※AtCoderのテストケースより

[入力例]

123

987987

[出力例]

312

799788

※AtCoderのテストケースより

[入力例]

11111111111111111111

111111111111111111111111111111

[出力例]

11111111111111111111

111111111111111111111111111111

※AtCoderのテストケースより

[入力例]

33231965444

773455566

[出力例]

19233444563

766555437

[入力例]

13785194584316927589

361659282125285

[出力例]

55299111335446887789

988665553222211

[入力例]

64298525857766878472

985733285545756164339168335839

[出力例]

98888777766655544222

888666599955311333233354455778

[入力例]

31415926535897932384626433832795

28841971693993751

[出力例]

66555443333999933221122345678887

99998877654321113

[入力例]

22175444971457187528782565139685443474229549313625352752311829887254616176822621978974878462694157495375954615447899327541617489148111884227358232886286227889645557945726241681611891958772213477437515

551641763747245118646413653235781313233898374817931453544492522426656592511875353264755952631934534191775794555619912773366291621596845688541515236561

[出力例]

88877777777777522222222222222111199999999999999999111111111111111111111222222222222255555533333333333354444444444444444444444444455555555555555555776666666666666666677777777777778888888888888888888888

999999999999888888888777777777777766666666666666666655555555555555555555555555544444444444444444333333333333333333322222222222221111111111111111111112

[入力例]

596566292477225167124797689822712989922218287694224795251699134214547334585329464159544189788918151193737328351346297845156335816156298861219182734638377894728227668331283653624246257276377836811971862752912774484634753467867376249442665576297677263994726859927416957145424679534826171713328616357727

76564588753992977891167538419732544499251298849996481579385543316893495799434283729514832677617324997637168395535682693663371365536697733465595971514825885974222929187611533998246944634996939819275442

[出力例]

888888888888777777777777777777777777777666666666666555554444444433333399999999999999999999999999999932222222222222222222222111111111111111111111111111111122222222222222222222233333333333333333333344444444444444444444444455555555555555555555556666666666666666666666666777777777777777788888888888888888

99999999999999999999999999999999999888888888888888888877777777777777777777766666666666666666666655555555555555555555555544444444444444444444443333333333333333333333333222222222222222211111111111111112

[入力例]

175558784176642428478886852882855583716348823311266168351117565526517246563464474343713186378358445825842875688328468224747862347184328843234558524873384588623418676322736867374751213285481637258731113376141451225431247636868272855271286637444364837212345678899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911648254724172726886576212874999999999999999999999998761513785328536141681424618172454423262172768855338

798712575381827545576737899297923911446969182444192158293357571521113147117194441699283651197668998739383164988824344734982795349365355256562868136216491554917941957124319167153177952521376528156791156976544147951266159411376581323677263132625248786714518936274126888662385854877456875923693193179271447287133625556351996281293848629914671463858318958835174529758272731193423

[出力例]

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999988876543221111111111111111111111111111111111111122222222222222222222222222222222222222222223333333333333333333333333333333333333344444444444444444444444444444444444444444444555555555555555555555555555555555555666666666666666666666666666666666666666777777777777777777777777777777777777778888888888888888888888888888888888888888888888888888889

999999999999999999999999999999999999999999998888888888888888888888888888888888888877777777777777777777777777777777777777777776666666666666666666666666666666666666655555555555555555555555555555555555555555555444444444444444444444444444444444444333333333333333333333333333333333333333222222222222222222222222222222222222221111111111111111111111111111111111111111111111111111111

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

// 解き直し.
// https://atcoder.jp/contests/arc130/editorial/2976
// -> 解説プログラムを参考に, 実際に, 桁和を計算を行い, 計算結果を比較する場合.
// 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--)
#define pb push_back
int aCount[10], bCount[10];

int main(){
    
    // 1. 入力情報.
    char s1[101010], s2[101010];
    scanf("%s %s", s1, s2);
    string sa(s1), sb(s2);
    
    // 2. a, b を 調整.
    bool aMinB = true;
    int al = sa.size(), bl = sb.size();
    if(al > bl){
        swap(sa, sb);
        aMinB = false;
    }
    
    // 3. 各桁の数字の出現回数.
    int lMax = max(al, bl), lMin = min(al, bl);
    rep(i, lMax){
        if(i < lMin) aCount[sa[i] - '0']++;
        bCount[sb[i] - '0']++;
    }
    aCount[0] += lMax - lMin;
    assert(bCount[0] == 0);
    // rep(i, 10) printf("%d ", aCount[i]);
    // puts("\n-----");
    // rep(i, 10) printf("%d ", bCount[i]);
    // puts("\n-----");
    
    // 4. 桁和を求める.
    auto f = [&](string t1, string t2) -> int {
        // 4-1. 初期化(ゼロ埋めほか).
        int ret = 0, carry = 0;
        string aStr = t1, bStr = t2;
        string zero(lMax - lMin, '0');
        bStr = zero + bStr;
        
        // 4-2. 桁和.
        while(aStr.size()){
            // 末尾を取得.
            int a = aStr.back();
            int b = bStr.back();
            aStr.pop_back();
            bStr.pop_back();
            
            // 桁上がりを考慮して, 加算.
            int x = (a - '0') + (b - '0') + carry;
            carry = 0;
            
            // 10以上か？
            if(x >= 10){
                x -= 10;
                carry = 1;
            }
            
            // 追加.
            ret += x;
        }
        
        // 4-3. 桁上がり.
        ret += carry;
        
        // 4-4. 返却.
        return ret;
    };
    
    // 5. 各桁の並び替え.
    int kMin = 2020202020;
    string ans[2];
    ans[0] = sa;
    ans[1] = sb;
    repx(a0, 1, 10){
        // 5-1. 変数を準備.
        string t[2];
        t[0] = "";
        t[1] = "";
        int ca[10], cb[10];
        rep(i, 10){
            ca[i] = aCount[i];
            cb[i] = bCount[i];
        }
        
        // 5-2. a[0] + b[0] >= 10 となるものを探す.
        bool ok = false;
        if(ca[a0]){
            repx(b0, 10 - a0, 10){
                // 見つかった場合は, 保存.
                if(cb[b0]){
                    t[0].pb(a0 + '0');
                    t[1].pb(b0 + '0');
                    ca[a0]--;
                    cb[b0]--;
                    ok = true;
                    break;
                }
            }
        }
        
        // 5-3. 見つからなかった場合.
        // printf("a0=%d t0=%s t1=%s\n", a0, t[0].c_str(), t[1].c_str());
        if(!ok) continue;
        
        // 5-4. 見つかった場合.
        repx(a, 1, 10){
            repx(b, 9 - a, 10){
                if(ca[a]){
                    // 各数字の出現回数を更新.
                    int l = min(ca[a], cb[b]);
                    ca[a] -= l;
                    cb[b] -= l;
                    
                    // 文字列作成.
                    string aStr(l, a + '0');
                    string bStr(l, b + '0');
                    
                    // 文字列追加.
                    t[0] = aStr + t[0];
                    t[1] = bStr + t[1];
                }
            }
        }
        
        // 5-5. 桁数以上(ゼロを考慮)の場合.
        if(ca[0]){
            if(cb[9]){
                // 該当する数字の出現回数を更新.
                int l = min(ca[0], cb[9]);
                ca[0] -= l;
                cb[9] -= l;
                
                // 文字列作成.
                string bStr(l, 9 + '0');
                
                // 文字列追加.
                t[1] = bStr + t[1];
            }
        }
        
        // 5-6. 残り.
        // -> 降順に追加するように修正.
        repr(a, 9, 1){
            if(ca[a]){
                string aStr(ca[a], a + '0');
                t[0] = aStr + t[0];
            }
        }
        repr(b, 9, 1){
            if(cb[b]){
                string bStr(cb[b], b + '0');
                t[1] = bStr + t[1];
            }
        }
        
        // 5-7. 桁和.
        int k = f(t[0], t[1]);
        // printf("k=%d t0=%s t1=%s", k, t[0].c_str(), t[1].c_str());
        // puts("-----");
        
        // 5-8. 桁和の最小値を更新.
        if(k < kMin){
            kMin = k;
            ans[0] = t[0];
            ans[1] = t[1];
        }
    }
    
    // 6. 入れ替え.
    if(!aMinB) swap(ans[0], ans[1]);
    
    // 7. 出力.
    printf("%s\n%s\n", ans[0].c_str(), ans[1].c_str());
    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

// 解き直し.

// https://atcoder.jp/contests/arc130/editorial/2976

// -> 解説プログラムを参考に, 実際に, 桁和を計算を行い, 計算結果を比較する場合.

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

#define pb push_back

int aCount[10], bCount[10];

int main(){

// 1. 入力情報.

char s1[101010], s2[101010];

scanf("%s %s", s1, s2);

string sa(s1), sb(s2);

// 2. a, b を調整.

bool aMinB = true;

int al = sa.size(), bl = sb.size();

if(al > bl){

swap(sa, sb);

aMinB = false;

}

// 3. 各桁の数字の出現回数.

int lMax = max(al, bl), lMin = min(al, bl);

rep(i, lMax){

if(i < lMin) aCount[sa[i] - '0']++;

bCount[sb[i] - '0']++;

}

aCount[0] += lMax - lMin;

assert(bCount[0] == 0);

// rep(i, 10) printf("%d ", aCount[i]);

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

// rep(i, 10) printf("%d ", bCount[i]);

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

// 4. 桁和を求める.

auto f = [&](string t1, string t2) -> int {

// 4-1. 初期化(ゼロ埋めほか).

int ret = 0, carry = 0;

string aStr = t1, bStr = t2;

string zero(lMax - lMin, '0');

bStr = zero + bStr;

// 4-2. 桁和.

while(aStr.size()){

// 末尾を取得.

int a = aStr.back();

int b = bStr.back();

aStr.pop_back();

bStr.pop_back();

// 桁上がりを考慮して, 加算.

int x = (a - '0') + (b - '0') + carry;

carry = 0;

// 10以上か？

if(x >= 10){

x -= 10;

carry = 1;

}

// 追加.

ret += x;

}

// 4-3. 桁上がり.

ret += carry;

// 4-4. 返却.

return ret;

};

// 5. 各桁の並び替え.

int kMin = 2020202020;

string ans[2];

ans[0] = sa;

ans[1] = sb;

repx(a0, 1, 10){

// 5-1. 変数を準備.

string t[2];

t[0] = "";

t[1] = "";

int ca[10], cb[10];

rep(i, 10){

ca[i] = aCount[i];

cb[i] = bCount[i];

}

// 5-2. a[0] + b[0] >= 10 となるものを探す.

bool ok = false;

if(ca[a0]){

repx(b0, 10 - a0, 10){

// 見つかった場合は, 保存.

if(cb[b0]){

t[0].pb(a0 + '0');

t[1].pb(b0 + '0');

ca[a0]--;

cb[b0]--;

ok = true;

break;

}

// 5-3. 見つからなかった場合.

// printf("a0=%d t0=%s t1=%s\n", a0, t[0].c_str(), t[1].c_str());

if(!ok) continue;

// 5-4. 見つかった場合.

repx(a, 1, 10){

repx(b, 9 - a, 10){

if(ca[a]){

// 各数字の出現回数を更新.

int l = min(ca[a], cb[b]);

ca[a] -= l;

cb[b] -= l;

// 文字列作成.

string aStr(l, a + '0');

string bStr(l, b + '0');

// 文字列追加.

t[0] = aStr + t[0];

t[1] = bStr + t[1];

}

// 5-5. 桁数以上(ゼロを考慮)の場合.

if(ca[0]){

if(cb[9]){

// 該当する数字の出現回数を更新.

int l = min(ca[0], cb[9]);

ca[0] -= l;

cb[9] -= l;

// 文字列作成.

string bStr(l, 9 + '0');

// 文字列追加.

t[1] = bStr + t[1];

}

// 5-6. 残り.

// -> 降順に追加するように修正.

repr(a, 9, 1){

if(ca[a]){

string aStr(ca[a], a + '0');

t[0] = aStr + t[0];

}

repr(b, 9, 1){

if(cb[b]){

string bStr(cb[b], b + '0');

t[1] = bStr + t[1];

}

// 5-7. 桁和.

int k = f(t[0], t[1]);

// printf("k=%d t0=%s t1=%s", k, t[0].c_str(), t[1].c_str());

// puts("-----");

// 5-8. 桁和の最小値を更新.

if(k < kMin){

kMin = k;

ans[0] = t[0];

ans[1] = t[1];

}

// 6. 入れ替え.

if(!aMinB) swap(ans[0], ans[1]);

// 7. 出力.

printf("%s\n%s\n", ans[0].c_str(), ans[1].c_str());

return 0;

}

[入力例]
253
286

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

[入力例]
345
556

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

[入力例]
123
987987

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

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

[入力例]
11111111111111111111
111111111111111111111111111111

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

[入力例]
33231965444
773455566

[出力例]
19233444563
766555437

[入力例]
13785194584316927589
361659282125285

[出力例]
25599111335446887789
988665553222211

[入力例]
64298525857766878472
985733285545756164339168335839

[出力例]
98888777766655544222
566688899955311333233354455778

[入力例]
31415926535897932384626433832795
28841971693993751

[出力例]
33334455567999932221123456678883
99998876543321117

[入力例]
22175444971457187528782565139685443474229549313625352752311829887254616176822621978974878462694157495375954615447899327541617489148111884227358232886286227889645557945726241681611891958772213477437515
551641763747245118646413653235781313233898374817931453544492522426656592511875353264755952631934534191775794555619912773366291621596845688541515236561

[出力例]
11112222222222222257777777777888899999999999999999111111111111111111111222222222222255555533333333333354444444444444444444444444455555555555555555766666666666666666777777777777778888888888888888888887
999999999999888888888777777777777766666666666666666655555555555555555555555555544444444444444444333333333333333333222222222222221111111111111111111113

[入力例]
596566292477225167124797689822712989922218287694224795251699134214547334585329464159544189788918151193737328351346297845156335816156298861219182734638377894728227668331283653624246257276377836811971862752912774484634753467867376249442665576297677263994726859927416957145424679534826171713328616357727
76564588753992977891167538419732544499251298849996481579385543316893495799434283729514832677617324997637168395535682693663371365536697733465595971514825885974222929187611533998246944634996939819275442

[出力例]
333333444444445555566666666666677777777777777777777777777888888888888899999999999999999999999999999922222222222222222222222111111111111111111111111111111122222222222222222222333333333333333333333444444444444444444444444555555555555555555555566666666666666666666666667777777777777777788888888888888883
99999999999999999999999999999999999888888888888888888877777777777777777777666666666666666666666555555555555555555555555444444444444444444444433333333333333333333333332222222222222222211111111111111117

[入力例]
175558784176642428478886852882855583716348823311266168351117565526517246563464474343713186378358445825842875688328468224747862347184328843234558524873384588623418676322736867374751213285481637258731113376141451225431247636868272855271286637444364837212345678899999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999911648254724172726886576212874999999999999999999999998761513785328536141681424618172454423262172768855338
798712575381827545576737899297923911446969182444192158293357571521113147117194441699283651197668998739383164988824344734982795349365355256562868136216491554917941957124319167153177952521376528156791156976544147951266159411376581323677263132625248786714518936274126888662385854877456875923693193179271447287133625556351996281293848629914671463858318958835174529758272731193423

[出力例]
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999988876543221111111111111111111111111111111111111122222222222222222222222222222222222222222223333333333333333333333333333333333333344444444444444444444444444444444444444444444555555555555555555555555555555555555666666666666666666666666666666666666666777777777777777777777777777777777777778888888888888888888888888888888888888888888888888888889
999999999999999999999999999999999999999999998888888888888888888888888888888888888877777777777777777777777777777777777777777776666666666666666666666666666666666666655555555555555555555555555555555555555555555444444444444444444444444444444444444333333333333333333333333333333333333333222222222222222222222222222222222222221111111111111111111111111111111111111111111111111111111

[入力例]

253

286

[出力例]

532

268

※AtCoderのテストケースより

[入力例]

345

556

[出力例]

435

565

※AtCoderのテストケースより

[入力例]

123

987987

[出力例]

312

799788

※AtCoderのテストケースより

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

213

899787

[入力例]

11111111111111111111

111111111111111111111111111111

[出力例]

11111111111111111111

111111111111111111111111111111

※AtCoderのテストケースより

[入力例]

33231965444

773455566

[出力例]

19233444563

766555437

[入力例]

13785194584316927589

361659282125285

[出力例]

25599111335446887789

988665553222211

[入力例]

64298525857766878472

985733285545756164339168335839

[出力例]

98888777766655544222

566688899955311333233354455778

[入力例]

31415926535897932384626433832795

28841971693993751

[出力例]

33334455567999932221123456678883

99998876543321117

[入力例]

551641763747245118646413653235781313233898374817931453544492522426656592511875353264755952631934534191775794555619912773366291621596845688541515236561

[出力例]

11112222222222222257777777777888899999999999999999111111111111111111111222222222222255555533333333333354444444444444444444444444455555555555555555766666666666666666777777777777778888888888888888888887

999999999999888888888777777777777766666666666666666655555555555555555555555555544444444444444444333333333333333333222222222222221111111111111111111113

[入力例]

[出力例]

333333444444445555566666666666677777777777777777777777777888888888888899999999999999999999999999999922222222222222222222222111111111111111111111111111111122222222222222222222333333333333333333333444444444444444444444444555555555555555555555566666666666666666666666667777777777777777788888888888888883

99999999999999999999999999999999999888888888888888888877777777777777777777666666666666666666666555555555555555555555555444444444444444444444433333333333333333333333332222222222222222211111111111111117

[入力例]

[出力例]

■参照サイト
AtCoder Regular Contest 130

2021年11月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 130 の問題A (Remove One Character) ～問題B (Colorful Lines) を解いてみた.

■感想.
1. 問題A, Bは, 方針を絞り込むことが出来たので, AC版に到達できたと思う.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char s[303030];
    scanf("%d %s", &N, s);
    s[N] = '#'; // 番兵.
    
    // 2. 文字列の連続箇所を把握.
    LL ans = 0, t = 0;
    char bef = '.', cur;
    rep(i, N + 1){
        // 今回分.
        cur = s[i];
        
        // 集計.
        if(bef == cur) t++;
        else           ans += t * (t - 1) / 2, t = 1;
        
        // 前回分.
        bef = cur;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char s[303030];

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

s[N] = '#'; // 番兵.

// 2. 文字列の連続箇所を把握.

LL ans = 0, t = 0;

char bef = '.', cur;

rep(i, N + 1){

// 今回分.

cur = s[i];

// 集計.

if(bef == cur) t++;

else ans += t * (t - 1) / 2, t = 1;

// 前回分.

bef = cur;

}

// 3. 出力.

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

return 0;

}

[入力例]
7
abbbcca

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

[入力例]
4
xxxx

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

[入力例]
2
pp

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

[入力例]
2
st

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

[入力例]
121
aaabccccdeeeeefffffffffgghhhhhhiiiiijjjkkkkkllllllllmmmmmmmmmnnnnnnnooooooooopppqqrrrssssssssttttuuuuuuvvwwwwwwxxxxyyyzzz

[出力例]
299

[入力例]
351
abbcccddddeeeeeffffffggggggghhhhhhhhiiiiiiiiijjjjjjjjjjkkkkkkkkkkkllllllllllllmmmmmmmmmmmmmnnnnnnnnnnnnnnoooooooooooooooppppppppppppppppqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrsssssssssssssssssssttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzz

[出力例]
2925

[入力例]
1807
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffffgggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrsssssssssssssssssssssssssssssssssstttttttttttttttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

[出力例]
78024

[入力例]

abbbcca

[出力例]

※AtCoderのテストケースより

[入力例]

xxxx

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

121

aaabccccdeeeeefffffffffgghhhhhhiiiiijjjkkkkkllllllllmmmmmmmmmnnnnnnnooooooooopppqqrrrssssssssttttuuuuuuvvwwwwwwxxxxyyyzzz

[出力例]

299

[入力例]

351

abbcccddddeeeeeffffffggggggghhhhhhhhiiiiiiiiijjjjjjjjjjkkkkkkkkkkkllllllllllllmmmmmmmmmmmmmnnnnnnnnnnnnnnoooooooooooooooppppppppppppppppqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrsssssssssssssssssssttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzz

[出力例]

2925

[入力例]

1807

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffffffffffffgggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggggghhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhiiiiiiiiiiiiiiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkllllllllllllllllllllllllllllmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnoooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrsssssssssssssssssssssssssssssssssstttttttttttttttttttttttttttttttttuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz

[出力例]

78024

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

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

int main(){
    
    // 1. 入力情報.
    int H, W, C, Q;
    scanf("%d %d %d %d", &H, &W, &C, &Q);
    rep(i, Q) scanf("%d %d %d", &t[i], &n[i], &c[i]);
    
    // 2. マスの色は？
    int rCount = 0, cCount = 0;
    set<int> rSt, cSt;
    repr(i, Q - 1, 0){
        // 2-1. 行方向.
        if(t[i] == 1){
            // まだ出現してない場合.
            if(!rSt.count(n[i])){
                // 行を保存.
                rSt.insert(n[i]);
                
                // 列数を考慮してカウント.
                ans[c[i]] += (LL)(W - cCount);
                
                // 行数カウント.
                rCount++;
            }
        }
        
        // 2-2. 列方向.
        if(t[i] == 2){
            // まだ出現してない場合.
            if(!cSt.count(n[i])){
                // 列を保存.
                cSt.insert(n[i]);
                
                // 行数を考慮してカウント.
                ans[c[i]] += (LL)(H - rCount);
                
                // 列数カウント.
                cCount++;
            }
        }
    }
    
    // 3. 出力.
    repx(i, 1, C + 1){
        printf("%lld", ans[i]);
        printf("%s", (i < C) ? " " : "\n");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL ans[303030];

int t[303030], n[303030], c[303030];

int main(){

// 1. 入力情報.

int H, W, C, Q;

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

rep(i, Q) scanf("%d %d %d", &t[i], &n[i], &c[i]);

// 2. マスの色は？

int rCount = 0, cCount = 0;

set<int> rSt, cSt;

repr(i, Q - 1, 0){

// 2-1. 行方向.

if(t[i] == 1){

// まだ出現してない場合.

if(!rSt.count(n[i])){

// 行を保存.

rSt.insert(n[i]);

// 列数を考慮してカウント.

ans[c[i]] += (LL)(W - cCount);

// 行数カウント.

rCount++;

}

// 2-2. 列方向.

if(t[i] == 2){

// まだ出現してない場合.

if(!cSt.count(n[i])){

// 列を保存.

cSt.insert(n[i]);

// 行数を考慮してカウント.

ans[c[i]] += (LL)(H - rCount);

// 列数カウント.

cCount++;

}

// 3. 出力.

repx(i, 1, C + 1){

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

printf("%s", (i < C) ? " " : "\n");

}

return 0;

}

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

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

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

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

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

[出力例]
20 17 9 0 15 19 0

[入力例]
20 21 11 28
1 13 8
2 11 11
1 5 10
1 11 2
2 7 8
2 19 4
1 1 7
1 10 2
1 20 1
2 17 1
2 5 1
1 13 11
1 4 2
1 11 8
2 9 3
1 7 3
2 7 5
2 21 5
1 19 9
2 3 6
2 10 1
2 17 9
1 20 7
2 7 10
1 1 8
2 7 11
2 21 8
1 19 11

[出力例]
30 29 32 12 0 17 19 53 17 13 66

[入力例]

4 5 6 5

1 1 6

1 3 3

2 2 4

2 4 2

1 1 2

[出力例]

0 8 3 3 0 0

※AtCoderのテストケースより

[入力例]

1000000000 1000000000 3 5

1 1 2

1 2 2

1 3 2

1 4 2

1 5 2

[出力例]

0 5000000000 0

※AtCoderのテストケースより

[入力例]

10 12 7 15

1 7 2

2 12 5

2 8 2

2 6 2

2 9 2

1 5 5

1 7 5

2 4 3

2 10 2

2 8 5

1 5 6

2 2 1

2 8 6

2 6 3

2 6 1

[出力例]

20 17 9 0 15 19 0

[入力例]

20 21 11 28

1 13 8

2 11 11

1 5 10

1 11 2

2 7 8

2 19 4

1 1 7

1 10 2

1 20 1

2 17 1

2 5 1

1 13 11

1 4 2

1 11 8

2 9 3

1 7 3

2 7 5

2 21 5

1 19 9

2 3 6

2 10 1

2 17 9

1 20 7

2 7 10

1 1 8

2 7 11

2 21 8

1 19 11

[出力例]

30 29 32 12 0 17 19 53 17 13 66

■参照サイト
AtCoder Regular Contest 130

C++の練習を兼ねて, JOI 2021/2022 二次予選 過去問 の 問題C (国土分割 (Land Division)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 054 の 問題C (鯛焼き) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題D (Kth Excluded) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 199 の 問題F (Graph Smoothing) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 230 の 問題E (Fraction Floor Sum) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 230 の 問題C (X drawing) ～ 問題D (Destroyer Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 130 の 問題C (Digit Sum Minimization) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 130 の 問題A (Remove One Character) ～ 問題B (Colorful Lines) を解いてみた.

C++の練習を兼ねて, JOI 2021/2022 二次予選過去問の問題C (国土分割 (Land Division)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 054 の問題C (鯛焼き) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題D (Kth Excluded) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 199 の問題F (Graph Smoothing) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 230 の問題E (Fraction Floor Sum) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 230 の問題C (X drawing) ～問題D (Destroyer Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 130 の問題C (Digit Sum Minimization) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 130 の問題A (Remove One Character) ～問題B (Colorful Lines) を解いてみた.