個人用メモ帳

2023年9月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題C (Harmonic Mean) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 解説のロジックで, 解けることが興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6695
// C++20(GCC 12.2)
#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--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. N = k * (k - 1) のパターンは？
    set<int> st;
    repx(i, 1, 23) st.insert(i * (i + 1));
    
    // 3. 各テストケース.
    rep(i, T){
        // 3-1. テストケース入力情報.
        int N;
        scanf("%d", &N);
        
        // 3-2. N = 1.
        if(N == 1) puts("Yes\n1");
        
        // 3-3. N = 2.
        if(N == 2){
            puts("No");
        }
        
        // 3-4. N >= 3.
        if(N >= 3){
            // N = k * (k - 1) のパターン.
            vi ans;
            if(st.count(N)){
                ans.pb(2);
                repx(j, 1, N - 1) ans.pb(2 * j * (j + 1));
                ans.pb(2 * (N - 1));
            }
            
            // 上記以外.
            if(!st.count(N)){
                repx(j, 1, N) ans.pb(j * (j + 1));
                ans.pb(N);
            }
            
            // 出力.
            puts("Yes");
            rep(j, N) printf("%d%s", ans[j], (j < N - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6695

// C++20(GCC 12.2)

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

#define pb push_back

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. N = k * (k - 1) のパターンは？

set<int> st;

repx(i, 1, 23) st.insert(i * (i + 1));

// 3. 各テストケース.

rep(i, T){

// 3-1. テストケース入力情報.

int N;

scanf("%d", &N);

// 3-2. N = 1.

if(N == 1) puts("Yes\n1");

// 3-3. N = 2.

if(N == 2){

puts("No");

}

// 3-4. N >= 3.

if(N >= 3){

// N = k * (k - 1) のパターン.

vi ans;

if(st.count(N)){

ans.pb(2);

repx(j, 1, N - 1) ans.pb(2 * j * (j + 1));

ans.pb(2 * (N - 1));

}

// 上記以外.

if(!st.count(N)){

repx(j, 1, N) ans.pb(j * (j + 1));

ans.pb(N);

}

// 出力.

puts("Yes");

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

}

return 0;

}

[入力例]
2
3
5

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

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
2 6 3
Yes
2 6 12 20 5

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

[出力例]
Yes
1
No
Yes
2 6 3
Yes
2 6 12 4
Yes
2 6 12 20 5
Yes
2 4 12 24 40 10
Yes
2 6 12 20 30 42 7
Yes
2 6 12 20 30 42 56 8
Yes
2 6 12 20 30 42 56 72 9
Yes
2 6 12 20 30 42 56 72 90 10

[入力例]
20
11
12
18
24
30
55
72
77
99
100
111
132
125
200
222
240
333
345
462
500

[出力例]
Yes
2 6 12 20 30 42 56 72 90 110 11
Yes
2 4 12 24 40 60 84 112 144 180 220 22
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 18
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 24
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 58
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 55
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 142
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 77
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 99
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 100
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 111
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 262
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 125
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 200
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 222
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 478
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 333
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 345
Yes
2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 114720 115680 116644 117612 118584 119560 120540 121524 122512 123504 124500 125500 126504 127512 128524 129540 130560 131584 132612 133644 134680 135720 136764 137812 138864 139920 140980 142044 143112 144184 145260 146340 147424 148512 149604 150700 151800 152904 154012 155124 156240 157360 158484 159612 160744 161880 163020 164164 165312 166464 167620 168780 169944 171112 172284 173460 174640 175824 177012 178204 179400 180600 181804 183012 184224 185440 186660 187884 189112 190344 191580 192820 194064 195312 196564 197820 199080 200344 201612 202884 204160 205440 206724 208012 209304 210600 211900 213204 214512 215824 217140 218460 219784 221112 222444 223780 225120 226464 227812 229164 230520 231880 233244 234612 235984 237360 238740 240124 241512 242904 244300 245700 247104 248512 249924 251340 252760 254184 255612 257044 258480 259920 261364 262812 264264 265720 267180 268644 270112 271584 273060 274540 276024 277512 279004 280500 282000 283504 285012 286524 288040 289560 291084 292612 294144 295680 297220 298764 300312 301864 303420 304980 306544 308112 309684 311260 312840 314424 316012 317604 319200 320800 322404 324012 325624 327240 328860 330484 332112 333744 335380 337020 338664 340312 341964 343620 345280 346944 348612 350284 351960 353640 355324 357012 358704 360400 362100 363804 365512 367224 368940 370660 372384 374112 375844 377580 379320 381064 382812 384564 386320 388080 389844 391612 393384 395160 396940 398724 400512 402304 404100 405900 407704 409512 411324 413140 414960 416784 418612 420444 422280 424120 922
Yes
2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 119370 120062 120756 121452 122150 122850 123552 124256 124962 125670 126380 127092 127806 128522 129240 129960 130682 131406 132132 132860 133590 134322 135056 135792 136530 137270 138012 138756 139502 140250 141000 141752 142506 143262 144020 144780 145542 146306 147072 147840 148610 149382 150156 150932 151710 152490 153272 154056 154842 155630 156420 157212 158006 158802 159600 160400 161202 162006 162812 163620 164430 165242 166056 166872 167690 168510 169332 170156 170982 171810 172640 173472 174306 175142 175980 176820 177662 178506 179352 180200 181050 181902 182756 183612 184470 185330 186192 187056 187922 188790 189660 190532 191406 192282 193160 194040 194922 195806 196692 197580 198470 199362 200256 201152 202050 202950 203852 204756 205662 206570 207480 208392 209306 210222 211140 212060 212982 213906 214832 215760 216690 217622 218556 219492 220430 221370 222312 223256 224202 225150 226100 227052 228006 228962 229920 230880 231842 232806 233772 234740 235710 236682 237656 238632 239610 240590 241572 242556 243542 244530 245520 246512 247506 248502 249500 500

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

[入力例]

[出力例]

Yes

2 3 6

Yes

3 4 5 6 20

※AtCoderのテストケースより

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

Yes

2 6 3

Yes

2 6 12 20 5

[入力例]

[出力例]

Yes

2 6 3

Yes

2 6 12 4

Yes

2 6 12 20 5

Yes

2 4 12 24 40 10

Yes

2 6 12 20 30 42 7

Yes

2 6 12 20 30 42 56 8

Yes

2 6 12 20 30 42 56 72 9

Yes

2 6 12 20 30 42 56 72 90 10

[入力例]

100

111

132

125

200

222

240

333

345

462

500

[出力例]

Yes

2 6 12 20 30 42 56 72 90 110 11

Yes

2 4 12 24 40 60 84 112 144 180 220 22

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 18

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 24

Yes

2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 58

Yes

2 4 12 24 40 60 84 112 144 180 220 264 312 364 420 480 544 612 684 760 840 924 1012 1104 1200 1300 1404 1512 1624 1740 1860 1984 2112 2244 2380 2520 2664 2812 2964 3120 3280 3444 3612 3784 3960 4140 4324 4512 4704 4900 5100 5304 5512 5724 5940 6160 6384 6612 6844 7080 7320 7564 7812 8064 8320 8580 8844 9112 9384 9660 9940 10224 10512 10804 11100 11400 11704 12012 12324 12640 12960 13284 13612 13944 14280 14620 14964 15312 15664 16020 16380 16744 17112 17484 17860 18240 18624 19012 19404 19800 20200 20604 21012 21424 21840 22260 22684 23112 23544 23980 24420 24864 25312 25764 26220 26680 27144 27612 28084 28560 29040 29524 30012 30504 31000 31500 32004 32512 33024 33540 34060 34584 35112 35644 36180 36720 37264 37812 38364 38920 39480 40044 40612 41184 41760 42340 42924 43512 44104 44700 45300 45904 46512 47124 47740 48360 48984 49612 50244 50880 51520 52164 52812 53464 54120 54780 55444 56112 56784 57460 58140 58824 59512 60204 60900 61600 62304 63012 63724 64440 65160 65884 66612 67344 68080 68820 69564 70312 71064 71820 72580 73344 74112 74884 75660 76440 77224 78012 78804 79600 80400 81204 82012 82824 83640 84460 85284 86112 86944 87780 88620 89464 90312 91164 92020 92880 93744 94612 95484 96360 97240 98124 99012 99904 100800 101700 102604 103512 104424 105340 106260 107184 108112 109044 109980 110920 111864 112812 113764 114720 115680 116644 117612 118584 119560 120540 121524 122512 123504 124500 125500 126504 127512 128524 129540 130560 131584 132612 133644 134680 135720 136764 137812 138864 139920 140980 142044 143112 144184 145260 146340 147424 148512 149604 150700 151800 152904 154012 155124 156240 157360 158484 159612 160744 161880 163020 164164 165312 166464 167620 168780 169944 171112 172284 173460 174640 175824 177012 178204 179400 180600 181804 183012 184224 185440 186660 187884 189112 190344 191580 192820 194064 195312 196564 197820 199080 200344 201612 202884 204160 205440 206724 208012 209304 210600 211900 213204 214512 215824 217140 218460 219784 221112 222444 223780 225120 226464 227812 229164 230520 231880 233244 234612 235984 237360 238740 240124 241512 242904 244300 245700 247104 248512 249924 251340 252760 254184 255612 257044 258480 259920 261364 262812 264264 265720 267180 268644 270112 271584 273060 274540 276024 277512 279004 280500 282000 283504 285012 286524 288040 289560 291084 292612 294144 295680 297220 298764 300312 301864 303420 304980 306544 308112 309684 311260 312840 314424 316012 317604 319200 320800 322404 324012 325624 327240 328860 330484 332112 333744 335380 337020 338664 340312 341964 343620 345280 346944 348612 350284 351960 353640 355324 357012 358704 360400 362100 363804 365512 367224 368940 370660 372384 374112 375844 377580 379320 381064 382812 384564 386320 388080 389844 391612 393384 395160 396940 398724 400512 402304 404100 405900 407704 409512 411324 413140 414960 416784 418612 420444 422280 424120 922

Yes

2 6 12 20 30 42 56 72 90 110 132 156 182 210 240 272 306 342 380 420 462 506 552 600 650 702 756 812 870 930 992 1056 1122 1190 1260 1332 1406 1482 1560 1640 1722 1806 1892 1980 2070 2162 2256 2352 2450 2550 2652 2756 2862 2970 3080 3192 3306 3422 3540 3660 3782 3906 4032 4160 4290 4422 4556 4692 4830 4970 5112 5256 5402 5550 5700 5852 6006 6162 6320 6480 6642 6806 6972 7140 7310 7482 7656 7832 8010 8190 8372 8556 8742 8930 9120 9312 9506 9702 9900 10100 10302 10506 10712 10920 11130 11342 11556 11772 11990 12210 12432 12656 12882 13110 13340 13572 13806 14042 14280 14520 14762 15006 15252 15500 15750 16002 16256 16512 16770 17030 17292 17556 17822 18090 18360 18632 18906 19182 19460 19740 20022 20306 20592 20880 21170 21462 21756 22052 22350 22650 22952 23256 23562 23870 24180 24492 24806 25122 25440 25760 26082 26406 26732 27060 27390 27722 28056 28392 28730 29070 29412 29756 30102 30450 30800 31152 31506 31862 32220 32580 32942 33306 33672 34040 34410 34782 35156 35532 35910 36290 36672 37056 37442 37830 38220 38612 39006 39402 39800 40200 40602 41006 41412 41820 42230 42642 43056 43472 43890 44310 44732 45156 45582 46010 46440 46872 47306 47742 48180 48620 49062 49506 49952 50400 50850 51302 51756 52212 52670 53130 53592 54056 54522 54990 55460 55932 56406 56882 57360 57840 58322 58806 59292 59780 60270 60762 61256 61752 62250 62750 63252 63756 64262 64770 65280 65792 66306 66822 67340 67860 68382 68906 69432 69960 70490 71022 71556 72092 72630 73170 73712 74256 74802 75350 75900 76452 77006 77562 78120 78680 79242 79806 80372 80940 81510 82082 82656 83232 83810 84390 84972 85556 86142 86730 87320 87912 88506 89102 89700 90300 90902 91506 92112 92720 93330 93942 94556 95172 95790 96410 97032 97656 98282 98910 99540 100172 100806 101442 102080 102720 103362 104006 104652 105300 105950 106602 107256 107912 108570 109230 109892 110556 111222 111890 112560 113232 113906 114582 115260 115940 116622 117306 117992 118680 119370 120062 120756 121452 122150 122850 123552 124256 124962 125670 126380 127092 127806 128522 129240 129960 130682 131406 132132 132860 133590 134322 135056 135792 136530 137270 138012 138756 139502 140250 141000 141752 142506 143262 144020 144780 145542 146306 147072 147840 148610 149382 150156 150932 151710 152490 153272 154056 154842 155630 156420 157212 158006 158802 159600 160400 161202 162006 162812 163620 164430 165242 166056 166872 167690 168510 169332 170156 170982 171810 172640 173472 174306 175142 175980 176820 177662 178506 179352 180200 181050 181902 182756 183612 184470 185330 186192 187056 187922 188790 189660 190532 191406 192282 193160 194040 194922 195806 196692 197580 198470 199362 200256 201152 202050 202950 203852 204756 205662 206570 207480 208392 209306 210222 211140 212060 212982 213906 214832 215760 216690 217622 218556 219492 220430 221370 222312 223256 224202 225150 226100 227052 228006 228962 229920 230880 231842 232806 233772 234740 235710 236682 237656 238632 239610 240590 241572 242556 243542 244530 245520 246512 247506 248502 249500 500

■参照サイト
AtCoder Regular Contest 163

2023年9月18日

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

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題A (Divide String) ～問題B (Favorite Game) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 両問とも, 解説のロジックで, 解けることが興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6693
// C++20(GCC 12.2)
#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 main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        char c[2020];
        scanf("%d %s", &N, c);
        string s(c);
        
        // 2-2. 長さ 2 の分割方法が存在するか？
        bool ok = false;
        rep(i, N - 1){
            string l = s.substr(0, i + 1);
            string r = s.substr(i + 1, N - i - 1);
            // printf("l=%s r=%s\n", l.c_str(), r.c_str());
            // 狭義単調増加に注意(等号は含めない).
            if(l < r){
                ok = true;
                break;
            }
        }
        
        // 2-3. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6693

// C++20(GCC 12.2)

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

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

// 2-1. 各テストケース.

int N;

char c[2020];

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

string s(c);

// 2-2. 長さ 2 の分割方法が存在するか？

bool ok = false;

rep(i, N - 1){

string l = s.substr(0, i + 1);

string r = s.substr(i + 1, N - i - 1);

// printf("l=%s r=%s\n", l.c_str(), r.c_str());

// 狭義単調増加に注意(等号は含めない).

if(l < r){

ok = true;

break;

}

// 2-3. 出力.

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

}

return 0;

}

[入力例]
5
4
abac
3
cac
2
ab
12
abababababab
5
edcba

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

[入力例]
9
2
aa
3
aba
4
zyyx
5
qqqqp
6
zyxwvx
7
pqrsqrp
8
zyxzxyzy
9
pqrpqrpqr
10
srqposrqpo

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

[入力例]

abac

cac

abababababab

edcba

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

aba

zyyx

qqqqp

zyxwvx

pqrsqrp

zyxzxyzy

pqrpqrpqr

srqposrqpo

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc163/editorial/6699
// C++20(GCC 12.2)
#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, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 数列 B.
    sort(a + 2, a + N);
    
    // 3. 全探索.
    LL ans = 202020202020202020;
    repx(i, 2, N - M + 1){
        // 左端, 右端.
        LL l = a[i];
        LL r = a[i + M - 1];
        
        // 操作回数.
        LL op = 0;
        op += max(0LL, a[0] - l);
        op += max(0LL, r - a[1]);
        
        // 最小値更新.
        ans = min(ans, op);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc163/editorial/6699

// C++20(GCC 12.2)

#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, M;

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

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

// 2. 数列 B.

sort(a + 2, a + N);

// 3. 全探索.

LL ans = 202020202020202020;

repx(i, 2, N - M + 1){

// 左端, 右端.

LL l = a[i];

LL r = a[i + M - 1];

// 操作回数.

LL op = 0;

op += max(0LL, a[0] - l);

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

// 最小値更新.

ans = min(ans, op);

}

// 4. 出力.

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

return 0;

}

[入力例]
3 1
2 3 5

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

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

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

[入力例]
8 5
15 59 64 96 31 17 88 9

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

[入力例]
7 5
31 14 91 40 16 56 99

[出力例]
100

[入力例]
20 12
81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51

[出力例]
105

[入力例]
30 15
830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776

[出力例]
525

[入力例]

3 1

2 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

5 2

1 4 2 3 5

[出力例]

※AtCoderのテストケースより

[入力例]

8 5

15 59 64 96 31 17 88 9

[出力例]

※AtCoderのテストケースより

[入力例]

7 5

31 14 91 40 16 56 99

[出力例]

100

[入力例]

20 12

81 43 53 37 98 14 38 92 84 31 8 17 77 72 123 83 6 57 117 51

[出力例]

105

[入力例]

30 15

830 698 320 654 1055 357 16 713 244 523 463 1020 912 514 298 528 549 801 424 490 323 246 1163 301 392 290 645 458 1099 776

[出力例]

525

■参照サイト
AtCoder Regular Contest 163

2023年9月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題E (Count Simple Paths) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 訪問済みフラグ(往路, 復路)を活用して, 数え上げできるロジックが, 興味深く思った.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc284/editorial/5494
// C++20(GCC 12.2)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    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. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    int ans = 0;
    auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m) -> void {
        // 終了条件.
        if(m[cur]) return;
        
        // 終了条件(TLE回避のため, ロジック追加).
        // -> 対象のテストケースは, 02_random_00.txt ～ 02_random_03.txt.
        if(ans == 1000000) return;
        
        // 訪問済みフラグ(往路).
        ++m[cur];
        ans = min(++ans, 1000000);
        
        // 隣接頂点.
        for(auto &nex : G[cur]){
            if(nex == bef) continue;
            self(self, G, nex, cur, m);
        }
        
        // 訪問済みフラグ(復路).
        --m[cur];
    };
    int memo[N];
    rep(i, N) memo[i] = 0;
    dfs(dfs, G, 0, -1, memo);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc284/editorial/5494

// C++20(GCC 12.2)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, M;

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

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. dfs.

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

int ans = 0;

auto dfs = [&](auto&& self, vvi &G, int cur, int bef, int* m) -> void {

// 終了条件.

if(m[cur]) return;

// 終了条件(TLE回避のため, ロジック追加).

// -> 対象のテストケースは, 02_random_00.txt ～ 02_random_03.txt.

if(ans == 1000000) return;

// 訪問済みフラグ(往路).

++m[cur];

ans = min(++ans, 1000000);

// 隣接頂点.

for(auto &nex : G[cur]){

if(nex == bef) continue;

self(self, G, nex, cur, m);

}

// 訪問済みフラグ(復路).

--m[cur];

};

int memo[N];

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

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

// 3. 出力.

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

return 0;

}

[入力例]
4 2
1 2
2 3

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

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

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

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

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

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

[出力例]
3

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

[出力例]
10

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

[出力例]
26

[入力例]

4 2

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 6

1 2

1 3

1 4

2 3

2 4

3 4

[出力例]

※AtCoderテストケースより

[入力例]

8 21

2 6

1 3

5 6

3 8

3 6

4 7

4 6

3 4

1 5

2 4

1 2

2 7

1 4

3 5

2 5

2 3

4 5

3 7

6 7

5 7

2 8

[出力例]

2023

※AtCoderテストケースより

[入力例]

5 3

1 2

2 3

4 5

[出力例]

[入力例]

10 9

1 2

2 3

2 4

1 5

5 6

5 7

7 8

7 9

7 10

[出力例]

[入力例]

18 20

1 2

2 3

3 4

4 5

5 3

1 6

6 8

6 9

9 8

9 10

11 9

7 1

7 12

18 7

12 13

12 14

12 15

13 16

16 17

17 13

[出力例]

■参照サイト
AtCoder Beginner Contest 284

2023年8月27日

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

C++の練習を兼ねて, AtCoder Grand Contest 049 の問題A (Erasing Vertices) ～問題B (Flip Digits) を解いてみた.

■感想.
1. 問題A, Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. 問題A で, 幅優先探索の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 問題A, B のいずれも, 解説のロジックが, 非常に不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    rep(i, N){
        char c[101];
        scanf("%s", c);
        rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺.
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d){
        // 空のキュー.
        queue<int> q;
        
        // 距離ゼロを設定.
        d[s] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v);
        }
    };
    
    // 3. S[v] の 計算(解説通り).
    vvi S(N);
    rep(i, N){
        // 頂点 i から, 到達可能な頂点は？
        int d[N];
        rep(j, N) d[j] = -1;
        bfs(G, i, d);
        
        // S[v] に 保存.
        rep(v, N) if(d[v] != -1) S[v].pb(i);
    }
    
    // 4. 集計.
    double ans = 0.0;
    rep(v, N) ans += 1.0 / (double)S[v].size();
    
    // 5. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc049/editorial/281

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

