個人用メモ帳

2022年1月30日

概要

Qiskit について, 学習サイトのサンプルプログラムを動かしてみた.
動作環境は, 学習サイト上で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

前回の続きを確認してみた, より複雑なパターンになるが, 非常に面白く感じた.

Hello Qiskitゲーム

パズル６

[Choose gate] で, [NOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果]
真ん中の円が, 白になった.
[Success!] が表示されるので, 操作手順が正しかったことを確認できる.

[参考（初期状態を, Zゲートに変更した場合）]

～（略）～
initialize = [['z', '0']]
～（略）～

～（略）～

initialize = [['z', '0']]

～（略）～

[Choose gate] で, [NOT]クリック.

[Choose bit] で, [the bit on the left]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果]
真ん中の円が, 白になった.
[Success!] が表示されるので, 操作手順が正しかったことを確認できる.

パズル７

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the left]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[Choose gate] で, [NOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果]
真ん中の円が, 白になった.
[Success!] が表示されるので, 操作手順が正しかったことを確認できる.

参照サイト

Hello Qiskitゲーム

2022年1月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題C (Row Column Sums) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 計算できてしまうことが, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc133/editorial/3282
// 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 H, W;
    LL K;
    scanf("%d %d %lld", &H, &W, &K);
    LL a, b, ta = 0, tb = 0, C = 0, D = 0;
    rep(i, H){
        scanf("%lld", &a);
        ta += a;
        C += ((K - 1) * (LL)W - a) % K;
    }
    rep(i, W){
        scanf("%lld", &b);
        tb += b;
        D += ((K - 1) * (LL)H - b) % K;
    }
    
    // 2. 例外.
    if(ta % K != tb % K){
        puts("-1");
        return 0;
    }
    
    // 3. 出力.
    printf("%lld\n", (LL)H * (LL)W * (K - 1) - max(C, D));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc133/editorial/3282

// 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 H, W;

LL K;

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

LL a, b, ta = 0, tb = 0, C = 0, D = 0;

rep(i, H){

scanf("%lld", &a);

ta += a;

C += ((K - 1) * (LL)W - a) % K;

}

rep(i, W){

scanf("%lld", &b);

tb += b;

D += ((K - 1) * (LL)H - b) % K;

}

// 2. 例外.

if(ta % K != tb % K){

puts("-1");

return 0;

}

// 3. 出力.

printf("%lld\n", (LL)H * (LL)W * (K - 1) - max(C, D));

return 0;

}

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

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

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

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

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

[出力例]
75

[入力例]
31 41 59
26 5 35 8 9 7 9 32 38 46 26 43 38 32 7 9 50 28 8 41 9 7 16 9 39 9 37 5 10 58 20
9 7 4 9 44 5 9 23 0 7 8 16 4 0 6 28 6 20 8 9 9 8 6 28 0 34 8 25 3 4 2 11 7 0 6 7 9 8 2 14 8

[出力例]
72873

[入力例]
123 234 345
309 226 171 216 1 176 264 188 212 318 50 40 92 124 29 320 297 338 251 26 133 271 90 155 217 252 212 136 43 247 141 141 18 290 91 176 239 47 120 326 182 62 18 149 18 266 109 192 229 188 153 162 115 13 145 219 132 281 309 250 221 270 136 5 5 138 307 301 333 42 222 122 20 304 178 24 42 182 316 122 245 311 316 305 47 66 211 155 35 196 149 128 297 160 213 27 228 59 258 156 142 295 216 240 178 201 19 94 248 63 247 187 225 242 321 162 339 143 148 160 10 135 15
164 243 102 226 16 65 212 291 311 159 342 251 195 195 326 165 39 266 242 44 213 28 34 165 127 228 252 189 153 234 23 225 279 101 263 150 165 333 204 83 307 153 74 162 298 343 63 4 92 55 1 16 109 115 175 174 33 169 116 66 67 119 123 115 138 132 320 285 157 142 58 44 229 212 122 138 260 189 104 194 216 248 94 151 275 211 310 130 248 303 195 20 116 238 331 190 241 103 223 238 64 185 247 10 89 74 146 55 39 16 75 0 304 85 25 122 27 301 255 243 129 125 172 109 276 255 261 213 12 38 167 286 260 50 265 129 92 236 249 192 230 338 123 240 5 268 205 288 32 132 105 117 21 209 7 107 5 217 38 297 166 243 293 310 38 171 110 82 102 41 271 245 16 60 192 211 132 201 169 47 14 232 216 307 34 334 284 12 27 245 315 336 65 192 189 57 46 79 245 74 281 247 126 84 201 3 205 51 313 274 34 197 289 330 65 32 159 296 45 204 42 93 60 141 256 231 58 191 84 50 326 107 335 240

[出力例]
9860467

[入力例]

2 4 3

0 2

1 2 2 0

[出力例]

※AtCoderのテストケースより

[入力例]

3 3 4

0 1 2

1 2 3

[出力例]

-1

※AtCoderのテストケースより

[入力例]

3 5 7

3 4 5

3 1 3 2 3

[出力例]

[入力例]

31 41 59

26 5 35 8 9 7 9 32 38 46 26 43 38 32 7 9 50 28 8 41 9 7 16 9 39 9 37 5 10 58 20

9 7 4 9 44 5 9 23 0 7 8 16 4 0 6 28 6 20 8 9 9 8 6 28 0 34 8 25 3 4 2 11 7 0 6 7 9 8 2 14 8

[出力例]

72873

[入力例]

123 234 345

309 226 171 216 1 176 264 188 212 318 50 40 92 124 29 320 297 338 251 26 133 271 90 155 217 252 212 136 43 247 141 141 18 290 91 176 239 47 120 326 182 62 18 149 18 266 109 192 229 188 153 162 115 13 145 219 132 281 309 250 221 270 136 5 5 138 307 301 333 42 222 122 20 304 178 24 42 182 316 122 245 311 316 305 47 66 211 155 35 196 149 128 297 160 213 27 228 59 258 156 142 295 216 240 178 201 19 94 248 63 247 187 225 242 321 162 339 143 148 160 10 135 15

164 243 102 226 16 65 212 291 311 159 342 251 195 195 326 165 39 266 242 44 213 28 34 165 127 228 252 189 153 234 23 225 279 101 263 150 165 333 204 83 307 153 74 162 298 343 63 4 92 55 1 16 109 115 175 174 33 169 116 66 67 119 123 115 138 132 320 285 157 142 58 44 229 212 122 138 260 189 104 194 216 248 94 151 275 211 310 130 248 303 195 20 116 238 331 190 241 103 223 238 64 185 247 10 89 74 146 55 39 16 75 0 304 85 25 122 27 301 255 243 129 125 172 109 276 255 261 213 12 38 167 286 260 50 265 129 92 236 249 192 230 338 123 240 5 268 205 288 32 132 105 117 21 209 7 107 5 217 38 297 166 243 293 310 38 171 110 82 102 41 271 245 16 60 192 211 132 201 169 47 14 232 216 307 34 334 284 12 27 245 315 336 65 192 189 57 46 79 245 74 281 247 126 84 201 3 205 51 313 274 34 197 289 330 65 32 159 296 45 204 42 93 60 141 256 231 58 191 84 50 326 107 335 240

[出力例]

9860467

■参照サイト
AtCoder Regular Contest 133

2022年1月29日2022年1月30日

Python（Qiskit）について（１７）

概要

Qiskit について, 学習サイトのサンプルプログラムを動かしてみた.
動作環境は, 学習サイト上で行った
実行プログラム, 解説は, 下記の参照サイトをご覧ください

感想

個人的には, 視覚的に, 量子ビット, 量子ゲートを確認出来るため, 非常に面白く感じた.
さらに, 学習サイト上で, プログラムを編集して, 実行できるので, 非常に便利に感じた.

Hello Qiskitゲーム

パズル１

[Choose gate] で, [NOT]クリック.

[Choose bit] で, [the only bit]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[一回目結果（NOTゲート）]

手順を略して,
[二回目結果（NOTゲート）]

[三回目結果（NOTゲート）]
[Success!] が表示されるので, 操作手順が正しかったか確認できる.

パズル２

[Choose gate] で, [NOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（NOTゲート）]

[参考（ANDゲート）]
ちなみに, AND を指定すると, もう一方のビットは, オン（黒 ⇒ 白）にならないことも確認できる.

～（略）～
allowed_gates = {'0': {}, '1': {'AND': 0}, 'both': {}}
～（略）～

～（略）～

allowed_gates = {'0': {}, '1': {'AND': 0}, 'both': {}}

～（略）～

とプログラムを修正している

パズル３

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（CNOTゲート）]
右側のビットがオンになったことを確認出来る

[参考（左側のビットをオンにするには？）]

～（略）～
initialize = [['x', '1']]
～（略）～

～（略）～

initialize = [['x', '1']]

～（略）～

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the left]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（CNOTゲート）]
左側のビットがオンになったことを確認出来る

