C++ | 個人用メモ帳

2023年2月5日

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

C++の練習を兼ねて, AtCoder Beginner Contest 275 の問題C (Counting Squares) ～問題D (Yet Another Recursive Function) を解いてみた.

■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, メモ化再帰の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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 a first
#define b second
#define pb push_back

int main(){
    
    // 1. 入力情報.
    vp o;
    rep(i, 9){
        char c[22];
        scanf("%s", c);
        rep(j, 9) if(c[j] == '#') o.pb({i, j});
    }
    
    // 2. ポーンが, 4頂点に置いてある正方形の個数は？
    int ans = 0, n = o.size();
    rep(v1, n){
        rep(v2, n){
            int x12 = o[v1].a - o[v2].a;
            int y12 = o[v1].b - o[v2].b;
            rep(v3, n){
                int x23 = o[v2].a - o[v3].a;
                int y23 = o[v2].b - o[v3].b;
                rep(v4, n){
                    int x34 = o[v3].a - o[v4].a;
                    int y34 = o[v3].b - o[v4].b;
                    int x41 = o[v4].a - o[v1].a;
                    int y41 = o[v4].b - o[v1].b;
                    
                    // 4頂点でない.
                    if(v1 == v2 || v2 == v3 || v3 == v4 || v4 == v1) continue;
                    
                    // 辺の長さが, すべて等しいか？
                    int d12 = x12 * x12 + y12 * y12;
                    int d23 = x23 * x23 + y23 * y23;
                    int d34 = x34 * x34 + y34 * y34;
                    int d41 = x41 * x41 + y41 * y41;
                    if(!(d12 == d23 && d23 == d34 && d34 == d41)) continue;
                    
                    // 共通の頂点を持つ二辺のなす角が, 90度か？
                    int a123 = x12 * x23 + y12 * y23;
                    int a234 = x23 * x34 + y23 * y34;
                    int a341 = x34 * x41 + y34 * y41;
                    int a412 = x41 * x12 + y41 * y12;
                    if(a123 != 0 || a234 != 0 || a341 != 0 || a412 != 0) continue;
                    
                    // カウント.
                    ++ans;
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans / 8);
    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 a first

#define b second

#define pb push_back

int main(){

// 1. 入力情報.

vp o;

rep(i, 9){

char c[22];

scanf("%s", c);

rep(j, 9) if(c[j] == '#') o.pb({i, j});

}

// 2. ポーンが, 4頂点に置いてある正方形の個数は？

int ans = 0, n = o.size();

rep(v1, n){

rep(v2, n){

int x12 = o[v1].a - o[v2].a;

int y12 = o[v1].b - o[v2].b;

rep(v3, n){

int x23 = o[v2].a - o[v3].a;

int y23 = o[v2].b - o[v3].b;

rep(v4, n){

int x34 = o[v3].a - o[v4].a;

int y34 = o[v3].b - o[v4].b;

int x41 = o[v4].a - o[v1].a;

int y41 = o[v4].b - o[v1].b;

// 4頂点でない.

if(v1 == v2 || v2 == v3 || v3 == v4 || v4 == v1) continue;

// 辺の長さが, すべて等しいか？

int d12 = x12 * x12 + y12 * y12;

int d23 = x23 * x23 + y23 * y23;

int d34 = x34 * x34 + y34 * y34;

int d41 = x41 * x41 + y41 * y41;

if(!(d12 == d23 && d23 == d34 && d34 == d41)) continue;

// 共通の頂点を持つ二辺のなす角が, 90度か？

int a123 = x12 * x23 + y12 * y23;

int a234 = x23 * x34 + y23 * y34;

int a341 = x34 * x41 + y34 * y41;

int a412 = x41 * x12 + y41 * y12;

if(a123 != 0 || a234 != 0 || a341 != 0 || a412 != 0) continue;

// カウント.

++ans;

}

// 3. 出力.

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

return 0;

}

[入力例]
##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

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

[入力例]
.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

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

[入力例]
....####.
..#.##.#.
#.##....#
.###.#..#
....#.#..
.......#.
.#..##...
..#.#.#.#
#..##.#.#

[出力例]
8

[入力例]
#.#...##.
#.#.##.##
.##......
#..#.##.#
.####.#.#
.#..###..
.#..##.##
#.####.##
##..#....

[出力例]
31

[入力例]
####.####
###.#.###
##.###.##
#.#####.#
.#######.
#.#####.#
##.###.##
###.#.###
####.####

[出力例]
252

[入力例]

##.......

.........

.......#.

.....#...

........#

......#..

.........

[出力例]

※AtCoderテストケースより

[入力例]

.#.......

#.#......

.#.......

.........

....#.#.#

.........

....#.#.#

........#

.........

[出力例]

※AtCoderテストケースより

[入力例]

....####.

..#.##.#.

#.##....#

.###.#..#

....#.#..

.......#.

.#..##...

..#.#.#.#

#..##.#.#

[出力例]

[入力例]

#.#...##.

#.#.##.##

.##......

#..#.##.#

.####.#.#

.#..###..

.#..##.##

#.####.##

##..#....

[出力例]

[入力例]

####.####

###.#.###

##.###.##

#.#####.#

.#######.

#.#####.#

##.###.##

###.#.###

####.####

[出力例]

252

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    map<LL, LL> memo;
    auto dfs = [&](auto&& self, LL k) -> LL {
        // 2-1. 終了条件.
        if(memo.count(k)) return memo[k];
        if(k == 0) return memo[0] = 1;
        
        // 2-2. メモ化.
        return (memo[k / 2] = self(self, k / 2)) + (memo[k / 3] = self(self, k / 3));
    };
    
    // 3. 出力.
    printf("%lld\n", dfs(dfs, N));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. dfs.

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

map<LL, LL> memo;

auto dfs = [&](auto&& self, LL k) -> LL {

// 2-1. 終了条件.

if(memo.count(k)) return memo[k];

if(k == 0) return memo[0] = 1;

// 2-2. メモ化.

return (memo[k / 2] = self(self, k / 2)) + (memo[k / 3] = self(self, k / 3));

};

// 3. 出力.

printf("%lld\n", dfs(dfs, N));

return 0;

}

[入力例]
2

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

[入力例]
0

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

[入力例]
100

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

[入力例]
2023

[出力例]
615

[入力例]
20230205

[出力例]
888145

[入力例]
202210292100

[出力例]
1160445931

[入力例]
1000000000000000000

[出力例]
224412958156019

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100

[出力例]

※AtCoderテストケースより

[入力例]

2023

[出力例]

615

[入力例]

20230205

[出力例]

888145

[入力例]

202210292100

[出力例]

1160445931

[入力例]

1000000000000000000

[出力例]

224412958156019

■参照サイト
AtCoder Beginner Contest 275

2023年2月4日2023年2月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 155 の問題A (ST and TS Palindrome) ～問題B (Abs Abs Function) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. 回文判定.
    auto isPalindrome = [&](string s) -> bool {
        string r = s;
        reverse(all(r));
        return (s == r);
    };
    
    // 3. テストケース.
    rep(i, T){
        // 3-1. 各テストケース.
        int N;
        LL k;
        scanf("%d %lld", &N, &k);
        char c[N + 1];
        scanf("%s", c);
        string S(c);
        
        // 3-2. K の 置き換え.
        int K = (int)(k % (N * 2));
        
        // 3-3. S' の 候補.
        // ex.
        // S = abracadabra, K = 15 のとき.
        // 左: arbadacarba....
        // 右: ....arbadacarba
        // -> 区間[4, 10] を 比較して, 一致しないので, S' の候補は, 存在しない.
        // 
        // S = opqrsopqrs, K = 15 の とき.
        // 左: srqposrqpo.....
        // 右: .....srqposrqpo
        // -> 区間[5, 9] を 比較して, 一致するので, S' の候補(srqposrqposrqpo)は, 存在する.
        //    但し, S + S', S' + S は 回文ではない.
        bool ok = true;
        string T(K, '.');
        rep(j, min(N, K)) T[j] = S[N - 1 - j];
        rep(j, min(N, K)){
            if(T[K - 1 - j] == '.'){
                T[K - 1 - j] = S[j];
                continue;
            }
            if(T[K - 1 - j] != S[j]){
                ok = false;
                break;
            }
        }
        
        // 3-4. S' の 候補なし.
        if(!ok){
            puts("No");
            continue;
        }
        // printf("T=%s\n", T.c_str());
        
        // 3-5. 出力.
        printf("%s\n", (isPalindrome(S + T) && isPalindrome(T + S)) ? "Yes" : "No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc155/editorial/5620

// 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 all(x) x.begin(), x.end()

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. 回文判定.

auto isPalindrome = [&](string s) -> bool {

string r = s;

reverse(all(r));

return (s == r);

};

// 3. テストケース.

rep(i, T){

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

int N;

LL k;

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

char c[N + 1];

scanf("%s", c);

string S(c);

// 3-2. K の置き換え.

int K = (int)(k % (N * 2));

// 3-3. S' の候補.

// ex.

// S = abracadabra, K = 15 のとき.

// 左: arbadacarba....

// 右: ....arbadacarba

// -> 区間[4, 10] を比較して, 一致しないので, S' の候補は, 存在しない.

// S = opqrsopqrs, K = 15 のとき.

// 左: srqposrqpo.....

// 右: .....srqposrqpo

// -> 区間[5, 9] を比較して, 一致するので, S' の候補(srqposrqposrqpo)は, 存在する.

// 但し, S + S', S' + S は回文ではない.

bool ok = true;

string T(K, '.');

rep(j, min(N, K)) T[j] = S[N - 1 - j];

rep(j, min(N, K)){

if(T[K - 1 - j] == '.'){

T[K - 1 - j] = S[j];

continue;

}

if(T[K - 1 - j] != S[j]){

ok = false;

break;

}

// 3-4. S' の候補なし.

if(!ok){

puts("No");

continue;

}

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

// 3-5. 出力.

printf("%s\n", (isPalindrome(S + T) && isPalindrome(T + S)) ? "Yes" : "No");

}

return 0;

}

[入力例]
2
6 2
abbaab
5 3
abcbb

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

[入力例]
3
12 400378271514996652
njvhhvjnnjvh
10 884633988115575508
rrhiyvrrur
36 71630165869626180
vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

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

[入力例]
10
1 1
a
3 3
abc
2 1
ab
3 5
cbaabccba
11 5
abracadabra
30 10
yyegvzokgmmgkozvgeyyyyegvzokgm
30 12
thluflfzefbdyexthluflfzefbdyex
18 6
pqrrqppqrrqppqrrqp
75 15
lksipgkfbetioayyaoitebfkgpiskllksipgkfbetioayyaoitebfkgpiskllksipgkfbetioay
210 30
xpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecsk

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

[入力例]

6 2

abbaab

5 3

abcbb

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

12 400378271514996652

njvhhvjnnjvh

10 884633988115575508

rrhiyvrrur

36 71630165869626180

vsxmxajrrduhhudrrjaxmxsvvsxmxajrrduh

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 1

3 3

abc

2 1

3 5

cbaabccba

11 5

abracadabra

30 10

yyegvzokgmmgkozvgeyyyyegvzokgm

30 12

thluflfzefbdyexthluflfzefbdyex

18 6

pqrrqppqrrqppqrrqp

75 15

lksipgkfbetioayyaoitebfkgpiskllksipgkfbetioayyaoitebfkgpiskllksipgkfbetioay

210 30

xpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecskksceqfzinvefoieyortctpirgrlzpxxpzlrgriptctroyeiofevnizfqecsk

[出力例]

Yes

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

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

int main(){
    
    // 1. 入力情報.
    int Q;
    LL A, B;
    scanf("%d %lld %lld", &Q, &A, &B);
    
    // 2. 初期化.
    set<LL> st;
    st.insert(-2020202020);
    st.insert(+2020202020);
    st.insert(A - B);
    st.insert(A + B);
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int t;
        LL a, b;
        scanf("%d %lld %lld", &t, &a, &b);
        
        // 3-2. クエリ 1.
        if(t == 1){
            st.insert(a - b);
            st.insert(a + b);
        }
        
        // 3-3. クエリ 2.
        if(t == 2){
            // [a, b] に, 要素がある.
            auto ia = st.lower_bound(a);
            if(*ia <= b){
                puts("0");
                continue;
            }
            
            // [a, b] に, 要素がない.
            if(*ia >= a) --ia;
            LL L = *ia;
            LL R = *st.upper_bound(b);
            
            // 出力.
            printf("%lld\n", min(a - L, R - b));
        }
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc155/editorial/5594

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

int Q;

LL A, B;

scanf("%d %lld %lld", &Q, &A, &B);

// 2. 初期化.

set<LL> st;

st.insert(-2020202020);

st.insert(+2020202020);

st.insert(A - B);

st.insert(A + B);

// 3. クエリ回答.

rep(i, Q){

// 3-1. クエリ入力情報.

int t;

LL a, b;

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

// 3-2. クエリ 1.

if(t == 1){

st.insert(a - b);

st.insert(a + b);

}

// 3-3. クエリ 2.

if(t == 2){

// [a, b] に, 要素がある.

auto ia = st.lower_bound(a);

if(*ia <= b){

puts("0");

continue;

}

// [a, b] に, 要素がない.

if(*ia >= a) --ia;

LL L = *ia;

LL R = *st.upper_bound(b);

// 出力.

printf("%lld\n", min(a - L, R - b));

}

return 0;

}

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

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

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

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

[入力例]
20 795629912 123625148
2 860243184 892786970
2 645778367 668513124
1 531411849 174630323
1 635062977 195695960
2 382061637 411843651
1 585964296 589553566
1 310118888 68936560
1 525351160 858166280
2 395304415 429823333
2 583145399 703645715
2 97768492 218377432
1 707220749 459967102
1 210842017 363390878
2 489541834 553583525
2 731279777 811513313
1 549864943 493384741
1 815378318 826084592
2 369622093 374205455
1 78240781 821999998
2 241667193 243982581

[出力例]
26468090
3491640
25280111
9543684
0
22804896
20649370
19245624
4849993
484865
※AtCoderのテストケースより

[入力例]
5 107 18
1 114 119
2 57 69
1 98 174
2 6 12
2 84 107

[出力例]
20
11
0

[入力例]
30 60894 114814
1 9771 9998
2 9658 10362
1 1365 13341
2 4171 13850
1 9150 11714
2 12131 14071
2 344 5388
1 5322 10266
2 4273 10731
2 11385 17232
1 10281 16940
1 6759 8420
1 5446 17385
2 6260 18019
1 4752 13325
2 10000 10097
1 7168 9965
2 6418 13448
1 2509 8811
1 10613 18269
2 8835 17767
2 1234 2345
1 7797 12603
2 6091 17241
1 9538 19041
1 6517 9903
2 4001 4119
1 5331 5746
2 2022 2023
2 10443 14634

[出力例]
9407
856
635
571
3975
0
0
4609
1258
0
1461
0
4228
2249
0

[入力例]
50 18589242 111515167
1 7857896 7870225
1 108996925 109007087
1 3231841 3240209
2 93037389 93041220
1 117002763 117005425
2 30927828 30938177
1 67763135 67763539
2 103805460 103806493
2 2567474 2573909
2 108020986 108023905
2 37217005 37225215
2 71809183 71809762
1 47840712 47847137
1 23141266 23150701
1 96045314 96056642
2 75122385 75129879
1 111472448 111479593
2 69249934 69255880
1 52940681 52948063
2 8747268 8748241
2 82901403 82910349
2 67133518 67139242
2 80698425 80703501
1 77496129 77504765
2 16477473 16489194
2 24902518 24903378
1 30300667 30307565
1 106636378 106640566
2 61268348 61273932
2 102619081 102619533
2 119718423 119724118
1 72829329 72839033
1 21800314 21802869
2 36235800 36238940
2 116969633 116981722
1 68026338 68031378
1 81596367 81597321
1 91644445 91646601
2 101519156 101529049
2 31970804 31976248
1 33941680 33942861
1 2973225 2980507
1 69937633 69948482
2 57466792 57470313
2 34804405 34808628
2 67101174 67108237
1 100202673 100211900
2 80333682 80345257
2 48041569 48048173
2 38853288 38857168

[出力例]
37063189
15199707
26297916
2567878
22080504
21488884
56081062
20557970
22957967
2275218
12777500
20841551
14984348
749352
9174397
660116
3269211
10380291
7364243
11080889
4359695
11626935
3137919
8794555
776304
12449141
1749602
4746015

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

[入力例]

4 0 5

1 3 11

2 7 8

1 8 2

2 8 9

[出力例]

※AtCoderのテストケースより

[入力例]

2 1 2

1 2 3

2 2 6

[出力例]

※AtCoderのテストケースより

[入力例]

20 795629912 123625148

2 860243184 892786970

2 645778367 668513124

1 531411849 174630323

1 635062977 195695960

2 382061637 411843651

1 585964296 589553566

1 310118888 68936560

1 525351160 858166280

2 395304415 429823333

2 583145399 703645715

2 97768492 218377432

1 707220749 459967102

1 210842017 363390878

2 489541834 553583525

2 731279777 811513313

1 549864943 493384741

1 815378318 826084592

2 369622093 374205455

1 78240781 821999998

2 241667193 243982581

[出力例]

26468090

3491640

25280111

9543684

22804896

20649370

19245624

4849993

484865

※AtCoderのテストケースより

[入力例]

5 107 18

1 114 119

2 57 69

1 98 174

2 6 12

2 84 107

[出力例]

[入力例]

30 60894 114814

1 9771 9998

2 9658 10362

1 1365 13341

2 4171 13850

1 9150 11714

2 12131 14071

2 344 5388

1 5322 10266

2 4273 10731

2 11385 17232

1 10281 16940

1 6759 8420

1 5446 17385

2 6260 18019

1 4752 13325

2 10000 10097

1 7168 9965

2 6418 13448

1 2509 8811

1 10613 18269

2 8835 17767

2 1234 2345

1 7797 12603

2 6091 17241

1 9538 19041

1 6517 9903

2 4001 4119

1 5331 5746

2 2022 2023

2 10443 14634

[出力例]

9407

856

635

571

3975

4609

1258

1461

4228

2249

[入力例]

50 18589242 111515167

1 7857896 7870225

1 108996925 109007087

1 3231841 3240209

2 93037389 93041220

1 117002763 117005425

2 30927828 30938177

1 67763135 67763539

2 103805460 103806493

2 2567474 2573909

2 108020986 108023905

2 37217005 37225215

2 71809183 71809762

1 47840712 47847137

1 23141266 23150701

1 96045314 96056642

2 75122385 75129879

1 111472448 111479593

2 69249934 69255880

1 52940681 52948063

2 8747268 8748241

2 82901403 82910349

2 67133518 67139242

2 80698425 80703501

1 77496129 77504765

2 16477473 16489194

2 24902518 24903378

1 30300667 30307565

1 106636378 106640566

2 61268348 61273932

2 102619081 102619533

2 119718423 119724118

1 72829329 72839033

1 21800314 21802869

2 36235800 36238940

2 116969633 116981722

1 68026338 68031378

1 81596367 81597321

1 91644445 91646601

2 101519156 101529049

2 31970804 31976248

1 33941680 33942861

1 2973225 2980507

1 69937633 69948482

2 57466792 57470313

2 34804405 34808628

2 67101174 67108237

1 100202673 100211900

2 80333682 80345257

2 48041569 48048173

2 38853288 38857168

[出力例]

37063189

15199707

26297916

2567878

22080504

21488884

56081062

20557970

22957967

2275218

12777500

20841551

14984348

749352

9174397

660116

3269211

10380291

7364243

11080889

4359695

11626935

3137919

8794555

776304

12449141

1749602

4746015

■参照サイト
AtCoder Regular Contest 155

2023年2月1日2023年2月1日

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

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

■感想.
1. 問題C は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 実装に苦労したものの, 個人的には, 解説のロジックで, 正整数列 A を正整数列 B が一致させることが出来るかどうかを判定できる点が, 非常に面白く感じた.
3. 実装上で, 判断に迷った箇所としては, rotate で, 正整数列 A と比較する対象が, 正整数列 B ではなく, 圧縮後の正整数列 B という点に, 少し注意が必要と感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc154/editorial/5548
// 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 pub push_back
#define pob pop_back

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N;
        scanf("%d", &N);
        vi A(N), B(N), ExA(N * 2);
        rep(j, N){
            scanf("%d", &A[j]);
            ExA[j] = ExA[j + N] = A[j];
        }
        rep(j, N) scanf("%d", &B[j]);
        
        // 2-2. A = B の 場合(操作回数ゼロ).
        if(A == B){
            puts("Yes");
            continue;
        }
        
        // 2-3. 数列 B 圧縮(操作回数ゼロでない).
        // -> 以下のようなパターンで, WA版となるため, ロジック修正.
        // ex.
        // 5
        // 2 1 2 1 2
        // 1 2 1 2 1
        // -> このケースは, 正整数列 B は, X = (1, 2, 1, 2), Y = (2, 1, 1, 1) に 圧縮され, 
        //    圧縮後の長さが, X = (1, 2, 1, 2) の 4 であるため, Yes の 候補となる.
        //    結論は, Yes.
        // 
        // ex.
        // 7
        // 1 2 3 2 1 2 3
        // 3 2 1 2 3 2 1
        // -> このケースは, 正整数列 B は, X = (3, 2, 1, 2, 3, 2, 1), Y = (1, 1, 1, 1, 1, 1, 1) に 圧縮され, 
        //    圧縮後の長さが, X = (3, 2, 1, 2, 3, 2, 1) の 7 (= N) であるため, No.
        // 
        // ex.
        // 10
        // 3 1 4 1 5 9 2 6 5 3
        // 1 1 4 1 5 2 2 5 1 1
        // -> このケースは, 正整数列 B は, X = (1, 4, 1, 5, 2, 5), Y = (4, 1, 1, 1, 2, 1) に 圧縮され, 
        //    圧縮後の長さが, X = (1, 4, 1, 5, 2, 5) の 6 であるため, Yes の 候補となる.
        //    結論は, Yes.
        vi C;
        C.pub(B[0]);
        repx(j, 1, N) if(C.back() != B[j]) C.pub(B[j]);
        if(C.size() > 1 && C.front() == C.back()) C.pob();
        
        // 2-4. 正整数列 B を 圧縮したときに, N である場合.
        if(C.size() == N){
            puts("No");
            continue;
        }
        
        // 2-5. 貪欲法.
        int x = 0;
        rep(a, N){
            // 初期化.
            x = 0;
            int idx = a;
            
            // 数列 A の 区間[a, a + N - 1] で 数列 C と 比較.
            for(auto &c : C){
                repx(j, idx, a + N){
                    if(ExA[j] == c){
                        ++x;
                        idx = j;
                        break;
                    }
                }
            }
            
            // ある単調増加整数列が, 見つかった.
            if(x == C.size()) break;
        }
        
        // 2-6. 出力.
        printf("%s\n", (x == C.size()) ? "Yes" : "No");
    }
    return 0;
    
}

100

// 解き直し.

// https://atcoder.jp/contests/arc154/editorial/5548

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

#define pob pop_back

int main(){

// 1. 入力情報.

int T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

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

int N;

scanf("%d", &N);

vi A(N), B(N), ExA(N * 2);

rep(j, N){

scanf("%d", &A[j]);

ExA[j] = ExA[j + N] = A[j];

}

rep(j, N) scanf("%d", &B[j]);

// 2-2. A = B の場合(操作回数ゼロ).

if(A == B){

puts("Yes");

continue;

}

// 2-3. 数列 B 圧縮(操作回数ゼロでない).

// -> 以下のようなパターンで, WA版となるため, ロジック修正.

// ex.

// 5

// 2 1 2 1 2

// 1 2 1 2 1

// -> このケースは, 正整数列 B は, X = (1, 2, 1, 2), Y = (2, 1, 1, 1) に圧縮され,

// 圧縮後の長さが, X = (1, 2, 1, 2) の 4 であるため, Yes の候補となる.

// 結論は, Yes.

// ex.

// 7

// 1 2 3 2 1 2 3

// 3 2 1 2 3 2 1

// -> このケースは, 正整数列 B は, X = (3, 2, 1, 2, 3, 2, 1), Y = (1, 1, 1, 1, 1, 1, 1) に圧縮され,

// 圧縮後の長さが, X = (3, 2, 1, 2, 3, 2, 1) の 7 (= N) であるため, No.

// ex.

// 10

// 3 1 4 1 5 9 2 6 5 3

// 1 1 4 1 5 2 2 5 1 1

// -> このケースは, 正整数列 B は, X = (1, 4, 1, 5, 2, 5), Y = (4, 1, 1, 1, 2, 1) に圧縮され,

// 圧縮後の長さが, X = (1, 4, 1, 5, 2, 5) の 6 であるため, Yes の候補となる.

// 結論は, Yes.

vi C;

C.pub(B[0]);

repx(j, 1, N) if(C.back() != B[j]) C.pub(B[j]);

if(C.size() > 1 && C.front() == C.back()) C.pob();

// 2-4. 正整数列 B を圧縮したときに, N である場合.

if(C.size() == N){

puts("No");

continue;

}

// 2-5. 貪欲法.

int x = 0;

rep(a, N){

// 初期化.

x = 0;

int idx = a;

// 数列 A の区間[a, a + N - 1] で数列 C と比較.

for(auto &c : C){

repx(j, idx, a + N){

if(ExA[j] == c){

++x;

idx = j;

break;

}

// ある単調増加整数列が, 見つかった.

if(x == C.size()) break;

}

// 2-6. 出力.

printf("%s\n", (x == C.size()) ? "Yes" : "No");

}

return 0;

}

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

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

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

[出力例]
Yes
Yes
No

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

[出力例]
Yes
Yes
No
No
Yes

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

[出力例]
Yes
Yes
Yes

[入力例]
3
50
22 1 29 32 26 17 39 47 34 7 7 7 13 21 16 40 50 16 8 37 16 27 38 50 43 11 28 21 32 29 15 39 26 23 33 15 37 4 22 23 5 20 4 17 28 32 34 5 47 46
1 1 29 32 17 17 39 47 34 7 7 13 13 21 50 50 50 16 8 37 16 50 50 50 43 11 28 21 15 15 33 33 33 33 33 15 37 22 22 23 20 20 4 17 28 32 34 5 47 1
30
21 9 29 23 13 10 15 1 2 17 12 27 27 27 17 4 21 7 24 30 28 7 17 19 2 29 1 8 14 9
21 10 10 23 10 10 15 1 2 17 12 10 27 27 17 21 21 24 24 28 28 17 2 2 2 1 1 8 14 9
120
27 1 64 44 46 65 62 31 30 50 40 48 13 14 34 76 29 55 17 22 44 77 27 42 72 10 24 35 35 8 25 68 63 13 4 28 34 14 50 40 60 25 72 54 2 5 68 47 63 72 61 51 30 69 9 22 24 32 75 19 8 47 42 32 46 32 11 76 34 39 67 25 39 58 77 27 69 3 49 17 15 5 30 36 66 44 46 58 6 58 46 9 61 55 11 5 38 10 54 39 22 16 45 22 19 10 39 80 15 56 54 30 42 1 2 21 7 42 73 77
1 1 64 50 50 50 50 50 50 50 40 48 13 14 34 76 29 55 17 22 77 77 72 72 72 10 24 35 8 8 25 68 63 13 50 50 50 50 50 40 60 5 5 5 5 5 63 63 63 61 61 51 30 69 9 22 24 75 75 19 8 11 11 11 11 11 11 39 39 39 77 77 77 77 77 3 3 3 17 17 5 5 30 36 66 6 6 6 6 11 11 11 11 11 11 5 10 10 54 39 22 16 22 22 19 10 80 80 15 56 54 1 1 1 2 7 7 77 77 77

[出力例]
Yes
No
Yes

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

[出力例]
Yes
No

100

101

102

103

104

105

106

[入力例]

1 2

2 2

2 3 1 1

2 1 1 2

1 1

2 2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 2 3 4 5

1 2 3 5 5

3 1 4 1 5 9 2 6 5 3

1 1 4 1 5 2 2 5 1 1

1 2 3 1 2 3 1 2 3

3 1 2 3 1 2 3 1 2

[出力例]

Yes

[入力例]

2 1

2 2

3 2 2

3 1 2

1 2 3 4

1 3 1 3

5 4 3 2 1

3 2 1 1 1

[出力例]

Yes

[入力例]

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

1 1 1 1 5 5 2 2 5 6 9 9

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

5 8 8 8 6 6 7 7 8 10 1 6 10 10 5

5 18 12 17 19 15 6 13 1 8 15 11 12 18 1 7 11 20 20 11

5 12 12 15 15 15 1 1 1 8 15 12 12 18 1 11 11 11 11 11

[出力例]

Yes

[入力例]

22 1 29 32 26 17 39 47 34 7 7 7 13 21 16 40 50 16 8 37 16 27 38 50 43 11 28 21 32 29 15 39 26 23 33 15 37 4 22 23 5 20 4 17 28 32 34 5 47 46

1 1 29 32 17 17 39 47 34 7 7 13 13 21 50 50 50 16 8 37 16 50 50 50 43 11 28 21 15 15 33 33 33 33 33 15 37 22 22 23 20 20 4 17 28 32 34 5 47 1

21 9 29 23 13 10 15 1 2 17 12 27 27 27 17 4 21 7 24 30 28 7 17 19 2 29 1 8 14 9

21 10 10 23 10 10 15 1 2 17 12 10 27 27 17 21 21 24 24 28 28 17 2 2 2 1 1 8 14 9

120

27 1 64 44 46 65 62 31 30 50 40 48 13 14 34 76 29 55 17 22 44 77 27 42 72 10 24 35 35 8 25 68 63 13 4 28 34 14 50 40 60 25 72 54 2 5 68 47 63 72 61 51 30 69 9 22 24 32 75 19 8 47 42 32 46 32 11 76 34 39 67 25 39 58 77 27 69 3 49 17 15 5 30 36 66 44 46 58 6 58 46 9 61 55 11 5 38 10 54 39 22 16 45 22 19 10 39 80 15 56 54 30 42 1 2 21 7 42 73 77

1 1 64 50 50 50 50 50 50 50 40 48 13 14 34 76 29 55 17 22 77 77 72 72 72 10 24 35 8 8 25 68 63 13 50 50 50 50 50 40 60 5 5 5 5 5 63 63 63 61 61 51 30 69 9 22 24 75 75 19 8 11 11 11 11 11 11 39 39 39 77 77 77 77 77 3 3 3 17 17 5 5 30 36 66 6 6 6 6 11 11 11 11 11 11 5 10 10 54 39 22 16 22 22 19 10 80 80 15 56 54 1 1 1 2 7 7 77 77 77

[出力例]

Yes

[入力例]

2 1 2 1 2

1 2 1 2 1

1 2 3 2 1 2 3

3 2 1 2 3 2 1

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 154

2023年1月31日2023年1月31日

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

C++の練習を兼ねて, AtCoder Regular Contest 154 の問題A (Swap Digit) ～問題B (New Place) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char a[202020], b[202020];
    scanf("%d %s %s", &N, a, b);
    
    // 2. 操作.
    LL A = 0, B = 0;
    int s = -1;
    bool f = true;
    rep(i, N){
        // A, B が 等しい間.
        if(s == -1){
            A = A * 10 + a[i] - '0';
            A %= MOD;
            B = B * 10 + b[i] - '0';
            B %= MOD;
            
            // A, B が, 最初に異なる場所.
            if(a[i] != b[i]){
                s = i;
                continue;
            }
        }
        
        // それ以外.
        if(s != -1){
            if(a[i] <= b[i]){
                if(a[s] < b[s]){
                    A = A * 10 + a[i] - '0';
                    A %= MOD;
                    B = B * 10 + b[i] - '0';
                    B %= MOD;
                }
                if(a[s] > b[s]){
                    A = A * 10 + b[i] - '0';
                    A %= MOD;
                    B = B * 10 + a[i] - '0';
                    B %= MOD;
                }
            }else{
                if(a[s] < b[s]){
                    A = A * 10 + b[i] - '0';
                    A %= MOD;
                    B = B * 10 + a[i] - '0';
                    B %= MOD;
                }
                if(a[s] > b[s]){
                    A = A * 10 + a[i] - '0';
                    A %= MOD;
                    B = B * 10 + b[i] - '0';
                    B %= MOD;
                }
            }
        }
    }
    
    // 3. 出力.
    printf("%lld\n", A * B % MOD);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

int N;

char a[202020], b[202020];

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

// 2. 操作.

LL A = 0, B = 0;

int s = -1;

bool f = true;

rep(i, N){

// A, B が等しい間.

if(s == -1){

A = A * 10 + a[i] - '0';

A %= MOD;

B = B * 10 + b[i] - '0';

B %= MOD;

// A, B が, 最初に異なる場所.

if(a[i] != b[i]){

s = i;

continue;

}

// それ以外.

if(s != -1){

if(a[i] <= b[i]){

if(a[s] < b[s]){

A = A * 10 + a[i] - '0';

A %= MOD;

B = B * 10 + b[i] - '0';

B %= MOD;

}

if(a[s] > b[s]){

A = A * 10 + b[i] - '0';

A %= MOD;

B = B * 10 + a[i] - '0';

B %= MOD;

}

}else{

if(a[s] < b[s]){

A = A * 10 + b[i] - '0';

A %= MOD;

B = B * 10 + a[i] - '0';

B %= MOD;

}

if(a[s] > b[s]){

A = A * 10 + a[i] - '0';

A %= MOD;

B = B * 10 + b[i] - '0';

B %= MOD;

}

// 3. 出力.

printf("%lld\n", A * B % MOD);

return 0;

}

[入力例]
2
13
22

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

[入力例]
8
20220122
21002300

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

[入力例]
5
13385
22576

[出力例]
291876750

[入力例]
20
55570287117956982219
55570312438184304678

[出力例]
414030506

[入力例]
50
73520943047002292615274910544319198112428012369710
71344425330648685657673067567450658751475913225975

[出力例]
319328486

[入力例]

[出力例]

276

※AtCoderのテストケースより

[入力例]

20220122

21002300

[出力例]

54558365

※AtCoderのテストケースより

[入力例]

13385

22576

[出力例]

291876750

[入力例]

55570287117956982219

55570312438184304678

[出力例]

414030506

[入力例]

73520943047002292615274910544319198112428012369710

71344425330648685657673067567450658751475913225975

[出力例]

319328486

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

// 解き直し.
// https://atcoder.jp/contests/arc154/editorial/5533
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    char a[202020], b[202020];
    scanf("%d %s %s", &N, a, b);
    string A(a), B(b), S(a), T(b);
    
    // 2. sort.
    sort(all(A));
    sort(all(B));
    
    // 3. 例外.
    if(A != B){
        puts("-1");
        return 0;
    }
    
    // 4. 評価関数.
    auto f = [&](int m) -> bool {
        // 4-1. 文字列 X.
        string X = S.substr(m, N - m);
        
        // 4-2. 文字列 T の 部分列か？
        int idx = 0;
        rep(i, N){
            // 比較.
            if(X[idx] == T[i]) ++idx;
            
            // 部分列である.
            if(idx == X.size()) return true;
        }
        
        // 4-3. 部分列でない.
        return false;
    };
    
    // 5. 二分探索で確認してみる.
    int l = -1, h = 2 * N;
    while(l + 1 < h){
        int m = (h + l) >> 1;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%d l=%d m=%d\n", h, l, m);
    }
    
    // 6. 出力.
    printf("%d\n", h);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc154/editorial/5533

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char a[202020], b[202020];

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

string A(a), B(b), S(a), T(b);

// 2. sort.

sort(all(A));

sort(all(B));

// 3. 例外.

if(A != B){

puts("-1");

return 0;

}

// 4. 評価関数.

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

// 4-1. 文字列 X.

string X = S.substr(m, N - m);

// 4-2. 文字列 T の部分列か？

int idx = 0;

rep(i, N){

// 比較.

if(X[idx] == T[i]) ++idx;

// 部分列である.

if(idx == X.size()) return true;

}

// 4-3. 部分列でない.

return false;

};

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

int l = -1, h = 2 * N;

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

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

}

// 6. 出力.

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

return 0;

}

[入力例]
4
abab
abba

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

[入力例]
3
arc
cra

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

[入力例]
5
pqrst
opqrs

[出力例]
-1

[入力例]
10
pqrpqrpqrp
pqrpqrpqrp

[出力例]
0

[入力例]
50
mpgiytiagtmzuinudtjjawhbpibnfwaordasntnudtjjawhbpi
mpgiytiagtsntnudtjjawhbpimzuinudtjjawhbpibnfwaorda

[出力例]
34

[入力例]
100
pibnfwaordawwagcokbzekatmpgiytiagtsntnudtjjawhbpimzuinudtjjawhbyghmqyntdjphtlckueltiznnvnoeufuksahef
atyghmqyntdjphtlckueltiznnvnoeufuksahempgiytiagtsntnudtjjawhbpimzuinudtjjawhbpibnfwaordawwagcokbzekf

[出力例]
63

[入力例]
500
fsksicxhybwcetiaqgtmjlympuampnwxtgmhavxnsdpegtfwetkeyhufkcemxrfgelvdvrafixfhhanojvuthmsvxkyfrbfkfpxeofwmzcovmodktmumvjtwlgrtmxdgyqlzlgxjynfiflquoyhyqzlzepeiwgqjoixswqiagalfonvwedflwtldcdkgpzmravwrmyihsshtruvhmupxubtkddaexfiducbxixvkeushrsipxaktkcbftixyckzopppuljredlrgktntxjgaxrebrigybovwttuiatfwcpyoqrmiscvwwoqcibzcnddyxhmignqcxjlibcqqnvwkpovqafmyfbrldesgesbhxsnmbvpwfvzzzohtdsmjnznvftqbigsyclqoqxjuudyeqlsrsbzjbxtflvqbyheqlqlrlugaqfbdjfjwzeoltnfaioyygbljwdajhfmwaejirzytuotibelypoqvtxjdhzjnvarbtzim
fgelvdvrafixfhhanojvuthmsvrmyihsshtruvhmupxubtkddaexfiducbxixvkeushrsipxaktkcbftixyckzopppuljrexkyfrbfkfpxeofwmzcovmodktmumvjtwldlrgktntxjgaxrebrivwwoqcibzcnddyxhmignqcxjlibcqqnvwkpovqafmyfbrlderbtzimgrtmxdgyqlzlgxjynfieiwgqjoixswqiagalsgesbhxsnmbvpwfvohtdsmjnznvftqbigsyclqoqxjuudyeqlsrsbzjbxttibelypoqvtxjdhzjnvafonvwgpzmravpuampnwxtgmhavxnsdpegtfwetkeyhufkcemxrffskzzzsicxhybwcetiaqgtmjlymwedflwtldcdklquoflvqbyheqlqlrlugaqfbdjfjwzeoltnfaioyygbljwdajhfmwaejirzytuoyhyqzlzepgybovwttuiatfwcpyoqrmisc

[出力例]
465

[入力例]

abab

abba

[出力例]

※AtCoderのテストケースより

[入力例]

arc

cra

[出力例]

※AtCoderのテストケースより

[入力例]

pqrst

opqrs

[出力例]

-1

[入力例]

pqrpqrpqrp

[出力例]

[入力例]

mpgiytiagtmzuinudtjjawhbpibnfwaordasntnudtjjawhbpi

mpgiytiagtsntnudtjjawhbpimzuinudtjjawhbpibnfwaorda

[出力例]

[入力例]

100

pibnfwaordawwagcokbzekatmpgiytiagtsntnudtjjawhbpimzuinudtjjawhbyghmqyntdjphtlckueltiznnvnoeufuksahef

atyghmqyntdjphtlckueltiznnvnoeufuksahempgiytiagtsntnudtjjawhbpimzuinudtjjawhbpibnfwaordawwagcokbzekf

[出力例]

[入力例]

500

fsksicxhybwcetiaqgtmjlympuampnwxtgmhavxnsdpegtfwetkeyhufkcemxrfgelvdvrafixfhhanojvuthmsvxkyfrbfkfpxeofwmzcovmodktmumvjtwlgrtmxdgyqlzlgxjynfiflquoyhyqzlzepeiwgqjoixswqiagalfonvwedflwtldcdkgpzmravwrmyihsshtruvhmupxubtkddaexfiducbxixvkeushrsipxaktkcbftixyckzopppuljredlrgktntxjgaxrebrigybovwttuiatfwcpyoqrmiscvwwoqcibzcnddyxhmignqcxjlibcqqnvwkpovqafmyfbrldesgesbhxsnmbvpwfvzzzohtdsmjnznvftqbigsyclqoqxjuudyeqlsrsbzjbxtflvqbyheqlqlrlugaqfbdjfjwzeoltnfaioyygbljwdajhfmwaejirzytuotibelypoqvtxjdhzjnvarbtzim

fgelvdvrafixfhhanojvuthmsvrmyihsshtruvhmupxubtkddaexfiducbxixvkeushrsipxaktkcbftixyckzopppuljrexkyfrbfkfpxeofwmzcovmodktmumvjtwldlrgktntxjgaxrebrivwwoqcibzcnddyxhmignqcxjlibcqqnvwkpovqafmyfbrlderbtzimgrtmxdgyqlzlgxjynfieiwgqjoixswqiagalsgesbhxsnmbvpwfvohtdsmjnznvftqbigsyclqoqxjuudyeqlsrsbzjbxttibelypoqvtxjdhzjnvafonvwgpzmravpuampnwxtgmhavxnsdpegtfwetkeyhufkcemxrffskzzzsicxhybwcetiaqgtmjlymwedflwtldcdklquoflvqbyheqlqlrlugaqfbdjfjwzeoltnfaioyygbljwdajhfmwaejirzytuoyhyqzlzepgybovwttuiatfwcpyoqrmisc

[出力例]

465

■参照サイト
AtCoder Regular Contest 154

2023年1月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 250 の問題G (Stonks) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &p[i]);
    
    // 2. 株式売買.
    multiset<LL> mst{p[0]};
    LL ans = 0;
    repx(i, 1, N){
        // 2-1. 多重集合の最小値 m よりも大きい.
        auto s = mst.begin();
        if(p[i] > *s){
            // 加算.
            ans += p[i] - *s;
            
            // m を 一つ削除.
            mst.erase(mst.find(*s));
            
            // p[i] を 二つ追加.
            mst.insert(p[i]);
            mst.insert(p[i]);
            
            // 次へ.
            continue;
        }
        
        // 2-2. 上記以外.
        // p[i] を 一つ追加.
        mst.insert(p[i]);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc250/editorial/3929

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 株式売買.

multiset<LL> mst{p[0]};

LL ans = 0;

repx(i, 1, N){

// 2-1. 多重集合の最小値 m よりも大きい.

auto s = mst.begin();

if(p[i] > *s){

// 加算.

ans += p[i] - *s;

// m を一つ削除.

mst.erase(mst.find(*s));

// p[i] を二つ追加.

mst.insert(p[i]);

// 次へ.

continue;

}

// 2-2. 上記以外.

// p[i] を一つ追加.

mst.insert(p[i]);

}

// 3. 出力.

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

return 0;

}

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

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

[入力例]
5
10000 1000 100 10 1

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

[入力例]
15
300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000

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

[入力例]
3
1 2 3

[出力例]
2

[入力例]
10
36 20 111 25 33 30 27 81 9 90

[出力例]
234

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

[出力例]
55

[入力例]
100
6690 7423 11902 3154 588 26 6624 10736 936 11162 10812 3451 8077 6682 332 11911 7566 1823 10226 8771 1821 2688 7867 688 3434 647 5539 2352 3853 5491 2200 7983 3677 8121 8989 10191 7285 8617 6973 5990 8029 6076 7992 21 2682 10838 5080 5987 11349 11797 9335 8847 6442 4158 8592 4701 12286 2214 11222 7583 8060 6700 9963 5903 12232 785 7842 8471 6665 2495 5977 1284 4888 71 1132 7018 5674 3170 10052 397 54 2534 9787 1634 3389 7259 530 8630 206 9697 9521 9159 11933 3273 1846 11222 836 4815 5777 7365

[出力例]
300000

[入力例]

2 5 4 3 7 1 8 6

[出力例]

※AtCoderテストケースより

[入力例]

10000 1000 100 10 1

[出力例]

※AtCoderテストケースより

[入力例]

300 1 4000 1 50000 900000000 20 600000 50000 300 50000 80000000 900000000 7000000 900000000

[出力例]

2787595378

※AtCoderテストケースより

[入力例]

1 2 3

[出力例]

[入力例]

36 20 111 25 33 30 27 81 9 90

[出力例]

234

[入力例]

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

[出力例]

[入力例]

100

6690 7423 11902 3154 588 26 6624 10736 936 11162 10812 3451 8077 6682 332 11911 7566 1823 10226 8771 1821 2688 7867 688 3434 647 5539 2352 3853 5491 2200 7983 3677 8121 8989 10191 7285 8617 6973 5990 8029 6076 7992 21 2682 10838 5080 5987 11349 11797 9335 8847 6442 4158 8592 4701 12286 2214 11222 7583 8060 6700 9963 5903 12232 785 7842 8471 6665 2495 5977 1284 4888 71 1132 7018 5674 3170 10052 397 54 2534 9787 1634 3389 7259 530 8630 206 9697 9521 9159 11933 3273 1846 11222 836 4815 5777 7365

[出力例]

300000

■参照サイト
AtCoder Beginner Contest 250

2023年1月28日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld %lld", &x[i], &y[i]);
        x[i + N] = x[i];
        y[i + N] = y[i];
    }
    
    // 2. ピザの面積(の二倍).
    LL S = 0;
    repx(i, 1, N) S += abs((x[i] - x[0]) * (y[i + 1] - y[0]) - (x[i + 1] - x[0]) * (y[i] - y[0]));
    
    // 3. 尺取り法.
    LL E = 0, ans = INF;
    int cur = 1;
    rep(p, N){
        // 頂点 p, (p + 1), q.
        int q = cur;
        LL px0 = x[p + 0], py0 = y[p + 0];
        LL px1 = x[p + 1], py1 = y[p + 1];
        
        // 食べる部分を増やしていく.
        repx(j, q, p + N){
            // 頂点 q, (q + 1).
            LL qx0 = x[j + 0], qy0 = y[j + 0];
            LL qx1 = x[j + 1], qy1 = y[j + 1];
            
            // インデックス更新.
            cur = j;
            
            // 最小値更新.
            ans = min(ans, abs(S - E * 4));
            
            // 評価.
            if(E * 4 < S){
                // 加算(頂点 p, q, (q + 1) からなる三角形).
                E += abs((qx0 - px0) * (qy1 - py0) - (qx1 - px0) * (qy0 - py0));
                
                // 次へ.
                continue;
            }
            
            // 減算(頂点 p, (p + 1), q からなる三角形).
            E -= abs((px1 - px0) * (qy0 - py0) - (qx0 - px0) * (py1 - py0));
            
            // 終了.
            break;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc250/editorial/3928

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL INF = 2020202020202020202;

LL x[202020], y[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

scanf("%lld %lld", &x[i], &y[i]);

x[i + N] = x[i];

y[i + N] = y[i];

}

// 2. ピザの面積(の二倍).

LL S = 0;

repx(i, 1, N) S += abs((x[i] - x[0]) * (y[i + 1] - y[0]) - (x[i + 1] - x[0]) * (y[i] - y[0]));

// 3. 尺取り法.

LL E = 0, ans = INF;

int cur = 1;

rep(p, N){

// 頂点 p, (p + 1), q.

int q = cur;

LL px0 = x[p + 0], py0 = y[p + 0];

LL px1 = x[p + 1], py1 = y[p + 1];

// 食べる部分を増やしていく.

repx(j, q, p + N){

// 頂点 q, (q + 1).

LL qx0 = x[j + 0], qy0 = y[j + 0];

LL qx1 = x[j + 1], qy1 = y[j + 1];

// インデックス更新.

cur = j;

// 最小値更新.

ans = min(ans, abs(S - E * 4));

// 評価.

if(E * 4 < S){

// 加算(頂点 p, q, (q + 1) からなる三角形).

E += abs((qx0 - px0) * (qy1 - py0) - (qx1 - px0) * (qy0 - py0));

// 次へ.

continue;

}

// 減算(頂点 p, (p + 1), q からなる三角形).

E -= abs((px1 - px0) * (qy0 - py0) - (qx0 - px0) * (py1 - py0));

// 終了.

break;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
4
400000000 400000000
-400000000 400000000
-400000000 -400000000
400000000 -400000000

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

[入力例]
6
-816 222
-801 -757
-165 -411
733 131
835 711
-374 979

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

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

[出力例]
9

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

[出力例]
12

[出力例]
13
21 0
20 5
18 7
15 10
12 11
8 7
6 5
3 2
5 -1
10 -5
13 -7
16 -6
18 -2

[出力例]
7

[入力例]

3 0

2 3

-1 3

-3 1

-1 -1

[出力例]

※AtCoderテストケースより

[入力例]

400000000 400000000

-400000000 400000000

-400000000 -400000000

400000000 -400000000

[出力例]

1280000000000000000

※AtCoderテストケースより

[入力例]

-816 222

-801 -757

-165 -411

733 131

835 711

-374 979

[出力例]

157889

※AtCoderテストケースより

[入力例]

0 -1

2 -2

5 1

4 3

1 4

-1 2

[出力例]

[入力例]

7 1

6 5

5 7

3 10

0 9

-2 4

-1 -3

3 -5

6 -2

[出力例]

21 0

20 5

18 7

15 10

12 11

8 7

6 5

3 2

5 -1

10 -5

13 -7

16 -6

18 -2

[出力例]

■参照サイト
AtCoder Beginner Contest 250

2023年1月25日

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

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

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i + 1]);
    
    // 2. 数列 B.
    repr(i, N - 1, 0) b[i] = b[i + 1] + a[i + 1];
    
    // 3. 整数列 x となる条件を満たすか？
    auto f = [&]() -> bool {
        // 返却値.
        bool ok = true;
        
        // 各項が, 1e12 以下か？
        repx(i, 1, N + 1) if(abs(x[i]) > 1e12) ok = false;
        
        // 単調増加か？
        repx(i, 1, N) if(x[i] >= x[i + 1]) ok = false;
        
        // 合計が, ゼロか？
        LL t = 0;
        repx(i, 1, N + 1) t += a[i] * x[i];
        if(t != 0) ok = false;
        
        // 返却.
        return ok;
    };
    
    // 4. 整数列 x 構築.
    // 4-1. B[0] != 0.
    if(b[0] != 0){
        repx(i, 1, N) y[i] = abs(b[0]);
        repx(i, 1, N) y[0] += b[i] * abs(b[0]);
        y[0] /= -b[0];
        repx(i, 1, N + 1) x[i] = x[i - 1] + y[i - 1];
        assert(f());
        puts("Yes");
        repx(i, 1, N + 1) printf("%lld%s", x[i], (i < N) ? " " : "\n");
    }
    
    // 4-2. B[0] == 0.
    if(b[0] == 0){
        // 符号チェック.
        int p = 0, m = 0;
        rep(i, N){
            p += (b[i] >= 0);
            m += (b[i] <= 0);
        }
        
        // 解あり.
        if(p != N && m != N){
            // p, q 計算.
            int p = -1, q = -1;
            rep(i, N){
                if(p == -1 && b[i] == -1) p = i;
                if(q == -1 && b[i] == +1) q = i;
            }
            assert(p != -1 && p != -1);
            
            // X 計算.
            LL X = 0;
            repx(i, 1, N) X += b[i];
            
            // X >= 0.
            if(X >= 0){
                rep(i, N) y[i] = 1;
                y[p] = 1 + X;
                repx(i, 1, N + 1) x[i] = x[i - 1] + y[i - 1];
                assert(f());
                puts("Yes");
                repx(i, 1, N + 1) printf("%lld%s", x[i], (i < N) ? " " : "\n");
            }
            
            // X < 0.
            if(X < 0){
                rep(i, N) y[i] = 1;
                y[q] = 1 - X;
                repx(i, 1, N + 1) x[i] = x[i - 1] + y[i - 1];
                assert(f());
                puts("Yes");
                repx(i, 1, N + 1) printf("%lld%s", x[i], (i < N) ? " " : "\n");
            }
        }
        
        // 解なし.
        if(p == N || m == N) puts("No");
    }
    return 0;
    
}

100

101

102

103

104

// 解き直し.

// https://atcoder.jp/contests/arc153/editorial/5485

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020], b[202020], x[202020], y[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 数列 B.

repr(i, N - 1, 0) b[i] = b[i + 1] + a[i + 1];

// 3. 整数列 x となる条件を満たすか？

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

// 返却値.

bool ok = true;

// 各項が, 1e12 以下か？

repx(i, 1, N + 1) if(abs(x[i]) > 1e12) ok = false;

// 単調増加か？

repx(i, 1, N) if(x[i] >= x[i + 1]) ok = false;

// 合計が, ゼロか？

LL t = 0;

repx(i, 1, N + 1) t += a[i] * x[i];

if(t != 0) ok = false;

// 返却.

return ok;

};

// 4. 整数列 x 構築.

// 4-1. B[0] != 0.

if(b[0] != 0){

repx(i, 1, N) y[i] = abs(b[0]);

repx(i, 1, N) y[0] += b[i] * abs(b[0]);

y[0] /= -b[0];

repx(i, 1, N + 1) x[i] = x[i - 1] + y[i - 1];

assert(f());

puts("Yes");

repx(i, 1, N + 1) printf("%lld%s", x[i], (i < N) ? " " : "\n");

}

// 4-2. B[0] == 0.

if(b[0] == 0){

// 符号チェック.

int p = 0, m = 0;

rep(i, N){

p += (b[i] >= 0);

m += (b[i] <= 0);

}

// 解あり.

if(p != N && m != N){

// p, q 計算.

int p = -1, q = -1;

rep(i, N){

if(p == -1 && b[i] == -1) p = i;

if(q == -1 && b[i] == +1) q = i;

}

assert(p != -1 && p != -1);

// X 計算.

LL X = 0;

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

// X >= 0.

if(X >= 0){

rep(i, N) y[i] = 1;

y[p] = 1 + X;

repx(i, 1, N + 1) x[i] = x[i - 1] + y[i - 1];

assert(f());

puts("Yes");

repx(i, 1, N + 1) printf("%lld%s", x[i], (i < N) ? " " : "\n");

}

// X < 0.

if(X < 0){

rep(i, N) y[i] = 1;

y[q] = 1 - X;

repx(i, 1, N + 1) x[i] = x[i - 1] + y[i - 1];

assert(f());

puts("Yes");

repx(i, 1, N + 1) printf("%lld%s", x[i], (i < N) ? " " : "\n");

}

// 解なし.

if(p == N || m == N) puts("No");

}

return 0;

}

[入力例]
5
-1 1 -1 -1 1

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

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

[入力例]
1
-1

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

[入力例]
2
1 -1

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

[入力例]
7
-1 -1 1 1 1 -1 1

[出力例]
Yes
-9 -8 -7 -6 -5 -4 -3

[入力例]
8
1 -1 1 -1 1 -1 1 -1

[出力例]
No

[入力例]
10
1 -1 1 1 -1 -1 1 -1 -1 1

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

[入力例]
12
-1 -1 1 1 -1 1 1 1 -1 -1 1 -1

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

[入力例]
16
1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1

[出力例]
Yes
1 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

[入力例]
20
1 1 1 1 -1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1

[出力例]
Yes
-100 -88 -76 -64 -52 -40 -28 -16 -4 8 20 32 44 56 68 80 92 104 116 128

[入力例]
100
1 -1 1 1 -1 1 1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 -1

[出力例]
Yes
566 568 570 572 574 576 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610 612 614 616 618 620 622 624 626 628 630 632 634 636 638 640 642 644 646 648 650 652 654 656 658 660 662 664 666 668 670 672 674 676 678 680 682 684 686 688 690 692 694 696 698 700 702 704 706 708 710 712 714 716 718 720 722 724 726 728 730 732 734 736 738 740 742 744 746 748 750 752 754 756 758 760 762 764

[入力例]
500
1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 1 1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 1

[出力例]
Yes
-388 -386 -384 -382 -380 -378 -376 -374 -372 -370 -368 -366 -364 -362 -360 -358 -356 -354 -352 -350 -348 -346 -344 -342 -340 -338 -336 -334 -332 -330 -328 -326 -324 -322 -320 -318 -316 -314 -312 -310 -308 -306 -304 -302 -300 -298 -296 -294 -292 -290 -288 -286 -284 -282 -280 -278 -276 -274 -272 -270 -268 -266 -264 -262 -260 -258 -256 -254 -252 -250 -248 -246 -244 -242 -240 -238 -236 -234 -232 -230 -228 -226 -224 -222 -220 -218 -216 -214 -212 -210 -208 -206 -204 -202 -200 -198 -196 -194 -192 -190 -188 -186 -184 -182 -180 -178 -176 -174 -172 -170 -168 -166 -164 -162 -160 -158 -156 -154 -152 -150 -148 -146 -144 -142 -140 -138 -136 -134 -132 -130 -128 -126 -124 -122 -120 -118 -116 -114 -112 -110 -108 -106 -104 -102 -100 -98 -96 -94 -92 -90 -88 -86 -84 -82 -80 -78 -76 -74 -72 -70 -68 -66 -64 -62 -60 -58 -56 -54 -52 -50 -48 -46 -44 -42 -40 -38 -36 -34 -32 -30 -28 -26 -24 -22 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 200 202 204 206 208 210 212 214 216 218 220 222 224 226 228 230 232 234 236 238 240 242 244 246 248 250 252 254 256 258 260 262 264 266 268 270 272 274 276 278 280 282 284 286 288 290 292 294 296 298 300 302 304 306 308 310 312 314 316 318 320 322 324 326 328 330 332 334 336 338 340 342 344 346 348 350 352 354 356 358 360 362 364 366 368 370 372 374 376 378 380 382 384 386 388 390 392 394 396 398 400 402 404 406 408 410 412 414 416 418 420 422 424 426 428 430 432 434 436 438 440 442 444 446 448 450 452 454 456 458 460 462 464 466 468 470 472 474 476 478 480 482 484 486 488 490 492 494 496 498 500 502 504 506 508 510 512 514 516 518 520 522 524 526 528 530 532 534 536 538 540 542 544 546 548 550 552 554 556 558 560 562 564 566 568 570 572 574 576 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610

[入力例]

-1 1 -1 -1 1

[出力例]

Yes

-3 -1 4 5 7

※AtCoderテストケースより

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

Yes

0 1 2 3 4

[入力例]

-1

[出力例]

Yes

※AtCoderテストケースより

[入力例]

1 -1

[出力例]

※AtCoderテストケースより

[入力例]

-1 -1 1 1 1 -1 1

[出力例]

Yes

-9 -8 -7 -6 -5 -4 -3

[入力例]

1 -1 1 -1 1 -1 1 -1

[出力例]

[入力例]

1 -1 1 1 -1 -1 1 -1 -1 1

[出力例]

Yes

1 2 3 4 5 6 7 8 9 15

[入力例]

-1 -1 1 1 -1 1 1 1 -1 -1 1 -1

[出力例]

Yes

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

[入力例]

1 -1 -1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1

[出力例]

Yes

1 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

[入力例]

1 1 1 1 -1 1 1 1 1 -1 1 1 1 -1 1 1 1 1 1 -1

[出力例]

Yes

-100 -88 -76 -64 -52 -40 -28 -16 -4 8 20 32 44 56 68 80 92 104 116 128

[入力例]

100

1 -1 1 1 -1 1 1 -1 -1 1 1 1 1 1 1 1 1 1 1 -1 -1 1 1 1 1 -1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 1 -1 1 -1

[出力例]

Yes

566 568 570 572 574 576 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610 612 614 616 618 620 622 624 626 628 630 632 634 636 638 640 642 644 646 648 650 652 654 656 658 660 662 664 666 668 670 672 674 676 678 680 682 684 686 688 690 692 694 696 698 700 702 704 706 708 710 712 714 716 718 720 722 724 726 728 730 732 734 736 738 740 742 744 746 748 750 752 754 756 758 760 762 764

[入力例]

500

1 -1 -1 1 1 -1 1 -1 1 1 1 1 1 1 -1 1 1 1 1 1 -1 1 -1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 1 1 -1 1 1 1 -1 1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 -1 1 1 -1 -1 1 -1 -1 1 1 -1 -1 1 1 -1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 1 1 1 1 -1 1 -1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 1 1 1 1 -1 1 -1 1 1 -1 -1 1 -1 -1 1 -1 -1 -1 -1 1 1 -1 1 1 1 -1 -1 -1 1 -1 -1 1 -1 1 -1 -1 1 -1 1 -1 -1 1 1 -1 1 1 -1 1 1 1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 -1 -1 -1 1 -1 1 -1 -1 -1 -1 -1 1 1 -1 -1 -1 1 1 -1 -1 -1 -1 1 1 1 -1 -1 -1 1 1 -1 -1 -1 1 -1 1 -1 -1 1 1 1 -1 -1 1 1 -1 -1 1 -1 -1 -1 1 1 -1 1 1 1 1 1 1 -1 -1 -1 -1 1 -1 1 1 -1 1 -1 -1 -1 1 1 1 1 1 -1 -1 -1 1 1 1 1 1 -1 1 1 1 -1 1 -1 -1 -1 1 -1 1 1 1 -1 -1 1 -1 1 1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 1 -1 -1 -1 -1 1 -1 1 -1 1 -1 -1 1 -1 1 -1 1 1 -1 1 1 -1 -1 1 1 1 -1 -1 1 -1 1 1 -1 -1 -1 -1 1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 1 1 1 -1 1 1 1 -1 1 -1 1 -1 -1 -1 1 -1 1 1 1 1 1 -1 1 1 1 -1 -1 1 1 1 -1 1 1 1 1 -1 -1 -1 -1 1 -1 -1 -1 1 1 1 1 -1 1 1 1 1 -1 1 -1 1 -1 1 1 -1 1 -1 1 1 -1 -1 -1 1 1 1 1 -1 1 1 -1 1 1 -1 -1 1 -1 -1 1 1 -1 1 -1 -1 -1 1 -1 1 -1 -1 1 1

[出力例]

Yes

-388 -386 -384 -382 -380 -378 -376 -374 -372 -370 -368 -366 -364 -362 -360 -358 -356 -354 -352 -350 -348 -346 -344 -342 -340 -338 -336 -334 -332 -330 -328 -326 -324 -322 -320 -318 -316 -314 -312 -310 -308 -306 -304 -302 -300 -298 -296 -294 -292 -290 -288 -286 -284 -282 -280 -278 -276 -274 -272 -270 -268 -266 -264 -262 -260 -258 -256 -254 -252 -250 -248 -246 -244 -242 -240 -238 -236 -234 -232 -230 -228 -226 -224 -222 -220 -218 -216 -214 -212 -210 -208 -206 -204 -202 -200 -198 -196 -194 -192 -190 -188 -186 -184 -182 -180 -178 -176 -174 -172 -170 -168 -166 -164 -162 -160 -158 -156 -154 -152 -150 -148 -146 -144 -142 -140 -138 -136 -134 -132 -130 -128 -126 -124 -122 -120 -118 -116 -114 -112 -110 -108 -106 -104 -102 -100 -98 -96 -94 -92 -90 -88 -86 -84 -82 -80 -78 -76 -74 -72 -70 -68 -66 -64 -62 -60 -58 -56 -54 -52 -50 -48 -46 -44 -42 -40 -38 -36 -34 -32 -30 -28 -26 -24 -22 -20 -18 -16 -14 -12 -10 -8 -6 -4 -2 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100 102 104 106 108 110 112 114 116 118 120 122 124 126 128 130 132 134 136 138 140 142 144 146 148 150 152 154 156 158 160 162 164 166 168 170 172 174 176 178 180 182 184 186 188 190 192 194 196 198 200 202 204 206 208 210 212 214 216 218 220 222 224 226 228 230 232 234 236 238 240 242 244 246 248 250 252 254 256 258 260 262 264 266 268 270 272 274 276 278 280 282 284 286 288 290 292 294 296 298 300 302 304 306 308 310 312 314 316 318 320 322 324 326 328 330 332 334 336 338 340 342 344 346 348 350 352 354 356 358 360 362 364 366 368 370 372 374 376 378 380 382 384 386 388 390 392 394 396 398 400 402 404 406 408 410 412 414 416 418 420 422 424 426 428 430 432 434 436 438 440 442 444 446 448 450 452 454 456 458 460 462 464 466 468 470 472 474 476 478 480 482 484 486 488 490 492 494 496 498 500 502 504 506 508 510 512 514 516 518 520 522 524 526 528 530 532 534 536 538 540 542 544 546 548 550 552 554 556 558 560 562 564 566 568 570 572 574 576 578 580 582 584 586 588 590 592 594 596 598 600 602 604 606 608 610

■参照サイト
AtCoder Regular Contest 153

2023年1月24日2023年1月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 153 の問題A (AABCDDEFE) ～問題B (Grid Rotations) を解いてみた.

■感想.
1. 問題B は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで, 操作後のグリッドの状態が分かる点が, 非常に不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■C++版プログラム(問題A／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 main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 全探索.
    int idx = 0;
    repx(s12, 1, 10){
        rep(s3, 10){
            rep(s4, 10){
                rep(s56, 10){
                    rep(s79, 10){
                        rep(s8, 10){
                            // 見つかった.
                            if(++idx == N){
                                int ans = 0;
                                ans += 1e8 * s12;
                                ans += 1e7 * s12;
                                ans += 1e6 * s3;
                                ans += 1e5 * s4;
                                ans += 1e4 * s56;
                                ans += 1e3 * s56;
                                ans += 1e2 * s79;
                                ans += 1e1 * s8;
                                ans += 1e0 * s79;
                                
                                // 出力.
                                printf("%d\n", ans);
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
    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 main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 全探索.

int idx = 0;

repx(s12, 1, 10){

rep(s3, 10){

rep(s4, 10){

rep(s56, 10){

rep(s79, 10){

rep(s8, 10){

// 見つかった.

if(++idx == N){

int ans = 0;

ans += 1e8 * s12;

ans += 1e7 * s12;

ans += 1e6 * s3;

ans += 1e5 * s4;

ans += 1e4 * s56;

ans += 1e3 * s56;

ans += 1e2 * s79;

ans += 1e1 * s8;

ans += 1e0 * s79;

// 出力.

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

return 0;

}

return 0;

}

[入力例]
3

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

[入力例]
882436

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

[入力例]
2023

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

[入力例]
321

[出力例]
110033202

[入力例]
31415

[出力例]
113144141

[入力例]
900000

[出力例]
999999999

[入力例]

[出力例]

110000020

※AtCoderのテストケースより

[入力例]

882436

[出力例]

998244353

※AtCoderのテストケースより

[入力例]

2023

[出力例]

110200222

※AtCoderのテストケースより

[入力例]

321

[出力例]

110033202

[入力例]

31415

[出力例]

113144141

[入力例]

900000

[出力例]

999999999

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

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

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    vs grid(H);
    rep(i, H){
        char c[W + 1];
        scanf("%s", c);
        string s(c);
        grid[i] = s;
    }
    
    // 2. 長方形に含まれるか？
    auto f = [&](P p, int sx, int sy, int gx, int gy) -> bool {
        return (p.a >= sx && p.b >= sy && p.a <= gx && p.b <= gy);
    };
    
    // 3. クエリ.
    // -> 長方形領域 に応じて, 移動先更新.
    // 左上: [1, 1]         ～ [a, b]
    // 左下: [a + 1, 1]     ～ [H, b]
    // 右上: [1, b + 1]     ～ [a, W]
    // 右下: [a + 1, b + 1] ～ [H, W]
    int Q;
    scanf("%d", &Q);
    vp g;
    g.pb({1, 1}); // [1, 1].
    g.pb({1, 2}); // [1, 2].
    g.pb({2, 1}); // [2, 1].
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int a, b;
        scanf("%d %d", &a, &b);
        
        // 3-2. [1, 1], [1, 2], [2, 1].
        rep(j, 3){
            int tx = 0;
            int ty = 0;
            
            // 左上.
            if(f(g[j], 1, 1, a, b)){
                tx = a + 1;
                ty = b + 1;
            }
            
            // 左下.
            if(f(g[j], a + 1, 1, H, b)){
                tx = H + a + 1;
                ty = b + 1;
            }
            
            // 右上.
            if(f(g[j], 1, b + 1, a, W)){
                tx = a + 1;
                ty = W + b + 1;
            }
            
            // 右下.
            if(f(g[j], a + 1, b + 1, H, W)){
                tx = H + a + 1;
                ty = W + b + 1;
            }
            
            // 移動.
            g[j].a = tx - g[j].a;
            g[j].b = ty - g[j].b;
        }
    }
    
    // 4. 移動先(数列).
    // 4-1. 行方向.
    vi wSequence(W);
    wSequence[0] = g[0].b;
    wSequence[1] = g[1].b;
    repx(i, 2, W){
        wSequence[i] = wSequence[i - 1];
        wSequence[i] += (wSequence[i - 1] - wSequence[i - 2]);
        wSequence[i] += W;
        wSequence[i] %= W;
        if(wSequence[i] == 0) wSequence[i] = W;
    }
    
    // 4-2. 列方向.
    vi hSequence(H);
    hSequence[0] = g[0].a;
    hSequence[1] = g[2].a;
    repx(i, 2, H){
        hSequence[i] = hSequence[i - 1];
        hSequence[i] += (hSequence[i - 1] - hSequence[i - 2]);
        hSequence[i] += H;
        hSequence[i] %= H;
        if(hSequence[i] == 0) hSequence[i] = H;
    }
    
    // 5. 変化後のグリッド.
    vs ans(H);
    rep(i, H){
        string s(W, '.');
        rep(j, W) s[wSequence[j] - 1] = grid[i][j];
        ans[hSequence[i] - 1] = s;
    }
    
    // 6. 出力.
    rep(i, H) printf("%s\n", ans[i].c_str());
    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

// 解き直し.

// https://atcoder.jp/contests/arc153/editorial/5484

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vs = vector<string>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int H, W;

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

vs grid(H);

rep(i, H){

char c[W + 1];

scanf("%s", c);

string s(c);

grid[i] = s;

}

// 2. 長方形に含まれるか？

auto f = [&](P p, int sx, int sy, int gx, int gy) -> bool {

return (p.a >= sx && p.b >= sy && p.a <= gx && p.b <= gy);

};

// 3. クエリ.

// -> 長方形領域に応じて, 移動先更新.

// 左上: [1, 1] ～ [a, b]

// 左下: [a + 1, 1] ～ [H, b]

// 右上: [1, b + 1] ～ [a, W]

// 右下: [a + 1, b + 1] ～ [H, W]

int Q;

scanf("%d", &Q);

vp g;

g.pb({1, 1}); // [1, 1].

g.pb({1, 2}); // [1, 2].

g.pb({2, 1}); // [2, 1].

rep(i, Q){

// 3-1. クエリ入力情報.

int a, b;

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

// 3-2. [1, 1], [1, 2], [2, 1].

rep(j, 3){

int tx = 0;

int ty = 0;

// 左上.

if(f(g[j], 1, 1, a, b)){

tx = a + 1;

ty = b + 1;

}

// 左下.

if(f(g[j], a + 1, 1, H, b)){

tx = H + a + 1;

ty = b + 1;

}

// 右上.

if(f(g[j], 1, b + 1, a, W)){

tx = a + 1;

ty = W + b + 1;

}

// 右下.

if(f(g[j], a + 1, b + 1, H, W)){

tx = H + a + 1;

ty = W + b + 1;

}

// 移動.

g[j].a = tx - g[j].a;

g[j].b = ty - g[j].b;

}

// 4. 移動先(数列).

// 4-1. 行方向.

vi wSequence(W);

wSequence[0] = g[0].b;

wSequence[1] = g[1].b;

repx(i, 2, W){

wSequence[i] = wSequence[i - 1];

wSequence[i] += (wSequence[i - 1] - wSequence[i - 2]);

wSequence[i] += W;

wSequence[i] %= W;

if(wSequence[i] == 0) wSequence[i] = W;

}

// 4-2. 列方向.

vi hSequence(H);

hSequence[0] = g[0].a;

hSequence[1] = g[2].a;

repx(i, 2, H){

hSequence[i] = hSequence[i - 1];

hSequence[i] += (hSequence[i - 1] - hSequence[i - 2]);

hSequence[i] += H;

hSequence[i] %= H;

if(hSequence[i] == 0) hSequence[i] = H;

}

// 5. 変化後のグリッド.

vs ans(H);

rep(i, H){

string s(W, '.');

rep(j, W) s[wSequence[j] - 1] = grid[i][j];

ans[hSequence[i] - 1] = s;

}

// 6. 出力.

rep(i, H) printf("%s\n", ans[i].c_str());

return 0;

}

[入力例]
4 5
abcde
fghij
klmno
pqrst
1
3 3

[出力例]
mlkon
hgfji
cbaed
rqpts
※AtCoderのテストケースより

[入力例]
3 7
atcoder
regular
contest
2
1 1
2 5

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

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

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

[入力例]
5 6
abcdef
ghijkl
mnopqr
stuvwx
yzabcd
3
1 3
2 3
4 5

[出力例]
qponmr
kjihgl
edcbaf
cbazyd
wvutsx

[入力例]
10 13
tgaiplwcarqvr
jcbxsaceowkvr
zlgfizldbdykc
wsuiehmwxgenk
yennclmvitqyj
cvbgnfgiijfaw
caoenyfbixzjw
hcuhogtbdlrzx
mmlpsutxgfoyf
yxgeoakdybqbj
5
9 2
7 5
6 1
4 9
1 11

[出力例]
jyqtivmlcnney
knegxwmheiusw
ckydbdlzifglz
rvkwoecasxbcj
rvqracwlpiagt
jbqbydkaoegxy
fyofgxtusplmm
xzrldbtgohuch
wjzxibfyneoac
wafjiigfngbvc

[入力例]
30 30
zlfuxyhbmlafcmykqjhqfxzdpsdcye
hrburupmvtcxigyaheuaxyhaledflw
slnzchgsigwtagnqwjalonbdqddidq
htifmgawdkraswqobqdxuppvlomrmj
kwmvtcmlgholgztnxkfcufzovxbjtl
zrvjaxarsqtvxjkydqwbekjagdmraf
oaxenrkklngmbfwqflmjdwfppricbu
wnjxgpujanfmwlvflmctkqyeozhcaf
nvzgzmqoeagdrkasjiwxoxrcszjlfo
dirylpnobhsbxkwwxxaqjkxzdyddsi
yyawndqdhiibtouonhcqdvyhftmnyh
lfyvkxbjhupgjkyqwaxgjdugewoetm
ihaylrvcegejtbyupofjxogkcbgfho
kqokpfokthlimtvbwjfnpjdaeqinms
adxzqrgfgkiwacfsbrioomsmpwyybc
mdewbkbcfftilrprxcecxbwxejblwt
qfstklfwvwahvammwujyvzscthwymn
wvlopkalgkdyiqddzgtkwvesaqtnbj
alywjbfosqktwtwfiezxgtnggnisua
vslitdjcgldturboqianadtpsbeyos
bplursgzyryyqgrjznhfniumiswjbk
xpihoeznhbhmzakkkpknxoklgysnvl
xbarzttrjwzmmqxaavyycwbaajdrhf
qfvcjkvtprjbocnbkbateqhtphjrbc
vccdtqjrcoqepwrznmmhylqkopgysr
tmaamlgdfxohtmyprpmwgjelbhmqnm
uvxqkuholicwvhbzqcumbvwqigirga
kjsqvscvzscucztmylttcrhymwnjnw
dokiptkkeccxbqiqdoldqciivfcnrr
gixxzovfgymntqbyhxenzkqwnvttkz
20
23 5
17 3
9 27
22 21
5 7
2 23
28 26
14 17
3 22
25 23
16 25
6 1
1 14
21 4
11 1
17 15
25 9
10 5
5 26
15 12

[出力例]
anfmwlvflmctkqyeozhcafwnjxgpuj
eagdrkasjiwxoxrcszjlfonvzgzmqo
bhsbxkwwxxaqjkxzdyddsidirylpno
hiibtouonhcqdvyhftmnyhyyawndqd
hupgjkyqwaxgjdugewoetmlfyvkxbj
egejtbyupofjxogkcbgfhoihaylrvc
thlimtvbwjfnpjdaeqinmskqokpfok
gkiwacfsbrioomsmpwyybcadxzqrgf
fftilrprxcecxbwxejblwtmdewbkbc
vwahvammwujyvzscthwymnqfstklfw
gkdyiqddzgtkwvesaqtnbjwvlopkal
sqktwtwfiezxgtnggnisuaalywjbfo
gldturboqianadtpsbeyosvslitdjc
yryyqgrjznhfniumiswjbkbplursgz
hbhmzakkkpknxoklgysnvlxpihoezn
jwzmmqxaavyycwbaajdrhfxbarzttr
prjbocnbkbateqhtphjrbcqfvcjkvt
coqepwrznmmhylqkopgysrvccdtqjr
fxohtmyprpmwgjelbhmqnmtmaamlgd
licwvhbzqcumbvwqigirgauvxqkuho
zscucztmylttcrhymwnjnwkjsqvscv
eccxbqiqdoldqciivfcnrrdokiptkk
gymntqbyhxenzkqwnvttkzgixxzovf
mlafcmykqjhqfxzdpsdcyezlfuxyhb
vtcxigyaheuaxyhaledflwhrburupm
igwtagnqwjalonbdqddidqslnzchgs
dkraswqobqdxuppvlomrmjhtifmgaw
gholgztnxkfcufzovxbjtlkwmvtcml
sqtvxjkydqwbekjagdmrafzrvjaxar
lngmbfwqflmjdwfppricbuoaxenrkk

[入力例]
52 48
lxlxtoqsbdwfdenrehhlxnkvjumbrxwmtxprxwyugjimgbji
erjcoskytrgpqzaraddmwodsvscwulesyzgtuzzkpdmfxmhb
chbzvmbejqrcdyfaoqdrgvuammogozyhfisgvmdcoxttgagq
hubeegribiqattvugiwmxmwlcejhjcjkcjgwsqaumwlyrfdj
unadargbnpgyweimzhpqhrbwrrguybjgdtuhhraumoitgsao
lwzvmfosvxitavjqndyorcyukgcftvkqqdfnggewbeerfwti
aawgpuptpkhzrfpifwwpoohcwwtymrfsrpkrkosgyeyhltfb
vyurxgwrullponlprhwlzfkhlcqlklfexaxiifgbobeldxbq
zdxkjwfsegioeungcovdyualkxyelomuxwvkhhwcmpdeanzl
fyomqrvqbdqmsjxcssudrlegffshqnkwqgqxpzfckaxjufzq
jsxdokejmvuwskvwbycvguuggeaickgrvzmvbduyrbikxsor
jmykcdmgnvprdorzybaywujgejdcwyyffskfeklhwknljzmw
kiqdzzmkmohemdvdufanplcpegzmifbglrgmzhgtqkxopnju
kgfwvaywkqmvhtpbrpfobvlkjhyfvigvlevliaomftqozsbg
equiujwjhmgochzbiofmyydkfzpezzsfhutloufttghngrru
kzsmxdflbikkpozwkxnxivtzshqdlwyifmtxnwupunpzvscr
jahbemkkcygkpaggvgavayukjahelvygxdiwigzzjyyevcao
mdutvyjhttvyumjeruphqnvuafzgjzrcgbimlkhodruxbteb
bpisbtkcwhchfkfnnnefgzosywmbplaopbodpgyqvwizplia
sydrenukpkhyppxktfgfyzivhusojbgcfukoygdjcispndup
tgwmkmnzchpzjkmggtbuehhshxmcvtbtcagoqzjszqmrnuee
mqrwouubcfoagowizqhlccnwbcbkryvjdqobvfyltenznord
uqaxyusonbitwhrkkkvmhekyywzjoibllpgjtdpczatddopw
lcquihmsadgtavenochpfyierpsxbvvamhlcthsdqwqnwlby
xtxbfvcvbsvwvuupalwtiiilyhjllnbvvkxcnfjnzlenoyia
cvrbshwnizyiveifxxowvmozvzeafuknjnfqcpyvrnjofwgk
ygteuwgssebxxqbqsbvaqxchumnpvigsddziqibmhmuokkbl
jqvzvcjtdzibcydvvzzsvqztpxpolykyeqqmgxysmcunsjnl
uaifshzswrtrkmlbxyyijabyriiixbqtkhqyhivjqpxxicmw
obcwicfyykytmcxjzakqmcriynogsgnrzwaeodwsxehmhylz
uahlbfgxweehpxojmlhmbfxndcqaajdtufqgdviewyyzfdly
idibsmuxajsqbaxfntwsmulbaamewgidomnpqefgqtddzmhr
iudojjrllxuvlzdhhxtaaytvrmpnktqnqeiojicpzpoaevvy
upjmiltejgkjetgkvghutkdkceaxishfgmzuiomvebwpggyg
ytciareyacgpzahojsnmeefgmejnbkdmfvfevrcusixxrhvy
mgmqpggclwdrahwhnvvfhracslfdfcnznqchtbfccudtxstp
orrlcabaojdkzugdwrykqczajajrvanztteqtorwxobswsdp
hmppoywettruxbnyoyptnjtaguomgeofmzxfbfsvzqytthai
ttagnjemvmbnsktmvnfpeqzvmzglihrjbdprwalohkgikvav
schyfaaprwhbjczunxxxdxddqfttsofpljmgalsmxvoexmqd
vzozqxfovtqjupmiedlhecmkprtqycnmysjaoaksfvdwttqn
skhepqlccwjlviqoaalbtnmjxqafhjznvxjkhzuttpyqvzrw
idlqhyaqcoakhpwcwxugojivjdkydgoddhgopnnogvnmeoae
hjpnpgbrrzrohcwreopuvyjtjziljpurxicehhgneaypqope
vafoxkalfrusbqdzamjymuxolsgmrzppiifkzdyneowydwhn
jyjboemrurvbkhdhfbwnfbcrpwzltezgancinrubccundjxf
khvoazsbaqdinovvorxdegprddxakqxfngyoqtbsfpqswjlt
zbgamiwcmlvaxygqtayhswdsydxwkfxdovkpjetcwqfetvva
svdxixguxpxzqninvmjjgdofjumrvhpxhfhikcsbnhjmrhen
qhatbwrxkhfkhagtcyyloujqmaypfswjhdoadhicgjgvftza
leotrrtptulbmrksovqfamkussnjvyhtleqaksjshxgakofj
lordtneuohncjxxtcsxgtcudidzhozuetlnibqbclkjvtkry
50
42 29
48 44
2 21
28 27
16 42
50 21
44 42
45 25
29 21
31 35
1 23
3 19
27 7
25 28
30 2
16 23
10 12
25 43
9 20
17 43
12 36
37 15
36 31
17 24
2 37
3 45
16 20
23 24
18 29
9 17
34 7
29 34
10 27
13 5
24 42
32 42
41 22
12 4
36 40
21 17
10 13
13 24
44 34
14 37
40 9
5 32
9 30
25 44
38 27
23 24

[出力例]
kjahelvygxdiwigzzjyyevcaojahbemkkcygkpaggvgavayu
uafzgjzrcgbimlkhodruxbtebmdutvyjhttvyumjeruphqnv
sywmbplaopbodpgyqvwizpliabpisbtkcwhchfkfnnnefgzo
vhusojbgcfukoygdjcispndupsydrenukpkhyppxktfgfyzi
shxmcvtbtcagoqzjszqmrnueetgwmkmnzchpzjkmggtbuehh
wbcbkryvjdqobvfyltenznordmqrwouubcfoagowizqhlccn
yywzjoibllpgjtdpczatddopwuqaxyusonbitwhrkkkvmhek
erpsxbvvamhlcthsdqwqnwlbylcquihmsadgtavenochpfyi
lyhjllnbvvkxcnfjnzlenoyiaxtxbfvcvbsvwvuupalwtiii
zvzeafuknjnfqcpyvrnjofwgkcvrbshwnizyiveifxxowvmo
humnpvigsddziqibmhmuokkblygteuwgssebxxqbqsbvaqxc
tpxpolykyeqqmgxysmcunsjnljqvzvcjtdzibcydvvzzsvqz
yriiixbqtkhqyhivjqpxxicmwuaifshzswrtrkmlbxyyijab
iynogsgnrzwaeodwsxehmhylzobcwicfyykytmcxjzakqmcr
ndcqaajdtufqgdviewyyzfdlyuahlbfgxweehpxojmlhmbfx
baamewgidomnpqefgqtddzmhridibsmuxajsqbaxfntwsmul
vrmpnktqnqeiojicpzpoaevvyiudojjrllxuvlzdhhxtaayt
kceaxishfgmzuiomvebwpggygupjmiltejgkjetgkvghutkd
gmejnbkdmfvfevrcusixxrhvyytciareyacgpzahojsnmeef
cslfdfcnznqchtbfccudtxstpmgmqpggclwdrahwhnvvfhra
ajajrvanztteqtorwxobswsdporrlcabaojdkzugdwrykqcz
aguomgeofmzxfbfsvzqytthaihmppoywettruxbnyoyptnjt
vmzglihrjbdprwalohkgikvavttagnjemvmbnsktmvnfpeqz
dqfttsofpljmgalsmxvoexmqdschyfaaprwhbjczunxxxdxd
kprtqycnmysjaoaksfvdwttqnvzozqxfovtqjupmiedlhecm
jxqafhjznvxjkhzuttpyqvzrwskhepqlccwjlviqoaalbtnm
vjdkydgoddhgopnnogvnmeoaeidlqhyaqcoakhpwcwxugoji
tjziljpurxicehhgneaypqopehjpnpgbrrzrohcwreopuvyj
olsgmrzppiifkzdyneowydwhnvafoxkalfrusbqdzamjymux
rpwzltezgancinrubccundjxfjyjboemrurvbkhdhfbwnfbc
rddxakqxfngyoqtbsfpqswjltkhvoazsbaqdinovvorxdegp
sydxwkfxdovkpjetcwqfetvvazbgamiwcmlvaxygqtayhswd
fjumrvhpxhfhikcsbnhjmrhensvdxixguxpxzqninvmjjgdo
qmaypfswjhdoadhicgjgvftzaqhatbwrxkhfkhagtcyylouj
ussnjvyhtleqaksjshxgakofjleotrrtptulbmrksovqfamk
didzhozuetlnibqbclkjvtkrylordtneuohncjxxtcsxgtcu
vjumbrxwmtxprxwyugjimgbjilxlxtoqsbdwfdenrehhlxnk
svscwulesyzgtuzzkpdmfxmhberjcoskytrgpqzaraddmwod
ammogozyhfisgvmdcoxttgagqchbzvmbejqrcdyfaoqdrgvu
lcejhjcjkcjgwsqaumwlyrfdjhubeegribiqattvugiwmxmw
wrrguybjgdtuhhraumoitgsaounadargbnpgyweimzhpqhrb
ukgcftvkqqdfnggewbeerfwtilwzvmfosvxitavjqndyorcy
cwwtymrfsrpkrkosgyeyhltfbaawgpuptpkhzrfpifwwpooh
hlcqlklfexaxiifgbobeldxbqvyurxgwrullponlprhwlzfk
lkxyelomuxwvkhhwcmpdeanzlzdxkjwfsegioeungcovdyua
gffshqnkwqgqxpzfckaxjufzqfyomqrvqbdqmsjxcssudrle
ggeaickgrvzmvbduyrbikxsorjsxdokejmvuwskvwbycvguu
gejdcwyyffskfeklhwknljzmwjmykcdmgnvprdorzybaywuj
pegzmifbglrgmzhgtqkxopnjukiqdzzmkmohemdvdufanplc
kjhyfvigvlevliaomftqozsbgkgfwvaywkqmvhtpbrpfobvl
kfzpezzsfhutloufttghngrruequiujwjhmgochzbiofmyyd
zshqdlwyifmtxnwupunpzvscrkzsmxdflbikkpozwkxnxivt

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

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

[入力例]

4 5

abcde

fghij

klmno

pqrst

3 3

[出力例]

mlkon

hgfji

cbaed

rqpts

※AtCoderのテストケースより

[入力例]

3 7

atcoder

regular

contest

1 1

2 5

[出力例]

testcon

oderatc

ularreg

※AtCoderのテストケースより

[入力例]

2 2

1 1

[出力例]

※AtCoderのテストケースより

[入力例]

5 6

abcdef

ghijkl

mnopqr

stuvwx

yzabcd

1 3

2 3

4 5

[出力例]

qponmr

kjihgl

edcbaf

cbazyd

wvutsx

[入力例]

10 13

tgaiplwcarqvr

jcbxsaceowkvr

zlgfizldbdykc

wsuiehmwxgenk

yennclmvitqyj

cvbgnfgiijfaw

caoenyfbixzjw

hcuhogtbdlrzx

mmlpsutxgfoyf

yxgeoakdybqbj

9 2

7 5

6 1

4 9

1 11

[出力例]

jyqtivmlcnney

knegxwmheiusw

ckydbdlzifglz

rvkwoecasxbcj

rvqracwlpiagt

jbqbydkaoegxy

fyofgxtusplmm

xzrldbtgohuch

wjzxibfyneoac

wafjiigfngbvc

[入力例]

30 30

zlfuxyhbmlafcmykqjhqfxzdpsdcye

hrburupmvtcxigyaheuaxyhaledflw

slnzchgsigwtagnqwjalonbdqddidq

htifmgawdkraswqobqdxuppvlomrmj

kwmvtcmlgholgztnxkfcufzovxbjtl

zrvjaxarsqtvxjkydqwbekjagdmraf

oaxenrkklngmbfwqflmjdwfppricbu

wnjxgpujanfmwlvflmctkqyeozhcaf

nvzgzmqoeagdrkasjiwxoxrcszjlfo

dirylpnobhsbxkwwxxaqjkxzdyddsi

yyawndqdhiibtouonhcqdvyhftmnyh

lfyvkxbjhupgjkyqwaxgjdugewoetm

ihaylrvcegejtbyupofjxogkcbgfho

kqokpfokthlimtvbwjfnpjdaeqinms

adxzqrgfgkiwacfsbrioomsmpwyybc

mdewbkbcfftilrprxcecxbwxejblwt

qfstklfwvwahvammwujyvzscthwymn

wvlopkalgkdyiqddzgtkwvesaqtnbj

alywjbfosqktwtwfiezxgtnggnisua

vslitdjcgldturboqianadtpsbeyos

bplursgzyryyqgrjznhfniumiswjbk

xpihoeznhbhmzakkkpknxoklgysnvl

xbarzttrjwzmmqxaavyycwbaajdrhf

qfvcjkvtprjbocnbkbateqhtphjrbc

vccdtqjrcoqepwrznmmhylqkopgysr

tmaamlgdfxohtmyprpmwgjelbhmqnm

uvxqkuholicwvhbzqcumbvwqigirga

kjsqvscvzscucztmylttcrhymwnjnw

dokiptkkeccxbqiqdoldqciivfcnrr

gixxzovfgymntqbyhxenzkqwnvttkz

23 5

17 3

9 27

22 21

5 7

2 23

28 26

14 17

3 22

25 23

16 25

6 1

1 14

21 4

11 1

17 15

25 9

10 5

5 26

15 12

[出力例]

anfmwlvflmctkqyeozhcafwnjxgpuj

eagdrkasjiwxoxrcszjlfonvzgzmqo

bhsbxkwwxxaqjkxzdyddsidirylpno

hiibtouonhcqdvyhftmnyhyyawndqd

hupgjkyqwaxgjdugewoetmlfyvkxbj

egejtbyupofjxogkcbgfhoihaylrvc

thlimtvbwjfnpjdaeqinmskqokpfok

gkiwacfsbrioomsmpwyybcadxzqrgf

fftilrprxcecxbwxejblwtmdewbkbc

vwahvammwujyvzscthwymnqfstklfw

gkdyiqddzgtkwvesaqtnbjwvlopkal

sqktwtwfiezxgtnggnisuaalywjbfo

gldturboqianadtpsbeyosvslitdjc

yryyqgrjznhfniumiswjbkbplursgz

hbhmzakkkpknxoklgysnvlxpihoezn

jwzmmqxaavyycwbaajdrhfxbarzttr

prjbocnbkbateqhtphjrbcqfvcjkvt

coqepwrznmmhylqkopgysrvccdtqjr

fxohtmyprpmwgjelbhmqnmtmaamlgd

licwvhbzqcumbvwqigirgauvxqkuho

zscucztmylttcrhymwnjnwkjsqvscv

eccxbqiqdoldqciivfcnrrdokiptkk

gymntqbyhxenzkqwnvttkzgixxzovf

mlafcmykqjhqfxzdpsdcyezlfuxyhb

vtcxigyaheuaxyhaledflwhrburupm

igwtagnqwjalonbdqddidqslnzchgs

dkraswqobqdxuppvlomrmjhtifmgaw

gholgztnxkfcufzovxbjtlkwmvtcml

sqtvxjkydqwbekjagdmrafzrvjaxar

lngmbfwqflmjdwfppricbuoaxenrkk

[入力例]

52 48

lxlxtoqsbdwfdenrehhlxnkvjumbrxwmtxprxwyugjimgbji

erjcoskytrgpqzaraddmwodsvscwulesyzgtuzzkpdmfxmhb

chbzvmbejqrcdyfaoqdrgvuammogozyhfisgvmdcoxttgagq

hubeegribiqattvugiwmxmwlcejhjcjkcjgwsqaumwlyrfdj

unadargbnpgyweimzhpqhrbwrrguybjgdtuhhraumoitgsao

lwzvmfosvxitavjqndyorcyukgcftvkqqdfnggewbeerfwti

aawgpuptpkhzrfpifwwpoohcwwtymrfsrpkrkosgyeyhltfb

vyurxgwrullponlprhwlzfkhlcqlklfexaxiifgbobeldxbq

zdxkjwfsegioeungcovdyualkxyelomuxwvkhhwcmpdeanzl

fyomqrvqbdqmsjxcssudrlegffshqnkwqgqxpzfckaxjufzq

jsxdokejmvuwskvwbycvguuggeaickgrvzmvbduyrbikxsor

jmykcdmgnvprdorzybaywujgejdcwyyffskfeklhwknljzmw

kiqdzzmkmohemdvdufanplcpegzmifbglrgmzhgtqkxopnju

kgfwvaywkqmvhtpbrpfobvlkjhyfvigvlevliaomftqozsbg

equiujwjhmgochzbiofmyydkfzpezzsfhutloufttghngrru

kzsmxdflbikkpozwkxnxivtzshqdlwyifmtxnwupunpzvscr

jahbemkkcygkpaggvgavayukjahelvygxdiwigzzjyyevcao

mdutvyjhttvyumjeruphqnvuafzgjzrcgbimlkhodruxbteb

bpisbtkcwhchfkfnnnefgzosywmbplaopbodpgyqvwizplia

sydrenukpkhyppxktfgfyzivhusojbgcfukoygdjcispndup

tgwmkmnzchpzjkmggtbuehhshxmcvtbtcagoqzjszqmrnuee

mqrwouubcfoagowizqhlccnwbcbkryvjdqobvfyltenznord

uqaxyusonbitwhrkkkvmhekyywzjoibllpgjtdpczatddopw

lcquihmsadgtavenochpfyierpsxbvvamhlcthsdqwqnwlby

xtxbfvcvbsvwvuupalwtiiilyhjllnbvvkxcnfjnzlenoyia

cvrbshwnizyiveifxxowvmozvzeafuknjnfqcpyvrnjofwgk

ygteuwgssebxxqbqsbvaqxchumnpvigsddziqibmhmuokkbl

jqvzvcjtdzibcydvvzzsvqztpxpolykyeqqmgxysmcunsjnl

uaifshzswrtrkmlbxyyijabyriiixbqtkhqyhivjqpxxicmw

obcwicfyykytmcxjzakqmcriynogsgnrzwaeodwsxehmhylz

uahlbfgxweehpxojmlhmbfxndcqaajdtufqgdviewyyzfdly

idibsmuxajsqbaxfntwsmulbaamewgidomnpqefgqtddzmhr

iudojjrllxuvlzdhhxtaaytvrmpnktqnqeiojicpzpoaevvy

upjmiltejgkjetgkvghutkdkceaxishfgmzuiomvebwpggyg

ytciareyacgpzahojsnmeefgmejnbkdmfvfevrcusixxrhvy

mgmqpggclwdrahwhnvvfhracslfdfcnznqchtbfccudtxstp

orrlcabaojdkzugdwrykqczajajrvanztteqtorwxobswsdp

hmppoywettruxbnyoyptnjtaguomgeofmzxfbfsvzqytthai

ttagnjemvmbnsktmvnfpeqzvmzglihrjbdprwalohkgikvav

schyfaaprwhbjczunxxxdxddqfttsofpljmgalsmxvoexmqd

vzozqxfovtqjupmiedlhecmkprtqycnmysjaoaksfvdwttqn

skhepqlccwjlviqoaalbtnmjxqafhjznvxjkhzuttpyqvzrw

idlqhyaqcoakhpwcwxugojivjdkydgoddhgopnnogvnmeoae

hjpnpgbrrzrohcwreopuvyjtjziljpurxicehhgneaypqope

vafoxkalfrusbqdzamjymuxolsgmrzppiifkzdyneowydwhn

jyjboemrurvbkhdhfbwnfbcrpwzltezgancinrubccundjxf

khvoazsbaqdinovvorxdegprddxakqxfngyoqtbsfpqswjlt

zbgamiwcmlvaxygqtayhswdsydxwkfxdovkpjetcwqfetvva

svdxixguxpxzqninvmjjgdofjumrvhpxhfhikcsbnhjmrhen

qhatbwrxkhfkhagtcyyloujqmaypfswjhdoadhicgjgvftza

leotrrtptulbmrksovqfamkussnjvyhtleqaksjshxgakofj

lordtneuohncjxxtcsxgtcudidzhozuetlnibqbclkjvtkry

42 29

48 44

2 21

28 27

16 42

50 21

44 42

45 25

29 21

31 35

1 23

3 19

27 7

25 28

30 2

16 23

10 12

25 43

9 20

17 43

12 36

37 15

36 31

17 24

2 37

3 45

16 20

23 24

18 29

9 17

34 7

29 34

10 27

13 5

24 42

32 42

41 22

12 4

36 40

21 17

10 13

13 24

44 34

14 37

40 9

5 32

9 30

25 44

38 27

23 24

[出力例]

kjahelvygxdiwigzzjyyevcaojahbemkkcygkpaggvgavayu

uafzgjzrcgbimlkhodruxbtebmdutvyjhttvyumjeruphqnv

sywmbplaopbodpgyqvwizpliabpisbtkcwhchfkfnnnefgzo

vhusojbgcfukoygdjcispndupsydrenukpkhyppxktfgfyzi

shxmcvtbtcagoqzjszqmrnueetgwmkmnzchpzjkmggtbuehh

wbcbkryvjdqobvfyltenznordmqrwouubcfoagowizqhlccn

yywzjoibllpgjtdpczatddopwuqaxyusonbitwhrkkkvmhek

erpsxbvvamhlcthsdqwqnwlbylcquihmsadgtavenochpfyi

lyhjllnbvvkxcnfjnzlenoyiaxtxbfvcvbsvwvuupalwtiii

zvzeafuknjnfqcpyvrnjofwgkcvrbshwnizyiveifxxowvmo

humnpvigsddziqibmhmuokkblygteuwgssebxxqbqsbvaqxc

tpxpolykyeqqmgxysmcunsjnljqvzvcjtdzibcydvvzzsvqz

yriiixbqtkhqyhivjqpxxicmwuaifshzswrtrkmlbxyyijab

iynogsgnrzwaeodwsxehmhylzobcwicfyykytmcxjzakqmcr

ndcqaajdtufqgdviewyyzfdlyuahlbfgxweehpxojmlhmbfx

baamewgidomnpqefgqtddzmhridibsmuxajsqbaxfntwsmul

vrmpnktqnqeiojicpzpoaevvyiudojjrllxuvlzdhhxtaayt

kceaxishfgmzuiomvebwpggygupjmiltejgkjetgkvghutkd

gmejnbkdmfvfevrcusixxrhvyytciareyacgpzahojsnmeef

cslfdfcnznqchtbfccudtxstpmgmqpggclwdrahwhnvvfhra

ajajrvanztteqtorwxobswsdporrlcabaojdkzugdwrykqcz

aguomgeofmzxfbfsvzqytthaihmppoywettruxbnyoyptnjt

vmzglihrjbdprwalohkgikvavttagnjemvmbnsktmvnfpeqz

dqfttsofpljmgalsmxvoexmqdschyfaaprwhbjczunxxxdxd

kprtqycnmysjaoaksfvdwttqnvzozqxfovtqjupmiedlhecm

jxqafhjznvxjkhzuttpyqvzrwskhepqlccwjlviqoaalbtnm

vjdkydgoddhgopnnogvnmeoaeidlqhyaqcoakhpwcwxugoji

tjziljpurxicehhgneaypqopehjpnpgbrrzrohcwreopuvyj

olsgmrzppiifkzdyneowydwhnvafoxkalfrusbqdzamjymux

rpwzltezgancinrubccundjxfjyjboemrurvbkhdhfbwnfbc

rddxakqxfngyoqtbsfpqswjltkhvoazsbaqdinovvorxdegp

sydxwkfxdovkpjetcwqfetvvazbgamiwcmlvaxygqtayhswd

fjumrvhpxhfhikcsbnhjmrhensvdxixguxpxzqninvmjjgdo

qmaypfswjhdoadhicgjgvftzaqhatbwrxkhfkhagtcyylouj

ussnjvyhtleqaksjshxgakofjleotrrtptulbmrksovqfamk

didzhozuetlnibqbclkjvtkrylordtneuohncjxxtcsxgtcu

vjumbrxwmtxprxwyugjimgbjilxlxtoqsbdwfdenrehhlxnk

svscwulesyzgtuzzkpdmfxmhberjcoskytrgpqzaraddmwod

ammogozyhfisgvmdcoxttgagqchbzvmbejqrcdyfaoqdrgvu

lcejhjcjkcjgwsqaumwlyrfdjhubeegribiqattvugiwmxmw

wrrguybjgdtuhhraumoitgsaounadargbnpgyweimzhpqhrb

ukgcftvkqqdfnggewbeerfwtilwzvmfosvxitavjqndyorcy

cwwtymrfsrpkrkosgyeyhltfbaawgpuptpkhzrfpifwwpooh

hlcqlklfexaxiifgbobeldxbqvyurxgwrullponlprhwlzfk

lkxyelomuxwvkhhwcmpdeanzlzdxkjwfsegioeungcovdyua

gffshqnkwqgqxpzfckaxjufzqfyomqrvqbdqmsjxcssudrle

ggeaickgrvzmvbduyrbikxsorjsxdokejmvuwskvwbycvguu

gejdcwyyffskfeklhwknljzmwjmykcdmgnvprdorzybaywuj

pegzmifbglrgmzhgtqkxopnjukiqdzzmkmohemdvdufanplc

kjhyfvigvlevliaomftqozsbgkgfwvaywkqmvhtpbrpfobvl

kfzpezzsfhutloufttghngrruequiujwjhmgochzbiofmyyd

zshqdlwyifmtxnwupunpzvscrkzsmxdflbikkpozwkxnxivt

■参照サイト
AtCoder Regular Contest 153

2023年1月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 282 の問題F (Union of Two Sets) を解いてみた.

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

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

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

// 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
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. (2 の 冪乗) + 1 を 保存.
    vi cPow2Plus1;
    cPow2Plus1.pb(1);
    while(cPow2Plus1.back() < 4000) cPow2Plus1.pb(2 * cPow2Plus1.back() + 1);
    // for(auto &p : cPow2Plus1) printf("%d\n", p);
    
    // 3. フェイズ 1.
    // 3-1. [l, r]作成.
    map<P, int> m;
    for(auto &p : cPow2Plus1) repx(i, 1, N + 2 - p) ++m[{i, i + p - 1}];
    
    // 3-2. 座標圧縮.
    int idx = 0;
    for(auto &p : m) p.b = ++idx;
    
    // 3-3. 出力.
    printf("%d\n", m.size());
    fflush(stdout);
    for(auto &x : m){
        printf("%d %d\n", x.a.a, x.a.b);
        fflush(stdout);
    }
    
    // 4. フェイズ 2.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 4-1. クエリ入力情報.
        int la, rb;
        scanf("%d %d", &la, &rb);
        
        // 4-2. a.
        int ra = la;
        for(auto &p : cPow2Plus1){
            if(la + p - 1 <= rb) ra = la + p - 1;
            else                 break;
        }
        
        // 4-3. b.
        int lb = rb;
        for(auto &p : cPow2Plus1){
            if(rb - p + 1 >= la) lb = rb - p + 1;
            else                 break;
        }
        // printf("la=%d ra=%d lb=%d rb=%d\n", la, ra, lb, rb);
        
        // 4-4. 出力.
        printf("%d %d\n", m[{la, ra}], m[{lb, rb}]);
        fflush(stdout);
    }
    return 0;
    
}

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

#define a first

#define b second

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. (2 の冪乗) + 1 を保存.

vi cPow2Plus1;

cPow2Plus1.pb(1);

while(cPow2Plus1.back() < 4000) cPow2Plus1.pb(2 * cPow2Plus1.back() + 1);

// for(auto &p : cPow2Plus1) printf("%d\n", p);

// 3. フェイズ 1.

// 3-1. [l, r]作成.

map<P, int> m;

for(auto &p : cPow2Plus1) repx(i, 1, N + 2 - p) ++m[{i, i + p - 1}];

// 3-2. 座標圧縮.

int idx = 0;

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

// 3-3. 出力.

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

fflush(stdout);

for(auto &x : m){

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

fflush(stdout);

}

// 4. フェイズ 2.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 4-1. クエリ入力情報.

int la, rb;

scanf("%d %d", &la, &rb);

// 4-2. a.

int ra = la;

for(auto &p : cPow2Plus1){

if(la + p - 1 <= rb) ra = la + p - 1;

else break;

}

// 4-3. b.

int lb = rb;

for(auto &p : cPow2Plus1){

if(rb - p + 1 >= la) lb = rb - p + 1;

else break;

}

// printf("la=%d ra=%d lb=%d rb=%d\n", la, ra, lb, rb);

// 4-4. 出力.

printf("%d %d\n", m[{la, ra}], m[{lb, rb}]);

fflush(stdout);

}

return 0;

}

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

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

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

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

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

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

[出力例]
78
1 1
1 3
1 7
1 15
2 2
2 4
2 8
2 16
3 3
3 5
3 9
3 17
4 4
4 6
4 10
4 18
5 5
5 7
5 11
5 19
6 6
6 8
6 12
6 20
7 7
7 9
7 13
7 21
8 8
8 10
8 14
8 22
9 9
9 11
9 15
9 23
10 10
10 12
10 16
10 24
11 11
11 13
11 17
11 25
12 12
12 14
12 18
13 13
13 15
13 19
14 14
14 16
14 20
15 15
15 17
15 21
16 16
16 18
16 22
17 17
17 19
17 23
18 18
18 20
18 24
19 19
19 21
19 25
20 20
20 22
21 21
21 23
22 22
22 24
23 23
23 25
24 24
25 25
2 2
6 18
11 15
15 43
17 21
21 21
26 38
31 35
35 59
39 53
43 47
47 68

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

※インタラクティブな問題のため, 入出力は, デバッグ時に使用したものを記載している.

[入力例]

1 1

5 5

1 2

3 5

2 4

2 5

1 5

[出力例]

1 1

1 3

2 2

2 4

3 3

3 5

4 4

5 5

1 1

8 8

1 3

6 6

4 4

4 6

2 6

[入力例]

1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

1 9

1 10

2 2

2 3

2 4

2 5

2 6

2 7

2 8

2 9

2 10

3 3

3 4

3 5

3 6

3 7

3 8

3 9

3 10

4 4

4 5

4 6

4 7

4 8

4 9

4 10

5 5

5 6

5 7

5 8

5 9

5 10

6 6

6 7

6 8

6 9

6 10

7 7

7 8

7 9

7 10

8 8

8 9

8 10

9 9

9 10

10 10

[出力例]

1 1

1 3

1 7

2 2

2 4

2 8

3 3

3 5

3 9

4 4

4 6

4 10

5 5

5 7

6 6

6 8

7 7

7 9

8 8

8 10

9 9

10 10

1 1

1 4

2 2

2 5

2 8

2 11

3 3

3 6

3 9

3 12

4 4

4 7

5 5

5 8

5 11

5 14

6 6

6 9

6 12

7 7

7 10

8 8

8 11

8 14

8 16

9 9

9 12

10 10

10 13

11 11

11 14

11 16

11 18

12 12

13 13

13 15

14 14

14 16

14 18

14 20

15 15

15 17

16 16

16 18

16 20

17 17

17 19

18 18

18 20

19 19

19 21

20 20

21 21

21 22

22 22

[入力例]

1 3

2 7

3 10

4 17

5 6

6 6

7 12

8 15

9 22

10 20

11 18

12 25

[出力例]

1 1

1 3

1 7

1 15

2 2

2 4

2 8

2 16

3 3

3 5

3 9

3 17

4 4

4 6

4 10

4 18

5 5

5 7

5 11

5 19

6 6

6 8

6 12

6 20

7 7

7 9

7 13

7 21

8 8

8 10

8 14

8 22

9 9

9 11

9 15

9 23

10 10

10 12

10 16

10 24

11 11

11 13

11 17

11 25

12 12

12 14

12 18

13 13

13 15

13 19

14 14

14 16

14 20

15 15

15 17

15 21

16 16

16 18

16 22

17 17

17 19

17 23

18 18

18 20

18 24

19 19

19 21

19 25

20 20

20 22

21 21

21 23

22 22

22 24

23 23

23 25

24 24

25 25

2 2

6 18

11 15

15 43

17 21

21 21

26 38

31 35

35 59

39 53

43 47

47 68

■参照サイト
HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

2023年1月20日

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

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題E (Increasing LCMs) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    set<LL> o;
    rep(i, N){
        LL a;
        scanf("%lld", &a);
        o.insert(a);
    }
    
    // 2. 正整数列の構築.
    stack<LL> st;
    set<LL> cur;
    rep(i, N){
        // 終了条件.
        if(cur.size() == o.size()) break;
        
        // 今回分更新.
        cur = o;
        
        // 条件を満たす要素は？
        for(auto &ai : cur){
            // 最大公約数.
            vl v;
            for(auto &aj : cur) if(ai != aj) v.pb(__gcd(aj, ai));
            
            // 最小公倍数.
            LL lcm = 1;
            for(auto &q : v){
                LL g = __gcd(lcm, q);
                lcm /= g;
                lcm *= q;
            }
            
            // 判定.
            if(lcm < ai){
                st.push(ai);
                o.erase(ai);
                break;
            }
        }
    }
    
    // 3. 出力.
    if(st.size() == N){
        puts("Yes");
        while(!st.empty()){
             LL ans = st.top();
             st.pop();
             printf("%lld%s", ans, !st.empty() ? " " : "\n");
        }
    }else{
        puts("No");
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc122/editorial/2042

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

set<LL> o;

rep(i, N){

LL a;

scanf("%lld", &a);

o.insert(a);

}

// 2. 正整数列の構築.

stack<LL> st;

set<LL> cur;

rep(i, N){

// 終了条件.

if(cur.size() == o.size()) break;

// 今回分更新.

cur = o;

// 条件を満たす要素は？

for(auto &ai : cur){

// 最大公約数.

vl v;

for(auto &aj : cur) if(ai != aj) v.pb(__gcd(aj, ai));

// 最小公倍数.

LL lcm = 1;

for(auto &q : v){

LL g = __gcd(lcm, q);

lcm /= g;

lcm *= q;

}

// 判定.

if(lcm < ai){

st.push(ai);

o.erase(ai);

break;

}

// 3. 出力.

if(st.size() == N){

puts("Yes");

while(!st.empty()){

LL ans = st.top();

st.pop();

printf("%lld%s", ans, !st.empty() ? " " : "\n");

}

}else{

puts("No");

}

return 0;

}

[入力例]
3
3 4 6

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

[入力例]
3
2 3 6

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

[入力例]
10
922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

[出力例]
Yes
922513 255595307440611247 156087536381939527 134115264093375553 116282391418772039 81706734998806133 18332844097865861 4638516664311857 3247317977078471 346046618969
※AtCoderテストケースより

※但し, 上記のプログラムでは, 以下の内容が出力される.
Yes
922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

[入力例]
5
6 8 12 18 28

[出力例]
Yes
6 12 28 18 8

[入力例]
7
8 10 16 22 27 36 50

[出力例]
Yes
10 50 36 27 22 8 16

[入力例]

3 4 6

[出力例]

Yes

3 6 4

※AtCoderテストケースより

[入力例]

2 3 6

[出力例]

※AtCoderテストケースより

[入力例]

922513 346046618969 3247317977078471 4638516664311857 18332844097865861 81706734998806133 116282391418772039 134115264093375553 156087536381939527 255595307440611247

[出力例]

Yes

922513 255595307440611247 156087536381939527 134115264093375553 116282391418772039 81706734998806133 18332844097865861 4638516664311857 3247317977078471 346046618969

※AtCoderテストケースより

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

Yes

922513 346046618969 116282391418772039 81706734998806133 255595307440611247 156087536381939527 134115264093375553 18332844097865861 3247317977078471 4638516664311857

[入力例]

6 8 12 18 28

[出力例]

Yes

6 12 28 18 8

[入力例]

8 10 16 22 27 36 50

[出力例]

Yes

10 50 36 27 22 8 16

■参照サイト
東京海上日動プログラミングコンテスト2021（AtCoder Regular Contest 122)

C++の練習を兼ねて, AtCoder Beginner Contest 275 の 問題C (Counting Squares) ～ 問題D (Yet Another Recursive Function) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 155 の 問題A (ST and TS Palindrome) ～ 問題B (Abs Abs Function) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 154 の 問題A (Swap Digit) ～ 問題B (New Place) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 250 の 問題G (Stonks) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 153 の 問題A (AABCDDEFE) ～ 問題B (Grid Rotations) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 282 の 問題F (Union of Two Sets) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の 問題E (Increasing LCMs) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 275 の問題C (Counting Squares) ～問題D (Yet Another Recursive Function) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 155 の問題A (ST and TS Palindrome) ～問題B (Abs Abs Function) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 154 の問題A (Swap Digit) ～問題B (New Place) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 250 の問題G (Stonks) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 153 の問題A (AABCDDEFE) ～問題B (Grid Rotations) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 282 の問題F (Union of Two Sets) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 122 の問題E (Increasing LCMs) を解いてみた.