C++ | 個人用メモ帳

2021年3月31日

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

C++の練習を兼ねて, AtCoder Grand Contest 041 の問題C (Domino Quality) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. ドミノ牌の敷き詰め方に, 不思議な性質があることを知って, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc041/editorial.pdf
// 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--)
char ans[1010][1010];

char q31[3][3] = {
    {'a', 'a', '.'},
    {'.', '.', 'a'},
    {'.', '.', 'a'}
};
char q43[4][4] = {
    {'a', 'a', 'b', 'c'},
    {'d', 'd', 'b', 'c'},
    {'b', 'c', 'a', 'a'},
    {'b', 'c', 'd', 'd'}
};
char q53[5][5] = {
    {'a', 'a', 'b', 'b', 'a'},
    {'b', 'c', 'c', '.', 'a'},
    {'b', '.', '.', 'c', 'b'},
    {'a', '.', '.', 'c', 'b'},
    {'a', 'b', 'b', 'a', 'a'}
};
char q63[6][6] = {
    {'a', 'a', 'b', 'c', '.', '.'},
    {'d', 'd', 'b', 'c', '.', '.'},
    {'.', '.', 'a', 'a', 'b', 'c'},
    {'.', '.', 'd', 'd', 'b', 'c'},
    {'b', 'c', '.', '.', 'a', 'a'},
    {'b', 'c', '.', '.', 'd', 'd'}
};
char q73[7][7] = {
    {'a', 'a', 'b', 'b', 'c', 'c', '.'},
    {'d', 'd', '.', 'd', 'd', '.', 'a'},
    {'.', '.', 'd', '.', '.', 'd', 'a'},
    {'.', '.', 'd', '.', '.', 'd', 'b'},
    {'d', 'd', '.', 'd', 'd', '.', 'b'},
    {'.', '.', 'd', '.', '.', 'd', 'c'},
    {'.', '.', 'd', '.', '.', 'd', 'c'}
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. N = 2.
    if(N == 2){
        puts("-1");
        return 0;
    }
    
    // 3. N = 3.
    if(N == 3){
        rep(i, 3){
            rep(j, 3) printf("%c", q31[i][j]);
            puts("");
        }
        return 0;
    }
    
    // 4. N >= 4.
    // 4-1. x, y を 算出.
    int x = N / 4, y = N - x * 4, s, e;
    if(y < 4) x--, y += 4;
    rep(i, N) rep(j, N) ans[i][j] = '.';
    
    // 4-2. 4 * 4 の マス(x個).
    rep(k, x){
        // 左上が, k番目の場合, (4 * k, 4 * k) ～ (4 * k + 3, 4 * k + 3)
        // の 範囲 を, q43 で 埋めるようにする.
        s = 4 * k;
        e = 4 * (k + 1);
        repx(i, s, e){
            int di = i - s;
            repx(j, s, e){
                int dj = j - s;
                ans[i][j] = q43[di][dj];
            }
        }
    }
    
    // 4-3. y * y の マス(1個).
    s = 4 * x;
    e = N;
    repx(i, s, e){
        int di = i - s;
        repx(j, s, e){
            int dj = j - s;
            if(y == 4) ans[i][j] = q43[di][dj];
            if(y == 5) ans[i][j] = q53[di][dj];
            if(y == 6) ans[i][j] = q63[di][dj];
            if(y == 7) ans[i][j] = q73[di][dj];
        }
    }
    
    // 5. 出力.
    rep(i, N){
        rep(j, N) printf("%c", ans[i][j]);
        puts("");
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

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

char ans[1010][1010];

char q31[3][3] = {

{'a', 'a', '.'},

{'.', '.', 'a'},

{'.', '.', 'a'}

};

char q43[4][4] = {

{'a', 'a', 'b', 'c'},

{'d', 'd', 'b', 'c'},

{'b', 'c', 'a', 'a'},

{'b', 'c', 'd', 'd'}

};

char q53[5][5] = {

{'a', 'a', 'b', 'b', 'a'},

{'b', 'c', 'c', '.', 'a'},

{'b', '.', '.', 'c', 'b'},

{'a', '.', '.', 'c', 'b'},

{'a', 'b', 'b', 'a', 'a'}

};

char q63[6][6] = {

{'a', 'a', 'b', 'c', '.', '.'},

{'d', 'd', 'b', 'c', '.', '.'},

{'.', '.', 'a', 'a', 'b', 'c'},

{'.', '.', 'd', 'd', 'b', 'c'},

{'b', 'c', '.', '.', 'a', 'a'},

{'b', 'c', '.', '.', 'd', 'd'}

};

char q73[7][7] = {

{'a', 'a', 'b', 'b', 'c', 'c', '.'},

{'d', 'd', '.', 'd', 'd', '.', 'a'},

{'.', '.', 'd', '.', '.', 'd', 'a'},

{'.', '.', 'd', '.', '.', 'd', 'b'},

{'d', 'd', '.', 'd', 'd', '.', 'b'},

{'.', '.', 'd', '.', '.', 'd', 'c'},

{'.', '.', 'd', '.', '.', 'd', 'c'}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. N = 2.

if(N == 2){

puts("-1");

return 0;

}

// 3. N = 3.

if(N == 3){

rep(i, 3){

rep(j, 3) printf("%c", q31[i][j]);

puts("");

}

return 0;

}

// 4. N >= 4.

// 4-1. x, y を算出.

int x = N / 4, y = N - x * 4, s, e;

if(y < 4) x--, y += 4;

rep(i, N) rep(j, N) ans[i][j] = '.';

// 4-2. 4 * 4 のマス(x個).

rep(k, x){

// 左上が, k番目の場合, (4 * k, 4 * k) ～ (4 * k + 3, 4 * k + 3)

// の範囲を, q43 で埋めるようにする.

s = 4 * k;

e = 4 * (k + 1);

repx(i, s, e){

int di = i - s;

repx(j, s, e){

int dj = j - s;

ans[i][j] = q43[di][dj];

}

// 4-3. y * y のマス(1個).

s = 4 * x;

e = N;

repx(i, s, e){

int di = i - s;

repx(j, s, e){

int dj = j - s;

if(y == 4) ans[i][j] = q43[di][dj];

if(y == 5) ans[i][j] = q53[di][dj];

if(y == 6) ans[i][j] = q63[di][dj];

if(y == 7) ans[i][j] = q73[di][dj];

}

// 5. 出力.

rep(i, N){

rep(j, N) printf("%c", ans[i][j]);

puts("");

}

return 0;

}

[入力例]
6

[出力例]
aabb..
b..zz.
ba....
.a..aa
..a..b
..a..b
※AtCoderテストケースより

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

[入力例]
2

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

[入力例]
3

[出力例]
aa.
..a
..a

[入力例]
7

[出力例]
aabbcc.
dd.dd.a
..d..da
..d..db
dd.dd.b
..d..dc
..d..dc

[入力例]
8

[出力例]
aabc....
ddbc....
bcaa....
bcdd....
....aabc
....ddbc
....bcaa
....bcdd

[入力例]
9

[出力例]
aabc.....
ddbc.....
bcaa.....
bcdd.....
....aabba
....bcc.a
....b..cb
....a..cb
....abbaa

[入力例]
10

[出力例]
aabc......
ddbc......
bcaa......
bcdd......
....aabc..
....ddbc..
......aabc
......ddbc
....bc..aa
....bc..dd

[入力例]
11

[出力例]
aabc.......
ddbc.......
bcaa.......
bcdd.......
....aabbcc.
....dd.dd.a
......d..da
......d..db
....dd.dd.b
......d..dc
......d..dc

[入力例]
33

[出力例]
aabc.............................
ddbc.............................
bcaa.............................
bcdd.............................
....aabc.........................
....ddbc.........................
....bcaa.........................
....bcdd.........................
........aabc.....................
........ddbc.....................
........bcaa.....................
........bcdd.....................
............aabc.................
............ddbc.................
............bcaa.................
............bcdd.................
................aabc.............
................ddbc.............
................bcaa.............
................bcdd.............
....................aabc.........
....................ddbc.........
....................bcaa.........
....................bcdd.........
........................aabc.....
........................ddbc.....
........................bcaa.....
........................bcdd.....
............................aabba
............................bcc.a
............................b..cb
............................a..cb
............................abbaa


[入力例]
55

[出力例]
aabc...................................................
ddbc...................................................
bcaa...................................................
bcdd...................................................
....aabc...............................................
....ddbc...............................................
....bcaa...............................................
....bcdd...............................................
........aabc...........................................
........ddbc...........................................
........bcaa...........................................
........bcdd...........................................
............aabc.......................................
............ddbc.......................................
............bcaa.......................................
............bcdd.......................................
................aabc...................................
................ddbc...................................
................bcaa...................................
................bcdd...................................
....................aabc...............................
....................ddbc...............................
....................bcaa...............................
....................bcdd...............................
........................aabc...........................
........................ddbc...........................
........................bcaa...........................
........................bcdd...........................
............................aabc.......................
............................ddbc.......................
............................bcaa.......................
............................bcdd.......................
................................aabc...................
................................ddbc...................
................................bcaa...................
................................bcdd...................
....................................aabc...............
....................................ddbc...............
....................................bcaa...............
....................................bcdd...............
........................................aabc...........
........................................ddbc...........
........................................bcaa...........
........................................bcdd...........
............................................aabc.......
............................................ddbc.......
............................................bcaa.......
............................................bcdd.......
................................................aabbcc.
................................................dd.dd.a
..................................................d..da
..................................................d..db
................................................dd.dd.b
..................................................d..dc
..................................................d..dc

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

[入力例]

[出力例]

aabb..

b..zz.

ba....

.a..aa

..a..b

※AtCoderテストケースより

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

aabc..

ddbc..

..aabc

..ddbc

bc..aa

bc..dd

[入力例]

[出力例]

-1

※AtCoderテストケースより

[入力例]

[出力例]

aa.

..a

[入力例]

[出力例]

aabbcc.

dd.dd.a

..d..da

..d..db

dd.dd.b

..d..dc

[入力例]

[出力例]

aabc....

ddbc....

bcaa....

bcdd....

....aabc

....ddbc

....bcaa

....bcdd

[入力例]

[出力例]

aabc.....

ddbc.....

bcaa.....

bcdd.....

....aabba

....bcc.a

....b..cb

....a..cb

....abbaa

[入力例]

[出力例]

aabc......

ddbc......

bcaa......

bcdd......

....aabc..

....ddbc..

......aabc

......ddbc

....bc..aa

....bc..dd

[入力例]

[出力例]

aabc.......

ddbc.......

bcaa.......

bcdd.......

....aabbcc.

....dd.dd.a

......d..da

......d..db

....dd.dd.b

......d..dc

[入力例]

[出力例]

aabc.............................

ddbc.............................

bcaa.............................

bcdd.............................

....aabc.........................

....ddbc.........................

....bcaa.........................

....bcdd.........................

........aabc.....................

........ddbc.....................

........bcaa.....................

........bcdd.....................

............aabc.................

............ddbc.................

............bcaa.................

............bcdd.................

................aabc.............

................ddbc.............

................bcaa.............

................bcdd.............

....................aabc.........

....................ddbc.........

....................bcaa.........

....................bcdd.........

........................aabc.....

........................ddbc.....

........................bcaa.....

........................bcdd.....

............................aabba

............................bcc.a

............................b..cb

............................a..cb

............................abbaa

[入力例]

[出力例]

aabc...................................................

ddbc...................................................

bcaa...................................................

bcdd...................................................

....aabc...............................................

....ddbc...............................................

....bcaa...............................................

....bcdd...............................................

........aabc...........................................

........ddbc...........................................

........bcaa...........................................

........bcdd...........................................

............aabc.......................................

............ddbc.......................................

............bcaa.......................................

............bcdd.......................................

................aabc...................................

................ddbc...................................

................bcaa...................................

................bcdd...................................

....................aabc...............................

....................ddbc...............................

....................bcaa...............................

....................bcdd...............................

........................aabc...........................

........................ddbc...........................

........................bcaa...........................

........................bcdd...........................

............................aabc.......................

............................ddbc.......................

............................bcaa.......................

............................bcdd.......................

................................aabc...................

................................ddbc...................

................................bcaa...................

................................bcdd...................

....................................aabc...............

....................................ddbc...............

....................................bcaa...............

....................................bcdd...............

........................................aabc...........

........................................ddbc...........

........................................bcaa...........

........................................bcdd...........

............................................aabc.......

............................................ddbc.......

............................................bcaa.......

............................................bcdd.......

................................................aabbcc.

................................................dd.dd.a

..................................................d..da

..................................................d..db

................................................dd.dd.b

..................................................d..dc

■参照サイト
AtCoder Grand Contest 041

2021年3月30日2021年3月30日

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

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

■感想.
1. 問題Eは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvl v(N + 2);
    rep(i, N){
        LL x;
        int c;
        scanf("%lld %d", &x, &c);
        v[c].pb(x);
    }
    
    // 2. 番兵(ボールの色: N + 1).
    // -> 原点を保存.
    v[N + 1].pb(0);
    
    // 3. sort.
    rep(i, N + 2) sort(all(v[i]));
    
    // 4. dp更新.
    LL befL = 0, befR = 0, curL, curR, d1, d2;
    repx(i, 1, N + 2){
        // 4-1. ボールの有無を保存.
        int f = v[i].size();
        
        // 4-2. ボールあり.
        if(f){
            // 今回分更新.
            curL = v[i].front();
            curR = v[i].back();
            
            // 色 i を回収して, 左側にいる場合.
            d1 = dp[i - 1][0];
            d1 += (befL > curR) ? (befL - curL) : ((curR - befL) + (curR - curL));
            d2 = dp[i - 1][1];
            d2 += (befR > curR) ? (befR - curL) : ((curR - befR) + (curR - curL));
            dp[i][0] = min(d1, d2);
            
            // 色 i を回収して, 右側にいる場合.
            d1 = dp[i - 1][0];
            d1 += (befL > curL) ? ((befL - curL) + (curR - curL)) : (curR - befL);
            d2 = dp[i - 1][1];
            d2 += (befR > curL) ? ((befR - curL) + (curR - curL)) : (curR - befR);
            dp[i][1] = min(d1, d2);
            
            // 前回分更新.
            befL = curL;
            befR = curR;
        }
        
        // 4-3. ボールなし.
        if(!f){
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = dp[i - 1][1];
        }
    }
    
    // 5. 出力.
    printf("%lld\n", min(dp[N + 1][0], dp[N + 1][1]));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc197/editorial/995

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

using vvl = vector<vl>;

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

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

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

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

#define pb push_back

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

LL dp[202020][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvl v(N + 2);

rep(i, N){

LL x;

int c;

scanf("%lld %d", &x, &c);

v[c].pb(x);

}

// 2. 番兵(ボールの色: N + 1).

// -> 原点を保存.

v[N + 1].pb(0);

// 3. sort.

rep(i, N + 2) sort(all(v[i]));

// 4. dp更新.

LL befL = 0, befR = 0, curL, curR, d1, d2;

repx(i, 1, N + 2){

// 4-1. ボールの有無を保存.

int f = v[i].size();

// 4-2. ボールあり.

if(f){

// 今回分更新.

curL = v[i].front();

curR = v[i].back();

// 色 i を回収して, 左側にいる場合.

d1 = dp[i - 1][0];

d1 += (befL > curR) ? (befL - curL) : ((curR - befL) + (curR - curL));

d2 = dp[i - 1][1];

d2 += (befR > curR) ? (befR - curL) : ((curR - befR) + (curR - curL));

dp[i][0] = min(d1, d2);

// 色 i を回収して, 右側にいる場合.

d1 = dp[i - 1][0];

d1 += (befL > curL) ? ((befL - curL) + (curR - curL)) : (curR - befL);

d2 = dp[i - 1][1];

d2 += (befR > curL) ? ((befR - curL) + (curR - curL)) : (curR - befR);

dp[i][1] = min(d1, d2);

// 前回分更新.

befL = curL;

befR = curR;

}

// 4-3. ボールなし.

if(!f){

dp[i][0] = dp[i - 1][0];

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

}

// 5. 出力.

printf("%lld\n", min(dp[N + 1][0], dp[N + 1][1]));

return 0;

}

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

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

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

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

[入力例]
25
-36 22
51 25
52 13
113 8
-35 20
62 15
119 13
-104 5
110 2
91 17
-125 4
-71 11
60 19
89 22
-58 8
-7 12
-20 6
-110 20
-70 13
28 25
84 8
120 20
-37 14
-56 22
-72 7

[出力例]
2020

[入力例]
50
-900094 26
-712369 24
443734 20
-219850 20
746600 4
443548 10
201076 43
200562 19
1054193 28
-1066985 7
-217953 12
-282472 15
-324321 14
-196387 25
-697769 41
1213776 6
-1048894 12
-565530 11
279075 16
60507 5
443964 24
-268933 50
-562404 27
208251 19
-414540 10
-334856 6
184481 40
-1065994 11
572836 25
-382416 40
-1142099 37
724968 50
827501 9
-816595 10
-650848 7
-392826 44
-151981 17
-1232079 36
-614437 37
825447 12
1056309 4
309613 22
-525126 46
-1043184 22
-1176284 17
-1158708 33
-347587 16
-819143 44
949645 15
626133 50

[出力例]
33996956

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

[入力例]

2 2

3 1

1 3

4 2

5 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5

-4 4

4 3

6 3

-5 5

-3 2

2 2

3 3

1 4

[出力例]

※AtCoderテストケースより

[入力例]

-36 22

51 25

52 13

113 8

-35 20

62 15

119 13

-104 5

110 2

91 17

-125 4

-71 11

60 19

89 22

-58 8

-7 12

-20 6

-110 20

-70 13

28 25

84 8

120 20

-37 14

-56 22

-72 7

[出力例]

2020

[入力例]

-900094 26

-712369 24

443734 20

-219850 20

746600 4

443548 10

201076 43

200562 19

1054193 28

-1066985 7

-217953 12

-282472 15

-324321 14

-196387 25

-697769 41

1213776 6

-1048894 12

-565530 11

279075 16

60507 5

443964 24

-268933 50

-562404 27

208251 19

-414540 10

-334856 6

184481 40

-1065994 11

572836 25

-382416 40

-1142099 37

724968 50

827501 9

-816595 10

-650848 7

-392826 44

-151981 17

-1232079 36

-614437 37

825447 12

1056309 4

309613 22

-525126 46

-1043184 22

-1176284 17

-1158708 33

-347587 16

-819143 44

949645 15

626133 50

[出力例]

33996956

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

2021年3月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 116 の問題A (Odd vs Even) ～問題B (Products of Min-Max) を解いてみた.

■感想.
1. 規則性を抽出できたので, AC版まで到達できたと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

■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 T;
    scanf("%d", &T);
    rep(i, T){
        // 与えられた整数.
        LL N;
        scanf("%lld", &N);
        
        // 倍数をチェック.
        int f = 0;
        if(N % 2 == 0) f++;
        if(N % 4 == 0) f++;
        
        // 出力.
        if(f == 0) puts("Odd");
        if(f == 1) puts("Same");
        if(f == 2) puts("Even");
    }
    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 T;

scanf("%d", &T);

rep(i, T){

// 与えられた整数.

LL N;

scanf("%lld", &N);

// 倍数をチェック.

int f = 0;

if(N % 2 == 0) f++;

if(N % 4 == 0) f++;

// 出力.

if(f == 0) puts("Odd");

if(f == 1) puts("Same");

if(f == 2) puts("Even");

}

return 0;

}

[入力例]
3
2
998244353
1000000000000000000

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

[入力例]
17
222079
533860
941892
685490
243916
404856
695734
34365
572866
940162
470243
133907
930142
667476
669648
477556
294291

[出力例]
Odd
Even
Even
Same
Even
Even
Same
Odd
Same
Same
Odd
Odd
Same
Even
Even
Even
Odd

[入力例]

998244353

1000000000000000000

[出力例]

Same

Odd

Even

※AtCoderのテストケースより

[入力例]

222079

533860

941892

685490

243916

404856

695734

34365

572866

940162

470243

133907

930142

667476

669648

477556

294291

[出力例]

Odd

Even

Same

Even

Same

Odd

Same

Odd

Same

Even

Odd

■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--)
const LL MOD = 998244353;
LL a[202020], sum[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. max(B) の 和 は？
    // ex.
    // a = {a1, a2, a3, a4, a5} の 場合.
    //  min(B)       max(B) の 和.
    //    a1   sum[1] = a1 * 1 + a2 * 1 + a3 * 2 + a4 * 4 + a5 * 8 (16通り)
    //    a2   sum[2] =          a2 * 1 + a3 * 1 + a4 * 2 + a5 * 4  (8通り)
    //    a3   sum[3] =                   a3 * 1 + a4 * 1 + a5 * 2  (4通り)
    //    a4   sum[4] =                            a4 * 1 + a5 * 1  (2通り)
    //    a5   sum[5] =                                     a5 * 1  (1通り)
    // -> 上記から, a1 * sum[1] * ... * a5 * sum[5] (31通りの和) を 計算すれば良さそうに見える.
    sum[N - 1] = a[N - 1];
    repr(i, N - 2, 0){
        sum[i] = sum[i + 1] * 2LL;
        sum[i] += (MOD - a[i + 1]);
        sum[i] += a[i];
        sum[i] %= MOD;
    }
    
    // 4. 集計.
    LL ans = 0;
    rep(i, N) ans += (a[i] * sum[i]), ans %= MOD;
    
    // 5. 出力.
    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--)

const LL MOD = 998244353;

LL a[202020], sum[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. sort.

sort(a, a + N);

// 3. max(B) の和は？

// ex.

// a = {a1, a2, a3, a4, a5} の場合.

// min(B) max(B) の和.

// a1 sum[1] = a1 * 1 + a2 * 1 + a3 * 2 + a4 * 4 + a5 * 8 (16通り)

// a2 sum[2] = a2 * 1 + a3 * 1 + a4 * 2 + a5 * 4 (8通り)

// a3 sum[3] = a3 * 1 + a4 * 1 + a5 * 2 (4通り)

// a4 sum[4] = a4 * 1 + a5 * 1 (2通り)

// a5 sum[5] = a5 * 1 (1通り)

// -> 上記から, a1 * sum[1] * ... * a5 * sum[5] (31通りの和) を計算すれば良さそうに見える.

sum[N - 1] = a[N - 1];

repr(i, N - 2, 0){

sum[i] = sum[i + 1] * 2LL;

sum[i] += (MOD - a[i + 1]);

sum[i] += a[i];

sum[i] %= MOD;

}

// 4. 集計.

LL ans = 0;

rep(i, N) ans += (a[i] * sum[i]), ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
3
2 4 3

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

[入力例]
1
10

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

[入力例]
7
853983 14095 543053 143209 4324 524361 45154

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

[入力例]
12
31 41 59 26 53 58 97 93 23 84 62 64

[出力例]
10307796

[入力例]

2 4 3

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

100

※AtCoderのテストケースより

[入力例]

853983 14095 543053 143209 4324 524361 45154

[出力例]

206521341

※AtCoderのテストケースより

[入力例]

31 41 59 26 53 58 97 93 23 84 62 64

[出力例]

10307796

■参照サイト
AtCoder Regular Contest 116

2021年3月28日

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

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

■感想.
1. 実装に苦労したものの, 解説見る前に, AC版に到達出来たので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 2 の 冪乗 を 保存.
    vi cPow2;
    int count = 0;
    cPow2.pb(1);
    while(count < N){
        // 最大値を2倍.
        int p = 2 * cPow2.back();
        
        // 保存.
        cPow2.pb(p);
        
        // インクリメント.
        count++;
    }
    
    // 3. 区間を生成し, 最小値を探索.
    LL ans = 202020202020202020;
    rep(i, 1 << N){
        // 3-1. 区間を生成.
        int bef = -1, cur;
        vi v;
        rep(j, N){
            // 今回分更新.
            cur = (cPow2[N - 1 - j] & i) ? 1 : 0;
            
            // 前回と異なる場合は, 区間開始地点と見て保存.
            if(bef != cur) v.pb(j);
            
            // 前回分更新.
            bef = cur;
        }
        
        // 3-2. 番兵.
        v.pb(N);
        
        // 3-3. XOR生成.
        LL cXOR = 0;
        rep(j, v.size() - 1){
            // 区間開始地点, 区間終了地点.
            LL cOR = 0;
            int s = v[j];
            int e = v[j + 1];
            
            // 区間内の数のビット単位OR を計算.
            repx(k, s, e) cOR |= a[k];
            
            // 全ての値のビット単位XOR を計算.
            cXOR ^= cOR;
        }
        
        // 3-4. 最小値更新.
        ans = min(ans, cXOR);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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

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

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

#define pb push_back

LL a[22];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 2 の冪乗を保存.

vi cPow2;

int count = 0;

cPow2.pb(1);

while(count < N){

// 最大値を2倍.

int p = 2 * cPow2.back();

// 保存.

cPow2.pb(p);

// インクリメント.

count++;

}

// 3. 区間を生成し, 最小値を探索.

LL ans = 202020202020202020;

rep(i, 1 << N){

// 3-1. 区間を生成.

int bef = -1, cur;

vi v;

rep(j, N){

// 今回分更新.

cur = (cPow2[N - 1 - j] & i) ? 1 : 0;

// 前回と異なる場合は, 区間開始地点と見て保存.

if(bef != cur) v.pb(j);

// 前回分更新.

bef = cur;

}

// 3-2. 番兵.

v.pb(N);

// 3-3. XOR生成.

LL cXOR = 0;

rep(j, v.size() - 1){

// 区間開始地点, 区間終了地点.

LL cOR = 0;

int s = v[j];

int e = v[j + 1];

// 区間内の数のビット単位OR を計算.

repx(k, s, e) cOR |= a[k];

// 全ての値のビット単位XOR を計算.

cXOR ^= cOR;

}

// 3-4. 最小値更新.

ans = min(ans, cXOR);

}

// 4. 出力.

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

return 0;

}

[入力例]
3
1 5 7

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

[入力例]
3
10 10 10

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

[入力例]
4
1 3 3 1

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

[入力例]
5
1 3 12 18 7

[出力例]
24

[入力例]
10
1 2 3 16 17 31 63 1 2 3

[出力例]
32

[入力例]
18
1 2 2 3 4 5 8 9 16 17 32 33 64 65 128 129 256 257

[出力例]
1

[入力例]

1 5 7

[出力例]

※AtCoderテストケースより

[入力例]

10 10 10

[出力例]

※AtCoderテストケースより

[入力例]

1 3 3 1

[出力例]

※AtCoderテストケースより

[入力例]

1 3 12 18 7

[出力例]

[入力例]

1 2 3 16 17 31 63 1 2 3

[出力例]

[入力例]

1 2 2 3 4 5 8 9 16 17 32 33 64 65 128 129 256 257

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    double xs, ys, xo, yo;
    scanf("%lf %lf %lf %lf", &xs, &ys, &xo, &yo);
    
    // 2. x1, y1 を 計算.
    // -> 中心を, C(cx, cy)と置いて, ベクトル P[0]C(ux, uy), P[0]P[1](vx, vy) の関係を確認.
    double ux = (xs + xo) / 2.0 - xs;
    double uy = (ys + yo) / 2.0 - ys;
    double theta = PI * (1.0 - 0.5 - 1.0 / (double)N);
    double e = 2.0 * cos(theta);
    double vx = (cos(-theta) * ux - sin(-theta) * uy) * e;
    double vy = (sin(-theta) * ux + cos(-theta) * uy) * e;
    double x1 = xs + vx;
    double y1 = ys + vy;
    
    // 3. 出力.
    printf("%.11lf %.11lf\n", x1, y1);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

const double PI = acos(-1.0);

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

double xs, ys, xo, yo;

scanf("%lf %lf %lf %lf", &xs, &ys, &xo, &yo);

// 2. x1, y1 を計算.

// -> 中心を, C(cx, cy)と置いて, ベクトル P[0]C(ux, uy), P[0]P[1](vx, vy) の関係を確認.

double ux = (xs + xo) / 2.0 - xs;

double uy = (ys + yo) / 2.0 - ys;

double theta = PI * (1.0 - 0.5 - 1.0 / (double)N);

double e = 2.0 * cos(theta);

double vx = (cos(-theta) * ux - sin(-theta) * uy) * e;

double vy = (sin(-theta) * ux + cos(-theta) * uy) * e;

double x1 = xs + vx;

double y1 = ys + vy;

// 3. 出力.

printf("%.11lf %.11lf\n", x1, y1);

return 0;

}

[入力例]
4
1 1
2 2

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

[入力例]
6
5 3
7 4

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

[入力例]
8
3 7
19 25

[出力例]
11.70710678119 3.97918471983

[入力例]
30
2 6
75 51

[出力例]
7.47562561662 -1.09709773136

[入力例]

1 1

2 2

[出力例]

2.00000000000 1.00000000000

※AtCoderテストケースより

[入力例]

5 3

7 4

[出力例]

5.93301270189 2.38397459622

※AtCoderテストケースより

[入力例]

3 7

19 25

[出力例]

11.70710678119 3.97918471983

[入力例]

2 6

75 51

[出力例]

7.47562561662 -1.09709773136

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

2021年3月27日

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

C++の練習を兼ねて, AtCoder Grand Contest 041 の問題B (Voting Judges) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 実装に苦労したものの, 二分探索の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc041/editorial.pdf
// 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 a first
#define b second
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, P;
    LL M, V;
    scanf("%d %lld %lld %d", &N, &M, &V, &P);
    vl A;
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        A.pb(a);
    }
    
    // 2. 降順sort.
    sort(all(A));
    reverse(all(A));
    
    // 3. A[Y] + M < A[P] となる Y は？
    int Y = N;
    rep(i, N){
        if(A[i] + M < A[P - 1]){
            Y = i;
            break;
        }
    }
    
    // 4. 二分探索.
    // -> 01-38.txt などで, WA版となったため, ロジック修正.
    // -> l, m, h は, index と見る(問題数 に変換する場合は, +1 を 加算).
    int l = P - 1, h = Y, m;
    auto f = [&](int X) -> bool {
        // 4-1. 問題 1 ～ (P - 1) までの(P - 1)問を, M人 が 投票.
        LL lVote = max(0, P - 1) * M;
        
        // 4-2. 問題 P ～ (X - 1) まで, (A[X] + M - A[i])人 が 投票.
        LL mVote = 0;
        repx(i, P - 1, X) mVote += max(0LL, A[X] + M - A[i]);
        
        // 4-3. 問題 (X + 1) ～ N までの(N - X)問を, M人 が 投票.
        LL rVote = max(0, N - X) * M;
        
        // 4-4. 投票されても構わないかチェック.
        // -> (M * V)未満ならば, 採用される可能性なし.
        LL vote = lVote + mVote + rVote;
        // printf("lVote=%lld mVote=%lld rVote=%lld vote=%lld MV=%lld\n", lVote, mVote, rVote, vote, M * V);
        
        return (vote < M * V);
    };
    // 二分探索で確認してみる.
    while(l + 1 < h){
        m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 5. 出力.
    printf("%d\n", l + 1);
    return 0;
    
}

// 解き直し.

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

// 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 a first

#define b second

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

int main(){

// 1. 入力情報.

int N, P;

LL M, V;

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

vl A;

rep(i, N){

LL a;

scanf("%lld", &a);

A.pb(a);

}

// 2. 降順sort.

sort(all(A));

reverse(all(A));

// 3. A[Y] + M < A[P] となる Y は？

int Y = N;

rep(i, N){

if(A[i] + M < A[P - 1]){

Y = i;

break;

}

// 4. 二分探索.

// -> 01-38.txt などで, WA版となったため, ロジック修正.

// -> l, m, h は, index と見る(問題数に変換する場合は, +1 を加算).

int l = P - 1, h = Y, m;

auto f = [&](int X) -> bool {

// 4-1. 問題 1 ～ (P - 1) までの(P - 1)問を, M人が投票.

LL lVote = max(0, P - 1) * M;

// 4-2. 問題 P ～ (X - 1) まで, (A[X] + M - A[i])人が投票.

LL mVote = 0;

repx(i, P - 1, X) mVote += max(0LL, A[X] + M - A[i]);

// 4-3. 問題 (X + 1) ～ N までの(N - X)問を, M人が投票.

LL rVote = max(0, N - X) * M;

// 4-4. 投票されても構わないかチェック.

// -> (M * V)未満ならば, 採用される可能性なし.

LL vote = lVote + mVote + rVote;

// printf("lVote=%lld mVote=%lld rVote=%lld vote=%lld MV=%lld\n", lVote, mVote, rVote, vote, M * V);

return (vote < M * V);

};

// 二分探索で確認してみる.

while(l + 1 < h){

m = (h + l) >> 1;

if(f(m)) h = m;

else l = m;

// printf("h=%lld l=%lld m=%lld\n", h, l, m);

}

// 5. 出力.

printf("%d\n", l + 1);

return 0;

}

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

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

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

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

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

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

[入力例]
20 3456 8 7
1728 11106 5834 12781 18820 14127 19412 9407 903 18066 14909 10426 10017 16164 21158 4660 18664 20245 3303 5934

[出力例]
10

[入力例]
50 2021 11 13
4365 17834 3440 5625 7833 2260 18430 10630 7648 2337 12612 9640 6127 12345 17602 15202 13456 16161 18060 12345 21191 6149 5440 778 14265 1574 8561 12345 20036 19537 12345 8049 21239 17688 5625 12591 13759 6962 12345 3933 14044 2721 652 12159 10982 19920 11192 5625 22068 9206

[出力例]
17

[入力例]

6 1 2 2

2 1 1 3 0 2

[出力例]

※AtCoderテストケースより

[入力例]

6 1 5 2

2 1 1 3 0 2

[出力例]

※AtCoderテストケースより

[入力例]

10 4 8 5

7 2 3 6 1 6 5 4 6 5

[出力例]

※AtCoderテストケースより

[入力例]

20 3456 8 7

1728 11106 5834 12781 18820 14127 19412 9407 903 18066 14909 10426 10017 16164 21158 4660 18664 20245 3303 5934

[出力例]

[入力例]

50 2021 11 13

4365 17834 3440 5625 7833 2260 18430 10630 7648 2337 12612 9640 6127 12345 17602 15202 13456 16161 18060 12345 21191 6149 5440 778 14265 1574 8561 12345 20036 19537 12345 8049 21239 17688 5625 12591 13759 6962 12345 3933 14044 2721 652 12159 10982 19920 11192 5625 22068 9206

[出力例]

■参照サイト
AtCoder Grand Contest 041

2021年3月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題D (Odd Degree) を解いてみた.

■感想.
1. 問題Dは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 苦手なdpの訓練を積めたので, 非常に良かったと思う.
3. 幅優先探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc115/editorial/853
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
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 a first
#define b second
#define pb push_back
const LL MOD = 998244353;
const int LIMIT = 5050;
LL FAC[LIMIT], INV[LIMIT], g[LIMIT][LIMIT], dp[LIMIT][LIMIT];

// 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 % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    vector<P> edges;
    rep(i, M){
        int a, b;
        scanf("%d %d", &a, &b);
        a--;
        b--;
        G[a].pb(b);
        G[b].pb(a);
        edges.pb({a, b});
    }
    FAC[0] = 1;
    repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, N + 1)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 2. グラフを連結成分に分解.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 2-1. 空のキュー.
        queue<int> q;
        
        // 2-2. 連結成分番号を設定.
        c[s] = l;
        
        // 2-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 2-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 2-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 2-6. 訪問済であれば, 処理をスキップ.
                if(c[e])            continue;
                if(!c[e] && e != s) c[e] = l, q.push(e);
            }
        }
        return;
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    // rep(i, N) printf("%d ", c[i]);
    // puts("");
    
    // 3. 連結成分ごとの頂点数, 辺数 を 計算.
    set<int> gn[idx]; // 各連結成分に対する頂点.
    int gm[idx];      // 各連結成分に対する辺数.
    rep(i, idx) gm[i] = 0;
    for(auto &e : edges){
        int a, b;
        a = e.a;
        b = e.b;
        int n = c[a] - 1;
        assert(c[a] == c[b]);
        
        // 頂点を保存.
        gn[n].insert(a);
        gn[n].insert(b);
        
        // 辺数をカウント.
        gm[n]++;
    }
    
    // 4. 連結成分ごとに集計.
    rep(i, idx){
        LL m = (LL)gm[i];
        LL n = (LL)gn[i].size();
        LL o = m - n + 1LL;
        rep(k, N + 1){
            // K が 奇数.
            // - >何もしない
            if(k & 1) continue;
            
            // K が 偶数.
            // -> 辺が有る場合は, 全域木を適当に一つ取り, 全域木に含まれない辺を残すかどうか自由に決める.
            LL res = (m == 0) ? 1LL : mPow(2LL, o);
            g[i][k] = res * combination(n, (LL)k) % MOD;
        }
    }
    
    // 5. dp更新.
    int nSum = gn[0].size();
    rep(k, nSum + 1) dp[0][k] = g[0][k];
    repx(i, 1, idx){
        // 5-1. 頂点数設定.
        int nCur = gn[i].size();
        
        // 5-2. (i - 1)番目の状態をベースに, i番目の状態を決定.
        rep(k1, nSum + 1){
            rep(k2, nCur + 1){
                dp[i][k1 + k2] += dp[i - 1][k1] * g[i][k2];
                dp[i][k1 + k2] %= MOD;
            }
        }
        
        // 5-3. 頂点数合計を更新.
        nSum += nCur;
    }
    
    // 6. 出力.
    rep(i, N + 1) printf("%lld\n", dp[idx - 1][i]);
    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

// 解き直し.

// https://atcoder.jp/contests/arc115/editorial/853

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

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 a first

#define b second

#define pb push_back

const LL MOD = 998244353;

const int LIMIT = 5050;

LL FAC[LIMIT], INV[LIMIT], g[LIMIT][LIMIT], dp[LIMIT][LIMIT];

// 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 % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

vector<P> edges;

rep(i, M){

int a, b;

scanf("%d %d", &a, &b);

a--;

b--;

G[a].pb(b);

G[b].pb(a);

edges.pb({a, b});

}

FAC[0] = 1;

repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;

rep(i, N + 1) INV[i] = mPow(FAC[i], MOD - 2) % MOD;

// 2. グラフを連結成分に分解.

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

auto bfs = [&](vvi &G, int s, int* c, int l){

// 2-1. 空のキュー.

queue<int> q;

// 2-2. 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

// 2-4. キューから取り出す.

int u = q.front();

q.pop();

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

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

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

if(c[e]) continue;

if(!c[e] && e != s) c[e] = l, q.push(e);

}

return;

};