rep(i, N){

char c[101];

scanf("%s", c);

rep(j, N) if(c[j] == '1') G[i].pb(j); // 有向辺.

}

// 2. bfs.

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

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

// 空のキュー.

queue<int> q;

// 距離ゼロを設定.

d[s] = 0;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &v : G[u]) if(d[v] == -1 && v != s) d[v] = d[u] + 1, q.push(v);

}

};

// 3. S[v] の計算(解説通り).

vvi S(N);

rep(i, N){

// 頂点 i から, 到達可能な頂点は？

int d[N];

rep(j, N) d[j] = -1;

bfs(G, i, d);

// S[v] に保存.

rep(v, N) if(d[v] != -1) S[v].pb(i);

}

// 4. 集計.

double ans = 0.0;

rep(v, N) ans += 1.0 / (double)S[v].size();

// 5. 出力.

printf("%.12lf\n", ans);

return 0;

}

[入力例]
3
010
001
010

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

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

[入力例]
3
000
000
000

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

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

[入力例]
3
011
101
110

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

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

[入力例]
4
0100
0010
0001
0100

[出力例]
1.750000000000

[入力例]
5
01001
00100
00010
01000
00000

[出力例]
2.250000000000

[入力例]
10
0100000100
0010010000
0001000001
0000100000
0000000000
0000001000
0000000000
0000000010
0000000000
0000000000