パズル４

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the left]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（CNOTゲート）]
左側のビットがオフ, 右側のビットがオンになったことを確認出来る

[参考（左側のビットをオン, 右側のビットをオフにするには？）]

～（略）～
initialize = [['x', '1']]
success_condition = {'ZI': -1.0, 'IZ': 1.0}
～（略）～

～（略）～

initialize = [['x', '1']]

success_condition = {'ZI': -1.0, 'IZ': 1.0}

～（略）～

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the left]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（CNOTゲート）]
左側のビットがオン, 右側のビットがオフになったことを確認出来る

パズル５

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the right]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（CNOTゲート）]
右側のビットがランダムになることを確認出来る

[参考（左側のビットをランダムにするには？）]

～（略）～
initialize = [['h', '1']]
～（略）～

～（略）～

initialize = [['h', '1']]

～（略）～

[Choose gate] で, [CNOT]クリック.

[Choose bit] で, [the bit on the left]クリック.

[Make it happen!] で, [Apply Operation]クリック.

[結果（CNOTゲート）]
左側のビットがランダムになることを確認出来る

参照サイト

Hello Qiskitゲーム

2022年1月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3279
// 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--)
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 評価関数(平均値).
    auto f = [&](LL m) -> bool {
        // 2-1. 平均値を, m以上にできるか？
        vl dp(N + 1), pd(N + 1);
        rep(i, N){
            dp[i + 1] = max(dp[i], pd[i]) + (1000 * a[i] - m);
            pd[i + 1] = dp[i];
        }
        
        // 2-2. 判定結果.
        return (max(dp[N], pd[N]) >= 0);
    };
    
    // 3. 評価関数(中央値).
    auto g = [&](LL m) -> bool {
        // 3-1. 中央値を, m以上にできるか？
        vl dp(N + 1), pd(N + 1);
        rep(i, N){
            dp[i + 1] = max(dp[i], pd[i]) + ((a[i] >= m) ? 1 : -1);
            pd[i + 1] = dp[i];
        }
        
        // 3-2. 判定結果.
        return (max(dp[N], pd[N]) > 0);
    };
    
    // 4. 二分探索で確認してみる(平均値).
    LL l = 0, h = 2e12 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    LL maxMean = l;
    
    // 5. 二分探索で確認してみる(中央値).
    l = 0, h = 2e9 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(g(m)) l = m;
        else     h = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    LL maxMedian = l;
    
    // 6. 出力.
    printf("%.3lf\n%lld\n", (double)maxMean / 1000.0, maxMedian);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3279

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 評価関数(平均値).

auto f = [&](LL m) -> bool {

// 2-1. 平均値を, m以上にできるか？

vl dp(N + 1), pd(N + 1);

rep(i, N){

dp[i + 1] = max(dp[i], pd[i]) + (1000 * a[i] - m);

pd[i + 1] = dp[i];

}

// 2-2. 判定結果.

return (max(dp[N], pd[N]) >= 0);

};

// 3. 評価関数(中央値).

auto g = [&](LL m) -> bool {

// 3-1. 中央値を, m以上にできるか？

vl dp(N + 1), pd(N + 1);

rep(i, N){

dp[i + 1] = max(dp[i], pd[i]) + ((a[i] >= m) ? 1 : -1);

pd[i + 1] = dp[i];

}

// 3-2. 判定結果.

return (max(dp[N], pd[N]) > 0);

};

// 4. 二分探索で確認してみる(平均値).

LL l = 0, h = 2e12 + 1;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(f(m)) l = m;

else h = m;

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

}

LL maxMean = l;

// 5. 二分探索で確認してみる(中央値).

l = 0, h = 2e9 + 1;

while(l + 1 < h){

LL m = (h + l) >> 1;

if(g(m)) l = m;

else h = m;

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

}

LL maxMedian = l;

// 6. 出力.

printf("%.3lf\n%lld\n", (double)maxMean / 1000.0, maxMedian);

return 0;

}

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

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

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

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

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

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

[入力例]
10
8 18 28 2 18 20 15 17 12 21

[出力例]
20.333
18

[入力例]
50
1534 1993 842 127 172 1834 409 510 1117 1172 804 157 516 1644 1877 505 1468 1204 1752 1445 960 1807 1335 1189 199 1117 394 98 1193 1221 496 470 1391 986 1665 820 447 1229 1454 86 1272 690 136 1853 488 728 1886 380 1221 1779

[出力例]
1259.096
1391

[入力例]
150
93302 62538 89452 42425 44435 71496 29725 90563 8793 99500 92586 16243 86849 53851 22514 39271 69471 80528 64641 58584 19431 66758 49676 47265 93718 1327 64433 13729 69773 84893 95444 15668 14975 81144 48397 32389 16928 97314 13842 16956 130 72861 65377 88928 28591 86404 72886 99434 29164 61853 91776 10823 23759 41434 71850 51656 19927 64536 16592 451 70065 35886 79105 53865 13176 37295 7871 17574 64756 92886 97573 31391 10596 98653 39374 34673 49248 41525 46520 60125 50024 92813 93518 30639 82782 59796 55623 69102 36042 36794 80653 85233 52208 40492 73530 35112 57254 6463 87848 49361 20681 61948 4737 50429 42490 30610 99179 13068 53455 84426 3921 22226 49329 48002 18928 84734 86630 10502 32007 57934 31180 11383 37728 26371 70605 20101 56202 91981 29667 702 96602 74258 50209 26074 86719 9891 99463 24847 52501 56676 38125 85244 3337 59419 75076 5607 4647 38281 49673 3307

[出力例]
65380.076
70065

[入力例]
300
45 48 70 79 96 86 5 89 21 48 45 25 97 45 75 87 11 89 97 93 34 80 77 54 14 68 83 25 33 70 47 95 52 26 29 46 47 58 67 20 66 89 69 42 67 51 57 14 82 62 30 39 89 35 43 57 14 61 14 33 15 66 10 45 90 21 83 39 2 92 24 94 76 73 39 34 95 60 68 77 57 47 79 34 56 14 15 23 51 80 79 2 93 16 16 93 6 67 19 4 1 37 83 99 27 54 36 1 10 76 12 19 86 87 78 23 89 5 27 16 56 19 81 72 46 82 77 94 8 85 33 24 70 59 71 46 71 87 4 18 51 11 48 14 74 83 37 57 82 60 23 60 23 93 97 33 14 11 24 19 42 93 99 63 79 45 5 46 98 14 60 21 87 29 89 55 51 52 44 31 83 93 74 86 58 49 92 99 7 86 94 80 24 53 3 64 35 29 58 27 48 1 53 83 57 6 74 19 78 21 37 13 92 95 84 8 85 39 4 59 74 87 85 97 86 32 28 34 42 5 6 64 15 81 8 2 35 57 32 99 64 34 89 12 54 81 17 91 57 14 99 52 81 91 69 82 88 99 40 34 45 92 9 30 54 80 70 55 62 85 41 65 38 46 82 69 92 18 52 17 19 81 66 21 2 32 3 93 14 26 70 37 94 18 89 50 1 64 92 8

[出力例]
67.476
77

[入力例]

2 1 2 1 1 10

[出力例]

※AtCoderテストケースより

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

4.000

[入力例]

3 1 4 1 5 9 2

[出力例]

5.250000000

※AtCoderテストケースより

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

5.250

[入力例]

8 18 28 2 18 20 15 17 12 21

[出力例]

20.333

[入力例]

1534 1993 842 127 172 1834 409 510 1117 1172 804 157 516 1644 1877 505 1468 1204 1752 1445 960 1807 1335 1189 199 1117 394 98 1193 1221 496 470 1391 986 1665 820 447 1229 1454 86 1272 690 136 1853 488 728 1886 380 1221 1779

[出力例]

1259.096

1391

[入力例]

150

93302 62538 89452 42425 44435 71496 29725 90563 8793 99500 92586 16243 86849 53851 22514 39271 69471 80528 64641 58584 19431 66758 49676 47265 93718 1327 64433 13729 69773 84893 95444 15668 14975 81144 48397 32389 16928 97314 13842 16956 130 72861 65377 88928 28591 86404 72886 99434 29164 61853 91776 10823 23759 41434 71850 51656 19927 64536 16592 451 70065 35886 79105 53865 13176 37295 7871 17574 64756 92886 97573 31391 10596 98653 39374 34673 49248 41525 46520 60125 50024 92813 93518 30639 82782 59796 55623 69102 36042 36794 80653 85233 52208 40492 73530 35112 57254 6463 87848 49361 20681 61948 4737 50429 42490 30610 99179 13068 53455 84426 3921 22226 49329 48002 18928 84734 86630 10502 32007 57934 31180 11383 37728 26371 70605 20101 56202 91981 29667 702 96602 74258 50209 26074 86719 9891 99463 24847 52501 56676 38125 85244 3337 59419 75076 5607 4647 38281 49673 3307

[出力例]

65380.076

70065

[入力例]

300