int c[N], idx = 0;

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

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// rep(i, N) printf("%d ", c[i]);

// puts("");

// 3. 連結成分ごとの頂点数, 辺数を計算.

set<int> gn[idx]; // 各連結成分に対する頂点.

int gm[idx]; // 各連結成分に対する辺数.

rep(i, idx) gm[i] = 0;

for(auto &e : edges){

int a, b;

a = e.a;

b = e.b;

int n = c[a] - 1;

assert(c[a] == c[b]);

// 頂点を保存.

gn[n].insert(a);

gn[n].insert(b);

// 辺数をカウント.

gm[n]++;

}

// 4. 連結成分ごとに集計.

rep(i, idx){

LL m = (LL)gm[i];

LL n = (LL)gn[i].size();

LL o = m - n + 1LL;

rep(k, N + 1){

// K が奇数.

// - >何もしない

if(k & 1) continue;

// K が偶数.

// -> 辺が有る場合は, 全域木を適当に一つ取り, 全域木に含まれない辺を残すかどうか自由に決める.

LL res = (m == 0) ? 1LL : mPow(2LL, o);

g[i][k] = res * combination(n, (LL)k) % MOD;

}

// 5. dp更新.

int nSum = gn[0].size();

rep(k, nSum + 1) dp[0][k] = g[0][k];

repx(i, 1, idx){

// 5-1. 頂点数設定.

int nCur = gn[i].size();

// 5-2. (i - 1)番目の状態をベースに, i番目の状態を決定.

rep(k1, nSum + 1){

rep(k2, nCur + 1){

dp[i][k1 + k2] += dp[i - 1][k1] * g[i][k2];

dp[i][k1 + k2] %= MOD;

}

// 5-3. 頂点数合計を更新.

nSum += nCur;

}

// 6. 出力.

rep(i, N + 1) printf("%lld\n", dp[idx - 1][i]);

return 0;

}

[入力例]
3 2
1 2
2 3

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

[入力例]
4 2
1 2
3 4

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

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

[出力例]
2
0
8
0
6
0

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

[出力例]
8
0
72
0
152
0
24
0

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

[出力例]
128
0
2560
0
14080
0
12800
0
3200
0
0

[入力例]

3 2

1 2

2 3

[出力例]

※AtCoderのテストケースより

[入力例]

4 2

1 2

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

5 4

1 2

3 2

1 3

4 5

[出力例]

[入力例]

7 8

1 2

2 3

3 4

4 1

3 1

5 6

6 7

7 5

[出力例]

152

[入力例]

10 15

1 2

1 3

2 3

1 4

1 5

6 7

6 8

6 9

6 10

7 8

7 9

7 10

8 9

8 10

9 10

[出力例]

128

2560

14080

12800

3200

■参照サイト
AtCoder Regular Contest 115

2021年3月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題C (ℕ Coloring) を解いてみた.

■感想.
1. 規則性が抽出出来たので, 久しぶりに, 解答見る前に, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. i の 小さい順に, 数列を更新.
    rep(i, 101010) ans[i] = 1;
    repx(i, 1, N + 1) repex(j, i * 2, N + 1, i) if(ans[i] == ans[j]) ans[j]++;
    
    // 3. 出力.
    repx(i, 1, N + 1){
        printf("%d", ans[i]);
        printf("%s", (i < N) ? " " : "\n");
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int ans[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. i の小さい順に, 数列を更新.

rep(i, 101010) ans[i] = 1;

repx(i, 1, N + 1) repex(j, i * 2, N + 1, i) if(ans[i] == ans[j]) ans[j]++;

// 3. 出力.

repx(i, 1, N + 1){

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

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

}

return 0;

}

[入力例]
4

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

[入力例]
7

[出力例]
1 2 2 3 2 3 2

[入力例]
77

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

[入力例]
777

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

[入力例]

[出力例]

1 2 2 3

※AtCoderのテストケースより

[入力例]

[出力例]

1 2 2 3 2 3 2

[入力例]

[出力例]

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

[入力例]

777

[出力例]

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

■参照サイト
AtCoder Regular Contest 115

2021年3月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題A (Two Choices) ～問題B (Plus Matrix) を解いてみた.

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

■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, M;
    LL odd = 0, even = 0;
    scanf("%d %d", &N, &M);
    rep(i, N){
        int one = 0;
        char c[22];
        scanf("%s", &c);
        rep(j, M) if(c[j] == '1') one++;
        if(one & 1) odd++;
        else        even++;
    }
    
    // 2. 出力.
    printf("%lld\n", odd * even);
    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, M;

LL odd = 0, even = 0;

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

rep(i, N){

int one = 0;

char c[22];

scanf("%s", &c);

rep(j, M) if(c[j] == '1') one++;

if(one & 1) odd++;

else even++;

}

// 2. 出力.

printf("%lld\n", odd * even);

return 0;

}

[入力例]
3 2
00
01
10

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

[入力例]
7 5
10101
00001
00110
11110
00100
11111
10000

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

[入力例]
10 6
000110
001110
100111
011000
100110
100011
011001
001001
100010
101010

[出力例]
25

[入力例]
50 10
0001100101
0011101000
1001110111
0110001011
1001100011
1000110101
0110011100
0010011111
1000100000
1010101111
0101010000
0010110100
1100011010
0000101101
1010101110
0000010010
1110011001
1111001101
0000001011
0001011010
1001100011
1110110111
0101010001
0010110011
0001100001
0110100000
1101001100
1010010100
1110001100
1110100110
0100000000
0110110000
0011101110
0001101110
0101001111
0001101100
0101100111
1110001100
1011001000
1111111001
1011111010
0101111011
1010011011
1001010110
1010110011
0101111110
0000001111
0110001111
0101100110
0011111100

[出力例]
624

[入力例]

3 2

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

10101

00001

00110

11110

00100

11111

10000

[出力例]

※AtCoderのテストケースより

[入力例]

10 6

000110

001110

100111

011000

100110

100011

011001

001001

100010

101010

[出力例]

[入力例]

50 10

0001100101

0011101000

1001110111

0110001011

1001100011

1000110101

0110011100

0010011111

1000100000

1010101111

0101010000

0010110100

1100011010

0000101101

1010101110

0000010010

1110011001

1111001101

0000001011

0001011010

1001100011

1110110111

0101010001

0010110011

0001100001

0110100000

1101001100

1010010100

1110001100

1110100110

0100000000

0110110000

0011101110

0001101110

0101001111

0001101100

0101100111

1110001100

1011001000

1111111001

1011111010

0101111011

1010011011

1001010110

1010110011

0101111110

0000001111

0110001111

0101100110

0011111100

[出力例]

624

■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 C[505][505], ka[505], kb[505], A[505], B[505];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) rep(j, N) scanf("%lld", &C[i][j]);
    
    // 2. 行方向.
    bool rOk = true;
    rep(i, N - 1){
        // (i + 1)行目 マイナス i行目.
        LL a = C[i + 1][0] - C[i][0];
        repx(j, 1, N) if(a != C[i + 1][j] - C[i][j]) rOk = false;
        
        // 条件を満たす場合は, 保存.
        if(rOk) ka[i] = a;
        else    break;
    }
    
    // 3. 列方向.
    bool cOk = true;
    rep(j, N - 1){
        // (j + 1)列目 マイナス j列目.
        LL b = C[0][j + 1] - C[0][j];
        repx(i, 1, N) if(b != C[i][j + 1] - C[i][j]) cOk = false;
        
        // 条件を満たす場合は, 保存.
        if(cOk) kb[j] = b;
        else    break;
    }
    
    // 4. 条件を満たさない場合は, 終了.
    if(!rOk || !cOk){
        puts("No");
        return 0;
    }
    
    // 5. 条件を満たす場合.
    // 5-1. A を 計算.
    LL minA = A[0];
    rep(i, N - 1) A[i + 1] = A[i] + ka[i], minA = min(minA, A[i + 1]);
    
    // 5-2. minA が マイナスの場合, 加算.
    if(minA < 0) rep(i, N) A[i] -= minA;
    
    // 5-3. B を 計算.
    LL minB = B[0];
    rep(i, N - 1) B[i + 1] = B[i] + kb[i], minB = min(minB, B[i + 1]);
    
    // 5-4. minB が マイナスの場合, 加算.
    if(minB < 0) rep(i, N) B[i] -= minB;
    
    // 5-5. C[0][0] と 比較し, 差分 を 加算.
    LL kc = C[0][0] - A[0] - B[0];
    if(kc > 0) rep(i, N) B[i] += kc;
    
    // 6. 出力.
    puts("Yes");
    rep(i, N){
        printf("%lld", A[i]);
        printf("%s", (i < N - 1) ? " " : "\n");
    }
    rep(i, N){
        printf("%lld", B[i]);
        printf("%s", (i < N - 1) ? " " : "\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 C[505][505], ka[505], kb[505], A[505], B[505];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 行方向.

bool rOk = true;

rep(i, N - 1){

// (i + 1)行目マイナス i行目.

LL a = C[i + 1][0] - C[i][0];

repx(j, 1, N) if(a != C[i + 1][j] - C[i][j]) rOk = false;

// 条件を満たす場合は, 保存.

if(rOk) ka[i] = a;

else break;

}

// 3. 列方向.

bool cOk = true;

rep(j, N - 1){

// (j + 1)列目マイナス j列目.

LL b = C[0][j + 1] - C[0][j];

repx(i, 1, N) if(b != C[i][j + 1] - C[i][j]) cOk = false;

// 条件を満たす場合は, 保存.

if(cOk) kb[j] = b;

else break;

}

// 4. 条件を満たさない場合は, 終了.

if(!rOk || !cOk){

puts("No");

return 0;

}

// 5. 条件を満たす場合.

// 5-1. A を計算.

LL minA = A[0];

rep(i, N - 1) A[i + 1] = A[i] + ka[i], minA = min(minA, A[i + 1]);

// 5-2. minA がマイナスの場合, 加算.

if(minA < 0) rep(i, N) A[i] -= minA;

// 5-3. B を計算.

LL minB = B[0];

rep(i, N - 1) B[i + 1] = B[i] + kb[i], minB = min(minB, B[i + 1]);

// 5-4. minB がマイナスの場合, 加算.

if(minB < 0) rep(i, N) B[i] -= minB;

// 5-5. C[0][0] と比較し, 差分を加算.

LL kc = C[0][0] - A[0] - B[0];

if(kc > 0) rep(i, N) B[i] += kc;

// 6. 出力.

puts("Yes");

rep(i, N){

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

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

}

rep(i, N){

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

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

}

return 0;

}

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

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

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

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

[入力例]
5
6 12 5 8 11
13 19 12 15 18
10 16 9 12 15
8 14 7 10 13
5 11 4 7 10

[出力例]
Yes
1 8 5 3 0
5 11 4 7 10

[入力例]

4 3 5

2 1 3

3 2 4

[出力例]

Yes

2 0 1

2 1 3

※AtCoderのテストケースより

[入力例]

4 3 5

2 2 3

3 2 4

[出力例]

※AtCoderのテストケースより

[入力例]

6 12 5 8 11

13 19 12 15 18

10 16 9 12 15

8 14 7 10 13

5 11 4 7 10

[出力例]

Yes

1 8 5 3 0

5 11 4 7 10

■参照サイト
AtCoder Regular Contest 115

2021年3月22日

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

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題C (Neither AB nor BA) を解いてみた.

■感想.
1. 問題Cは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc040/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const LL MOD = 998244353;
const int LIMIT = 10101010;
LL FAC[LIMIT], INV[LIMIT];

// 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 % MOD;
}

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    FAC[0] = 1;
    repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;
    rep(i, N + 1)     INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    
    // 2. 解説通り.
    // 2-1. 3 の N乗.
    LL ans = mPow(3LL, (LL)N);
    
    // 2-2. 'A' もしくは 'B' が 過半数となる文字列の個数.
    LL aORb = 0;
    repx(r, N / 2 + 1, N + 1){
        aORb += combination((LL)N, (LL)r) * mPow(2LL, (LL)(N - r));
        aORb %= MOD;
    }
    
    // 2-3. 集計.
    ans = (ans + MOD - aORb) % MOD;
    ans = (ans + MOD - aORb) % MOD;
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