[出力例]
3.950000000000

[入力例]
15
010000000010000
000000000000000
000100000000100
000010000000010
000000000100001
000000000000100
000000000010001
000000000000000
000000010000000
000001000000000
000010000000000
000100000000000
000000000000010
010000000000000
110000000000000

[出力例]
5.795609945610

[入力例]

010

001

010

[出力例]

1.66666666666666666667

※AtCoderのテストケースより

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

1.666666666667

[入力例]

000

[出力例]

3.00000000000000000000

※AtCoderのテストケースより

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

3.000000000000

[入力例]

011

101

110

[出力例]

1.00000000000000000000

※AtCoderのテストケースより

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

1.000000000000

[入力例]

0100

0010

0001

0100

[出力例]

1.750000000000

[入力例]

01001

00100

00010

01000

00000

[出力例]

2.250000000000

[入力例]

0100000100

0010010000

0001000001

0000100000

0000000000

0000001000

0000000000

0000000010

0000000000

[出力例]

3.950000000000

[入力例]

010000000010000

000000000000000

000100000000100

000010000000010

000000000100001

000000000000100

000000000010001

000000000000000

000000010000000

000001000000000

000010000000000

000100000000000

000000000000010

010000000000000

110000000000000

[出力例]

5.795609945610

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

// 解き直し.
// https://atcoder.jp/contests/agc049/editorial/330
// 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 sXorCum[505050], tXorCum[505050], cur[2];