45 48 70 79 96 86 5 89 21 48 45 25 97 45 75 87 11 89 97 93 34 80 77 54 14 68 83 25 33 70 47 95 52 26 29 46 47 58 67 20 66 89 69 42 67 51 57 14 82 62 30 39 89 35 43 57 14 61 14 33 15 66 10 45 90 21 83 39 2 92 24 94 76 73 39 34 95 60 68 77 57 47 79 34 56 14 15 23 51 80 79 2 93 16 16 93 6 67 19 4 1 37 83 99 27 54 36 1 10 76 12 19 86 87 78 23 89 5 27 16 56 19 81 72 46 82 77 94 8 85 33 24 70 59 71 46 71 87 4 18 51 11 48 14 74 83 37 57 82 60 23 60 23 93 97 33 14 11 24 19 42 93 99 63 79 45 5 46 98 14 60 21 87 29 89 55 51 52 44 31 83 93 74 86 58 49 92 99 7 86 94 80 24 53 3 64 35 29 58 27 48 1 53 83 57 6 74 19 78 21 37 13 92 95 84 8 85 39 4 59 74 87 85 97 86 32 28 34 42 5 6 64 15 81 8 2 35 57 32 99 64 34 89 12 54 81 17 91 57 14 99 52 81 91 69 82 88 99 40 34 45 92 9 30 54 80 70 55 62 85 41 65 38 46 82 69 92 18 52 17 19 81 66 21 2 32 3 93 14 26 70 37 94 18 89 50 1 64 92 8

[出力例]

67.476

■参照サイト
AtCoder Beginner Contest 236

2022年1月29日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3287
// 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 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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()
int b[1 << 16], c[1 << 16];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v;
    repx(i, 1, 1 << N){
        scanf("%d", &c[i]);
        v.pb({c[i], i});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 貪欲アルゴリズム(解説通り).
    vi S;
    b[0] = 1;
    for(auto &p : v){
        // S の 要素から, 辛さ p.b を 作れる場合.
        if(b[p.b]) continue;
        
        // S の 要素から, 辛さ p.b を 作れない場合. 
        // -> S に 要素を追加し, フラグ b を 更新.
        S.pb(p.b);
        rep(i, 1 << N) if(b[i]) b[i ^ p.b] = 1;
    }
    
    // 4. 集計.
    LL ans = 0;
    for(auto &p : S) ans += (LL)c[p];
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3287

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

#define b second

#define pb push_back

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

int b[1 << 16], c[1 << 16];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v;

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

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

v.pb({c[i], i});

}

// 2. sort.

sort(all(v));

// 3. 貪欲アルゴリズム(解説通り).

vi S;

b[0] = 1;

for(auto &p : v){

// S の要素から, 辛さ p.b を作れる場合.

if(b[p.b]) continue;

// S の要素から, 辛さ p.b を作れない場合.

// -> S に要素を追加し, フラグ b を更新.

S.pb(p.b);

rep(i, 1 << N) if(b[i]) b[i ^ p.b] = 1;

}

// 4. 集計.

LL ans = 0;

for(auto &p : S) ans += (LL)c[p];

// 5. 出力.

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

return 0;

}

[入力例]
2
4 5 3

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

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

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

[入力例]
1
10

[出力例]
10

[入力例]
3
16 30 26 6 33 18 27

[出力例]
40

[入力例]
7
129 290 138 144 521 138 541 413 255 462 202 497 245 7 414 246 529 547 342 366 442 348 509 166 67 140 40 115 129 34 476 62 312 390 461 194 352 518 21 436 426 146 220 403 207 152 309 44 472 293 50 133 322 374 544 311 553 499 549 90 293 59 109 279 338 475 307 162 527 404 282 498 258 220 126 268 341 355 160 301 480 331 263 289 393 187 528 182 285 471 345 395 454 209 419 551 137 242 282 186 466 361 63 358 199 209 308 371 31 369 141 534 213 515 262 335 56 103 153 284 218 518 541 15 418 190 435

[出力例]
192

[入力例]
10
858 582 452 236 475 298 137 74 213 307 808 73 141 585 5 561 770 524 416 663 180 822 70 769 248 730 254 363 19 667 280 235 328 715 291 404 668 496 202 862 56 230 664 582 428 793 559 795 71 891 532 902 582 341 216 519 819 899 968 380 402 405 828 66 472 959 224 204 599 711 651 962 414 33 412 654 689 370 528 512 570 140 114 407 779 945 271 48 168 856 221 279 737 307 957 994 646 214 336 25 760 968 934 318 341 42 780 863 941 507 64 179 315 379 411 612 610 48 831 533 938 525 344 695 420 363 176 824 354 180 787 324 13 729 504 456 996 631 250 840 708 161 620 595 689 316 761 458 60 127 703 701 90 539 156 432 483 540 274 845 416 259 55 133 143 786 969 826 853 195 757 171 963 316 842 744 84 465 281 432 527 146 896 897 507 960 312 997 941 584 524 526 11 663 148 344 53 315 838 486 708 555 273 830 820 346 506 37 485 133 159 417 394 211 73 862 886 930 550 446 550 626 145 624 854 615 624 598 840 895 817 646 640 425 628 434 831 165 993 434 897 248 427 646 936 349 270 512 683 921 961 699 823 79 570 507 923 105 56 826 23 768 562 705 976 25 481 653 511 682 313 945 472 174 858 137 760 540 59 546 983 6 940 236 657 877 863 457 374 791 153 839 709 688 871 333 634 395 66 443 397 659 12 696 993 661 452 795 606 407 582 439 756 31 651 738 858 151 451 565 193 677 112 590 736 734 53 537 192 862 870 352 725 349 936 988 388 639 96 356 156 938 708 335 323 937 986 621 950 33 837 571 958 333 374 873 222 892 96 819 980 542 748 231 161 786 244 441 639 358 843 734 102 802 249 42 222 407 142 564 54 876 430 278 592 498 119 125 451 317 678 814 150 927 887 10 93 916 708 729 669 724 296 733 533 834 412 940 488 529 887 982 915 958 769 977 432 800 995 443 76 164 182 653 40 631 737 249 863 955 199 545 288 396 454 129 905 908 130 389 173 474 257 997 164 74 444 171 465 363 848 689 225 30 26 515 185 477 141 47 293 199 515 362 752 875 500 513 397 602 468 834 758 832 129 878 82 510 651 23 28 369 224 227 962 201 779 596 270 247 328 749 910 803 14 563 561 344 49 3 869 742 874 800 448 109 659 231 986 792 183 831 920 575 460 311 99 306 762 696 370 58 35 306 534 731 128 446 187 113 143 547 149 404 613 816 567 785 367 702 703 881 494 37 931 579 572 572 387 294 74 54 283 265 356 764 364 124 66 202 287 609 350 40 680 344 272 763 311 447 276 782 975 637 98 660 260 545 834 678 865 563 701 773 837 380 592 22 441 608 554 87 421 13 261 48 959 409 955 763 672 438 284 77 86 112 886 528 464 484 801 188 161 301 140 296 252 35 655 115 89 673 915 860 911 980 271 493 876 183 806 719 568 62 187 211 145 66 895 50 13 992 758 710 832 221 949 645 874 86 745 953 369 730 715 389 427 725 633 15 950 318 160 248 290 979 225 550 285 139 231 414 673 853 264 219 33 352 823 430 526 679 489 855 998 638 148 345 976 189 668 336 938 880 567 90 481 847 189 952 151 55 702 956 23 550 647 125 7 276 721 961 556 498 774 448 794 333 100 705 156 714 414 259 534 645 356 140 767 54 691 827 716 742 824 77 694 701 336 212 366 285 148 871 531 487 920 936 442 778 960 928 524 642 460 163 795 334 793 644 890 392 180 683 464 490 397 776 20 718 668 344 408 890 714 399 627 775 276 612 460 336 772 634 302 257 944 695 636 995 116 709 183 397 40 694 101 564 598 720 457 439 56 904 657 161 471 625 262 68 437 883 833 443 758 883 660 435 693 618 21 456 163 238 16 568 173 28 548 844 608 814 69 842 917 788 774 106 585 704 950 115 802 56 457 135 496 193 658 687 355 912 573 91 515 976 182 764 510 505 461 216 376 474 886 731 460 934 520 503 202 331 82 178 752 559 177 787 657 911 877 687 644 636 440 862 139 835 200 399 769 455 109 752 742 412 20 636 418 211 523 758 798 163 329 906 789 282 748 992 322 531 15 761 478 522 610 859 206 893 738 81 229 305 788 775 45 514 505 1 854 699 916 320 476 239 736 815 856 745 215 91 502 962 232 154 287 258 354 133 476 101 540 784 104 489 459 589 984 198 907 958 721 183 529 243 306 184 420 533 334 916 410 192 603 919 348 133 575 337 697 325 718 279 533 117 362 324 320 531 862 668 109 883 225 57 735 62 313 229 641 943 402 488 9 242 415 202 906 412 624 149 584 265 321 40 554 299 453 392 205 72 99

[出力例]
77

[入力例]