const int LIMIT = 10101010;

LL FAC[LIMIT], INV[LIMIT];

// 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 % MOD;

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列FAC, INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, LL k){

if(n < 0 || k < 0 || k > n) return 0;

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

FAC[0] = 1;

repx(i, 1, N + 1) FAC[i] = i * FAC[i - 1] % MOD;

rep(i, N + 1) INV[i] = mPow(FAC[i], MOD - 2) % MOD;

// 2. 解説通り.

// 2-1. 3 の N乗.

LL ans = mPow(3LL, (LL)N);

// 2-2. 'A' もしくは 'B' が過半数となる文字列の個数.

LL aORb = 0;

repx(r, N / 2 + 1, N + 1){

aORb += combination((LL)N, (LL)r) * mPow(2LL, (LL)(N - r));

aORb %= MOD;

}

// 2-3. 集計.

ans = (ans + MOD - aORb) % MOD;

// 3. 出力.

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

return 0;

}

[入力例]
2

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

[入力例]
10

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

[入力例]
1000000

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

[入力例]
5

[出力例]
141

[入力例]
18

[出力例]
353832631

[入力例]
3141592

[出力例]
895463844

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

50007

※AtCoderテストケースより

[入力例]

1000000

[出力例]

210055358

※AtCoderテストケースより