int main(){
    
    // 1. 入力情報.
    int N;
    char s[505050], t[505050];
    scanf("%d %s %s", &N, s, t);
    
    // 2. 累積XOR.
    rep(i, N){
        sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1');
        tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1');
    }
    
    // 3. 操作(解説通り).
    int k = -1, jMax = -1;
    LL ans = 0;
    bool ok = true;
    repx(i, 1, N + 1){
        // すでに, tXorCum と sXorCum が 一致しているときは, Skip.
        if(cur[tXorCum[i]] >= i) continue;
        
        // 探索開始位置(今回分).
        k = max(jMax, i);
        
        // 探索済みにも関わらず, tXorCum と sXorCum が 一致しない場合は, NG.
        if(k == N + 1) ok = false;
        
        // tXorCum の i番目 と sXorCum の j番目 が 等しくなるものは？
        repx(j, k, N + 1){
            // 探索開始位置(次回分).
            jMax = max(jMax, j + 1);
            
            // 見つかった.
            if(tXorCum[i] == sXorCum[j]){
                // 集計.
                ans += (j - i);
                
                // 操作履歴保存.
                cur[tXorCum[i]] = j;
                cur[!tXorCum[i]] = -1;
                
                // 次へ.
                break;
            }
            
            // 見つからなかった.
            if(jMax == N + 1) ok = false;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ok ? ans : -1);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/agc049/editorial/330

// 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 sXorCum[505050], tXorCum[505050], cur[2];

int main(){

// 1. 入力情報.

int N;

char s[505050], t[505050];

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

// 2. 累積XOR.

rep(i, N){

sXorCum[i + 1] = sXorCum[i] ^ (s[i] == '1');

tXorCum[i + 1] = tXorCum[i] ^ (t[i] == '1');

}

// 3. 操作(解説通り).

int k = -1, jMax = -1;

LL ans = 0;

bool ok = true;

repx(i, 1, N + 1){

// すでに, tXorCum と sXorCum が一致しているときは, Skip.

if(cur[tXorCum[i]] >= i) continue;

// 探索開始位置(今回分).

k = max(jMax, i);

// 探索済みにも関わらず, tXorCum と sXorCum が一致しない場合は, NG.

if(k == N + 1) ok = false;

// tXorCum の i番目と sXorCum の j番目が等しくなるものは？

repx(j, k, N + 1){

// 探索開始位置(次回分).

jMax = max(jMax, j + 1);

// 見つかった.

if(tXorCum[i] == sXorCum[j]){

// 集計.

ans += (j - i);

// 操作履歴保存.

cur[tXorCum[i]] = j;

cur[!tXorCum[i]] = -1;

// 次へ.

break;

}

// 見つからなかった.

if(jMax == N + 1) ok = false;

}

// 4. 出力.

printf("%lld\n", ok ? ans : -1);

return 0;

}

[入力例]
3
001
100

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

[入力例]
3
001
110

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

[入力例]
5
10111
01010

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

[入力例]
7
0101101
1001100

[出力例]
-1

[入力例]
7
0111101
1001100

[出力例]
5

[入力例]
10
1010111101
1000101100

[出力例]
-1

[入力例]
10
1010111101
1100101100

[出力例]
5

[入力例]
30
001010001110011100110110111101
110001010100011100100110011000

[出力例]
18

[入力例]

001

100

[出力例]

※AtCoderのテストケースより

[入力例]

001

110

[出力例]

-1

※AtCoderのテストケースより

[入力例]

10111

01010

[出力例]

※AtCoderのテストケースより

[入力例]

0101101

1001100

[出力例]

-1

[入力例]

0111101

1001100

[出力例]

[入力例]

1010111101

1000101100

[出力例]

-1

[入力例]

1010111101

1100101100

[出力例]

[入力例]

001010001110011100110110111101

110001010100011100100110011000

[出力例]

■参照サイト
AtCoder Grand Contest 049

2023年8月20日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc189/editorial/541
// 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--)
#define pb push_back
int a[202020];
double dp[202020], dpCum[202020], pd[202020], pdCum[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vi v;
    rep(i, K){
        int idx;
        scanf("%d", &idx);
        ++a[idx];
        v.pb(idx);
    }
    
    // 2. マス N に, 到達不可能.
    if(K >= M){
        rep(i, K - M + 1){
            if(v[i + M - 1] - v[i] == M - 1){
                puts("-1");
                return 0;
            }
        }
    }
    
    // 3. dp更新.
    repr(i, N - 1, 0){
        // 振り出しに戻るマス.
        if(a[i]){
            // g[i].
            dp[i] = 0.0;
            dpCum[i] = dp[i] + dpCum[i + 1];
            
            // x の 係数.
            pd[i] = 1.0;
            pdCum[i] = pd[i] + pdCum[i + 1];
            
            // 次へ.
            continue;
        }
        
        // それ以外.
        // g[i].
        dp[i] = 1.0 / M * (dpCum[i + 1] - dpCum[i + M + 1]) + 1.0;
        dpCum[i] = dp[i] + dpCum[i + 1];
        
        // x の 係数.
        pd[i] = 1.0 / M * (pdCum[i + 1] - pdCum[i + M + 1]);
        pdCum[i] = pd[i] + pdCum[i + 1];
    }
    
    // 4. 出力.
    printf("%.6lf\n", dp[0] / (1.0 - pd[0]));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc189/editorial/541

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

#define pb push_back

int a[202020];

double dp[202020], dpCum[202020], pd[202020], pdCum[202020];

int main(){

// 1. 入力情報.

int N, M, K;

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

vi v;

rep(i, K){

int idx;

scanf("%d", &idx);

++a[idx];

v.pb(idx);

}

// 2. マス N に, 到達不可能.

if(K >= M){

rep(i, K - M + 1){

if(v[i + M - 1] - v[i] == M - 1){

puts("-1");

return 0;

}

// 3. dp更新.

repr(i, N - 1, 0){

// 振り出しに戻るマス.

if(a[i]){

// g[i].

dp[i] = 0.0;

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

// x の係数.

pd[i] = 1.0;

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

// 次へ.

continue;

}

// それ以外.

// g[i].

dp[i] = 1.0 / M * (dpCum[i + 1] - dpCum[i + M + 1]) + 1.0;

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

// x の係数.

pd[i] = 1.0 / M * (pdCum[i + 1] - pdCum[i + M + 1]);

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

}

// 4. 出力.

printf("%.6lf\n", dp[0] / (1.0 - pd[0]));

return 0;

}

[入力例]
2 2 0

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

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

[入力例]
2 2 1
1

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

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

[入力例]
100 6 10
11 12 13 14 15 16 17 18 19 20

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

[入力例]
100000 2 2
2997 92458

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

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

[入力例]
5 4 2
2 3

[出力例]
4.166667

[入力例]
5 3 3
2 4 5

[出力例]
6.000000

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

[出力例]
-1

[入力例]
7 5 3
1 4 5

[出力例]
6.821429

[入力例]
2023 3 8
123 234 345 456 567 678 789 890 

[出力例]
30397.833333

[入力例]
12345 3 5
1234 2345 3456 4567 5678

[出力例]
39742.833332

[入力例]

2 2 0

[出力例]

1.5000

※AtCoderテストケースより

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

1.500000

[入力例]

2 2 1

[出力例]

2.0000

※AtCoderテストケースより

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

2.000000

[入力例]

100 6 10

11 12 13 14 15 16 17 18 19 20

[出力例]

-1

※AtCoderテストケースより

[入力例]

100000 2 2

2997 92458

[出力例]

201932.2222

※AtCoderテストケースより

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

201932.225051

[入力例]

5 4 2

2 3

[出力例]

4.166667

[入力例]

5 3 3

2 4 5

[出力例]

6.000000

[入力例]

6 3 4

1 3 4 5

[出力例]

-1

[入力例]

7 5 3

1 4 5

[出力例]

6.821429

[入力例]

2023 3 8

123 234 345 456 567 678 789 890

[出力例]

30397.833333

[入力例]

12345 3 5

1234 2345 3456 4567 5678

[出力例]

39742.833332

■参照サイト
AtCoder Beginner Contest 189

2023年8月18日2023年8月18日

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題F (Grid and Tokens) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できた.
2. Dinic法に触れることが出来たので, 非常に良かったと思う.
※ 競プロ典型 90 問のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc205/editorial/2057
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using P = pair<int, int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 2020;
int PA[101], PB[101], PC[101], PD[101];

struct Edge{
    int to, cap, rev;
};

// Dinic
// https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp
// -> 一部改変(2022/04/23).
struct Dinic{
    int size_;
    vi level, iter;
    vector<Edge> G[MAX];
    
    Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {}
    void edge(int u, int v, int c){
        G[u].pb(Edge{v, c, (int)G[v].size()});
        G[v].pb(Edge{u, 0, (int)G[u].size() - 1});
    }
    void bfs(int s){
        rep(i, size_ + 1) level[i] = -1;
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()){
            int pos = q.front();
            q.pop();
            rep(i, G[pos].size()){
                if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue;
                q.push(G[pos][i].to);
                level[G[pos][i].to] = level[pos] + 1;
            }
        }
    }
    int dfs(int pos, int to, int f){
        if(pos == to) return f;
        for(int& i = iter[pos]; i < G[pos].size(); i++){
            if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){
                int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap));
                if(z > 0){
                    G[pos][i].cap -= z;
                    G[G[pos][i].to][G[pos][i].rev].cap += z;
                    return z;
                }
            }
        }
        return 0;
    }
    int maxFlow(int s, int t){
        int ret = 0;
        while(1){
            bfs(s);
            if(level[t] == -1) break;
            rep(i, size_ + 1) iter[i] = 0;
            while(1){
                int f = dfs(s, t, 1000000007);
                if(f == 0) break;
                ret += f;
            }
        }
        return ret;
    }
};

int main(){
    
    // 1. 入力情報.
    int H, W, N;
    scanf("%d %d %d", &H, &W, &N);
    rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]);
    rep(i, N){
        PB[i] += H;
        PD[i] += H;
    }
    
    // 2. グラフ構築(解説通り).
    // -> 頂点番号は, 以下のように設定.
    // src = 0
    // R = 1 ～ H
    // C = H + 1 ～ H + W
    // U = H + W + 1 ～ H + W + N
    // V = H + W + N + 1 ～ H + W + N + N
    // dst = H + W + N + N + 1
    // 
    int src = 0, dst = H + W + N + N + 1;
    Dinic D(H + W + N + N + 5);
    repx(r, 1, H + 1) D.edge(src, r, 1);
    rep(i, N){
        int u = H + W + i + 1;
        repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1);
    }
    rep(i, N){
        int u = H + W + i + 1;
        int v = H + W + N + i + 1;
        D.edge(u, v, 1);
    }
    rep(i, N){
        int v = H + W + N + i + 1;
        repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1);
    }
    repx(c, H + 1, H + W + 1) D.edge(c, dst, 1);
    
    // 3. 出力.
    printf("%d\n", D.maxFlow(src, dst));
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

