C++ | 個人用メモ帳

2022年11月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 118 の問題D (Hamiltonian Cycle) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, ハミルトン閉路の性質に触れることが出来たので, 非常に, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc118/editorial/1210
// 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

int main(){
    
    // 1. 入力情報.
    int P;
    LL a, b;
    scanf("%d %lld %lld", &P, &a, &b);
    
    // 2. a の 冪乗 が 1 となる n.
    int n = -1;
    LL cur = 1;
    set<LL> H;
    H.insert(1);
    repx(i, 1, P){
        // a の 冪 (mod P).
        cur *= a;
        cur %= P;
        
        // n が 見つかった.
        if(cur == 1){
            n = i;
            break;
        }
        
        // 保存.
        H.insert(cur);
    }
    
    // 3. b の 冪乗 が H に含まれる m.
    int m = -1;
    repx(i, 1, P){
        // b の 冪 (mod P).
        cur *= b;
        cur %= P;
        
        // n が 見つかった.
        if(H.count(cur)){
            m = i;
            break;
        }
    }
    
    // 5. 例外(ハミルトン閉路 が 存在しない).
    if((LL)(P - 1) != (LL)n * (LL)m){
        puts("No");
        return 0;
    }
    
    // 6. ハミルトン閉路となるか？
    auto isHamiltonianCycle = [&](vl &v) -> bool {
        // 6-1. A[1], A[P] が, いずれも 1 か？
        if(v[0] != 1 || v[P - 1] != 1) return false;
        
        // 6-2. A[1] ～ A[P - 1] は, 1, 2, ...., P - 1 の 並び替えか？
        int p[P];
        rep(i, P) p[i] = 0;
        rep(i, P - 1) ++p[(int)v[i]];
        repx(i, 1, P) if(p[i] != 1) return false;
        
        // 6-3. 2 ～ P の i で, 指定された合同式を満たしているか？
        bool ok = true;
        repx(i, 1, P - 1){
            if(v[i - 0] == v[i - 1] * a % P) continue;
            if(v[i - 1] == v[i - 0] * a % P) continue;
            if(v[i - 0] == v[i - 1] * b % P) continue;
            if(v[i - 1] == v[i - 0] * b % P) continue;
            ok = false;
        }
        
        // 6-4. 返却.
        return ok;
    };
    
    // 7. n, m が 1.
    // 7-1. n = 1.
    if(n == 1){
        vl ans;
        ans.pb(1);
        rep(i, P) ans.pb(ans.back() * b % P);
        assert(isHamiltonianCycle(ans));
        puts("Yes");
        rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");
        return 0;
    }
    
    // 7-2. m = 1.
    if(m == 1){
        vl ans;
        ans.pb(1);
        rep(i, P) ans.pb(ans.back() * a % P);
        assert(isHamiltonianCycle(ans));
        puts("Yes");
        rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");
        return 0;
    }
    
    // 8. n, m > 1.
    // 8-1. m が 偶数.
    if(!(m & 1)){
        vvl v(n, vl(m));
        v[0][0] = 1;
        repx(i, 1, n) v[i][0] = v[i - 1][0] * a % P;
        rep(i, n) repx(j, 1, m) v[i][j] = v[i][j - 1] * b % P;
        vl ans;
        ans.pb(v[0][0]);
        rep(j, m){
            if(j & 1) repr(i, n - 1, 1) ans.pb(v[i][j]);
            else      repx(i, 1, n)     ans.pb(v[i][j]);
        }
        repr(j, m - 1, 0) ans.pb(v[0][j]);
        assert(isHamiltonianCycle(ans));
        puts("Yes");
        rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");
        return 0;
    }
    
    // 8-2. n が 偶数.
    if(!(n & 1)){
        vvl v(m, vl(n));
        v[0][0] = 1;
        repx(i, 1, m) v[i][0] = v[i - 1][0] * b % P;
        rep(i, m) repx(j, 1, n) v[i][j] = v[i][j - 1] * a % P;
        vl ans;
        ans.pb(v[0][0]);
        rep(j, n){
            if(j & 1) repr(i, m - 1, 1) ans.pb(v[i][j]);
            else      repx(i, 1, m)     ans.pb(v[i][j]);
        }
        repr(j, n - 1, 0) ans.pb(v[0][j]);
        assert(isHamiltonianCycle(ans));
        puts("Yes");
        rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");
        return 0;
    }
    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

// 解き直し.

// https://atcoder.jp/contests/arc118/editorial/1210

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

int main(){

// 1. 入力情報.

int P;

LL a, b;

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

// 2. a の冪乗が 1 となる n.

int n = -1;

LL cur = 1;

set<LL> H;

H.insert(1);

repx(i, 1, P){

// a の冪 (mod P).

cur *= a;

cur %= P;

// n が見つかった.

if(cur == 1){

n = i;

break;

}

// 保存.

H.insert(cur);

}

// 3. b の冪乗が H に含まれる m.

int m = -1;

repx(i, 1, P){

// b の冪 (mod P).

cur *= b;

cur %= P;

// n が見つかった.

if(H.count(cur)){

m = i;

break;

}

// 5. 例外(ハミルトン閉路が存在しない).

if((LL)(P - 1) != (LL)n * (LL)m){

puts("No");

return 0;

}

// 6. ハミルトン閉路となるか？

auto isHamiltonianCycle = [&](vl &v) -> bool {

// 6-1. A[1], A[P] が, いずれも 1 か？

if(v[0] != 1 || v[P - 1] != 1) return false;

// 6-2. A[1] ～ A[P - 1] は, 1, 2, ...., P - 1 の並び替えか？

int p[P];

rep(i, P) p[i] = 0;

rep(i, P - 1) ++p[(int)v[i]];

repx(i, 1, P) if(p[i] != 1) return false;

// 6-3. 2 ～ P の i で, 指定された合同式を満たしているか？

bool ok = true;

repx(i, 1, P - 1){

if(v[i - 0] == v[i - 1] * a % P) continue;

if(v[i - 1] == v[i - 0] * a % P) continue;

if(v[i - 0] == v[i - 1] * b % P) continue;

if(v[i - 1] == v[i - 0] * b % P) continue;

ok = false;

}

// 6-4. 返却.

return ok;

};

// 7. n, m が 1.

// 7-1. n = 1.

if(n == 1){

vl ans;

ans.pb(1);

rep(i, P) ans.pb(ans.back() * b % P);

assert(isHamiltonianCycle(ans));

puts("Yes");

rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");

return 0;

}

// 7-2. m = 1.

if(m == 1){

vl ans;

ans.pb(1);

rep(i, P) ans.pb(ans.back() * a % P);

assert(isHamiltonianCycle(ans));

puts("Yes");

rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");

return 0;

}

// 8. n, m > 1.

// 8-1. m が偶数.

if(!(m & 1)){

vvl v(n, vl(m));

v[0][0] = 1;

repx(i, 1, n) v[i][0] = v[i - 1][0] * a % P;

rep(i, n) repx(j, 1, m) v[i][j] = v[i][j - 1] * b % P;

vl ans;

ans.pb(v[0][0]);

rep(j, m){

if(j & 1) repr(i, n - 1, 1) ans.pb(v[i][j]);

else repx(i, 1, n) ans.pb(v[i][j]);

}

repr(j, m - 1, 0) ans.pb(v[0][j]);

assert(isHamiltonianCycle(ans));

puts("Yes");

rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");

return 0;

}

// 8-2. n が偶数.

if(!(n & 1)){

vvl v(m, vl(n));

v[0][0] = 1;

repx(i, 1, m) v[i][0] = v[i - 1][0] * b % P;

rep(i, m) repx(j, 1, n) v[i][j] = v[i][j - 1] * a % P;

vl ans;

ans.pb(v[0][0]);

rep(j, n){

if(j & 1) repr(i, m - 1, 1) ans.pb(v[i][j]);

else repx(i, 1, m) ans.pb(v[i][j]);

}

repr(j, n - 1, 0) ans.pb(v[0][j]);

assert(isHamiltonianCycle(ans));

puts("Yes");

rep(i, P) printf("%d%s", ans[i], (i < P - 1) ? " " : "\n");

return 0;

}

return 0;

}

[入力例]
13 4 5

[出力例]
Yes
1 5 11 3 12 9 7 4 6 8 2 10 1
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
1 4 3 12 9 10 11 6 8 2 7 5 1

[入力例]
13 1 2

[出力例]
Yes
1 2 4 8 3 6 12 11 9 5 10 7 1
※AtCoderテストケースより

[入力例]
13 9 3

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

[入力例]
13 1 1

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

[入力例]
19 20 22

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

[入力例]
23 11 9

[出力例]
Yes
1 11 6 20 13 5 9 7 8 19 2 22 12 17 3 10 18 14 16 15 4 21 1

[入力例]
37 12 21

[出力例]
No

[入力例]
211 314 159

[出力例]
Yes
1 103 59 169 105 54 76 21 53 184 173 95 79 119 19 58 66 46 96 182 178 188 163 120 122 117 24 151 150 47 199 30 136 82 6 196 143 170 208 113 34 126 107 49 194 148 52 81 114 137 185 65 154 37 13 73 134 87 99 69 144 62 56 71 139 180 183 70 36 121 14 176 193 45 204 123 9 83 109 44 101 64 51 189 55 179 80 11 78 16 171 100 172 203 20 161 125 4 201 25 43 209 5 93 84 63 17 162 104 85 177 98 3 41 68 15 205 129 75 181 12 164 61 60 187 94 89 91 48 23 33 29 115 165 145 153 192 92 132 116 38 27 158 190 135 157 106 42 152 108 210 127 118 206 2 168 186 10 207 86 50 191 8 39 111 40 195 133 200 131 32 156 22 160 147 110 167 102 128 202 88 7 166 18 35 197 90 175 141 28 31 72 140 155 149 67 142 112 124 77 138 198 174 57 146 26 74 97 130 159 1

[入力例]

13 4 5

[出力例]

Yes

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

※AtCoderテストケースより

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

Yes

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

[入力例]

13 1 2

[出力例]

Yes

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

※AtCoderテストケースより

[入力例]

13 9 3

[出力例]

※AtCoderテストケースより

[入力例]

13 1 1

[出力例]

※AtCoderテストケースより

[入力例]

19 20 22

[出力例]

Yes

1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 1

[入力例]

23 11 9

[出力例]

Yes

1 11 6 20 13 5 9 7 8 19 2 22 12 17 3 10 18 14 16 15 4 21 1

[入力例]

37 12 21

[出力例]

[入力例]

211 314 159

[出力例]

Yes

1 103 59 169 105 54 76 21 53 184 173 95 79 119 19 58 66 46 96 182 178 188 163 120 122 117 24 151 150 47 199 30 136 82 6 196 143 170 208 113 34 126 107 49 194 148 52 81 114 137 185 65 154 37 13 73 134 87 99 69 144 62 56 71 139 180 183 70 36 121 14 176 193 45 204 123 9 83 109 44 101 64 51 189 55 179 80 11 78 16 171 100 172 203 20 161 125 4 201 25 43 209 5 93 84 63 17 162 104 85 177 98 3 41 68 15 205 129 75 181 12 164 61 60 187 94 89 91 48 23 33 29 115 165 145 153 192 92 132 116 38 27 158 190 135 157 106 42 152 108 210 127 118 206 2 168 186 10 207 86 50 191 8 39 111 40 195 133 200 131 32 156 22 160 147 110 167 102 128 202 88 7 166 18 35 197 90 175 141 28 31 72 140 155 149 67 142 112 124 77 138 198 174 57 146 26 74 97 130 159 1

■参照サイト
AtCoder Regular Contest 118

2022年11月6日

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題E (Non-coprime DAG) を解いてみた.

■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 解説のロジックで, 価値の総和としてあり得る最大値が計算されることが, 摩訶不思議な印象を受け, 非常に, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc136/editorial/3464
// 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 f[1010101], l[1010101], r[1010101];
LL a[1010101], b[2020202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. f を 計算.
    repx(i, 2, N + 1){
        if(!f[i]) repex(j, i, N + 1, i) if(!f[j]) f[j] = i;
    }
    
    // 3. l, r を 計算.
    repx(x, 2, N + 1){
        // 偶数.
        if(!(x & 1)){
            l[x] = x;
            r[x] = x + 1;
        }
        
        // 奇数.
        if(x & 1){
            l[x] = x - f[x] + 1;
            r[x] = x + f[x];
        }
    }
    
    // 4. いもす法.
    repx(i, 1, N){
        b[l[i + 1]] += a[i];
        b[r[i + 1]] -= a[i];
    }
    repx(i, 1, 2020202) b[i] += b[i - 1];
    
    // 5. 最大値は？
    LL ans = 0;
    repx(i, 1, N + 1) ans = max(ans, b[i]);
    
    // 6. 出力.
    printf("%lld\n", ans + a[0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc136/editorial/3464

// 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 f[1010101], l[1010101], r[1010101];

LL a[1010101], b[2020202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. f を計算.

repx(i, 2, N + 1){

if(!f[i]) repex(j, i, N + 1, i) if(!f[j]) f[j] = i;

}

// 3. l, r を計算.

repx(x, 2, N + 1){

// 偶数.

if(!(x & 1)){

l[x] = x;

r[x] = x + 1;

}

// 奇数.

if(x & 1){

l[x] = x - f[x] + 1;

r[x] = x + f[x];

}

// 4. いもす法.

repx(i, 1, N){

b[l[i + 1]] += a[i];

b[r[i + 1]] -= a[i];

}

repx(i, 1, 2020202) b[i] += b[i - 1];

// 5. 最大値は？

LL ans = 0;

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

// 6. 出力.

printf("%lld\n", ans + a[0]);

return 0;

}

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

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

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

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

[入力例]
20
40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

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

[入力例]
5
3 1 4 1 5

[出力例]
13

[入力例]
10
32 47 55 7 78 25 10 25 64 36

[出力例]
222

[入力例]
50
10896 8989 6913 7732 9901 1249 10000 8888 2983 11045 7840 9597 9781 4801 1762 4530 5819 4577 2222 3266 10833 9555 11111 5555 12391 7850 7623 333 1111 1563 3985 12212 10421 12455 9493 7819 5281 9997 10789 9611 454 5411 2364 3891 596 8919 3333 11085 7507 5555

[出力例]
100000

[入力例]

1 1 1 1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 1 3 1 6

[出力例]

※AtCoderのテストケースより

[入力例]

40 39 31 54 27 31 80 3 62 66 15 72 21 38 74 49 15 24 44 3

[出力例]

343

※AtCoderのテストケースより

[入力例]

3 1 4 1 5

[出力例]

[入力例]

32 47 55 7 78 25 10 25 64 36

[出力例]

222

[入力例]

10896 8989 6913 7732 9901 1249 10000 8888 2983 11045 7840 9597 9781 4801 1762 4530 5819 4577 2222 3266 10833 9555 11111 5555 12391 7850 7623 333 1111 1563 3985 12212 10421 12455 9493 7819 5281 9997 10789 9611 454 5411 2364 3891 596 8919 3333 11085 7507 5555

[出力例]

100000

■参照サイト
AtCoder Regular Contest 136

2022年11月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 114 の問題C (Sequence Scores) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc114/editorial/898
// 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 mPow[5050][5050];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 冪乗.
    rep(i, 5050) mPow[i][0] = 1;
    repx(i, 1, 5050) repx(j, 1, 5050) mPow[i][j] = mPow[i][j - 1] * i % MOD;
    
    // 3. 集計.
    // 3-1. 全ての和.
    LL ans = N;
    rep(i, N) ans = ans * M % MOD;
    
    // 3-2. 減算.
    repx(k, 1, N){
        // i - j = k と 置いたときに, 
        // (k, 0), (k + 1, 1), (k + 2, 2), ..., (N - 1, N - k - 1) の (N - k) 通りと, 
        // 0 の (k - 1)乗, ..., (M - 1) の (k - 1)乗 の 合計 に対する積を, 減算.
        LL cur = 0;
        repx(x, 1, M + 1) cur = (cur + mPow[M - x][k - 1]) % MOD;
        cur = cur * mPow[M][N - k - 1] % MOD * (N - k) % MOD;
        ans = (ans + MOD - cur) % MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc114/editorial/898

// 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 mPow[5050][5050];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 冪乗.

rep(i, 5050) mPow[i][0] = 1;

repx(i, 1, 5050) repx(j, 1, 5050) mPow[i][j] = mPow[i][j - 1] * i % MOD;

// 3. 集計.

// 3-1. 全ての和.

LL ans = N;

rep(i, N) ans = ans * M % MOD;

// 3-2. 減算.

repx(k, 1, N){

// i - j = k と置いたときに,

// (k, 0), (k + 1, 1), (k + 2, 2), ..., (N - 1, N - k - 1) の (N - k) 通りと,

// 0 の (k - 1)乗, ..., (M - 1) の (k - 1)乗の合計に対する積を, 減算.

LL cur = 0;

repx(x, 1, M + 1) cur = (cur + mPow[M - x][k - 1]) % MOD;

cur = cur * mPow[M][N - k - 1] % MOD * (N - k) % MOD;

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

}

// 4. 出力.

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

return 0;

}

[入力例]
2 3

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

[入力例]
3 2

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

[入力例]
34 56

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

[入力例]
1 2

[出力例]
2

[入力例]
3 5

[出力例]
315

[入力例]
20 22

[出力例]
52764907

[入力例]
2022 1105

[出力例]
815162723

[入力例]

2 3

[出力例]

※AtCoderのテストケースより

[入力例]

3 2

[出力例]

※AtCoderのテストケースより

[入力例]

34 56

[出力例]

649717324

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

[入力例]

3 5

[出力例]

315

[入力例]

20 22

[出力例]

52764907

[入力例]

2022 1105

[出力例]

815162723

■参照サイト
AtCoder Regular Contest 114

2022年11月5日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc244/editorial/3601
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 998244353;
LL dp[2020][2020][2];

int main(){
    
    // 1. 入力情報.
    int N, M, K, S, T, X;
    scanf("%d %d %d %d %d %d", &N, &M, &K, &S, &T, &X);
    --S, --T, --X;
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u, --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. dp更新.
    dp[0][S][0] = 1;
    rep(i, K){
        // 辺 (u, v) に 関して, 更新.
        rep(u, N){
            for(auto &v : G[u]){
                // 隣接頂点 v が, 頂点 X の 場合.
                if(v == X){
                    dp[i + 1][v][0] += dp[i][u][1];
                    dp[i + 1][v][0] %= MOD;
                    dp[i + 1][v][1] += dp[i][u][0];
                    dp[i + 1][v][1] %= MOD;
                }
                
                // 隣接頂点 v が, 頂点 X でない 場合.
                if(v != X){
                    dp[i + 1][v][0] += dp[i][u][0];
                    dp[i + 1][v][0] %= MOD;
                    dp[i + 1][v][1] += dp[i][u][1];
                    dp[i + 1][v][1] %= MOD;
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[K][T][0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc244/editorial/3601

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using LL = long long;

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

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

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

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

#define pb push_back

const LL MOD = 998244353;

LL dp[2020][2020][2];

int main(){

// 1. 入力情報.

int N, M, K, S, T, X;

scanf("%d %d %d %d %d %d", &N, &M, &K, &S, &T, &X);

--S, --T, --X;

vvi G(N);

rep(i, M){

int u, v;

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

--u, --v;

G[u].pb(v);

G[v].pb(u);

}

// 2. dp更新.

dp[0][S][0] = 1;

rep(i, K){

// 辺 (u, v) に関して, 更新.

rep(u, N){

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

// 隣接頂点 v が, 頂点 X の場合.

if(v == X){

dp[i + 1][v][0] += dp[i][u][1];

dp[i + 1][v][0] %= MOD;

dp[i + 1][v][1] += dp[i][u][0];

dp[i + 1][v][1] %= MOD;

}

// 隣接頂点 v が, 頂点 X でない場合.

if(v != X){

dp[i + 1][v][0] += dp[i][u][0];

dp[i + 1][v][0] %= MOD;

dp[i + 1][v][1] += dp[i][u][1];

dp[i + 1][v][1] %= MOD;

}

// 3. 出力.

printf("%lld\n", dp[K][T][0]);

return 0;

}

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

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

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

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

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

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

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

[出力例]
1

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

[出力例]
5

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

[出力例]
38

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

[出力例]
36371

[入力例]

4 4 4 1 3 2

1 2

2 3

3 4

1 4

[出力例]

※AtCoderテストケースより

[入力例]

6 5 10 1 2 3

2 3

2 4

4 6

3 6

1 5

[出力例]

※AtCoderテストケースより

[入力例]

10 15 20 4 4 6

2 6

2 7

5 7

4 5

2 4

3 7

1 7

1 4

2 9

5 10

1 3

7 8

7 9

1 6

1 2

[出力例]

952504739

※AtCoderテストケースより

[入力例]

3 3 3 1 2 3

1 2

2 3

1 3

[出力例]

[入力例]

5 5 5 2 1 3

1 3

2 3

3 5

2 5

2 4

[出力例]

[入力例]

7 10 6 1 5 7

1 3

2 3

3 4

2 4

4 5

2 5

5 6

2 6

6 7

3 7

[出力例]

[入力例]

11 12 15 2 3 5

1 8

2 8

8 10

9 10

10 11

2 11

6 11

2 7

3 7

4 7

4 6

5 6

[出力例]

36371

■参照サイト
AtCoder Beginner Contest 244

2022年11月3日2022年11月3日

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題C (Circular Addition) ～問題D (Without Carry) を解いてみた.

■感想.
1. 問題C, D は, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. なお, 問題D は, dominate と繰り上がりとの関係性が理解しずらかったため, 実装後に, 解説プログラムを確認し, 実装誤り部分を修正して(特に, 重複カウント部分の減算に関する処理と思われる箇所), 提出した版である.
3. 問題D で, 高速ゼータ変換に関する考え方に触れることが出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc136/editorial/3466
// 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 a[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. M, D を 計算.
    LL M = 0, D = 0;
    rep(i, N){
        M = max(M, a[i]);
        if(i < N - 1) D += abs(a[i] - a[i + 1]);
        else          D += abs(a[0] - a[N - 1]);
    }
    D /= 2;
    
    // 3. 出力.
    printf("%lld\n", max(M, D));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc136/editorial/3466

// 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 a[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. M, D を計算.

LL M = 0, D = 0;

rep(i, N){

M = max(M, a[i]);

if(i < N - 1) D += abs(a[i] - a[i + 1]);

else D += abs(a[0] - a[N - 1]);

}

D /= 2;

// 3. 出力.

printf("%lld\n", max(M, D));

return 0;

}

[入力例]
4
1 2 1 2

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

[入力例]
5
3 1 4 1 5

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

[入力例]
1
1000000000

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

[入力例]
10
71 102 33 82 29 64 94 56 50 105

[出力例]
200

[入力例]
100
777 778 255 1899 1530 269 1878 1515 963 1701 369 1654 634 1195 911 860 1184 1011 1089 425 1927 1019 1562 1709 1766 1119 820 1878 1972 867 1266 1819 299 305 160 1843 1016 595 27 1226 922 172 1123 867 7 1475 632 739 492 347 493 998 535 898 1241 764 1358 129 189 277 1905 215 841 2000 1206 1431 439 1974 1543 710 517 941 359 1033 564 487 5 1030 320 671 1113 1956 774 54 1424 895 303 771 632 780 363 1890 320 137 656 1320 281 1318 1880 998

[出力例]
33333

[入力例]

1 2 1 2

[出力例]

※AtCoderのテストケースより

[入力例]

3 1 4 1 5

[出力例]

※AtCoderのテストケースより

[入力例]

1000000000

[出力例]

1000000000

※AtCoderのテストケースより

[入力例]

71 102 33 82 29 64 94 56 50 105

[出力例]

200

[入力例]

100

777 778 255 1899 1530 269 1878 1515 963 1701 369 1654 634 1195 911 860 1184 1011 1089 425 1927 1019 1562 1709 1766 1119 820 1878 1972 867 1266 1819 299 305 160 1843 1016 595 27 1226 922 172 1123 867 7 1475 632 739 492 347 493 998 535 898 1241 764 1358 129 189 277 1905 215 841 2000 1206 1431 439 1974 1543 710 517 941 359 1033 564 487 5 1030 320 671 1113 1956 774 54 1424 895 303 771 632 780 363 1890 320 137 656 1320 281 1318 1880 998

[出力例]

33333

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

// 解き直し.
// https://atcoder.jp/contests/arc136/editorial/3465
// 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
int a[1010101];
LL dp[2020202];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 10 の 冪乗.
    int L = 6;
    vi cPow10;
    cPow10.pb(1);
    while(cPow10.size() <= L) cPow10.pb(10 * cPow10.back());
    
    // 3. dp更新.
    // -> 各a[i] を起点として, dominate に関する情報を, dp更新式で, 集計.
    rep(i, N) ++dp[a[i]];
    rep(j, L){
        rep(i, cPow10[L]){
            int q = i / cPow10[j];
            int r = q % 10;
            if(r < 9) dp[i + cPow10[j]] += dp[i];
        }
    }
    
    // 4. 集計.
    // 以下の解説プログラム参照.
    // https://atcoder.jp/contests/arc136/submissions/29411459
    LL ans = 0;
    rep(i, N){
        // Skip.
        if(!dp[cPow10[L] - 1 - a[i]]) continue;
        
        // 加算(dominate の 集計結果).
        // -> 各a[i] について, dp から 繰り上がりしているかどうかを見る場合は, 
        //    dominate の 考え方に基づいて, cPow10[L] - 1 - a[i] から, 判断する点に注意.
        ans += dp[cPow10[L] - 1 - a[i]];
        
        // 繰り上がりしているか否か.
        int q = a[i];
        bool ok = false;
        rep(j, L){
            int r = q % 10;
            if(r >= 5) ok = true;
            q /= 10;
        }
        
        // 減算(おそらく, 繰り上がりして "いない" ケースは, 重複で数えていると解釈するらしい).
        if(!ok) --ans;
    }
    
    // 5. 出力.
    printf("%lld\n", ans / 2);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc136/editorial/3465

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

int a[1010101];

LL dp[2020202];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 10 の冪乗.

int L = 6;

vi cPow10;

cPow10.pb(1);

while(cPow10.size() <= L) cPow10.pb(10 * cPow10.back());

// 3. dp更新.

// -> 各a[i] を起点として, dominate に関する情報を, dp更新式で, 集計.

rep(i, N) ++dp[a[i]];

rep(j, L){

rep(i, cPow10[L]){

int q = i / cPow10[j];

int r = q % 10;

if(r < 9) dp[i + cPow10[j]] += dp[i];

}

// 4. 集計.

// 以下の解説プログラム参照.

// https://atcoder.jp/contests/arc136/submissions/29411459

LL ans = 0;

rep(i, N){

// Skip.

if(!dp[cPow10[L] - 1 - a[i]]) continue;

// 加算(dominate の集計結果).

// -> 各a[i] について, dp から繰り上がりしているかどうかを見る場合は,

// dominate の考え方に基づいて, cPow10[L] - 1 - a[i] から, 判断する点に注意.

ans += dp[cPow10[L] - 1 - a[i]];

// 繰り上がりしているか否か.

int q = a[i];

bool ok = false;

rep(j, L){

int r = q % 10;

if(r >= 5) ok = true;

q /= 10;

}

// 減算(おそらく, 繰り上がりして "いない" ケースは, 重複で数えていると解釈するらしい).

if(!ok) --ans;

}

// 5. 出力.

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

return 0;

}

[入力例]
4
4 8 12 90

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

[入力例]
20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

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

[入力例]
5
1 1 1 1 1

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

[入力例]
10
12 15 28 30 33 47 52 61 72 81

[出力例]
23

[入力例]
50
73 2 99 15 24 117 115 104 104 90 28 36 83 5 35 115 32 49 20 90 80 25 37 95 98 112 93 3 92 8 72 21 90 118 106 17 98 88 40 46 59 83 85 6 25 64 18 54 119 78

[出力例]
334

[入力例]
300
77777 100191 3141 72381 88888 89264 112738 18295 99999 74111 111111 56267 15131 59124 29354 50538 15200 118291 106621 6954 64325 19574 87600 101010 101010 91749 24130 99999 16645 42360 97636 53268 19981 7983 112934 16693 111111 53051 35741 95710 108291 48780 92605 69904 117734 96974 18803 27990 30856 55295 26860 19664 39658 102350 60830 22358 54462 57928 95038 101010 21238 65826 21844 35987 8759 79919 58382 98650 121756 94754 90627 59551 46070 57713 62686 95762 13580 49759 85685 53493 97168 18566 24523 54415 97632 76598 26417 74914 32918 68505 84746 115100 78161 93752 55606 93493 9142 73351 107531 101010 28262 67198 114766 96968 11472 61629 79328 120269 71342 42949 85685 9954 88888 81691 106340 79492 94133 98212 3218 71808 18202 101010 94154 105925 57115 14174 20327 37548 23723 51748 41437 75163 59384 55886 62085 12030 72110 40612 104190 8632 101010 61313 77777 85724 86475 37230 88888 25160 1894 58666 95972 106212 114828 89842 77539 14728 96997 111254 5480 96808 94846 121364 33333 72941 59833 39288 82818 89814 54956 24421 15098 111111 79408 111111 74272 115159 121188 118736 18120 25301 28807 23059 12232 101492 88888 99999 74435 37640 18807 66924 72570 106351 111111 11578 37304 47366 106791 12098 51621 120445 21618 50865 87371 37123 99999 42850 90816 40761 16328 87966 66391 66073 41298 99996 12674 20953 82396 53977 19794 101010 31303 107657 88888 115737 75017 28616 77777 93695 106440 102631 115693 22015 40374 17325 32202 112271 27818 23076 13804 59979 53090 68177 91002 88104 4519 30863 106347 56756 81872 70403 37573 101010 101010 81003 63251 66193 47642 26479 50171 121360 97946 64862 121158 72978 32948 27493 89543 23379 771 112381 105968 113218 37324 15276 39985 2700 34627 94999 47999 19957 119916 99999 118865 68160 50445 77777 13770 11611 71834 77777 88888 95468 20369 46059 105334 101010 70265 22222 101010 82059

[出力例]
5602

[入力例]

4 8 12 90

[出力例]

※AtCoderのテストケースより

[入力例]

313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

12 15 28 30 33 47 52 61 72 81

[出力例]

[入力例]

73 2 99 15 24 117 115 104 104 90 28 36 83 5 35 115 32 49 20 90 80 25 37 95 98 112 93 3 92 8 72 21 90 118 106 17 98 88 40 46 59 83 85 6 25 64 18 54 119 78

[出力例]

334

[入力例]

300

77777 100191 3141 72381 88888 89264 112738 18295 99999 74111 111111 56267 15131 59124 29354 50538 15200 118291 106621 6954 64325 19574 87600 101010 101010 91749 24130 99999 16645 42360 97636 53268 19981 7983 112934 16693 111111 53051 35741 95710 108291 48780 92605 69904 117734 96974 18803 27990 30856 55295 26860 19664 39658 102350 60830 22358 54462 57928 95038 101010 21238 65826 21844 35987 8759 79919 58382 98650 121756 94754 90627 59551 46070 57713 62686 95762 13580 49759 85685 53493 97168 18566 24523 54415 97632 76598 26417 74914 32918 68505 84746 115100 78161 93752 55606 93493 9142 73351 107531 101010 28262 67198 114766 96968 11472 61629 79328 120269 71342 42949 85685 9954 88888 81691 106340 79492 94133 98212 3218 71808 18202 101010 94154 105925 57115 14174 20327 37548 23723 51748 41437 75163 59384 55886 62085 12030 72110 40612 104190 8632 101010 61313 77777 85724 86475 37230 88888 25160 1894 58666 95972 106212 114828 89842 77539 14728 96997 111254 5480 96808 94846 121364 33333 72941 59833 39288 82818 89814 54956 24421 15098 111111 79408 111111 74272 115159 121188 118736 18120 25301 28807 23059 12232 101492 88888 99999 74435 37640 18807 66924 72570 106351 111111 11578 37304 47366 106791 12098 51621 120445 21618 50865 87371 37123 99999 42850 90816 40761 16328 87966 66391 66073 41298 99996 12674 20953 82396 53977 19794 101010 31303 107657 88888 115737 75017 28616 77777 93695 106440 102631 115693 22015 40374 17325 32202 112271 27818 23076 13804 59979 53090 68177 91002 88104 4519 30863 106347 56756 81872 70403 37573 101010 101010 81003 63251 66193 47642 26479 50171 121360 97946 64862 121158 72978 32948 27493 89543 23379 771 112381 105968 113218 37324 15276 39985 2700 34627 94999 47999 19957 119916 99999 118865 68160 50445 77777 13770 11611 71834 77777 88888 95468 20369 46059 105334 101010 70265 22222 101010 82059

[出力例]

5602

■参照サイト
AtCoder Regular Contest 136

2022年11月2日2022年11月2日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考にして, ようやく, AC版に到達出来た.
2. 個人的には, 解説にあるように, 木の性質を利用したロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc273/editorial/5023
// 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 o[505050]; // 各頂点に書き込まれた整数.
int p[505050]; // 親頂点.

int main(){
    
    // 1. 入力情報.
    int Q;
    scanf("%d", &Q);
    
    // 2. クエリ回答.
    int cur = 0, v = 0;
    map<int, int> n;
    o[cur] = -1;
    rep(i, Q){
        // クエリ入力情報.
        char c[11];
        scanf("%s", c);
        string q(c);
        
        // ADD.
        if(q == "ADD"){
            // 整数 x.
            int x;
            scanf("%d", &x);
            
            // 頂点を追加.
            ++v;
            
            // 頂点の親子関係を保存.
            p[v] = cur;
            o[v] = x;
            cur = v;
        }
        
        // DELETE.
        if(q == "DELETE"){
            // 親頂点に移動.
            cur = p[cur];
        }
        
        // SAVE.
        if(q == "SAVE"){
            // 整数 y.
            int y;
            scanf("%d", &y);
            
            // 現在コマがある頂点を保存.
            n[y] = cur;
        }
        
        // LOAD.
        if(q == "LOAD"){
            // 整数 z.
            int z;
            scanf("%d", &z);
            
            // ノート の z ページ目を参照し, 移動.
            cur = n[z];
        }
        
        // 出力.
        printf("%d%s", o[cur], (i < Q - 1) ? " " : "\n");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc273/editorial/5023

// 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 o[505050]; // 各頂点に書き込まれた整数.

int p[505050]; // 親頂点.

int main(){

// 1. 入力情報.

int Q;

scanf("%d", &Q);

// 2. クエリ回答.

int cur = 0, v = 0;

map<int, int> n;

o[cur] = -1;

rep(i, Q){

// クエリ入力情報.

char c[11];

scanf("%s", c);

string q(c);

// ADD.

if(q == "ADD"){

// 整数 x.

int x;

scanf("%d", &x);

// 頂点を追加.

++v;

// 頂点の親子関係を保存.

p[v] = cur;

o[v] = x;

cur = v;

}

// DELETE.

if(q == "DELETE"){

// 親頂点に移動.

cur = p[cur];

}

// SAVE.

if(q == "SAVE"){

// 整数 y.

int y;

scanf("%d", &y);

// 現在コマがある頂点を保存.

n[y] = cur;

}

// LOAD.

if(q == "LOAD"){

// 整数 z.

int z;

scanf("%d", &z);

// ノートの z ページ目を参照し, 移動.

cur = n[z];

}

// 出力.

printf("%d%s", o[cur], (i < Q - 1) ? " " : "\n");

}

return 0;

}

[入力例]
11
ADD 3
SAVE 1
ADD 4
SAVE 2
LOAD 1
DELETE
DELETE
LOAD 2
SAVE 1
LOAD 3
LOAD 1

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

[入力例]
21
ADD 4
ADD 3
DELETE
ADD 10
LOAD 7
SAVE 5
SAVE 5
ADD 4
ADD 4
ADD 5
SAVE 5
ADD 2
DELETE
ADD 1
SAVE 5
ADD 7
ADD 8
DELETE
ADD 4
DELETE
LOAD 5

[出力例]
4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1
※AtCoderテストケースより

[入力例]
5
ADD 2
SAVE 3
DELETE
LOAD 3
ADD 3

[出力例]
2 2 -1 2 3

[入力例]
50
ADD 15
ADD 10
LOAD 15
ADD 19
LOAD 1
SAVE 5
DELETE
ADD 20
LOAD 5
ADD 13
LOAD 19
SAVE 7
ADD 22
ADD 11
ADD 4
SAVE 18
ADD 6
SAVE 10
LOAD 16
LOAD 5
ADD 1
ADD 15
ADD 19
ADD 3
SAVE 12
ADD 7
DELETE
LOAD 10
SAVE 10
ADD 7
DELETE
ADD 18
SAVE 5
ADD 1
SAVE 5
LOAD 10
ADD 15
DELETE
ADD 23
LOAD 5
DELETE
SAVE 10
ADD 9
ADD 7
SAVE 15
ADD 25
LOAD 5
DELETE
SAVE 14
ADD 7

[出力例]
15 10 -1 19 -1 -1 -1 20 -1 13 -1 -1 22 11 4 4 6 6 -1 -1 1 15 19 3 3 7 3 6 6 7 6 18 18 1 1 6 15 6 23 1 18 18 9 7 7 25 1 18 18 7

[入力例]
100
ADD 6
LOAD 9
SAVE 3
ADD 27
LOAD 3
DELETE
ADD 7
ADD 7
DELETE
SAVE 3
ADD 9
SAVE 28
LOAD 19
DELETE
LOAD 16
ADD 24
SAVE 20
ADD 18
ADD 77
SAVE 10
LOAD 12
ADD 30
SAVE 15
ADD 16
SAVE 4
ADD 77
ADD 55
ADD 777
LOAD 8
ADD 10
LOAD 10
LOAD 25
ADD 88
DELETE
ADD 77
DELETE
ADD 77
SAVE 23
ADD 66
LOAD 25
ADD 27
ADD 111
LOAD 8
DELETE
ADD 500
DELETE
SAVE 18
SAVE 4
SAVE 3
SAVE 13
DELETE
LOAD 28
SAVE 18
LOAD 2
LOAD 19
ADD 6
LOAD 27
ADD 3
DELETE
ADD 123
ADD 3
SAVE 18
ADD 4
SAVE 25
DELETE
ADD 8
ADD 17
SAVE 19
SAVE 25
DELETE
SAVE 17
LOAD 25
LOAD 20
DELETE
SAVE 8
ADD 27
LOAD 14
LOAD 11
ADD 8
ADD 111
SAVE 29
LOAD 1
LOAD 14
ADD 22
SAVE 26
SAVE 18
ADD 77
SAVE 8
LOAD 5
SAVE 20
ADD 20
SAVE 9
ADD 8
SAVE 23
LOAD 28
DELETE
LOAD 18
ADD 11
SAVE 16
ADD 77

[出力例]
6 -1 -1 27 -1 -1 7 7 7 7 9 9 -1 -1 -1 24 24 18 77 77 -1 30 30 16 16 77 55 777 -1 10 77 -1 88 -1 77 -1 77 77 66 -1 27 111 -1 -1 500 -1 -1 -1 -1 -1 -1 9 9 -1 -1 6 -1 3 -1 123 3 3 4 4 3 8 17 17 17 8 8 17 24 -1 -1 27 -1 -1 8 111 111 -1 -1 22 22 22 77 77 -1 -1 20 20 8 8 9 7 22 11 11 77

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

[入力例]

ADD 3

SAVE 1

ADD 4

SAVE 2

LOAD 1

DELETE

LOAD 2

SAVE 1

LOAD 3

LOAD 1

[出力例]

3 3 4 4 3 -1 -1 4 4 -1 4

※AtCoderテストケースより

[入力例]

ADD 4

ADD 3

DELETE

ADD 10

LOAD 7

SAVE 5

ADD 4

ADD 5

SAVE 5

ADD 2

DELETE

ADD 1

SAVE 5

ADD 7

ADD 8

DELETE

ADD 4

DELETE

LOAD 5

[出力例]

4 3 4 10 -1 -1 -1 4 4 5 5 2 5 1 1 7 8 7 4 7 1

※AtCoderテストケースより

[入力例]

ADD 2

SAVE 3

DELETE

LOAD 3

ADD 3

[出力例]

2 2 -1 2 3

[入力例]

ADD 15

ADD 10

LOAD 15

ADD 19

LOAD 1

SAVE 5

DELETE

ADD 20

LOAD 5

ADD 13

LOAD 19

SAVE 7

ADD 22

ADD 11

ADD 4

SAVE 18

ADD 6

SAVE 10

LOAD 16

LOAD 5

ADD 1

ADD 15

ADD 19

ADD 3

SAVE 12

ADD 7

DELETE

LOAD 10

SAVE 10

ADD 7

DELETE

ADD 18

SAVE 5

ADD 1

SAVE 5

LOAD 10

ADD 15

DELETE

ADD 23

LOAD 5

DELETE

SAVE 10

ADD 9

ADD 7

SAVE 15

ADD 25

LOAD 5

DELETE

SAVE 14

ADD 7

[出力例]

15 10 -1 19 -1 -1 -1 20 -1 13 -1 -1 22 11 4 4 6 6 -1 -1 1 15 19 3 3 7 3 6 6 7 6 18 18 1 1 6 15 6 23 1 18 18 9 7 7 25 1 18 18 7

[入力例]

100

ADD 6

LOAD 9

SAVE 3

ADD 27

LOAD 3

DELETE

ADD 7

DELETE

SAVE 3

ADD 9

SAVE 28

LOAD 19

DELETE

LOAD 16

ADD 24

SAVE 20

ADD 18

ADD 77

SAVE 10

LOAD 12

ADD 30

SAVE 15

ADD 16

SAVE 4

ADD 77

ADD 55

ADD 777

LOAD 8

ADD 10

LOAD 10

LOAD 25

ADD 88

DELETE

ADD 77

DELETE

ADD 77

SAVE 23

ADD 66

LOAD 25

ADD 27

ADD 111

LOAD 8

DELETE

ADD 500

DELETE

SAVE 18

SAVE 4

SAVE 3

SAVE 13

DELETE

LOAD 28

SAVE 18

LOAD 2

LOAD 19

ADD 6

LOAD 27

ADD 3

DELETE

ADD 123

ADD 3

SAVE 18

ADD 4

SAVE 25

DELETE

ADD 8

ADD 17

SAVE 19

SAVE 25

DELETE

SAVE 17

LOAD 25

LOAD 20

DELETE

SAVE 8

ADD 27

LOAD 14

LOAD 11

ADD 8

ADD 111

SAVE 29

LOAD 1

LOAD 14

ADD 22

SAVE 26

SAVE 18

ADD 77

SAVE 8

LOAD 5

SAVE 20

ADD 20

SAVE 9

ADD 8

SAVE 23

LOAD 28

DELETE

LOAD 18

ADD 11

SAVE 16

ADD 77

[出力例]

6 -1 -1 27 -1 -1 7 7 7 7 9 9 -1 -1 -1 24 24 18 77 77 -1 30 30 16 16 77 55 777 -1 10 77 -1 88 -1 77 -1 77 77 66 -1 27 111 -1 -1 500 -1 -1 -1 -1 -1 -1 9 9 -1 -1 6 -1 3 -1 123 3 3 4 4 3 8 17 17 17 8 8 17 24 -1 -1 27 -1 -1 8 111 111 -1 -1 22 22 22 77 77 -1 -1 20 20 8 8 9 7 22 11 11 77

■参照サイト
パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）

2022年11月2日2022年11月2日

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

C++の練習を兼ねて, AtCoder Beginner Contest 273 の問題C ((K+1)-th Largest Number) ～問題D (LRUD Instructions) を解いてみた.

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

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

■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--)
#define a first
#define b second
int a[202020], b[202020], ans[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    map<int, int> o;
    rep(i, N){
        scanf("%d", &a[i]);
        o[a[i]] = 0;
    }
    
    // 2. 座標圧縮.
    int idx = 0;
    for(auto &p : o) p.b = ++idx;
    
    // 3. 種類数.
    rep(i, N) b[i] = idx - o[a[i]];
    rep(i, N) ++ans[b[i]];
    
    // 4. 出力.
    rep(i, N) printf("%d\n", ans[i]);
    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--)

#define a first

#define b second

int a[202020], b[202020], ans[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

map<int, int> o;

rep(i, N){

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

o[a[i]] = 0;

}

// 2. 座標圧縮.

int idx = 0;

for(auto &p : o) p.b = ++idx;

// 3. 種類数.

rep(i, N) b[i] = idx - o[a[i]];

rep(i, N) ++ans[b[i]];

// 4. 出力.

rep(i, N) printf("%d\n", ans[i]);

return 0;

}

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

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

[入力例]
1
1

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

[入力例]
10
979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

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

[入力例]
10
1234 1233 1234 1235 1234 1233 1235 1235 1236 1232

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

[入力例]
30
12 13 7 2 3 14 6 10 9 13 3 2 12 1 9 3 11 15 13 9 3 6 2 1 14 12 9 1 8 1

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

[入力例]

2 7 1 8 2 8

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

979861204 57882493 979861204 447672230 644706927 710511029 763027379 710511029 447672230 136397527

[出力例]

※AtCoderテストケースより

[入力例]

1234 1233 1234 1235 1234 1233 1235 1235 1236 1232

[出力例]

[入力例]

12 13 7 2 3 14 6 10 9 13 3 2 12 1 9 3 11 15 13 9 3 6 2 1 14 12 9 1 8 1

[出力例]

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

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

int main(){
    
    // 1. 入力情報.
    int H, W, rs, cs, N;
    scanf("%d %d %d %d %d", &H, &W, &rs, &cs, &N);
    vp v(N);
    map<int, int> mr, mc;
    rep(i, N){
        scanf("%d %d", &v[i].a, &v[i].b);
        mr[v[i].a] = 0;
        mc[v[i].b] = 0;
    }
    
    // 2. 座標圧縮.
    // 2-1. 行方向.
    int rIdx = -1;
    for(auto &p : mr) p.b = ++rIdx;
    
    // 2-2. 列方向.
    int cIdx = -1;
    for(auto &p : mc) p.b = ++cIdx;
    
    // 3. 壁情報.
    vvi gr(rIdx + 1), gc(cIdx + 1);
    rep(i, N){
        gr[mr[v[i].a]].pb(v[i].b);
        gc[mc[v[i].b]].pb(v[i].a);
    }
    
    // 4. sort.
    // 4-1. 行方向.
    rep(i, rIdx + 1){
        gr[i].pb(0);
        gr[i].pb(W + 1);
        sort(all(gr[i]));
    }
    
    // 4-2. 列方向.
    rep(i, cIdx + 1){
        gc[i].pb(0);
        gc[i].pb(H + 1);
        sort(all(gc[i]));
    }
    
    // 5. クエリ回答.
    int Q;
    scanf("%d", &Q);
    P cur = {rs, cs};
    rep(i, Q){
        // クエリ入力情報.
        char d[11];
        int l;
        scanf("%s %d", d, &l);
        
        // 上.
        if(d[0] == 'U'){
            if(mc.count(cur.b)){
                int rAt = lower_bound(all(gc[mc[cur.b]]), cur.a) - gc[mc[cur.b]].begin();
                --rAt;
                cur.a = max(gc[mc[cur.b]][rAt] + 1, cur.a - l);
            }else{
                cur.a = max(1, cur.a - l);
            }
        }
        
        // 下.
        if(d[0] == 'D'){
            if(mc.count(cur.b)){
                int rAt = lower_bound(all(gc[mc[cur.b]]), cur.a) - gc[mc[cur.b]].begin();
                cur.a = min(gc[mc[cur.b]][rAt] - 1, cur.a + l);
            }else{
                cur.a = min(H, cur.a + l);
            }
        }
        
        // 左.
        if(d[0] == 'L'){
            if(mr.count(cur.a)){
                int cAt = lower_bound(all(gr[mr[cur.a]]), cur.b) - gr[mr[cur.a]].begin();
                --cAt;
                cur.b = max(gr[mr[cur.a]][cAt] + 1, cur.b - l);
            }else{
                cur.b = max(1, cur.b - l);
            }
        }
        
        // 右.
        if(d[0] == 'R'){
            if(mr.count(cur.a)){
                int cAt = lower_bound(all(gr[mr[cur.a]]), cur.b) - gr[mr[cur.a]].begin();
                cur.b = min(gr[mr[cur.a]][cAt] - 1, cur.b + l);
            }else{
                cur.b = min(W, cur.b + l);
            }
        }
        
        // 出力.
        printf("%d %d\n", cur.a, cur.b);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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 pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int H, W, rs, cs, N;

scanf("%d %d %d %d %d", &H, &W, &rs, &cs, &N);

vp v(N);

map<int, int> mr, mc;

rep(i, N){

scanf("%d %d", &v[i].a, &v[i].b);

mr[v[i].a] = 0;

mc[v[i].b] = 0;

}

// 2. 座標圧縮.

// 2-1. 行方向.

int rIdx = -1;

for(auto &p : mr) p.b = ++rIdx;

// 2-2. 列方向.

int cIdx = -1;

for(auto &p : mc) p.b = ++cIdx;

// 3. 壁情報.

vvi gr(rIdx + 1), gc(cIdx + 1);

rep(i, N){

gr[mr[v[i].a]].pb(v[i].b);

gc[mc[v[i].b]].pb(v[i].a);

}

// 4. sort.

// 4-1. 行方向.

rep(i, rIdx + 1){

gr[i].pb(0);

gr[i].pb(W + 1);

sort(all(gr[i]));

}

// 4-2. 列方向.

rep(i, cIdx + 1){

gc[i].pb(0);

gc[i].pb(H + 1);

sort(all(gc[i]));

}

// 5. クエリ回答.

int Q;

scanf("%d", &Q);

P cur = {rs, cs};

rep(i, Q){

// クエリ入力情報.

char d[11];

int l;

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

// 上.

if(d[0] == 'U'){

if(mc.count(cur.b)){

int rAt = lower_bound(all(gc[mc[cur.b]]), cur.a) - gc[mc[cur.b]].begin();

--rAt;

cur.a = max(gc[mc[cur.b]][rAt] + 1, cur.a - l);

}else{

cur.a = max(1, cur.a - l);

}

// 下.

if(d[0] == 'D'){

if(mc.count(cur.b)){

int rAt = lower_bound(all(gc[mc[cur.b]]), cur.a) - gc[mc[cur.b]].begin();

cur.a = min(gc[mc[cur.b]][rAt] - 1, cur.a + l);

}else{

cur.a = min(H, cur.a + l);

}

// 左.

if(d[0] == 'L'){

if(mr.count(cur.a)){

int cAt = lower_bound(all(gr[mr[cur.a]]), cur.b) - gr[mr[cur.a]].begin();

--cAt;

cur.b = max(gr[mr[cur.a]][cAt] + 1, cur.b - l);

}else{

cur.b = max(1, cur.b - l);

}

// 右.

if(d[0] == 'R'){

if(mr.count(cur.a)){

int cAt = lower_bound(all(gr[mr[cur.a]]), cur.b) - gr[mr[cur.a]].begin();

cur.b = min(gr[mr[cur.a]][cAt] - 1, cur.b + l);

}else{

cur.b = min(W, cur.b + l);

}

// 出力.

printf("%d %d\n", cur.a, cur.b);

}

return 0;

}

[入力例]
5 5 4 4
3
5 3
2 2
1 4
4
L 2
U 3
L 2
R 4

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

[入力例]
6 6 6 3
7
3 1
4 3
2 6
3 4
5 5
1 1
3 2
10
D 3
U 3
L 2
D 2
U 3
D 3
U 3
R 3
L 3
D 1

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

[入力例]
15 20 5 5
20
1 10
2 6
2 20
3 3
3 17
4 10
7 2
7 8
7 11
7 13
10 7
10 19
11 13
12 1
12 3
12 7
13 10
14 20
15 5
15 16
18
D 2
R 3
D 3
L 4
D 4
R 2
D 5
R 8
U 5
R 8
D 2
L 10
U 7
L 1
U 5
L 5
U 2
R 12

[出力例]
7 5
7 7
9 7
9 3
11 3
11 5
14 5
14 13
12 13
12 20
13 20
13 11
8 11
8 10
5 10
5 5
3 5
3 16

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

5 5 4 4

5 3

2 2

1 4

L 2

U 3

L 2

R 4

[出力例]

4 2

3 2

3 1

3 5

※AtCoderテストケースより

[入力例]

6 6 6 3

3 1

4 3

2 6

3 4

5 5

1 1

3 2

D 3

U 3

L 2

D 2

U 3

D 3

U 3

R 3

L 3

D 1

[出力例]

6 3

5 3

5 1

6 1

4 1

6 1

4 1

4 2

4 1

5 1

※AtCoderテストケースより

[入力例]

15 20 5 5

1 10

2 6

2 20

3 3

3 17

4 10

7 2

7 8

7 11

7 13

10 7

10 19

11 13

12 1

12 3

12 7

13 10

14 20

15 5

15 16

D 2

R 3

D 3

L 4

D 4

R 2

D 5

R 8

U 5

R 8

D 2

L 10

U 7

L 1

U 5

L 5

U 2

R 12

[出力例]

7 5

7 7

9 7

9 3

11 3

11 5

14 5

14 13

12 13

12 20

13 20

13 11

8 11

8 10

5 10

5 5

3 5

3 16

■参照サイト
パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）

2022年10月28日

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

C++の練習を兼ねて, AtCoder Regular Contest 149 の問題D (Simultaneous Sugoroku) を解いてみた.

■感想.
1. 問題D は, 方針が見えなかったので, 実装に非常に苦労したものの, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 個人的には, 解説のロジックで, 最終状態の各コマの座標が分かるという点が, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc149/editorial/4902
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, LL>;
using vp = vector<P>;
using 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
int X[303030], D[303030];
P g[1010101];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &X[i]);
    rep(i, M) scanf("%d", &D[i]);
    int n = X[N - 1] + 1;
    
    // 2. コマの移動.
    // -> ロジック修正(04_small_d_01.txt などの WA を 回避するため).
    LL m = 0;
    P nCur = {1, X[N - 1]}; // 数字 {左端, 右端}.
    P pCur = {1, X[N - 1]}; // 座標 {左端, 右端}.
    rep(i, M){
        // 終了条件.
        if(nCur.a == nCur.b && g[nCur.a].a) break;
        
        // チェック.
        assert(nCur.a <= nCur.b);
        assert(pCur.a <= pCur.b);
        
        // 移動先候補.
        P pNex = {pCur.a, pCur.b};
        
        // 移動方向 が 負.
        if(pCur.a > 0){
            pNex.a -= D[i];
            pNex.b -= D[i];
            m -= D[i];
        }
        
        // 移動方向 が 正.
        if(pCur.b < 0){
            pNex.a += D[i];
            pNex.b += D[i];
            m += D[i];
        }
        
        // ゼロを含む.
        if(pNex.a * pNex.b == 0){
            // 両端がゼロ.
            if(pNex.a == 0 && pNex.b == 0){
                // 0 の 位置.
                int z = (int)(nCur.b);
                
                // コマが原点に到達した.
                g[z].a = i + 1;
                
                // 終了.
                break;
            }
            
            // 左端がゼロ.
            if(pNex.a == 0){
                // 0 の 位置.
                int z = (int)(nCur.a);
                
                // コマが原点に到達した.
                g[z].a = i + 1;
                
                // 更新.
                nCur.a = z + 1;  // 左端 の 数字.
                pCur.a = 1;      // 左端 の 座標.
                pCur.b = pNex.b; // 右端 の 座標.
            }
            
            // 右端がゼロ.
            if(pNex.b == 0){
                // 0 の 位置.
                int z = (int)(nCur.b);
                
                // コマが原点に到達した.
                g[z].a = i + 1;
                
                // 更新.
                nCur.b = z - 1;  // 右端 の 数字.
                pCur.b = -1;     // 右端 の 座標.
                pCur.a = pNex.a; // 左端 の 座標.
            }
            
            // 次へ.
            continue;
        }
        
        // 符号が異なる.
        if(pNex.a * pNex.b < 0){
            // 左側, 右側 の 長さ.
            int l = (int)abs(pNex.a);
            int r = (int)abs(pNex.b);
            
            // 左側 >= 右側.
            if(l >= r){
                // 0 の 位置.
                int z = (int)(nCur.b - r);
                
                // コマが原点に到達した.
                g[z].a = i + 1;
                
                // それ以外のコマ.
                rep(j, r) g[z + (j + 1)].b = z - (j + 1);
                
                // 更新.
                nCur.b = z - 1;  // 右端 の 数字.
                pCur.b = -1;     // 右端 の 座標.
                pCur.a = pNex.a; // 左端 の 座標.
            }
            
            // 左側 < 右側.
            if(l < r){
                // 0 の 位置.
                int z = (int)(nCur.a + l);
                
                // コマが原点に到達した.
                g[z].a = i + 1;
                
                // それ以外のコマ.
                rep(j, l) g[z - (j + 1)].b = z + (j + 1);
                
                // 更新.
                nCur.a = z + 1;  // 左端 の 数字.
                pCur.a = 1;      // 左端 の 座標.
                pCur.b = pNex.b; // 右端 の 座標.
            }
        }
        
        // 符号が同じ.
        if(pNex.a * pNex.b > 0) pCur = pNex;
    }
    
    // 3. グラフ作成.
    vvi G(n);
    repx(i, 1, n){
        // コマが原点に到達した.
        if(g[i].a) continue;
        
        // コマが原点に到達しなかった.
        if(!g[i].b) continue;
        
        // それ以外.
        G[i].pb(g[i].b);
        G[g[i].b].pb(i);
    }
    
    // 4. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, vp &p, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]){
                if(!d[v] && v != s){
                    d[v] = d[u] + 1;
                    q.push(v);
                    
                    // 根であるコマが原点に到達した.
                    if(g[s].a){
                        p[v].a = p[s].a;
                        p[v].b = p[s].b;
                        continue;
                    }
                    
                    // 根であるコマが原点に到達しなかった.
                    p[v].a = p[s].a * ((d[v] & 1) ? (-1) : 1);
                    p[v].b = p[s].b;
                }
            }
        }
    };
    
    // 5. 各コマ情報の更新.
    // -> 根は, コマが原点に到達した or 到達しなかったものとして, bfs.
    int d[n];
    vp ans(n);
    repx(i, 1, n){
        ans[i].a = 0;
        ans[i].b = 0;
        d[i] = 0;
        
        if(!g[i].b){
            // 根であるコマが原点に到達した.
            if(g[i].a){
                ans[i].a = g[i].a;
                ans[i].b = 1;
                continue;
            }
            
            // 根であるコマが原点に到達しなかった.
            ans[i].a = i + m;
            ans[i].b = 0;
        }
    }
    repx(i, 1, n) if(!g[i].b && !d[i]) bfs(G, ans, i, d);
    
    // 6. 出力.
    rep(i, N) printf("%s %lld\n", ans[X[i]].b ? "Yes" : "No", ans[X[i]].a);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

// 解き直し.

// https://atcoder.jp/contests/arc149/editorial/4902

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector<P>;

using 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

int X[303030], D[303030];

P g[1010101];

int main(){

// 1. 入力情報.

int N, M;

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

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

rep(i, M) scanf("%d", &D[i]);

int n = X[N - 1] + 1;

// 2. コマの移動.

// -> ロジック修正(04_small_d_01.txt などの WA を回避するため).

LL m = 0;

P nCur = {1, X[N - 1]}; // 数字 {左端, 右端}.

P pCur = {1, X[N - 1]}; // 座標 {左端, 右端}.

rep(i, M){

// 終了条件.

if(nCur.a == nCur.b && g[nCur.a].a) break;

// チェック.

assert(nCur.a <= nCur.b);

assert(pCur.a <= pCur.b);

// 移動先候補.

P pNex = {pCur.a, pCur.b};

// 移動方向が負.

if(pCur.a > 0){

pNex.a -= D[i];

pNex.b -= D[i];

m -= D[i];

}

// 移動方向が正.

if(pCur.b < 0){

pNex.a += D[i];

pNex.b += D[i];

m += D[i];

}

// ゼロを含む.

if(pNex.a * pNex.b == 0){

// 両端がゼロ.

if(pNex.a == 0 && pNex.b == 0){

// 0 の位置.

int z = (int)(nCur.b);

// コマが原点に到達した.

g[z].a = i + 1;

// 終了.

break;

}

// 左端がゼロ.

if(pNex.a == 0){

// 0 の位置.

int z = (int)(nCur.a);

// コマが原点に到達した.

g[z].a = i + 1;

// 更新.

nCur.a = z + 1; // 左端の数字.

pCur.a = 1; // 左端の座標.

pCur.b = pNex.b; // 右端の座標.

}

// 右端がゼロ.

if(pNex.b == 0){

// 0 の位置.

int z = (int)(nCur.b);

// コマが原点に到達した.

g[z].a = i + 1;

// 更新.

nCur.b = z - 1; // 右端の数字.

pCur.b = -1; // 右端の座標.

pCur.a = pNex.a; // 左端の座標.

}

// 次へ.

continue;

}

// 符号が異なる.

if(pNex.a * pNex.b < 0){

// 左側, 右側の長さ.

int l = (int)abs(pNex.a);

int r = (int)abs(pNex.b);

// 左側 >= 右側.

if(l >= r){

// 0 の位置.

int z = (int)(nCur.b - r);

// コマが原点に到達した.

g[z].a = i + 1;

// それ以外のコマ.

rep(j, r) g[z + (j + 1)].b = z - (j + 1);

// 更新.

nCur.b = z - 1; // 右端の数字.

pCur.b = -1; // 右端の座標.

pCur.a = pNex.a; // 左端の座標.

}

// 左側 < 右側.

if(l < r){

// 0 の位置.

int z = (int)(nCur.a + l);

// コマが原点に到達した.

g[z].a = i + 1;

// それ以外のコマ.

rep(j, l) g[z - (j + 1)].b = z + (j + 1);

// 更新.

nCur.a = z + 1; // 左端の数字.

pCur.a = 1; // 左端の座標.

pCur.b = pNex.b; // 右端の座標.

}

// 符号が同じ.

if(pNex.a * pNex.b > 0) pCur = pNex;

}

// 3. グラフ作成.

vvi G(n);

repx(i, 1, n){

// コマが原点に到達した.

if(g[i].a) continue;

// コマが原点に到達しなかった.

if(!g[i].b) continue;

// それ以外.

G[i].pb(g[i].b);

G[g[i].b].pb(i);

}

// 4. bfs.

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

auto bfs = [&](vvi &G, vp &p, int s, int* d){

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

// 隣接頂点をチェック.

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

if(!d[v] && v != s){

d[v] = d[u] + 1;

q.push(v);

// 根であるコマが原点に到達した.

if(g[s].a){

p[v].a = p[s].a;

p[v].b = p[s].b;

continue;

}

// 根であるコマが原点に到達しなかった.

p[v].a = p[s].a * ((d[v] & 1) ? (-1) : 1);

p[v].b = p[s].b;

}

};

// 5. 各コマ情報の更新.

// -> 根は, コマが原点に到達した or 到達しなかったものとして, bfs.

int d[n];

vp ans(n);

repx(i, 1, n){

ans[i].a = 0;

ans[i].b = 0;

d[i] = 0;

if(!g[i].b){

// 根であるコマが原点に到達した.

if(g[i].a){

ans[i].a = g[i].a;

ans[i].b = 1;

continue;

}

// 根であるコマが原点に到達しなかった.

ans[i].a = i + m;

ans[i].b = 0;

}

repx(i, 1, n) if(!g[i].b && !d[i]) bfs(G, ans, i, d);

// 6. 出力.

rep(i, N) printf("%s %lld\n", ans[X[i]].b ? "Yes" : "No", ans[X[i]].a);

return 0;

}

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

[出力例]
No -6
No -4
Yes 2
Yes 1
Yes 2
No 4
※AtCoderテストケースより

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

[出力例]
Yes 1
Yes 2
Yes 3

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

[出力例]
No -1
Yes 1
No 1

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

[出力例]
Yes 1
Yes 2
Yes 5
Yes 3
Yes 4
Yes 5
No 1

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

[出力例]
No 4
Yes 2
Yes 1
Yes 2
No -4
No -3
Yes 4
Yes 3
Yes 4
No 3

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

[出力例]
No -6
No -5
Yes 2
No -6
Yes 1
No 5
Yes 3
No -6
Yes 2
No 5
No -6
No -5

[入力例]
30 30
6 9 10 11 13 14 19 21 23 26 28 29 34 36 41 45 47 49 52 55 58 61 66 68 73 77 81 83 84 87
22 3 60 6 7 9 77 4 9 9 78 96 9 6 40 91 7 36 68 73 12 7 6 23 5 4 40 6 18 3

[出力例]
No -12
Yes 25
No 10
No 11
Yes 26
No -12
Yes 2
No 9
No -9
No 8
No 10
No 11
No -10
No 10
Yes 26
Yes 15
No 11
Yes 26
No -12
Yes 25
No 12
No -11
No 12
No -12
Yes 25
Yes 26
Yes 26
No -11
No -10
No 11

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

[入力例]

6 4

2 4 6 8 10 12

8 2 5 7

[出力例]

No -6

No -4

Yes 2

Yes 1

Yes 2

No 4

※AtCoderテストケースより

[入力例]

3 3

1 2 3

1 1 1

[出力例]

Yes 1

Yes 2

Yes 3

[入力例]

3 3

1 2 3

2 2 2

[出力例]

No -1

Yes 1

No 1

[入力例]

7 5

1 3 5 6 8 9 10

1 2 3 2 1

[出力例]

Yes 1

Yes 2

Yes 5

Yes 3

Yes 4

Yes 5

No 1

[入力例]

10 7

1 2 3 4 5 6 7 8 9 10

3 1 4 1 5 9 2

[出力例]

No 4

Yes 2

Yes 1

Yes 2

No -4

No -3

Yes 4

Yes 3

Yes 4

No 3

[入力例]

12 10

1 2 3 7 9 10 12 13 15 16 19 20

9 6 3 4 8 2 1 5 7 10

[出力例]

No -6

No -5

Yes 2

No -6

Yes 1

No 5

Yes 3

No -6

Yes 2

No 5

No -6

No -5

[入力例]

30 30

6 9 10 11 13 14 19 21 23 26 28 29 34 36 41 45 47 49 52 55 58 61 66 68 73 77 81 83 84 87

22 3 60 6 7 9 77 4 9 9 78 96 9 6 40 91 7 36 68 73 12 7 6 23 5 4 40 6 18 3

[出力例]

No -12

Yes 25

No 10

No 11

Yes 26

No -12

Yes 2

No 9

No -9

No 8

No 10

No 11

No -10

No 10

Yes 26

Yes 15

No 11

Yes 26

No -12

Yes 25

No 12

No -11

No 12

No -12

Yes 25

Yes 26

No -11

No -10

No 11

■参照サイト
AtCoder Regular Contest 149

2022年10月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 151 の問題D (Binary Representations and Queries) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 解説にあるように, 行列の積を, 事前に計算しておくロジックが, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc151/editorial/5029
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
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 a first
#define b second
const LL MOD = 998244353;
LL a[1 << 18];

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    int n = 1 << N;
    rep(i, n) scanf("%lld", &a[i]);
    vp v(Q);
    rep(i, Q) scanf("%d %d", &v[i].a, &v[i].b);
    
    // 2. 事前計算(行列の積).
    // -> X[i] が, 0 ～ N - 1 に, わたって計算.
    vl eMatrix = {1, 0, 0, 1};
    vvl qMatrix(N, eMatrix);
    rep(i, Q){
        // クエリ情報.
        int x = v[i].a;
        int y = v[i].b;
        vl cur = qMatrix[x];
        
        // y = 0.
        if(y == 0) qMatrix[x] = {cur[0], cur[1], (cur[0] + cur[2]) % MOD, (cur[1] + cur[3]) % MOD};
        
        // y = 1.
        if(y == 1) qMatrix[x] = {(cur[0] + cur[2]) % MOD, (cur[1] + cur[3]) % MOD, cur[2], cur[3]};
    }
    /*
    rep(i, N){
        vl cur = qMatrix[i];
        printf("i=%d m00=%lld m01=%lld m10=%lld m11=%lld\n", i, cur[0], cur[1], cur[2], cur[3]);
    }
    */
    
    // 3. 整数列更新.
    // ex. N = 5
    // b[i] = 1 は, b[i] = 0 と, [加算される側], [加算する側] を 入れ替えたものと見ることができる.
    // また, 以下のように, [加算される側], [加算する側] が, 対応するインデックス が, 動的に変わることに注意.
    // 
    // b[0] = 0
    // [加算される側] 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31
    // [加算する側]   0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
    // 
    // b[1] = 0
    // [加算される側] 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31
    // [加算する側]   0 1 4 5  8  9 12 13 16 17 20 21 24 25 28 29
    // 
    // b[2] = 0
    // [加算される側] 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31
    // [加算する側]   0 1 2 3  8  9 10 11 16 17 18 19 24 25 26 27
    // 
    // b[3] = 0
    // [加算される側] 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31
    // [加算する側]   0 1  2  3  4  5  6  7 16 17 18 19 20 21 22 23
    // 
    // b[4] = 0
    // [加算される側] 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
    // [加算する側]    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
    rep(i, N){
        vl cur = qMatrix[i];
        int u = 1 << i;
        int v = 1 << (i + 1);
        repex(j, 0, 1 << N, v){
            repx(k, j, j + u){
                // 更新前情報.
                LL p = a[k + 0];
                LL q = a[k + u];
                
                // 更新.
                a[k + 0] = cur[0] * p % MOD + cur[1] * q % MOD;
                a[k + 0] %= MOD;
                a[k + u] = cur[2] * p % MOD + cur[3] * q % MOD;
                a[k + u] %= MOD;
            }
        }
    }
    
    // 4. 出力.
    rep(i, n) printf("%lld%s", a[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc151/editorial/5029

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

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

#define b second

const LL MOD = 998244353;

LL a[1 << 18];

int main(){

// 1. 入力情報.

int N, Q;

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

int n = 1 << N;

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

vp v(Q);

rep(i, Q) scanf("%d %d", &v[i].a, &v[i].b);

// 2. 事前計算(行列の積).

// -> X[i] が, 0 ～ N - 1 に, わたって計算.

vl eMatrix = {1, 0, 0, 1};

vvl qMatrix(N, eMatrix);

rep(i, Q){

// クエリ情報.

int x = v[i].a;

int y = v[i].b;

vl cur = qMatrix[x];

// y = 0.

if(y == 0) qMatrix[x] = {cur[0], cur[1], (cur[0] + cur[2]) % MOD, (cur[1] + cur[3]) % MOD};

// y = 1.

if(y == 1) qMatrix[x] = {(cur[0] + cur[2]) % MOD, (cur[1] + cur[3]) % MOD, cur[2], cur[3]};

}

rep(i, N){

vl cur = qMatrix[i];

printf("i=%d m00=%lld m01=%lld m10=%lld m11=%lld\n", i, cur[0], cur[1], cur[2], cur[3]);

}

// 3. 整数列更新.

// ex. N = 5

// b[i] = 1 は, b[i] = 0 と, [加算される側], [加算する側] を入れ替えたものと見ることができる.

// また, 以下のように, [加算される側], [加算する側] が, 対応するインデックスが, 動的に変わることに注意.

// b[0] = 0

// [加算される側] 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31

// [加算する側] 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

// b[1] = 0

// [加算される側] 2 3 6 7 10 11 14 15 18 19 22 23 26 27 30 31

// [加算する側] 0 1 4 5 8 9 12 13 16 17 20 21 24 25 28 29

// b[2] = 0

// [加算される側] 4 5 6 7 12 13 14 15 20 21 22 23 28 29 30 31

// [加算する側] 0 1 2 3 8 9 10 11 16 17 18 19 24 25 26 27

// b[3] = 0

// [加算される側] 8 9 10 11 12 13 14 15 24 25 26 27 28 29 30 31

// [加算する側] 0 1 2 3 4 5 6 7 16 17 18 19 20 21 22 23

// b[4] = 0

// [加算される側] 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

// [加算する側] 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

rep(i, N){

vl cur = qMatrix[i];

int u = 1 << i;

int v = 1 << (i + 1);

repex(j, 0, 1 << N, v){

repx(k, j, j + u){

// 更新前情報.

LL p = a[k + 0];

LL q = a[k + u];

// 更新.

a[k + 0] = cur[0] * p % MOD + cur[1] * q % MOD;

a[k + 0] %= MOD;

a[k + u] = cur[2] * p % MOD + cur[3] * q % MOD;

a[k + u] %= MOD;

}

// 4. 出力.

rep(i, n) printf("%lld%s", a[i], (i < n - 1) ? " " : "\n");

return 0;

}

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

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

[入力例]
3 10
606248357 338306877 919152167 981537317 808873985 845549408 680941783 921035119
1 1
0 0
0 0
0 0
0 1
0 1
0 1
2 0
2 0
2 0

[出力例]
246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980
※AtCoderのテストケースより

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

[出力例]
45 31 64 44 74 53 103 74

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

[出力例]
3184 1837 5011 2896 4110 2371 6469 3738 1967 1134 3078 1778 2538 1463 3972 2294 5813 3358 8850 5116 7468 4314 11367 6571 3519 2031 5357 3095 4519 2608 6877 3973

[入力例]
7 50
105 65 84 96 44 84 114 29 101 85 107 16 63 39 64 62 54 59 56 7 69 92 0 58 78 113 8 11 108 79 84 122 11 63 94 92 51 46 14 81 105 0 72 53 98 100 50 27 28 60 72 30 107 86 19 33 84 19 17 120 109 72 64 7 24 75 14 63 1 61 37 70 76 85 59 37 68 109 74 85 49 64 73 100 43 94 51 38 72 1 32 38 114 91 56 39 102 35 90 30 81 76 71 78 29 88 79 64 77 52 121 31 75 35 5 73 66 47 32 116 112 98 88 75 16 24 52 103
6 1
1 0
3 0
2 0
2 1
5 1
6 0
2 1
1 0
4 1
0 1
4 1
2 0
2 1
4 1
0 1
5 1
3 1
1 1
3 0
5 0
1 0
1 1
6 1
4 1
0 0
2 1
4 0
3 0
0 0
6 1
5 1
6 1
6 1
0 0
3 1
0 0
5 1
3 0
6 1
3 1
3 0
6 0
5 0
3 0
3 0
0 1
0 1
6 1
0 1

[出力例]
88126790 240381482 51552281 514638308 199195645 774400092 760294249 401546881 224524928 209170759 489420394 672773238 325941805 717801442 201192366 727200754 676636858 279821546 243421329 811652115 627978707 526795799 306734163 879102198 167523305 618940189 721262090 387830206 153879606 450491377 816147042 465892088 104067306 958020824 695998303 880303207 628528832 146604919 579397171 274187367 882939691 720758794 269733526 271369651 422318169 699671401 442707565 896791957 86802880 738611319 411364892 649523406 939815836 171597330 686215793 925185833 521955928 822365926 34939833 697552625 455694697 424588556 99048474 267439342 884153389 534676791 378779225 521054823 593340723 40891658 195186633 298007808 985259095 113237189 346140098 795537288 958720177 415020808 243844755 716897207 446815658 636927490 644378123 222952753 906040118 446638787 30957510 556145792 927383936 118872216 579408946 344748640 730764997 891043707 279476482 656587924 380244244 544902818 511376758 799676718 987314293 780733555 717961322 768764675 586045102 416848955 362597359 443760755 660168846 108472957 779184020 430884266 235987825 48581070 600351802 755874351 777846243 335584921 856640682 122411711 228945524 876436615 586470034 916963377 165535763 121637992 917180332 711225132

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

[入力例]

2 2

0 1 2 3

1 1

0 0

[出力例]

2 6 2 5

※AtCoderのテストケースより

[入力例]

3 10

606248357 338306877 919152167 981537317 808873985 845549408 680941783 921035119

1 1

0 0

0 1

2 0

[出力例]

246895115 904824001 157201385 744260759 973709546 964549010 61683812 205420980

※AtCoderのテストケースより

[入力例]

3 6

3 1 4 1 5 9 2 6

2 1

2 0

1 1

1 0

0 0

0 1

[出力例]

45 31 64 44 74 53 103 74

[入力例]

5 15

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

2 0

2 1

1 1

1 0

0 1

0 0

2 1

0 1

4 0

3 1

2 1

2 0

3 0

3 1

[出力例]

3184 1837 5011 2896 4110 2371 6469 3738 1967 1134 3078 1778 2538 1463 3972 2294 5813 3358 8850 5116 7468 4314 11367 6571 3519 2031 5357 3095 4519 2608 6877 3973

[入力例]

7 50

105 65 84 96 44 84 114 29 101 85 107 16 63 39 64 62 54 59 56 7 69 92 0 58 78 113 8 11 108 79 84 122 11 63 94 92 51 46 14 81 105 0 72 53 98 100 50 27 28 60 72 30 107 86 19 33 84 19 17 120 109 72 64 7 24 75 14 63 1 61 37 70 76 85 59 37 68 109 74 85 49 64 73 100 43 94 51 38 72 1 32 38 114 91 56 39 102 35 90 30 81 76 71 78 29 88 79 64 77 52 121 31 75 35 5 73 66 47 32 116 112 98 88 75 16 24 52 103

6 1

1 0

3 0

2 0

2 1

5 1

6 0

2 1

1 0

4 1

0 1

4 1

2 0

2 1

4 1

0 1

5 1

3 1

1 1

3 0

5 0

1 0

1 1

6 1

4 1

0 0

2 1

4 0

3 0

0 0

6 1

5 1

6 1

0 0

3 1

0 0

5 1

3 0

6 1

3 1

3 0

6 0

5 0

3 0

0 1

6 1

0 1

[出力例]

88126790 240381482 51552281 514638308 199195645 774400092 760294249 401546881 224524928 209170759 489420394 672773238 325941805 717801442 201192366 727200754 676636858 279821546 243421329 811652115 627978707 526795799 306734163 879102198 167523305 618940189 721262090 387830206 153879606 450491377 816147042 465892088 104067306 958020824 695998303 880303207 628528832 146604919 579397171 274187367 882939691 720758794 269733526 271369651 422318169 699671401 442707565 896791957 86802880 738611319 411364892 649523406 939815836 171597330 686215793 925185833 521955928 822365926 34939833 697552625 455694697 424588556 99048474 267439342 884153389 534676791 378779225 521054823 593340723 40891658 195186633 298007808 985259095 113237189 346140098 795537288 958720177 415020808 243844755 716897207 446815658 636927490 644378123 222952753 906040118 446638787 30957510 556145792 927383936 118872216 579408946 344748640 730764997 891043707 279476482 656587924 380244244 544902818 511376758 799676718 987314293 780733555 717961322 768764675 586045102 416848955 362597359 443760755 660168846 108472957 779184020 430884266 235987825 48581070 600351802 755874351 777846243 335584921 856640682 122411711 228945524 876436615 586470034 916963377 165535763 121637992 917180332 711225132

■参照サイト
AtCoder Regular Contest 151

2022年10月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 151 の問題C (01 Game) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    int M;
    scanf("%lld %d", &N, &M);
    vp v(M);
    rep(i, M) scanf("%lld %lld", &v[i].a, &v[i].b);
    
    // 2. Grundy数.
    // 2-1. どちらの端も数字と接していない.
    LL ans = 0;
    if(!M) ans ^= (N % 2);
    
    // 2-2. それ以外.
    if(M){
        // 一方の端のみが数字と接している.
        if(v[0].a > 1)     ans ^= (v[0].a - 1);
        if(v[M - 1].a < N) ans ^= (N - v[M - 1].a);
        
        rep(i, M - 1){
            // 両端が異なる数字.
            if(v[i].b != v[i + 1].b) ans ^= 0;
            
            // 両端が同じ数字.
            if(v[i].b == v[i + 1].b) ans ^= 1;
        }
    }
    
    // 3. 出力.
    printf("%s\n", ans ? "Takahashi" : "Aoki");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc151/editorial/5027

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

LL N;

int M;

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

vp v(M);

rep(i, M) scanf("%lld %lld", &v[i].a, &v[i].b);

// 2. Grundy数.

// 2-1. どちらの端も数字と接していない.

LL ans = 0;

if(!M) ans ^= (N % 2);

// 2-2. それ以外.

if(M){

// 一方の端のみが数字と接している.

if(v[0].a > 1) ans ^= (v[0].a - 1);

if(v[M - 1].a < N) ans ^= (N - v[M - 1].a);

rep(i, M - 1){

// 両端が異なる数字.

if(v[i].b != v[i + 1].b) ans ^= 0;

// 両端が同じ数字.

if(v[i].b == v[i + 1].b) ans ^= 1;

}

// 3. 出力.

printf("%s\n", ans ? "Takahashi" : "Aoki");

return 0;

}

[入力例]
7 2
2 0
4 1

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

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

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

[入力例]
1000000000000000000 0

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

[入力例]
20 5
3 1
7 0
10 1
13 1
17 0

[出力例]
Aoki

[入力例]
30 10
1 1
5 1
9 0
12 0
15 1
20 1
22 0
23 1
28 1
30 0

[出力例]
Aoki

[入力例]
50 12
5 0
7 1
13 1
17 0
21 0
24 1
29 1
33 1
34 0
38 0
43 0
44 1

[出力例]
Takahashi

[入力例]

7 2

2 0

4 1

[出力例]

Takahashi

※AtCoderのテストケースより

[入力例]

3 3

1 1

2 0

3 1

[出力例]

Aoki

※AtCoderのテストケースより

[入力例]

1000000000000000000 0

[出力例]

Aoki

※AtCoderのテストケースより

[入力例]

20 5

3 1

7 0

10 1

13 1

17 0

[出力例]

Aoki

[入力例]

30 10

1 1

5 1

9 0

12 0

15 1

20 1

22 0

23 1

28 1

30 0

[出力例]

Aoki

[入力例]

50 12

5 0

7 1

13 1

17 0

21 0

24 1

29 1

33 1

34 0

38 0

43 0

44 1

[出力例]

Takahashi

■参照サイト
AtCoder Regular Contest 151

C++の練習を兼ねて, AtCoder Regular Contest 118 の 問題D (Hamiltonian Cycle) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題E (Non-coprime DAG) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 114 の 問題C (Sequence Scores) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の 問題C (Circular Addition) ～ 問題D (Without Carry) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 273 の 問題C ((K+1)-th Largest Number) ～ 問題D (LRUD Instructions) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 149 の 問題D (Simultaneous Sugoroku) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 151 の 問題D (Binary Representations and Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 151 の 問題C (01 Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 118 の問題D (Hamiltonian Cycle) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題E (Non-coprime DAG) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 114 の問題C (Sequence Scores) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 136 の問題C (Circular Addition) ～問題D (Without Carry) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 273 の問題C ((K+1)-th Largest Number) ～問題D (LRUD Instructions) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 149 の問題D (Simultaneous Sugoroku) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 151 の問題D (Binary Representations and Queries) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 151 の問題C (01 Game) を解いてみた.