4 5 3

[出力例]

※AtCoderテストケースより

[入力例]

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

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

16 30 26 6 33 18 27

[出力例]

[入力例]

129 290 138 144 521 138 541 413 255 462 202 497 245 7 414 246 529 547 342 366 442 348 509 166 67 140 40 115 129 34 476 62 312 390 461 194 352 518 21 436 426 146 220 403 207 152 309 44 472 293 50 133 322 374 544 311 553 499 549 90 293 59 109 279 338 475 307 162 527 404 282 498 258 220 126 268 341 355 160 301 480 331 263 289 393 187 528 182 285 471 345 395 454 209 419 551 137 242 282 186 466 361 63 358 199 209 308 371 31 369 141 534 213 515 262 335 56 103 153 284 218 518 541 15 418 190 435

[出力例]

192

[入力例]

858 582 452 236 475 298 137 74 213 307 808 73 141 585 5 561 770 524 416 663 180 822 70 769 248 730 254 363 19 667 280 235 328 715 291 404 668 496 202 862 56 230 664 582 428 793 559 795 71 891 532 902 582 341 216 519 819 899 968 380 402 405 828 66 472 959 224 204 599 711 651 962 414 33 412 654 689 370 528 512 570 140 114 407 779 945 271 48 168 856 221 279 737 307 957 994 646 214 336 25 760 968 934 318 341 42 780 863 941 507 64 179 315 379 411 612 610 48 831 533 938 525 344 695 420 363 176 824 354 180 787 324 13 729 504 456 996 631 250 840 708 161 620 595 689 316 761 458 60 127 703 701 90 539 156 432 483 540 274 845 416 259 55 133 143 786 969 826 853 195 757 171 963 316 842 744 84 465 281 432 527 146 896 897 507 960 312 997 941 584 524 526 11 663 148 344 53 315 838 486 708 555 273 830 820 346 506 37 485 133 159 417 394 211 73 862 886 930 550 446 550 626 145 624 854 615 624 598 840 895 817 646 640 425 628 434 831 165 993 434 897 248 427 646 936 349 270 512 683 921 961 699 823 79 570 507 923 105 56 826 23 768 562 705 976 25 481 653 511 682 313 945 472 174 858 137 760 540 59 546 983 6 940 236 657 877 863 457 374 791 153 839 709 688 871 333 634 395 66 443 397 659 12 696 993 661 452 795 606 407 582 439 756 31 651 738 858 151 451 565 193 677 112 590 736 734 53 537 192 862 870 352 725 349 936 988 388 639 96 356 156 938 708 335 323 937 986 621 950 33 837 571 958 333 374 873 222 892 96 819 980 542 748 231 161 786 244 441 639 358 843 734 102 802 249 42 222 407 142 564 54 876 430 278 592 498 119 125 451 317 678 814 150 927 887 10 93 916 708 729 669 724 296 733 533 834 412 940 488 529 887 982 915 958 769 977 432 800 995 443 76 164 182 653 40 631 737 249 863 955 199 545 288 396 454 129 905 908 130 389 173 474 257 997 164 74 444 171 465 363 848 689 225 30 26 515 185 477 141 47 293 199 515 362 752 875 500 513 397 602 468 834 758 832 129 878 82 510 651 23 28 369 224 227 962 201 779 596 270 247 328 749 910 803 14 563 561 344 49 3 869 742 874 800 448 109 659 231 986 792 183 831 920 575 460 311 99 306 762 696 370 58 35 306 534 731 128 446 187 113 143 547 149 404 613 816 567 785 367 702 703 881 494 37 931 579 572 572 387 294 74 54 283 265 356 764 364 124 66 202 287 609 350 40 680 344 272 763 311 447 276 782 975 637 98 660 260 545 834 678 865 563 701 773 837 380 592 22 441 608 554 87 421 13 261 48 959 409 955 763 672 438 284 77 86 112 886 528 464 484 801 188 161 301 140 296 252 35 655 115 89 673 915 860 911 980 271 493 876 183 806 719 568 62 187 211 145 66 895 50 13 992 758 710 832 221 949 645 874 86 745 953 369 730 715 389 427 725 633 15 950 318 160 248 290 979 225 550 285 139 231 414 673 853 264 219 33 352 823 430 526 679 489 855 998 638 148 345 976 189 668 336 938 880 567 90 481 847 189 952 151 55 702 956 23 550 647 125 7 276 721 961 556 498 774 448 794 333 100 705 156 714 414 259 534 645 356 140 767 54 691 827 716 742 824 77 694 701 336 212 366 285 148 871 531 487 920 936 442 778 960 928 524 642 460 163 795 334 793 644 890 392 180 683 464 490 397 776 20 718 668 344 408 890 714 399 627 775 276 612 460 336 772 634 302 257 944 695 636 995 116 709 183 397 40 694 101 564 598 720 457 439 56 904 657 161 471 625 262 68 437 883 833 443 758 883 660 435 693 618 21 456 163 238 16 568 173 28 548 844 608 814 69 842 917 788 774 106 585 704 950 115 802 56 457 135 496 193 658 687 355 912 573 91 515 976 182 764 510 505 461 216 376 474 886 731 460 934 520 503 202 331 82 178 752 559 177 787 657 911 877 687 644 636 440 862 139 835 200 399 769 455 109 752 742 412 20 636 418 211 523 758 798 163 329 906 789 282 748 992 322 531 15 761 478 522 610 859 206 893 738 81 229 305 788 775 45 514 505 1 854 699 916 320 476 239 736 815 856 745 215 91 502 962 232 154 287 258 354 133 476 101 540 784 104 489 459 589 984 198 907 958 721 183 529 243 306 184 420 533 334 916 410 192 603 919 348 133 575 337 697 325 718 279 533 117 362 324 320 531 862 668 109 883 225 57 735 62 313 229 641 943 402 488 9 242 415 202 906 412 624 149 584 265 321 40 554 299 453 392 205 72 99

[出力例]

■参照サイト
AtCoder Beginner Contest 236

2022年1月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題C (Route Map) ～問題D (Dance) を解いてみた.

■感想.
1. 問題Dは, 計算量を絞り込む方針が見えなかったので, 解説を参考に実装して, AC版に到達できたと思う.
2. 問題Dは, 何度も提出する羽目になったが, WA原因が, 入力情報を保存する配列サイズが, 小さすぎて, エラーとなっていることが判明し, 今後の教訓となったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    set<string> st;
    vs v;
    rep(i, N){
        char s[22];
        scanf("%s", s);
        string S(s);
        v.pb(S);
    }
    rep(i, M){
        char t[22];
        scanf("%s", t);
        string T(t);
        st.insert(T);
    }
    
    // 2. クエリ回答.
    for(auto &p : v) printf("%s\n", (st.count(p)) ? "Yes" : "No");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

set<string> st;

vs v;

rep(i, N){

char s[22];

scanf("%s", s);

string S(s);

v.pb(S);

}

rep(i, M){

char t[22];

scanf("%s", t);

string T(t);

st.insert(T);

}

// 2. クエリ回答.

for(auto &p : v) printf("%s\n", (st.count(p)) ? "Yes" : "No");

return 0;

}

[入力例]
5 3
tokyo kanda akiba okachi ueno
tokyo akiba ueno

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

[入力例]
7 7
a t c o d e r
a t c o d e r

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

[入力例]
20 9
lcwgenqipr zfrbunslev pdibkpbtdd pwtmemygdc cmvyepxc rfkmmxednu oomsfllbru ezrbdhcf uvgylorliw sieuyjsnnr txbywcr rdjnwydjbh ropmkcmqqq ogtovwoy ckeptdqojl mrprnbxomt aldlg usryxisqok utlcwszbci farwbcne
lcwgenqipr pdibkpbtdd cmvyepxc oomsfllbru ezrbdhcf txbywcr ogtovwoy aldlg farwbcne

[出力例]
Yes
No
Yes
No
Yes
No
Yes
Yes
No
No
Yes
No
No
Yes
No
No
Yes
No
No
Yes

[入力例]

5 3

tokyo kanda akiba okachi ueno

tokyo akiba ueno

[出力例]

Yes

※AtCoderテストケースより

[入力例]

7 7

a t c o d e r

[出力例]

Yes

※AtCoderテストケースより

[入力例]

20 9

lcwgenqipr zfrbunslev pdibkpbtdd pwtmemygdc cmvyepxc rfkmmxednu oomsfllbru ezrbdhcf uvgylorliw sieuyjsnnr txbywcr rdjnwydjbh ropmkcmqqq ogtovwoy ckeptdqojl mrprnbxomt aldlg usryxisqok utlcwszbci farwbcne