[入力例]

[出力例]

141

[入力例]

[出力例]

353832631

[入力例]

3141592

[出力例]

895463844

■参照サイト
AtCoder Grand Contest 040

2021年3月21日

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

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題B (Two Contests) を解いてみた.

■感想.
1. 問題Bは, 解答方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc040/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
const LL INF = 202020202020202020;
LL l[101010], r[101010], as[101010], bt[101010];

struct joy{
    int i;
    LL a, b;
    bool operator < (const joy& rhs) const{
        return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b));
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    LL ans = 0, maxL = 0, minR = INF;
    int p = -1, q = -1;
    rep(i, N){
        scanf("%lld %lld", &l[i], &r[i]);
        if(maxL < l[i]){
            maxL = l[i];
            p = i;
        }
        if(minR > r[i]){
            minR = r[i];
            q = i;
        }
        ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存.
    }
    ans += max(0LL, minR - maxL + 1LL);
    
    // 2. 解説通り.
    vector<joy> v;
    rep(i, N){
        LL a = max(r[i] - maxL + 1LL, 0LL);
        LL b = max(minR - l[i] + 1LL, 0LL);
        joy j;
        j.i = i;
        j.a = a;
        j.b = b;
        v.pb(j);
    }
    
    // 3. sort.
    sort(all(v));
    // for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b);
    
    // 4. 事前準備.
    rep(i, N + 1)     as[i] = bt[i] = INF;
    repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a);
    rep(i, N)         bt[i + 1] = min(bt[i], v[i].b);
    // rep(i, N + 1) printf("%lld ", as[i]);
    // puts("");  
    // rep(i, N + 1) printf("%lld ", bt[i]);
    // puts("");
    
    // 5. 最大値は？
    repx(i, 1, N) ans = max(ans, as[i] + bt[i]);
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

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

