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

C++の練習を兼ねて, AtCoder Beginner Contest 264 の問題C (Matrix Reducing) ～問題D (“redocta”.swap(i,i+1)) を解いてみた.

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

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

■C++版プログラム(問題C／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--)
#define pb push_back
int a[22][22], b[22][22];

int main(){
    
    // 1. 入力情報.
    int h1, w1;
    scanf("%d %d", &h1, &w1);
    rep(i, h1) rep(j, w1) scanf("%d", &a[i][j]);
    int h2, w2;
    scanf("%d %d", &h2, &w2);
    rep(i, h2) rep(j, w2) scanf("%d", &b[i][j]);
    
    // 2. 判定.
    bool ok = false;
    rep(i, 1 << h1){
        rep(j, 1 << w1){
            if(__builtin_popcount(i) == h2 && __builtin_popcount(j) == w2){
                vi r, c;
                rep(k, h1) if(i & (1 << (h1 - 1 - k))) r.pb(k);
                rep(k, w1) if(j & (1 << (w1 - 1 - k))) c.pb(k);
                int m = 0;
                rep(k, h2) rep(l, w2) if(a[r[k]][c[l]] == b[k][l]) ++m;
                if(m == h2 * w2) ok = true;
            }
            if(ok) break;
        }
        if(ok) break;
    }
    
    // 3. 出力.
    printf("%s\n", ok ? "Yes" : "No");
    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--)

#define pb push_back

int a[22][22], b[22][22];