lcwgenqipr pdibkpbtdd cmvyepxc oomsfllbru ezrbdhcf txbywcr ogtovwoy aldlg farwbcne

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/abc236/editorial/3285
// 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 a[33][33]; // 配列サイズ要注意.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, 2 * N - 1) repx(j, i + 1, 2 * N) scanf("%d", &a[i][j]);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int befMemo, int curXor, int d) -> int{
        // 2-1. 終了条件.
        if(d == N) return curXor;
        
        // 2-2. ペア一人目を探す.
        int p1 = 0;
        rep(i, 2 * N){
            if(!(befMemo & (1 << (2 * N - i)))){
                p1 = i;
                break;
            }
        }
        
        // 2-3. ペア二人目を探しながら, XOR を 計算.
        int ret = 0;
        int curMemo = befMemo | (1 << (2 * N - p1));
        repx(p2, p1 + 1, 2 * N){
            if(!(curMemo & (1 << (2 * N - p2)))){
                int nexXor = curXor ^ a[p1][p2];
                int nexMemo = curMemo | (1 << (2 * N - p2));
                ret = max(ret, self(self, nexMemo, nexXor, d + 1));
            }
        }
        
        // 2-4. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%d\n", dfs(dfs, 0, 0, 0));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc236/editorial/3285

// 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 a[33][33]; // 配列サイズ要注意.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, 2 * N - 1) repx(j, i + 1, 2 * N) scanf("%d", &a[i][j]);

// 2. dfs.

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