const LL INF = 202020202020202020;

LL l[101010], r[101010], as[101010], bt[101010];

struct joy{

int i;

LL a, b;

bool operator < (const joy& rhs) const{

return (a < rhs.a) || ((a == rhs.a) && (b > rhs.b));

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

LL ans = 0, maxL = 0, minR = INF;

int p = -1, q = -1;

rep(i, N){

scanf("%lld %lld", &l[i], &r[i]);

if(maxL < l[i]){

maxL = l[i];

p = i;

}

if(minR > r[i]){

minR = r[i];

q = i;

}

ans = max(ans, r[i] - l[i] + 1LL); // 最も長い区間を保存.

}

ans += max(0LL, minR - maxL + 1LL);

// 2. 解説通り.

vector<joy> v;

rep(i, N){

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

LL b = max(minR - l[i] + 1LL, 0LL);

joy j;

j.i = i;

j.a = a;

j.b = b;

v.pb(j);

}

// 3. sort.

sort(all(v));

// for(auto &p : v) printf("i=%d a=%lld b=%lld\n", p.i, p.a, p.b);

// 4. 事前準備.

rep(i, N + 1) as[i] = bt[i] = INF;

repr(i, N - 1, 0) as[i] = min(as[i + 1], v[i].a);

rep(i, N) bt[i + 1] = min(bt[i], v[i].b);

// rep(i, N + 1) printf("%lld ", as[i]);

// puts("");

// rep(i, N + 1) printf("%lld ", bt[i]);

// puts("");

// 5. 最大値は？

repx(i, 1, N) ans = max(ans, as[i] + bt[i]);

// 6. 出力.

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

return 0;

}

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

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

[入力例]
4
1 20
2 19
3 18
4 17

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

[入力例]
10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526

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

[入力例]
25
1 6
17 23
16 31
7 22
4 5
3 13
19 27
7 13
11 22
2 3
6 21
3 19
3 13
7 7
15 20
2 11
9 23
17 25
6 15
15 19
9 19
4 5
15 19
1 2
11 21

[出力例]
17

[入力例]

4 7

1 4

5 8

2 5

[出力例]

※AtCoderテストケースより

[入力例]

1 20

2 19

3 18

4 17

[出力例]

※AtCoderテストケースより

[入力例]

457835016 996058008

456475528 529149798

455108441 512701454

455817105 523506955

457368248 814532746

455073228 459494089

456651538 774276744

457667152 974637457

457293701 800549465

456580262 636471526

[出力例]

540049931

※AtCoderテストケースより

[入力例]

1 6

17 23

16 31

7 22

4 5

3 13

19 27

7 13

11 22

2 3

6 21

3 19

3 13

7 7

15 20

2 11

9 23

17 25

6 15

15 19

9 19

4 5

15 19

1 2

11 21

[出力例]

■参照サイト
AtCoder Grand Contest 040

C++の練習を兼ねて, AtCoder Grand Contest 041 の 問題C (Domino Quality) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 116 の 問題A (Odd vs Even) ～ 問題B (Products of Min-Max) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 041 の 問題B (Voting Judges) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 115 の 問題D (Odd Degree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 115 の 問題C (ℕ Coloring) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 115 の 問題A (Two Choices) ～ 問題B (Plus Matrix) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 040 の 問題C (Neither AB nor BA) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 040 の 問題B (Two Contests) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 041 の問題C (Domino Quality) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 116 の問題A (Odd vs Even) ～問題B (Products of Min-Max) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 041 の問題B (Voting Judges) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題D (Odd Degree) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題C (ℕ Coloring) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 115 の問題A (Two Choices) ～問題B (Plus Matrix) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題C (Neither AB nor BA) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題B (Two Contests) を解いてみた.