int main(){

// 1. 入力情報.

int h1, w1;

scanf("%d %d", &h1, &w1);

rep(i, h1) rep(j, w1) scanf("%d", &a[i][j]);

int h2, w2;

scanf("%d %d", &h2, &w2);

rep(i, h2) rep(j, w2) scanf("%d", &b[i][j]);

// 2. 判定.

bool ok = false;

rep(i, 1 << h1){

rep(j, 1 << w1){

if(__builtin_popcount(i) == h2 && __builtin_popcount(j) == w2){

vi r, c;

rep(k, h1) if(i & (1 << (h1 - 1 - k))) r.pb(k);

rep(k, w1) if(j & (1 << (w1 - 1 - k))) c.pb(k);

int m = 0;

rep(k, h2) rep(l, w2) if(a[r[k]][c[l]] == b[k][l]) ++m;

if(m == h2 * w2) ok = true;

}

if(ok) break;

}

if(ok) break;

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
No

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

[出力例]
Yes

[入力例]
15 13
14112 6703 7454 16669 7504 15174 10947 5600 16299 9455 8775 14843 15446
10004 15105 7182 12983 7848 16470 10802 7418 11339 14214 10209 10642 11947
7872 7590 10518 6332 15478 7121 15346 13572 12418 9757 16916 15100 15001
6754 16819 8481 6762 9875 11093 11354 11475 9663 17822 6608 6654 12567
14542 6957 6254 11540 10730 7004 12983 10200 10338 6225 16679 14253 13898
9651 12852 10111 13123 12501 17677 14465 12935 6714 5636 5867 8039 12899
9268 6793 8535 16434 12347 14547 17801 16118 6708 6989 7556 12148 13991
12462 10999 13742 11830 12261 12256 8219 9739 13284 13676 10999 6516 6809
12489 11964 13749 5888 6891 16004 17815 8654 13771 11399 15752 16153 8000
12995 13348 6191 13298 11707 17111 10732 11997 13590 6752 12167 8851 10078
13631 10939 7729 14238 11173 10749 14903 7076 7150 6899 10203 13855 13507
12197 14511 11419 14041 17497 6261 10789 12046 17145 8358 16503 6293 15987
7459 15819 15843 15591 12920 15026 6222 15588 17770 7812 11065 10296 16756
11297 16984 7284 16838 8746 5622 9769 13472 15395 14944 16958 15049 15310
16923 13275 10278 17897 7761 16148 15743 10395 17356 8316 10620 15096 13629
11 10
14112 6703 16669 7504 15174 5600 16299 9455 8775 15446
10004 15105 12983 7848 16470 7418 11339 14214 10209 11947
6754 16819 6762 9875 11093 11475 9663 17822 6608 12567
14542 6957 11540 10730 7004 10200 10338 6225 16679 13898
12462 10999 11830 12261 12256 9739 13284 13676 10999 6809
12489 11964 5888 6891 16004 8654 13771 11399 15752 8000
12995 13348 13298 11707 17111 11997 13590 6752 12167 10078
12197 14511 14041 17497 6261 12046 17145 8358 16503 15987
7459 15819 15591 12920 15026 15588 17770 7812 11065 16756
11297 16984 16838 8746 5622 13472 15395 14944 16958 15310
16923 13275 17897 7761 16148 10395 17356 8316 10620 13629

[出力例]
Yes
※ 整数 H1, W1, H2, W2 が, 問題文の制約条件から範囲外であるケース.

[入力例]

4 5

1 2 3 4 5

6 7 8 9 10

11 12 13 14 15

16 17 18 19 20

2 3

6 8 9

16 18 19

[出力例]

Yes

※AtCoderテストケースより

[入力例]

3 3

1 1 1

1 1

[出力例]

※AtCoderテストケースより

[入力例]

2 3

1 2 3

3 2 1

1 2

1 1

[出力例]

[入力例]

10 10

18 4 12 12 9 7 14 15 4 9

17 19 16 17 17 15 20 5 17 12

13 20 19 18 16 2 1 20 18 5

11 2 16 10 1 16 18 18 5 16

14 6 13 7 11 16 20 6 8 16

16 8 14 3 16 11 20 11 6 10

12 4 19 1 8 3 13 9 19 1

15 3 11 6 12 10 8 19 9 20

6 9 9 9 4 11 8 6 1 17

16 11 7 7 6 7 17 12 13 6

6 6

18 12 9 7 14 9

11 10 1 16 18 16

14 7 11 16 20 16

15 6 12 10 8 20

6 9 4 11 8 17

16 7 6 7 17 6

[出力例]

Yes

[入力例]

15 13

14112 6703 7454 16669 7504 15174 10947 5600 16299 9455 8775 14843 15446

10004 15105 7182 12983 7848 16470 10802 7418 11339 14214 10209 10642 11947

7872 7590 10518 6332 15478 7121 15346 13572 12418 9757 16916 15100 15001

6754 16819 8481 6762 9875 11093 11354 11475 9663 17822 6608 6654 12567

14542 6957 6254 11540 10730 7004 12983 10200 10338 6225 16679 14253 13898

9651 12852 10111 13123 12501 17677 14465 12935 6714 5636 5867 8039 12899

9268 6793 8535 16434 12347 14547 17801 16118 6708 6989 7556 12148 13991

12462 10999 13742 11830 12261 12256 8219 9739 13284 13676 10999 6516 6809

12489 11964 13749 5888 6891 16004 17815 8654 13771 11399 15752 16153 8000

12995 13348 6191 13298 11707 17111 10732 11997 13590 6752 12167 8851 10078

13631 10939 7729 14238 11173 10749 14903 7076 7150 6899 10203 13855 13507

12197 14511 11419 14041 17497 6261 10789 12046 17145 8358 16503 6293 15987

7459 15819 15843 15591 12920 15026 6222 15588 17770 7812 11065 10296 16756

11297 16984 7284 16838 8746 5622 9769 13472 15395 14944 16958 15049 15310

16923 13275 10278 17897 7761 16148 15743 10395 17356 8316 10620 15096 13629

11 10

14112 6703 16669 7504 15174 5600 16299 9455 8775 15446

10004 15105 12983 7848 16470 7418 11339 14214 10209 11947

6754 16819 6762 9875 11093 11475 9663 17822 6608 12567

14542 6957 11540 10730 7004 10200 10338 6225 16679 13898

12462 10999 11830 12261 12256 9739 13284 13676 10999 6809

12489 11964 5888 6891 16004 8654 13771 11399 15752 8000

12995 13348 13298 11707 17111 11997 13590 6752 12167 10078

12197 14511 14041 17497 6261 12046 17145 8358 16503 15987

7459 15819 15591 12920 15026 15588 17770 7812 11065 16756

11297 16984 16838 8746 5622 13472 15395 14944 16958 15310

16923 13275 17897 7761 16148 10395 17356 8316 10620 13629

[出力例]

Yes

※ 整数 H1, W1, H2, W2 が, 問題文の制約条件から範囲外であるケース.

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

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

int main(){
    
    // 1. 入力情報.
    char c[11];
    scanf("%s", c);
    string s(c);
    
    // 2. 転倒数.
    int ans = 0;
    string atcoder = "atcoder";
    rep(i, 7) a[atcoder[i] - 'a'] = i + 1;
    rep(i, 7) p[i] = a[s[i] - 'a'];
    rep(i, 7) repx(j, i + 1, 7) if(p[i] > p[j]) ++ans;
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int a[33], p[11];

int main(){

// 1. 入力情報.

char c[11];

scanf("%s", c);

string s(c);

// 2. 転倒数.

int ans = 0;

string atcoder = "atcoder";

rep(i, 7) a[atcoder[i] - 'a'] = i + 1;

rep(i, 7) p[i] = a[s[i] - 'a'];

rep(i, 7) repx(j, i + 1, 7) if(p[i] > p[j]) ++ans;

// 3. 出力.

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

return 0;

}

[入力例]
catredo

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

[入力例]
atcoder

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

[入力例]
redocta

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

[入力例]
deratco

[出力例]
12

[入力例]
ercatdo

[出力例]
13

[入力例]

catredo

[出力例]

※AtCoderテストケースより

[入力例]

atcoder

[出力例]

※AtCoderテストケースより

[入力例]

redocta

[出力例]

※AtCoderテストケースより

[入力例]

deratco

[出力例]

[入力例]

ercatdo

[出力例]

■参照サイト
freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）

C++の練習を兼ねて, AtCoder Beginner Contest 264 の 問題C (Matrix Reducing) ～ 問題D (“redocta”.swap(i,i+1)) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Beginner Contest 264 の問題C (Matrix Reducing) ～問題D (“redocta”.swap(i,i+1)) を解いてみた.

コメントを残すコメントをキャンセル