// 解き直し.

// https://atcoder.jp/contests/abc205/editorial/2057

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using P = pair<int, int>;

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

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

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

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

#define pb push_back

const int MAX = 2020;

int PA[101], PB[101], PC[101], PD[101];

struct Edge{

int to, cap, rev;

};

// Dinic

// https://github.com/E869120/kyopro_educational_90/blob/main/sol/077-04a.cpp

// -> 一部改変(2022/04/23).

struct Dinic{

int size_;

vi level, iter;

vector<Edge> G[MAX];

Dinic(int n = 0) : size_(n), level(n + 1), iter(n + 1) {}

void edge(int u, int v, int c){

G[u].pb(Edge{v, c, (int)G[v].size()});

G[v].pb(Edge{u, 0, (int)G[u].size() - 1});

}

void bfs(int s){

rep(i, size_ + 1) level[i] = -1;

queue<int> q;

q.push(s);

level[s] = 0;

while(!q.empty()){

int pos = q.front();

q.pop();

rep(i, G[pos].size()){

if(G[pos][i].cap == 0 || level[G[pos][i].to] != -1) continue;

q.push(G[pos][i].to);

level[G[pos][i].to] = level[pos] + 1;

}

int dfs(int pos, int to, int f){

if(pos == to) return f;

for(int& i = iter[pos]; i < G[pos].size(); i++){

if(G[pos][i].cap > 0 && level[pos] < level[G[pos][i].to]){

int z = dfs(G[pos][i].to, to, min(f, G[pos][i].cap));

if(z > 0){

G[pos][i].cap -= z;

G[G[pos][i].to][G[pos][i].rev].cap += z;

return z;

}

return 0;

}

int maxFlow(int s, int t){

int ret = 0;

while(1){

bfs(s);

if(level[t] == -1) break;

rep(i, size_ + 1) iter[i] = 0;

while(1){

int f = dfs(s, t, 1000000007);

if(f == 0) break;

ret += f;

}

return ret;

}

};

int main(){

// 1. 入力情報.

int H, W, N;

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

rep(i, N) scanf("%d %d %d %d", &PA[i], &PB[i], &PC[i], &PD[i]);

rep(i, N){

PB[i] += H;

PD[i] += H;

}

// 2. グラフ構築(解説通り).

// -> 頂点番号は, 以下のように設定.

// src = 0

// R = 1 ～ H

// C = H + 1 ～ H + W

// U = H + W + 1 ～ H + W + N

// V = H + W + N + 1 ～ H + W + N + N

// dst = H + W + N + N + 1

int src = 0, dst = H + W + N + N + 1;

Dinic D(H + W + N + N + 5);

repx(r, 1, H + 1) D.edge(src, r, 1);

rep(i, N){

int u = H + W + i + 1;

repx(r, PA[i], PC[i] + 1) D.edge(r, u, 1);

}

rep(i, N){

int u = H + W + i + 1;

int v = H + W + N + i + 1;

D.edge(u, v, 1);

}

rep(i, N){

int v = H + W + N + i + 1;

repx(c, PB[i], PD[i] + 1) D.edge(v, c, 1);

}

repx(c, H + 1, H + W + 1) D.edge(c, dst, 1);

// 3. 出力.

printf("%d\n", D.maxFlow(src, dst));

return 0;

}

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

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

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

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

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

[出力例]
2

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

[出力例]
6

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

[出力例]
10

[入力例]

2 3 3

1 1 2 2

1 2 2 3

1 1 1 3

[出力例]

※AtCoderテストケースより

[入力例]

5 5 3

1 1 5 5

1 1 4 4

2 2 3 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2

1 1 1 1

1 1 2 2

[出力例]

[入力例]

7 10 12

3 3 6 4

3 3 5 5

3 8 4 10

2 9 5 10

3 3 5 5

2 7 3 8

3 8 3 10

2 9 7 10

3 4 5 5

3 5 5 5

2 3 3 6

2 9 6 10

[出力例]

[入力例]

12 15 18

5 4 7 7

5 5 6 6

5 4 7 8

4 5 5 7

3 5 9 6

3 6 10 6

3 5 9 7

2 6 8 7

2 7 7 8

2 8 7 9

1 6 5 7

1 5 6 7

1 6 7 9

1 3 3 4

1 5 2 6

10 12 12 12

10 12 11 13

10 11 11 13

[出力例]

■参照サイト
AtCoder Beginner Contest 205
競プロ典型 90 問の問題077

2023年8月16日

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    LL X;
    scanf("%d %lld", &N, &X);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, N - 1) b[i] = a[i + 1] / a[i];
    b[N - 1] = INF;
    
    // 2. dp更新.
    map<LL, LL> dp[N + 1];
    dp[N][-X] = 1;
    repr(i, N - 1, 0){
        for(auto &j : dp[i + 1]){
            // x の 出現チェック.
            set<LL> st;
            
            // x を -2 ～ 2 の差分に渡り, 余分に見る.
            for(auto &p : {-2, -1, 0, 1, 2}){
                // x, d の 計算.
                LL x = -j.a / a[i] + p;
                LL d = a[i] * x + j.a;
                
                // 条件を満たすか？
                if(!st.count(x) && abs(d) < a[i] && abs(x) < b[i]){
                    // dp更新.
                    dp[i][d] += dp[i + 1][j.a];
                    
                    // 出現済.
                    st.insert(x);
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", dp[0][0]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc182/editorial/293

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define a first

const LL INF = 202020202020202020;

LL a[55], b[55];

int main(){

// 1. 入力情報.

int N;

LL X;

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

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

rep(i, N - 1) b[i] = a[i + 1] / a[i];

b[N - 1] = INF;

// 2. dp更新.

map<LL, LL> dp[N + 1];

dp[N][-X] = 1;

repr(i, N - 1, 0){

for(auto &j : dp[i + 1]){

// x の出現チェック.

set<LL> st;

// x を -2 ～ 2 の差分に渡り, 余分に見る.

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

// x, d の計算.

LL x = -j.a / a[i] + p;

LL d = a[i] * x + j.a;

// 条件を満たすか？

if(!st.count(x) && abs(d) < a[i] && abs(x) < b[i]){

// dp更新.

dp[i][d] += dp[i + 1][j.a];

// 出現済.

st.insert(x);

}

// 3. 出力.

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

return 0;

}

[入力例]
3 9
1 5 10

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

[入力例]
5 198
1 5 10 50 100

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

[入力例]
4 44
1 4 20 100

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

[入力例]
9 11837029798
1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

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

[入力例]
15 304050607080
1 111 333 1665 11655 34965 244755 734265 2202795 11013975 33041925 99125775 198251550 396503100 1189509300

[出力例]
2160

[入力例]
23 20230816
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304

[出力例]
2675

[入力例]
25 202011082100
1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907 43046721 129140163 387420489 1162261467 3486784401 10460353203 31381059609 94143178827 282429536481

[出力例]
1075200

[入力例]

3 9

1 5 10

[出力例]

※AtCoderテストケースより

[入力例]

5 198

1 5 10 50 100

[出力例]

※AtCoderテストケースより

[入力例]

4 44

1 4 20 100

[出力例]

※AtCoderテストケースより

[入力例]

9 11837029798

1 942454037 2827362111 19791534777 257289952101 771869856303 3859349281515 30874794252120 216123559764840

[出力例]

※AtCoderテストケースより

[入力例]

15 304050607080

1 111 333 1665 11655 34965 244755 734265 2202795 11013975 33041925 99125775 198251550 396503100 1189509300

[出力例]

2160

[入力例]

23 20230816

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304

[出力例]

2675

[入力例]

25 202011082100

1 3 9 27 81 243 729 2187 6561 19683 59049 177147 531441 1594323 4782969 14348907 43046721 129140163 387420489 1162261467 3486784401 10460353203 31381059609 94143178827 282429536481

[出力例]

1075200

■参照サイト
AtCoder Beginner Contest 182

2023年8月13日

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

C++の練習を兼ねて, AtCoder Beginner Contest 306 の問題C (Centers) ～問題E (Best Performances) を解いてみた.

■感想.
1. 問題C ～問題E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題Dで, 苦手な動的計画法の訓練が積めたので, 非常に良かったと思う.
3. 問題Eで, 実装に苦労したものの, std::multiset の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;
using vp = vector<P>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define all(x) x.begin(), x.end()
#define a first
#define b second
int a[303030], c[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N * 3) scanf("%d", &a[i]);
    
    // 2. f[i].
    vp f;
    rep(i, N * 3) if(++c[a[i]] == 2) f.pb({i, a[i]});
    
    // 3. sort.
    sort(all(f));
    
    // 4. 出力.
    rep(i, N) printf("%d%s", f[i].b, (i < N - 1) ? " " : "\n");
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

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

#define a first

#define b second

int a[303030], c[101010];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. f[i].

vp f;

rep(i, N * 3) if(++c[a[i]] == 2) f.pb({i, a[i]});

// 3. sort.

sort(all(f));

// 4. 出力.

rep(i, N) printf("%d%s", f[i].b, (i < N - 1) ? " " : "\n");

return 0;

}

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

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

[入力例]
1
1 1 1

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

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

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

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

[出力例]
5 1 2 3 4

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

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

[入力例]

1 1 3 2 3 2 2 3 1

[出力例]

1 3 2

※AtCoderテストケースより

[入力例]

1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

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

[出力例]

3 4 1 2

※AtCoderテストケースより

[入力例]

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

[出力例]

5 1 2 3 4

[入力例]

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

[出力例]

7 10 9 1 2 5 6 3 4 8

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int x[303030], y[303030];
LL dp[303030][2]; // (第二成分) 0: お腹を壊してない, 1: お腹を壊している.

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d %d", &x[i], &y[i]);
    
    // 2. dp更新.
    repx(i, 1, N + 1){
        // 前回分.
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        
        // 解毒剤入りの料理.
        if(x[i - 1] == 0){
            // 下げてもらう, お腹を壊していない時, お腹を壊している時.
            dp[i][0] = max({dp[i][0], dp[i - 1][0] + y[i - 1], dp[i - 1][1] + y[i - 1]});
        }
        
        // 毒入りの料理.
        if(x[i - 1] == 1){
            // 下げてもらう, お腹を壊していない時.
            dp[i][1] = max(dp[i][1], dp[i - 1][0] + y[i - 1]);
        }
    }
    
    // 3. 出力.
    printf("%lld\n", max(dp[N][0], dp[N][1]));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int x[303030], y[303030];

LL dp[303030][2]; // (第二成分) 0: お腹を壊してない, 1: お腹を壊している.

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. dp更新.

repx(i, 1, N + 1){

// 前回分.

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

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

// 解毒剤入りの料理.

if(x[i - 1] == 0){

// 下げてもらう, お腹を壊していない時, お腹を壊している時.

dp[i][0] = max({dp[i][0], dp[i - 1][0] + y[i - 1], dp[i - 1][1] + y[i - 1]});

}

// 毒入りの料理.

if(x[i - 1] == 1){

// 下げてもらう, お腹を壊していない時.

dp[i][1] = max(dp[i][1], dp[i - 1][0] + y[i - 1]);

}

// 3. 出力.

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

return 0;

}

[入力例]
5
1 100
1 300
0 -200
1 500
1 300

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

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

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

[入力例]
15
1 900000000
0 600000000
1 -300000000
0 -700000000
1 200000000
1 300000000
0 -600000000
1 -900000000
1 600000000
1 -100000000
1 -400000000
0 900000000
0 200000000
1 -500000000
1 900000000

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

[入力例]
5
0 -47
1 37
1 47
0 -1
1 31

[出力例]
77

[入力例]
17
1 -5927
0 -5083
1 -4874
0 2133
0 -3008
1 -4097
0 -6399
1 -7708
0 5110
1 3952
1 -8882
0 415
1 2652
0 -8000
1 6377
1 2607
0 2013

[出力例]
20000

[入力例]
50
1 443328
0 73836
1 935506
0 167707
1 -721984
1 868820
1 935436
1 -837258
0 -178397
1 466026
0 256747
1 598834
0 -346502
1 245871
1 -448547
1 -840209
1 -322995
0 858559
1 953866
1 -601510
1 402645
0 737038
0 -305937
0 617873
0 370498
1 -526848
1 434673
0 784215
1 860840
1 73853
1 299615
1 777998
0 -811686
0 -532055
1 -347241
0 181457
0 -180547
1 -156049
1 -701547
0 198698
1 423549
1 -408934
1 -584618
0 19276
1 226669
0 -728976
1 690256
0 297078
1 873101
1 530457

[出力例]
12000000

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

[入力例]

1 100

1 300

0 -200

1 500

1 300

[出力例]

600

※AtCoderテストケースより

[入力例]

0 -1

1 -2

0 -3

1 -4

[出力例]

※AtCoderテストケースより

[入力例]

1 900000000

0 600000000

1 -300000000

0 -700000000

1 200000000

1 300000000

0 -600000000

1 -900000000

1 600000000

1 -100000000

1 -400000000

0 900000000

0 200000000

1 -500000000

1 900000000

[出力例]

4100000000

※AtCoderテストケースより

[入力例]

0 -47

1 37

1 47

0 -1

1 31

[出力例]

[入力例]

1 -5927

0 -5083

1 -4874

0 2133

0 -3008

1 -4097

0 -6399

1 -7708

0 5110

1 3952

1 -8882

0 415

1 2652

0 -8000

1 6377

1 2607

0 2013

[出力例]

20000

[入力例]

1 443328

0 73836

1 935506

0 167707

1 -721984

1 868820

1 935436

1 -837258

0 -178397

1 466026

0 256747

1 598834

0 -346502

1 245871

1 -448547

1 -840209

1 -322995

0 858559

1 953866

1 -601510

1 402645

0 737038

0 -305937

0 617873

0 370498

1 -526848

1 434673

0 784215

1 860840

1 73853

1 299615

1 777998

0 -811686

0 -532055

1 -347241

0 181457

0 -180547

1 -156049

1 -701547

0 198698

1 423549

1 -408934

1 -584618

0 19276

1 226669

0 -728976

1 690256

0 297078

1 873101

1 530457

[出力例]

12000000

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

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

int main(){
    
    // 1. 入力情報.
    int N, K, Q;
    scanf("%d %d %d", &N, &K, &Q);
    
    // 2. 事前準備.
    multiset<LL> lMst, rMst;
    rep(i, N){
        if(i < N - K) lMst.insert(0);
        else          rMst.insert(0);
    }
    
    // 3. クエリ回答.
    LL f = 0;
    rep(i, Q){
        // クエリ入力情報.
        int x, y;
        scanf("%d %d", &x, &y);
        --x;
        
        // 更新予定の値.
        LL cur = a[x];
        
        // 更新.
        a[x] = y;
        
        // 左側.
        bool isSwap = false;
        if(!lMst.empty()){
            auto lItr = lMst.find(cur);
            if(lItr != lMst.end()){
                // 入れ替え.
                lMst.erase(lItr);
                lMst.insert(y);
                isSwap = !isSwap;
            }
        }
        
        // 右側.
        auto rItr = rMst.find(cur);
        if(!isSwap && rItr != rMst.end()){
            // 入れ替え.
            rMst.erase(rItr);
            rMst.insert(y);
            
            // f 更新.
            f += y;
            f -= cur;
        }
        
        // 最大値チェック.
        if(!lMst.empty()){
            LL lMax = *(--lMst.end());
            LL rMin = *rMst.begin();
            if(lMax > rMin){
                // 削除.
                auto lDel = lMst.find(lMax);
                lMst.erase(lDel);
                auto rDel = rMst.find(rMin);
                rMst.erase(rDel);
                
                // 追加.
                lMst.insert(rMin);
                rMst.insert(lMax);
                
                // f 更新.
                f += lMax;
                f -= rMin;
            }
        }
        
        // 出力.
        printf("%lld\n", f);
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[505050];

int main(){

// 1. 入力情報.

int N, K, Q;

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

// 2. 事前準備.

multiset<LL> lMst, rMst;

rep(i, N){

if(i < N - K) lMst.insert(0);

else rMst.insert(0);

}

// 3. クエリ回答.

LL f = 0;

rep(i, Q){

// クエリ入力情報.

int x, y;

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

--x;

// 更新予定の値.

LL cur = a[x];

// 更新.

a[x] = y;

// 左側.

bool isSwap = false;

if(!lMst.empty()){

auto lItr = lMst.find(cur);

if(lItr != lMst.end()){

// 入れ替え.

lMst.erase(lItr);

lMst.insert(y);

isSwap = !isSwap;

}

// 右側.

auto rItr = rMst.find(cur);

if(!isSwap && rItr != rMst.end()){

// 入れ替え.

rMst.erase(rItr);

rMst.insert(y);

// f 更新.

f += y;

f -= cur;

}

// 最大値チェック.

if(!lMst.empty()){

LL lMax = *(--lMst.end());

LL rMin = *rMst.begin();

if(lMax > rMin){

// 削除.

auto lDel = lMst.find(lMax);

lMst.erase(lDel);

auto rDel = rMst.find(rMin);

rMst.erase(rDel);

// 追加.

lMst.insert(rMin);

rMst.insert(lMax);

// f 更新.

f += lMax;

f -= rMin;

}

// 出力.

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

}

return 0;

}

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

[出力例]
5
6
8
8
15
13
13
11
1
0
※AtCoderテストケースより

[入力例]
10 3 30
2 120
7 114
1 36
9 99
1 8
7 122
2 45
1 58
6 88
9 74
7 69
2 6
3 10
5 31
3 116
3 73
9 32
2 43
7 38
7 41
9 61
4 14
6 28
4 110
8 10
6 91
7 100
1 53
5 112
6 79

[出力例]
120
234
270
333
333
341
266
279
309
284
231
231
231
231
278
235
230
230
219
219
222
222
192
244
244
274
301
301
322
322

[入力例]
20 5 100
6 8520
9 1903
7 10099
2 655
8 9326
16 2653
19 6018
13 4188
7 4612
7 5699
18 7730
5 383
12 3149
6 764
7 3043
7 1626
8 2701
17 9019
1 2749
17 8514
18 89
4 1192
8 2974
3 9292
18 7511
7 8047
19 2216
20 1991
11 5850
5 7479
12 11977
20 63
6 12325
8 7013
6 7715
5 2225
6 5161
6 9220
14 10668
9 7839
19 5285
17 7557
7 2664
13 1823
6 3766
3 7557
17 9157
6 9224
5 3799
9 10820
4 10364
6 9731
16 9634
1 3711
2 1061
8 704
1 405
3 17
4 8014
8 4445
1 4903
4 11265
18 2861
20 12261
7 1500
20 6723
7 9299
14 7574
20 5920
18 5223
6 10318
14 6469
17 6790
17 1844
18 4048
18 11912
7 5035
17 11880
13 2837
4 6373
20 1383
12 12308
14 11816
7 2600
10 6148
4 5572
14 3855
12 2960
19 2854
11 8674
6 5111
20 7973
3 3969
4 5009
15 10535
12 2267
4 10367
5 9390
11 6519
10 7310

[出力例]
8520
10423
20522
21177
30503
32501
36616
38151
32664
33751
37293
37293
37293
32961
30411
30411
23786
30104
30104
29599
24618
24618
24843
31161
35523
39382
37552
37552
39214
40843
45341
45341
50155
50155
45545
45545
45341
47050
49671
49671
49671
49204
48996
48996
47333
45598
47198
48865
48865
51846
53053
53560
53560
53560
53560
53560
53560
53560
52830
52830
52830
54461
54461
56991
56991
54461
54461
53427
53427
53427
54014
54014
54014
54014
54014
56292
56292
57854
57854
56907
56907
57238
58736
58736
58736
58736
57238
54564
54564
54564
52920
52920
52920
52920
54781
54781
55514
55514
55514
55514

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

[入力例]

4 2 10

1 5

2 1

3 3

4 2

2 10

1 0

4 0

3 1

2 0

3 0

[出力例]

※AtCoderテストケースより

[入力例]

10 3 30

2 120

7 114

1 36

9 99

1 8

7 122

2 45

1 58

6 88

9 74

7 69

2 6

3 10

5 31

3 116

3 73

9 32

2 43

7 38

7 41

9 61

4 14

6 28

4 110

8 10

6 91

7 100

1 53

5 112

6 79

[出力例]

120

234

270

333

341

266

279

309

284

231

278

235

230

219

222

192

244

274

301

322

[入力例]

20 5 100

6 8520

9 1903

7 10099

2 655

8 9326

16 2653

19 6018

13 4188

7 4612

7 5699

18 7730

5 383

12 3149

6 764

7 3043

7 1626

8 2701

17 9019

1 2749

17 8514

18 89

4 1192

8 2974

3 9292

18 7511

7 8047

19 2216

20 1991

11 5850

5 7479

12 11977

20 63

6 12325

8 7013

6 7715

5 2225

6 5161

6 9220

14 10668

9 7839

19 5285

17 7557

7 2664

13 1823

6 3766

3 7557

17 9157

6 9224

5 3799

9 10820

4 10364

6 9731

16 9634

1 3711

2 1061

8 704

1 405

3 17

4 8014

8 4445

1 4903

4 11265

18 2861

20 12261

7 1500

20 6723

7 9299

14 7574

20 5920

18 5223

6 10318

14 6469

17 6790

17 1844

18 4048

18 11912

7 5035

17 11880

13 2837

4 6373

20 1383

12 12308

14 11816

7 2600

10 6148

4 5572

14 3855

12 2960

19 2854

11 8674

6 5111

20 7973

3 3969

4 5009

15 10535

12 2267

4 10367

5 9390

11 6519

10 7310

[出力例]

8520

10423

20522

21177

30503

32501

36616

38151

32664

33751

37293

32961

30411

23786

30104

29599

24618

24843

31161

35523

39382

37552

39214

40843

45341

50155

45545

45341

47050

49671

49204

48996

47333

45598

47198

48865

51846

53053

53560

52830

54461

56991

54461

53427

54014

56292

57854

56907

57238

58736

57238

54564

52920

54781

55514

■参照サイト
トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306)

2023年8月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 143 の問題C (Piles of Pebbles) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで勝者を判定できる点が, 非常に興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc143/editorial/4194
// 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--)
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. B の 計算.
    vi b(N);
    rep(i, N) b[i] = a[i] % (X + Y);
    
    // 3. sort.
    sort(all(b));
    
    // 4. B[i] が, すべて X より小さい.
    if(b.back() < X){
        puts("Second");
        return 0;
    }
    
    // 5. X <= Y で, ある b[i] が X 以上.
    if(X <= Y){
        if(b.back() >= X){
            puts("First");
            return 0;
        }
    }
    
    // 6. X > Y.
    // 6-1. 先手が, X個以上の山(一つ)から, X個取り除く.
    b.back() -= X;
    
    // 6-2. sort.
    sort(all(b));
    
    // 6-3. B[i] が, すべて Y より小さい.
    if(b.back() < Y){
        puts("First");
        return 0;
    }
    
    // 6-4. ある b[i] が Y 以上.
    puts("Second");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc143/editorial/4194

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

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

int main(){

// 1. 入力情報.

int N, X, Y;

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

vi a(N);

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

// 2. B の計算.

vi b(N);

rep(i, N) b[i] = a[i] % (X + Y);

// 3. sort.

sort(all(b));

// 4. B[i] が, すべて X より小さい.

if(b.back() < X){

puts("Second");

return 0;

}

// 5. X <= Y で, ある b[i] が X 以上.

if(X <= Y){

if(b.back() >= X){

puts("First");

return 0;

}

// 6. X > Y.

// 6-1. 先手が, X個以上の山(一つ)から, X個取り除く.

b.back() -= X;

// 6-2. sort.

sort(all(b));

// 6-3. B[i] が, すべて Y より小さい.

if(b.back() < Y){

puts("First");

return 0;

}

// 6-4. ある b[i] が Y 以上.

puts("Second");

return 0;

}

[入力例]
2 1 1
3 3

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

[入力例]
2 1 2
3 3

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

[入力例]
3 1 2
2 5 6

[出力例]
First

[入力例]
5 5 3
19 20 21 22 23

[出力例]
Second

[入力例]
5 5 3
16 17 18 23 24

[出力例]
First

[入力例]
10 7 9
37 22 21 17 49 65 82 20 18 19

[出力例]
Second

[入力例]
20 12 13
25 36 25 13 13 29 21 17 37 27 27 24 34 21 24 22 34 14 17 24

[出力例]
First

[入力例]
30 55 50
489 550 368 440 541 255 423 509 378 496 296 466 315 380 404 397 322 296 346 283 492 430 438 517 541 411 426 477 331 347

[出力例]
Second

[入力例]
50 2023 2020
8586 8043 4543 12629 21215 17172 4543 9086 16672 13129 12629 8586 13129 20715 16672 5043 5043 8586 21215 9086 20715 17172 5043 21215 20715 17172 21215 12629 16672 4543 12629 9086 12629 12629 20715 17172 9086 4543 9086 5043 12629 4543 12629 17172 12629 13129 21215 4543 17172 17172

[出力例]
First

[入力例]

2 1 1

3 3

[出力例]

First

※AtCoderのテストケースより

[入力例]

2 1 2

3 3

[出力例]

Second

※AtCoderのテストケースより

[入力例]

3 1 2

2 5 6

[出力例]

First

[入力例]

5 5 3

19 20 21 22 23

[出力例]

Second

[入力例]

5 5 3

16 17 18 23 24

[出力例]

First

[入力例]

10 7 9

37 22 21 17 49 65 82 20 18 19

[出力例]

Second

[入力例]

20 12 13

25 36 25 13 13 29 21 17 37 27 27 24 34 21 24 22 34 14 17 24

[出力例]

First

[入力例]

30 55 50

489 550 368 440 541 255 423 509 378 496 296 466 315 380 404 397 322 296 346 283 492 430 438 517 541 411 426 477 331 347

[出力例]

Second

[入力例]

50 2023 2020

8586 8043 4543 12629 21215 17172 4543 9086 16672 13129 12629 8586 13129 20715 16672 5043 5043 8586 21215 9086 20715 17172 5043 21215 20715 17172 21215 12629 16672 4543 12629 9086 12629 12629 20715 17172 9086 4543 9086 5043 12629 4543 12629 17172 12629 13129 21215 4543 17172 17172

[出力例]

First

■参照サイト
AtCoder Regular Contest 143

2023年7月30日

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

C++の練習を兼ねて, AtCoder Beginner Contest 301 の問題E (Pac-Takahashi) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 幅優先探索, 苦手な動的計画法(bitDP, 巡回セールスマン問題)の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc301/editorial/6343
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
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 pb push_back
#define a first
#define b second
const int INF = 1010101010;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
char board[303][303];
int memo[22][22];

int main(){
    
    // 1. 入力情報.
    int H, W, T;
    scanf("%d %d %d", &H, &W, &T);
    rep(i, H){
        char c[303];
        scanf("%s", c);
        rep(j, W) board[i][j] = c[j];
    }
    
    // 2. マス(スタート, お菓子, ゴール)を保存.
    vp cells;
    rep(i, H) rep(j, W) if(board[i][j] == 'S') cells.pb({i, j});
    rep(i, H) rep(j, W) if(board[i][j] == 'o') cells.pb({i, j});
    rep(i, H) rep(j, W) if(board[i][j] == 'G') cells.pb({i, j});
    int n = cells.size();
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](P s, int x) -> void {
        // 訪問フラグ.
        int v[303][303];
        rep(i, H) rep(j, W) v[i][j] = INF;
        
        // 空のキュー.
        queue<P> q;
        
        // 訪問済みフラグ設定.
        v[s.a][s.b] = 0;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            P c = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            rep(i, 4){
                int nx = c.b + dx[i];
                int ny = c.a + dy[i];
                
                // 訪問不可能なマスは, スキップ.
                if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[ny][nx] == '#') continue;
                
                // 未訪問のマスは, 最短距離を設定.
                if(v[ny][nx] == INF) v[ny][nx] = v[c.a][c.b] + 1, q.push({ny, nx});
            }
        }
        
        // 結果の保存.
        rep(i, n) memo[x][i] = v[cells[i].a][cells[i].b];
    };
    
    // 4. 全探索(指定した二地点間).
    rep(i, n) bfs(cells[i], i);
    
    // 5. bitDP(巡回セールスマン問題).
    // AtCoder Beginner Contest 180 (E - Traveling Salesman among Aerial Cities) 参照.
    // https://atcoder.jp/contests/abc180/editorial/154
    // スタート(0), お菓子の数(1 ～ n - 2 まで), ゴール(n - 1).
    // スタートは, フラグ(1) を 立てておく.
    // ex. 
    // n = 9
    // 訪問済マスの部分集合(s) が 10010010G -> 10010011G に変化する場合は, マス 3 or 6 から マス 7 へ 移動と解釈.
    int ans = -1;
    int dp[n - 1][1 << (n - 1)];
    rep(i, n - 1) rep(j, 1 << (n - 1)) dp[i][j] = INF;
    dp[0][1 << (n - 2)] = 0;
    repx(p, 1, n){
        // 5-1. (p + 1)個目 の マス を 訪問する場合は？
        repx(s, 1 << (n - 2), 1 << (n - 1)){
            // 訪問済マスの部分集合が, p個でない場合, Skip.
            if(__builtin_popcount(s) != p) continue;
            
            // 移動元 を マス i とする.
            rep(i, n - 1){
                int bef = 1 << (n - 2 - i);
                if(s & bef){
                    // 移動先 を マス j とする.
                    repx(j, 1, n - 1){
                        int cur = 1 << (n - 2 - j);
                        
                        // 未訪問の場合は, dp更新.
                        if(!(s & cur)) dp[j][s + cur] = min(dp[j][s + cur], dp[i][s] + memo[i][j]);
                    }
                }
            }
        }
        
        // 5-2. ゴール に 到着.
        int d = INF;
        repx(s, 1 << (n - 2), 1 << (n - 1)){
            // 訪問済マスの部分集合が, p個でない場合, Skip.
            if(__builtin_popcount(s) != p) continue;
            
            // ゴール直前のマスを全探索.
            rep(j, n - 1){
                int bef = 1 << (n - 2 - j);
                if(s & bef) d = min(d, dp[j][s] + memo[j][n - 1]);
            }
        }
        
        // 5-3. 最大値更新.
        // -> p は, スタート地点を含むので, 1個少ない値を指定.
        if(d <= T) ans = p - 1;
    }
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

// 解き直し.

// https://atcoder.jp/contests/abc301/editorial/6343

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

#define a first

#define b second

const int INF = 1010101010;

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

char board[303][303];

int memo[22][22];

int main(){

// 1. 入力情報.

int H, W, T;

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

rep(i, H){

char c[303];

scanf("%s", c);

rep(j, W) board[i][j] = c[j];

}

// 2. マス(スタート, お菓子, ゴール)を保存.

vp cells;

rep(i, H) rep(j, W) if(board[i][j] == 'S') cells.pb({i, j});

rep(i, H) rep(j, W) if(board[i][j] == 'o') cells.pb({i, j});

rep(i, H) rep(j, W) if(board[i][j] == 'G') cells.pb({i, j});

int n = cells.size();

// 3. bfs.

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

auto bfs = [&](P s, int x) -> void {

// 訪問フラグ.

int v[303][303];

rep(i, H) rep(j, W) v[i][j] = INF;

// 空のキュー.

queue<P> q;

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

v[s.a][s.b] = 0;

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

q.push(s);

while(!q.empty()){

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

P c = q.front();

q.pop();

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

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

rep(i, 4){

int nx = c.b + dx[i];

int ny = c.a + dy[i];

// 訪問不可能なマスは, スキップ.

if(nx < 0 || nx >= W || ny < 0 || ny >= H || board[ny][nx] == '#') continue;

// 未訪問のマスは, 最短距離を設定.

if(v[ny][nx] == INF) v[ny][nx] = v[c.a][c.b] + 1, q.push({ny, nx});

}

// 結果の保存.

rep(i, n) memo[x][i] = v[cells[i].a][cells[i].b];

};

// 4. 全探索(指定した二地点間).

rep(i, n) bfs(cells[i], i);

// 5. bitDP(巡回セールスマン問題).

// AtCoder Beginner Contest 180 (E - Traveling Salesman among Aerial Cities) 参照.

// https://atcoder.jp/contests/abc180/editorial/154

// スタート(0), お菓子の数(1 ～ n - 2 まで), ゴール(n - 1).

// スタートは, フラグ(1) を立てておく.

// ex.

// n = 9

// 訪問済マスの部分集合(s) が 10010010G -> 10010011G に変化する場合は, マス 3 or 6 からマス 7 へ

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題C (Harmonic Mean) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の 問題A (Divide String) ～ 問題B (Favorite Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の 問題E (Count Simple Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 049 の 問題A (Erasing Vertices) ～ 問題B (Flip Digits) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の 問題F (Grid and Tokens) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 306 の 問題C (Centers) ～ 問題E (Best Performances) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 143 の 問題C (Piles of Pebbles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 301 の 問題E (Pac-Takahashi) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題C (Harmonic Mean) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 163 の問題A (Divide String) ～問題B (Favorite Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 284 の問題E (Count Simple Paths) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 049 の問題A (Erasing Vertices) ～問題B (Flip Digits) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 205 の問題F (Grid and Tokens) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 306 の問題C (Centers) ～問題E (Best Performances) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 143 の問題C (Piles of Pebbles) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 301 の問題E (Pac-Takahashi) を解いてみた.