auto dfs = [&](auto&& self, int befMemo, int curXor, int d) -> int{

// 2-1. 終了条件.

if(d == N) return curXor;

// 2-2. ペア一人目を探す.

int p1 = 0;

rep(i, 2 * N){

if(!(befMemo & (1 << (2 * N - i)))){

p1 = i;

break;

}

// 2-3. ペア二人目を探しながら, XOR を計算.

int ret = 0;

int curMemo = befMemo | (1 << (2 * N - p1));

repx(p2, p1 + 1, 2 * N){

if(!(curMemo & (1 << (2 * N - p2)))){

int nexXor = curXor ^ a[p1][p2];

int nexMemo = curMemo | (1 << (2 * N - p2));

ret = max(ret, self(self, nexMemo, nexXor, d + 1));

}

// 2-4. 返却.

return ret;

};

// 3. 出力.

printf("%d\n", dfs(dfs, 0, 0, 0));

return 0;

}

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

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

[入力例]
1
5

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

[入力例]
5
900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467
369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136
138172503 571268336 111747377 595746631 934427285 840101927 757856472
655483844 580613112 445614713 607825444 252585196 725229185
827291247 105489451 58628521 1032791417 152042357
919691140 703307785 100772330 370415195
666350287 691977663 987658020
1039679956 218233643
70938785

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

[入力例]
3
14 15 92 65 35
89 79 32 38
46 26 43
38 32
79

[出力例]
118

[入力例]
5
123 234 345 456 567 678 789 890 901
234 345 456 567 678 789 890 901
345 456 567 678 789 890 901
456 567 678 789 890 901
567 678 789 890 901
678 789 890 901
789 890 901
890 901
901

[出力例]
1002

[入力例]
8
33 41 74 34 17 120 63 28 60 15 66 109 72 71 43
122 115 4 87 94 44 44 75 100 54 12 82 51 41
111 92 39 97 98 104 33 72 77 57 14 99 56
47 89 97 84 36 7 87 116 55 117 13 66
93 18 61 42 99 63 75 10 105 31 70
14 59 97 91 112 119 68 69 109 17
70 34 37 9 113 59 105 47 48
97 50 117 33 93 29 11 83
67 49 38 54 99 45 40
64 71 112 113 19 97
39 95 96 40 107
28 38 49 78
60 69 111
93 13
81

[出力例]
127

[入力例]
8
487139 861602 238520 164035 219099 446008 57720 1070750 1221210 1188858 1219203 923136 864732 363177 954566
419922 652427 810787 1183029 56796 255648 943313 1021792 1106533 34949 1184033 1039329 255017 864084
978644 1234010 1094491 762205 547977 553838 409861 103892 685576 804096 90883 796024 262869
1085316 365039 174833 856988 852486 84100 986363 112387 114824 750889 447938 189952
1134885 325412 522196 35294 257017 223135 1024726 325755 645126 451627 136648
707360 1080890 1205504 178100 1053562 977147 1201855 3036 814479 474568
939809 1138580 1218464 550648 854137 220126 805878 679119 834341
30933 962583 578866 212608 808809 1142922 290941 553016
303617 915128 488234 479671 855889 1136571 643387
26759 1033397 569716 382522 1012306 830053
885272 857909 677947 773771 48951
840700 48568 912933 328071
522956 796084 837213
1158942 370742
182683

[出力例]
2097151

100

101

[入力例]

4 0 1

5 3

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

900606388 317329110 665451442 1045743214 260775845 726039763 57365372 741277060 944347467

369646735 642395945 599952146 86221147 523579390 591944369 911198494 695097136

138172503 571268336 111747377 595746631 934427285 840101927 757856472

655483844 580613112 445614713 607825444 252585196 725229185

827291247 105489451 58628521 1032791417 152042357

919691140 703307785 100772330 370415195

666350287 691977663 987658020

1039679956 218233643

70938785

[出力例]

1073289207

※AtCoderテストケースより

[入力例]

14 15 92 65 35

89 79 32 38

46 26 43

38 32

[出力例]

118

[入力例]

123 234 345 456 567 678 789 890 901

234 345 456 567 678 789 890 901

345 456 567 678 789 890 901

456 567 678 789 890 901

567 678 789 890 901

678 789 890 901

789 890 901

890 901

901

[出力例]

1002

[入力例]

33 41 74 34 17 120 63 28 60 15 66 109 72 71 43

122 115 4 87 94 44 44 75 100 54 12 82 51 41

111 92 39 97 98 104 33 72 77 57 14 99 56

47 89 97 84 36 7 87 116 55 117 13 66

93 18 61 42 99 63 75 10 105 31 70

14 59 97 91 112 119 68 69 109 17

70 34 37 9 113 59 105 47 48

97 50 117 33 93 29 11 83

67 49 38 54 99 45 40

64 71 112 113 19 97

39 95 96 40 107

28 38 49 78

60 69 111

93 13

[出力例]

127

[入力例]

487139 861602 238520 164035 219099 446008 57720 1070750 1221210 1188858 1219203 923136 864732 363177 954566

419922 652427 810787 1183029 56796 255648 943313 1021792 1106533 34949 1184033 1039329 255017 864084

978644 1234010 1094491 762205 547977 553838 409861 103892 685576 804096 90883 796024 262869

1085316 365039 174833 856988 852486 84100 986363 112387 114824 750889 447938 189952

1134885 325412 522196 35294 257017 223135 1024726 325755 645126 451627 136648

707360 1080890 1205504 178100 1053562 977147 1201855 3036 814479 474568

939809 1138580 1218464 550648 854137 220126 805878 679119 834341

30933 962583 578866 212608 808809 1142922 290941 553016

303617 915128 488234 479671 855889 1136571 643387

26759 1033397 569716 382522 1012306 830053

885272 857909 677947 773771 48951

840700 48568 912933 328071

522956 796084 837213

1158942 370742

182683

[出力例]

2097151

■参照サイト
AtCoder Beginner Contest 236

2022年1月26日

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

C++の練習を兼ねて, JOIG 2021/2022 本選過去問の問題D (いちご 2 (Strawberry 2)) を解いてみた.

■感想.
1. 問題Dは, 方針を絞り込めたので, AC版に到達できたので十分だと思う.
2. 個人的には, 数え上げの方法に, std::map を使う方針が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト JOIG 2021/2022 本選過去問解説の各リンクをご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    map<P, int> m;
    rep(i, N){
        scanf("%d %d", &a[i], &b[i]);
        m[{a[i], b[i]}]++;
    }
    
    // 2. 取得可能ないちごの最大数は？
    int ans = 0;
    rep(i, N){
        // i番目のいちごを基準に, 81通りチェック.
        for(auto dh : {-2, -1, 0}){
            for(auto dw : {-2, -1, 0}){
                // (基準とする)左上の位置.
                int hBase = a[i] + dh;
                int wBase = b[i] + dw;
                
                // 縦3行, 横3行 の いちごを集計.
                int t = 0;
                rep(h, 3){
                    rep(w, 3){
                        int hCur = hBase + h;
                        int wCur = wBase + w;
                        if(hCur >= 1 && wCur >= 1 && hCur <= H && wCur <= W) t += m[{hCur, wCur}];
                    }
                }
                
                // 最大値更新.
                ans = max(ans, t);
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;

}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

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

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

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

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

int a[60606], b[60606];

int main(){

// 1. 入力情報.

int H, W, N;

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

map<P, int> m;

rep(i, N){

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

m[{a[i], b[i]}]++;

}

// 2. 取得可能ないちごの最大数は？

int ans = 0;

rep(i, N){

// i番目のいちごを基準に, 81通りチェック.

for(auto dh : {-2, -1, 0}){

for(auto dw : {-2, -1, 0}){

// (基準とする)左上の位置.

int hBase = a[i] + dh;

int wBase = b[i] + dw;

// 縦3行, 横3行のいちごを集計.

int t = 0;

rep(h, 3){

rep(w, 3){

int hCur = hBase + h;

int wCur = wBase + w;

if(hCur >= 1 && wCur >= 1 && hCur <= H && wCur <= W) t += m[{hCur, wCur}];

}

// 最大値更新.

ans = max(ans, t);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

[入力例]
3 99999
9
1 77813
2 77813
3 77813
1 77814
2 77814
3 77814
1 77815
2 77815
3 77815

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

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

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

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

[出力例]
18

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

[入力例]

4 5

1 1

1 5

2 2

2 4

3 3

4 2

4 4

[出力例]

※AtCoderテストケースより

[入力例]

3 5

1 1

1 2

2 1

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

3 99999

1 77813

2 77813

3 77813

1 77814

2 77814

3 77814

1 77815

2 77815

3 77815

[出力例]

※AtCoderテストケースより

[入力例]

11 11

7 7

6 11

5 7

8 8

9 9

5 5

8 4

4 4

4 8

2 6

1 6

6 2

3 3

9 3

7 5

6 1

10 6

6 10

11 6

3 9

[出力例]

※AtCoderテストケースより

[入力例]

6 7

6 3

4 5

3 3

3 2

1 7

5 7

2 5

4 4

6 5

1 2

2 1

5 7

4 3

6 5

1 2

4 5

5 4

6 5

2 6

2 5

5 2

4 3

2 1

6 6

2 1

6 7

5 2

4 1

4 5

4 3

1 2

3 2

5 2

2 5

4 7

4 3

5 2

2 1

2 6

2 1

4 3

5 2

2 5

1 7

2 5

1 7

2 5

3 4

4 1

4 3

[出力例]

■参照サイト
JOIG 2021/2022 本選過去問

2022年1月25日2022年1月25日

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

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題A (Erase by Value) ～問題B (Dividing Subsequence) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. LIS(Longest increase subsequence) の応用版(追加条件) を, 確認することができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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--)

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. x を 求める.
    int x = a[0];
    rep(i, N){
        // 減少.
        if(x > a[i]) break;
        
        // 増加.
        if(x < a[i]) x = a[i];
    }
    
    // 3. 出力.
    rep(i, N){
        if(a[i] == x) continue;
        else          printf("%d ", a[i]);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi a(N);

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

// 2. x を求める.

int x = a[0];

rep(i, N){

// 減少.

if(x > a[i]) break;

// 増加.

if(x < a[i]) x = a[i];

}

// 3. 出力.

rep(i, N){

if(a[i] == x) continue;

else printf("%d ", a[i]);

}

return 0;

}

[入力例]
5
2 4 4 1 2

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

[入力例]
3
1 1 1

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

[入力例]
5
1 1 2 3 3

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

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

[出力例]
1 4 1 5 9 2 

[入力例]
20
1 1 2 2 3 3 5 5 7 7 7 7 11 11 11 10 5 3 2 1

[出力例]
1 1 2 2 3 3 5 5 7 7 7 7 10 5 3 2 1

[入力例]

2 4 4 1 2

[出力例]

2 1 2

※AtCoderのテストケースより

[入力例]

1 1 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 2 3 3

[出力例]

1 1 2

※AtCoderのテストケースより

[入力例]

3 1 4 1 5 9 2

[出力例]

1 4 1 5 9 2

[入力例]

1 1 2 2 3 3 5 5 7 7 7 7 11 11 11 10 5 3 2 1

[出力例]

1 1 2 2 3 3 5 5 7 7 7 7 10 5 3 2 1

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

// 解き直し.
// https://atcoder.jp/contests/arc133/editorial/3283
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
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 p[202020], q[202020];

int main(){
    
    // 1. 入力情報.
    int N, x;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &x);
        p[x] = i + 1;
    }
    rep(i, N){
        scanf("%d", &x);
        q[x] = i + 1;
    }
    
    // 2. Q[j] が P[i] の 倍数になっているペアは？
    vp v;
    repx(i, 1, N + 1) repex(j, i, N + 1, i) v.pb({p[i], -q[j]});
    
    // 3. sort.
    sort(all(v));
    
    // 4. 狭義単調増加な数列の長さの最大値は？
    // 以下の問題を参照.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    for(auto &p : v){
        // 数列を保存.
        // -> 但し, 符号を反転したもので, 保存等を行うこと.
        if(dp.size() == 0 || dp.back() < -p.b){
            dp.pb(-p.b);
        }else{
            int at = lower_bound(all(dp), -p.b) - dp.begin();
            dp[at] = -p.b;
        }
    }
    
    // 5. 出力.
    printf("%d\n", dp.size());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc133/editorial/3283

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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 p[202020], q[202020];

int main(){

// 1. 入力情報.

int N, x;

scanf("%d", &N);

rep(i, N){

scanf("%d", &x);

p[x] = i + 1;

}

rep(i, N){

scanf("%d", &x);

q[x] = i + 1;

}

// 2. Q[j] が P[i] の倍数になっているペアは？

vp v;

repx(i, 1, N + 1) repex(j, i, N + 1, i) v.pb({p[i], -q[j]});

// 3. sort.

sort(all(v));

// 4. 狭義単調増加な数列の長さの最大値は？

// 以下の問題を参照.

// https://atcoder.jp/contests/typical90/tasks/typical90_bh

// -> LIS(Longest increase subsequence) を利用.

vi dp;

for(auto &p : v){

// 数列を保存.

// -> 但し, 符号を反転したもので, 保存等を行うこと.

if(dp.size() == 0 || dp.back() < -p.b){

dp.pb(-p.b);

}else{

int at = lower_bound(all(dp), -p.b) - dp.begin();

dp[at] = -p.b;

}

// 5. 出力.

printf("%d\n", dp.size());

return 0;

}

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

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

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

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

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

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

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

[出力例]
10

[入力例]
100
68 49 78 16 97 82 47 41 69 44 38 45 36 32 92 66 33 10 57 94 52 100 30 75 59 89 37 83 11 55 17 60 50 71 28 2 20 12 81 53 3 96 19 42 14 1 67 70 58 72 23 98 51 56 84 95 6 26 79 73 8 13 48 5 80 63 29 85 76 31 34 90 25 65 86 99 54 77 62 74 91 7 87 35 22 4 9 40 43 64 27 24 15 93 46 61 18 21 39 88
78 11 52 79 82 46 90 8 83 80 39 58 35 54 3 6 75 51 76 27 13 96 33 25 65 2 43 20 92 21 60 84 9 74 30 63 32 19 22 14 86 55 15 85 100 61 37 34 81 23 1 40 26 59 94 47 70 88 89 71 62 69 87 7 68 66 4 44 48 36 95 67 10 38 12 64 45 72 24 16 28 93 99 17 53 42 18 29 97 41 56 49 91 73 77 5 50 98 31 57

[出力例]
27

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

[出力例]
45

[入力例]

3 1 4 2

4 2 1 3

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 4 5

5 4 3 2 1

[出力例]

※AtCoderのテストケースより

[入力例]

4 3 1 10 9 2 8 6 5 7

9 6 5 4 2 3 8 10 1 7

[出力例]

※AtCoderのテストケースより

[入力例]

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

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

[出力例]

[入力例]

100

68 49 78 16 97 82 47 41 69 44 38 45 36 32 92 66 33 10 57 94 52 100 30 75 59 89 37 83 11 55 17 60 50 71 28 2 20 12 81 53 3 96 19 42 14 1 67 70 58 72 23 98 51 56 84 95 6 26 79 73 8 13 48 5 80 63 29 85 76 31 34 90 25 65 86 99 54 77 62 74 91 7 87 35 22 4 9 40 43 64 27 24 15 93 46 61 18 21 39 88

78 11 52 79 82 46 90 8 83 80 39 58 35 54 3 6 75 51 76 27 13 96 33 25 65 2 43 20 92 21 60 84 9 74 30 63 32 19 22 14 86 55 15 85 100 61 37 34 81 23 1 40 26 59 94 47 70 88 89 71 62 69 87 7 68 66 4 44 48 36 95 67 10 38 12 64 45 72 24 16 28 93 99 17 53 42 18 29 97 41 56 49 91 73 77 5 50 98 31 57

[出力例]

[入力例]

250

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

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

[出力例]

■参照サイト
AtCoder Regular Contest 133
060 – Chimera

2022年1月25日2022年1月25日

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

C++の練習を兼ねて, AtCoder Beginner Contest 037 の問題D (経路) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 本問は, メモ化再帰の例題として, 学習した内容である.
相変わらず, メモ化再帰の本質が見えてないため, 理解が進むまでは, 本問を, 典型的な例題として, いったん丸暗記の方針とした.
とはいえ, メモ化再帰は, 以下の構成要素(ロジック)が含まれていると, とりあえず理解した.
① 第一段階 … メモ化が終わっているか確認する作業, 再帰処理の終了条件として使用する.
② 第二段階 … 再帰処理の実装, 本問では, “経路数” を知りたいので, 経路数を集計する実装が必要.
③ 第三段階 … メモ化が終わってないため, メモ化の作業を追加, なお, 本問では, メモ化の対象は, “経路数” と理解.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/data/abc/037/editorial.pdf
// 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--)
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
const LL MOD = 1e9 + 7;

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vvl a(H, vl(W));
    rep(i, H) rep(j, W) scanf("%lld", &a[i][j]);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    vvl dp(H, vl(W));
    auto dfs = [&](auto self, int hCur, int wCur) -> LL{
        // 2-1. 終了条件.
        // -> 前回以前に, メモ化が完了しているため終了.
        if(dp[hCur][wCur]) return dp[hCur][wCur];
        
        // 2-2. 経路数 f(i, j) の 計算.
        LL ret = 1;
        rep(i, 4){
            // 移動先候補.
            int hNex = hCur + dy[i];
            int wNex = wCur + dx[i];
            
            // 移動不可能.
            if(wNex < 0 || wNex >= W || hNex < 0 || hNex >= H) continue;
            
            // 移動可能.
            if(a[hCur][wCur] < a[hNex][wNex]) ret = (ret + self(self, hNex, wNex)) % MOD;
        }
        
        // 2-3. メモ化.
        // -> まだ, メモ化していないマスに対して, メモ化する.
        //    ここで, 本問でのメモ化対象は, 解説にある f(i, j) を dp[i][j] に保存(メモ化)すると理解.
        return dp[hCur][wCur] = ret;
    };
    
    // 3. 集計.
    LL ans = 0;
    rep(i, H) rep(j, W) ans = (ans + dfs(dfs, i, j)) % MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/data/abc/037/editorial.pdf

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

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

const LL MOD = 1e9 + 7;

int main(){

// 1. 入力情報.

int H, W;

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

vvl a(H, vl(W));

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

// 2. dfs.

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

vvl dp(H, vl(W));

auto dfs = [&](auto self, int hCur, int wCur) -> LL{

// 2-1. 終了条件.

// -> 前回以前に, メモ化が完了しているため終了.

if(dp[hCur][wCur]) return dp[hCur][wCur];

// 2-2. 経路数 f(i, j) の計算.

LL ret = 1;

rep(i, 4){

// 移動先候補.

int hNex = hCur + dy[i];

int wNex = wCur + dx[i];

// 移動不可能.

if(wNex < 0 || wNex >= W || hNex < 0 || hNex >= H) continue;

// 移動可能.

if(a[hCur][wCur] < a[hNex][wNex]) ret = (ret + self(self, hNex, wNex)) % MOD;

}

// 2-3. メモ化.

// -> まだ, メモ化していないマスに対して, メモ化する.

// ここで, 本問でのメモ化対象は, 解説にある f(i, j) を dp[i][j] に保存(メモ化)すると理解.

return dp[hCur][wCur] = ret;

};

// 3. 集計.

LL ans = 0;

rep(i, H) rep(j, W) ans = (ans + dfs(dfs, i, j)) % MOD;

// 4. 出力.

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

return 0;

}

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

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

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

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


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

[出力例]
77

[入力例]
20 10
6 44 80 52 78 83 4 44 83 71
62 78 40 65 94 29 59 74 23 116
75 14 103 67 18 7 15 73 116 12
44 14 64 103 9 3 122 40 91 12
96 48 71 14 87 13 41 57 29 88
112 39 39 53 108 69 18 8 113 22
85 37 9 48 4 34 101 119 28 12
51 35 30 28 76 51 107 106 20 121
49 118 9 67 89 92 54 97 123 32
68 83 37 102 119 54 67 60 2 64
105 72 81 107 50 92 51 30 30 78
122 32 20 3 33 42 112 45 14 118
108 13 64 33 49 82 104 63 115 115
36 96 83 57 120 58 23 54 77 41
120 47 113 34 100 99 84 79 70 12
4 114 98 118 104 116 78 14 5 121
46 8 97 64 68 117 115 90 57 120
13 117 23 106 27 23 11 74 57 73
86 75 80 6 115 75 79 36 45 59
13 66 103 28 89 92 54 114 114 9

[出力例]
1335

[入力例]
25 30
111 59 96 84 98 107 13 25 75 36 8 14 13 115 29 24 37 5 75 100 2 100 101 81 24 9 4 90 120 26
35 21 47 111 103 69 95 40 34 17 8 82 34 75 34 90 30 103 16 22 84 71 49 13 30 26 47 9 60 34
43 4 36 64 60 114 37 121 77 102 38 123 77 121 86 22 43 80 76 30 89 57 60 7 40 11 7 96 66 55
2 73 105 40 45 90 89 37 8 113 10 102 47 109 82 114 19 52 55 72 39 57 53 70 122 83 4 23 38 46
72 66 110 28 39 101 63 59 68 82 110 65 9 106 118 115 122 102 42 3 71 43 114 20 81 97 71 113 51 39
62 62 104 45 1 23 23 36 66 63 76 3 24 109 68 70 66 38 85 68 21 98 74 118 107 60 117 11 40 117
84 52 61 30 122 92 50 87 94 114 108 52 91 48 97 31 120 67 67 93 55 33 17 70 22 15 30 95 36 93
43 66 117 31 8 11 53 47 69 13 110 51 118 117 92 2 84 119 18 34 18 34 16 86 55 103 52 51 47 92
41 36 106 70 93 108 41 117 119 120 89 85 37 7 123 55 69 44 112 30 77 76 67 25 63 40 89 107 111 22
18 6 25 9 55 69 120 24 14 92 58 64 109 84 113 68 46 103 56 105 13 108 8 29 36 31 58 115 30 5
119 54 98 77 96 46 39 59 65 77 77 105 20 20 79 13 83 78 66 5 31 27 43 60 102 5 23 119 55 23
52 46 84 105 15 105 92 81 32 70 25 17 58 70 17 102 115 85 65 37 59 92 66 80 90 22 5 15 45 89
22 65 43 58 105 40 33 29 113 37 59 53 81 113 116 88 51 20 42 82 32 5 91 3 99 98 11 97 99 72
106 2 87 16 38 55 118 63 30 68 9 57 114 36 102 40 110 46 42 3 72 116 104 98 51 59 95 3 10 25
110 117 103 18 32 78 2 42 49 111 51 40 121 18 34 5 32 87 1 64 81 43 45 106 69 36 100 68 77 38
27 37 121 44 93 89 79 62 120 64 56 70 47 101 96 102 50 119 117 112 108 95 109 85 110 104 91 121 9 2
93 83 30 98 92 36 92 90 88 25 5 23 27 116 72 76 71 17 20 67 94 83 100 56 77 26 66 23 90 58
46 51 5 115 11 21 52 38 28 4 113 27 44 72 32 39 19 11 38 38 99 3 46 52 14 22 47 68 31 13
46 118 103 11 14 79 77 113 90 99 33 87 54 96 90 92 35 1 89 16 36 109 38 65 81 25 34 8 50 24
34 45 10 44 23 103 57 96 86 122 37 84 33 64 85 41 59 38 105 55 45 10 32 87 107 106 10 2 84 42
53 8 23 34 73 77 24 39 10 91 18 58 85 88 112 44 38 64 58 69 72 57 101 39 51 86 32 85 40 91
17 11 6 88 26 31 79 91 106 4 23 64 5 78 48 108 89 95 59 64 33 80 33 73 12 30 52 78 96 109
72 10 120 18 42 4 36 48 16 45 40 58 52 28 74 49 85 15 123 33 114 12 52 65 6 105 86 62 38 49
5 86 76 106 22 28 111 78 8 33 73 14 116 84 85 113 54 99 80 37 4 91 123 85 120 3 114 79 66 98
52 76 26 102 32 28 54 37 60 104 9 104 47 20 90 25 29 53 84 22 3 122 121 109 72 3 5 76 31 58

[出力例]
5185

[入力例]

2 3

1 4 5

2 4 9

[出力例]

※AtCoderテストケースより

[入力例]

6 6

1 3 4 6 7 5

1 2 4 8 8 7

2 7 9 2 7 2

9 4 2 7 6 5

2 8 4 6 7 6

3 7 9 1 2 7

[出力例]

170

※AtCoderテストケースより

[入力例]

3 3

1 2 3

6 5 4

7 8 9

[出力例]

[入力例]

20 10

6 44 80 52 78 83 4 44 83 71

62 78 40 65 94 29 59 74 23 116

75 14 103 67 18 7 15 73 116 12

44 14 64 103 9 3 122 40 91 12

96 48 71 14 87 13 41 57 29 88

112 39 39 53 108 69 18 8 113 22

85 37 9 48 4 34 101 119 28 12

51 35 30 28 76 51 107 106 20 121

49 118 9 67 89 92 54 97 123 32

68 83 37 102 119 54 67 60 2 64

105 72 81 107 50 92 51 30 30 78

122 32 20 3 33 42 112 45 14 118

108 13 64 33 49 82 104 63 115 115

36 96 83 57 120 58 23 54 77 41

120 47 113 34 100 99 84 79 70 12

4 114 98 118 104 116 78 14 5 121

46 8 97 64 68 117 115 90 57 120

13 117 23 106 27 23 11 74 57 73

86 75 80 6 115 75 79 36 45 59

13 66 103 28 89 92 54 114 114 9

[出力例]

1335

[入力例]

25 30

111 59 96 84 98 107 13 25 75 36 8 14 13 115 29 24 37 5 75 100 2 100 101 81 24 9 4 90 120 26

35 21 47 111 103 69 95 40 34 17 8 82 34 75 34 90 30 103 16 22 84 71 49 13 30 26 47 9 60 34

43 4 36 64 60 114 37 121 77 102 38 123 77 121 86 22 43 80 76 30 89 57 60 7 40 11 7 96 66 55

2 73 105 40 45 90 89 37 8 113 10 102 47 109 82 114 19 52 55 72 39 57 53 70 122 83 4 23 38 46

72 66 110 28 39 101 63 59 68 82 110 65 9 106 118 115 122 102 42 3 71 43 114 20 81 97 71 113 51 39

62 62 104 45 1 23 23 36 66 63 76 3 24 109 68 70 66 38 85 68 21 98 74 118 107 60 117 11 40 117

84 52 61 30 122 92 50 87 94 114 108 52 91 48 97 31 120 67 67 93 55 33 17 70 22 15 30 95 36 93

43 66 117 31 8 11 53 47 69 13 110 51 118 117 92 2 84 119 18 34 18 34 16 86 55 103 52 51 47 92

41 36 106 70 93 108 41 117 119 120 89 85 37 7 123 55 69 44 112 30 77 76 67 25 63 40 89 107 111 22

18 6 25 9 55 69 120 24 14 92 58 64 109 84 113 68 46 103 56 105 13 108 8 29 36 31 58 115 30 5

119 54 98 77 96 46 39 59 65 77 77 105 20 20 79 13 83 78 66 5 31 27 43 60 102 5 23 119 55 23

52 46 84 105 15 105 92 81 32 70 25 17 58 70 17 102 115 85 65 37 59 92 66 80 90 22 5 15 45 89

22 65 43 58 105 40 33 29 113 37 59 53 81 113 116 88 51 20 42 82 32 5 91 3 99 98 11 97 99 72

106 2 87 16 38 55 118 63 30 68 9 57 114 36 102 40 110 46 42 3 72 116 104 98 51 59 95 3 10 25

110 117 103 18 32 78 2 42 49 111 51 40 121 18 34 5 32 87 1 64 81 43 45 106 69 36 100 68 77 38

27 37 121 44 93 89 79 62 120 64 56 70 47 101 96 102 50 119 117 112 108 95 109 85 110 104 91 121 9 2

93 83 30 98 92 36 92 90 88 25 5 23 27 116 72 76 71 17 20 67 94 83 100 56 77 26 66 23 90 58

46 51 5 115 11 21 52 38 28 4 113 27 44 72 32 39 19 11 38 38 99 3 46 52 14 22 47 68 31 13

46 118 103 11 14 79 77 113 90 99 33 87 54 96 90 92 35 1 89 16 36 109 38 65 81 25 34 8 50 24

34 45 10 44 23 103 57 96 86 122 37 84 33 64 85 41 59 38 105 55 45 10 32 87 107 106 10 2 84 42

53 8 23 34 73 77 24 39 10 91 18 58 85 88 112 44 38 64 58 69 72 57 101 39 51 86 32 85 40 91

17 11 6 88 26 31 79 91 106 4 23 64 5 78 48 108 89 95 59 64 33 80 33 73 12 30 52 78 96 109

72 10 120 18 42 4 36 48 16 45 40 58 52 28 74 49 85 15 123 33 114 12 52 65 6 105 86 62 38 49

5 86 76 106 22 28 111 78 8 33 73 14 116 84 85 113 54 99 80 37 4 91 123 85 120 3 114 79 66 98

52 76 26 102 32 28 54 37 60 104 9 104 47 20 90 25 29 53 84 22 3 122 121 109 72 3 5 76 31 58

[出力例]

5185

■参照サイト
AtCoder Beginner Contest 037

2022年1月23日

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

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 個人的には, 特殊な性質を持つグラフを抽出するロジックが, 面白いと感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char x[101010];
    scanf("%s", x);
    string s(x);
    int N = s.size();
    
    // 2. 条件を満たすか？
    bool ok = true;
    if(s[0] != '1' || s[N - 1] != '0') ok = false;
    repx(i, 1, N - 1) if(s[i] != s[N - 2 - i]) ok = false;
    
    // 3. 例外.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 4. グラフ構築.
    // 4-1. 根 を 設定.
    s[N - 1] = '1';
    
    // 4-2. 文字 '1'.
    vp ans(N - 1);
    int c = 0;
    repx(i, 1, N){
        if(s[i] == '1'){
            // {子頂点, 親頂点} を 設定.
            ans[c] = {c + 1, i + 1};
            
            // 子頂点更新.
            c = i;
        }
    }
    
    // 4-3. 文字 '0'.
    rep(i, N){
        // 子頂点 を 設定.
        if(s[i] == '1') c = ans[i].b;
        
        // {子頂点, 親頂点} を 設定.
        if(s[i] == '0') ans[i] = {c, i + 1};
    }
    
    // 5. 出力.
    for(auto &p : ans) printf("%d %d\n", p.a, p.b);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

int main(){

// 1. 入力情報.

char x[101010];

scanf("%s", x);

string s(x);

int N = s.size();

// 2. 条件を満たすか？

bool ok = true;

if(s[0] != '1' || s[N - 1] != '0') ok = false;

repx(i, 1, N - 1) if(s[i] != s[N - 2 - i]) ok = false;

// 3. 例外.

if(!ok){

puts("-1");

return 0;

}

// 4. グラフ構築.

// 4-1. 根を設定.

s[N - 1] = '1';

// 4-2. 文字 '1'.

vp ans(N - 1);

int c = 0;

repx(i, 1, N){

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

// {子頂点, 親頂点} を設定.

ans[c] = {c + 1, i + 1};

// 子頂点更新.

c = i;

}

// 4-3. 文字 '0'.

rep(i, N){

// 子頂点を設定.

if(s[i] == '1') c = ans[i].b;

// {子頂点, 親頂点} を設定.

if(s[i] == '0') ans[i] = {c, i + 1};

}

// 5. 出力.

for(auto &p : ans) printf("%d %d\n", p.a, p.b);

return 0;

}

[入力例]
1111

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

[入力例]
1110

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

[入力例]
1010

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

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

[入力例]
1001110010

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

[入力例]
11000010101010000110

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

[入力例]

1111

[出力例]

-1

※AtCoderテストケースより

[入力例]

1110

[出力例]

1 2

2 3

3 4

※AtCoderテストケースより

[入力例]

1010

[出力例]

1 2

1 3

1 4

※AtCoderテストケースより

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

1 3

3 2

3 4

[入力例]

1001110010

[出力例]

1 4

4 2

4 3

4 5

5 6

6 9

9 7

9 8

9 10

[入力例]

11000010101010000110

[出力例]

1 2

2 7

7 3

7 4

7 5

7 6

7 9

9 8

9 11

11 10

11 13

13 12

13 18

18 14

18 15

18 16

18 17

18 19

19 20

■参照サイト
AtCoder Regular Contest 103

個人用メモ帳

投稿

Python（Qiskit）について（１８）

概要

感想

Hello Qiskitゲーム

参照サイト

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

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題C (Row Column Sums) を解いてみた.

Python（Qiskit）について（１７）

概要

感想

Hello Qiskitゲーム

参照サイト

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題C (Route Map) ～問題D (Dance) を解いてみた.

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

C++の練習を兼ねて, JOIG 2021/2022 本選過去問の問題D (いちご 2 (Strawberry 2)) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題A (Erase by Value) ～問題B (Dividing Subsequence) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 037 の問題D (経路) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.

概要

感想

Hello Qiskitゲーム

参照サイト

C++の練習を兼ねて, AtCoder Regular Contest 133 の 問題C (Row Column Sums) を解いてみた.

概要

感想

Hello Qiskitゲーム

参照サイト

C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題E (Average and Median) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の 問題C (Route Map) ～ 問題D (Dance) を解いてみた.

C++の練習を兼ねて, JOIG 2021/2022 本選 過去問 の 問題D (いちご 2 (Strawberry 2)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の 問題A (Erase by Value) ～ 問題B (Dividing Subsequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 037 の 問題D (経路) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 103 の 問題E (Tr/ee) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題C (Row Column Sums) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題E (Average and Median) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 236 の問題C (Route Map) ～問題D (Dance) を解いてみた.

C++の練習を兼ねて, JOIG 2021/2022 本選過去問の問題D (いちご 2 (Strawberry 2)) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 133 の問題A (Erase by Value) ～問題B (Dividing Subsequence) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 037 の問題D (経路) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 103 の問題E (Tr/ee) を解いてみた.