C++ | 個人用メモ帳

2022年10月22日2022年10月22日

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

C++の練習を兼ねて, AtCoder Regular Contest 151 の問題A (Equal Hamming Distances) ～問題B (A < AP) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char s[202020], t[202020];
    scanf("%d %s %s", &N, s, t);
    
    // 2. 事前計算.
    int d = 0;
    rep(i, N) if(s[i] != t[i]) ++d;
    
    // 3. 例外.
    if(d & 1){
        puts("-1");
        return 0;
    }
    
    // 4. U を 構成.
    d /= 2;
    int dus = d, dut = d;
    rep(i, N){
        if(s[i] != t[i]){
            if(s[i] == '0'){
                if(dut){
                    --dut;
                    continue;
                }
                if(dus){
                    u[i] = 1;
                    --dus;
                }
            }
            if(s[i] == '1'){
                if(dus){
                    --dus;
                    continue;
                }
                if(dut){
                    u[i] = 1;
                    --dut;
                }
            }
        }
    }
    
    // 5. 検証.
    int e1 = 0, e2 = 0;
    rep(i, N){
        if(s[i] - '0' != u[i]) ++e1;
        if(t[i] - '0' != u[i]) ++e2;
    }
    assert(e1 == e2);
    
    // 6. 出力.
    rep(i, N) printf("%d", u[i]);
    return 0;
    
}

// 解き直し.

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

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

int main(){

// 1. 入力情報.

int N;

char s[202020], t[202020];

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

// 2. 事前計算.

int d = 0;

rep(i, N) if(s[i] != t[i]) ++d;

// 3. 例外.

if(d & 1){

puts("-1");

return 0;

}

// 4. U を構成.

d /= 2;

int dus = d, dut = d;

rep(i, N){

if(s[i] != t[i]){

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

if(dut){

--dut;

continue;

}

if(dus){

u[i] = 1;

--dus;

}

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

if(dus){

--dus;

continue;

}

if(dut){

u[i] = 1;

--dut;

}

// 5. 検証.

int e1 = 0, e2 = 0;

rep(i, N){

if(s[i] - '0' != u[i]) ++e1;

if(t[i] - '0' != u[i]) ++e2;

}

assert(e1 == e2);

// 6. 出力.

rep(i, N) printf("%d", u[i]);

return 0;

}

[入力例]
5
00100
10011

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

[入力例]
1
0
1

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

[入力例]
10
0000101101
1011111011

[出力例]
0000010010

[入力例]
20
10100100010000100000
01100011110000011111

[出力例]
00000000000000000111

[入力例]
100
1010110111100111110001110011011100011100011110011110101000001001101110110110111001000011101100101000
0100011101111010110001001111000100101011001000110010011111101111001100111010100100111011110111101011

[出力例]
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

[入力例]
500
00101101101010110000110011011001101111110111010111011000111011111100110111010101010011011010110000100001101011000001100011111100000111011010100111010111001110010000110100001100110100010010111111111101110000101111001000100101001110110000011110011100000010100111100101111111100011011010001011100101100110111110011110111101010001011000110101010010101101100110010001011110001100101011110010000111101011110100111101000100101000101101100001110110111110001110111100001111000110100101111010000011101101101101
11111000010110001010001110001111111101110000000001000001010010100000110011010010001010010010001110100101110100001110010010100101101001010001011001101000100111000001001100010111010110111100010000100010001101110110111000101110110111110111001001110000011011100110001111101100110001101110111110000110100101100100000100011011100011110101101010011000000110010001101010101011101111111011100000100101001010011111111011101010110011001111101101010010010110100110010010000001101100010101110100111111110101000101

[出力例]
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100001110000010100000001010000000001000101000

[入力例]

00100

10011

[出力例]

00001

※AtCoderのテストケースより

[入力例]

[出力例]

-1

※AtCoderのテストケースより

[入力例]

0000101101

1011111011

[出力例]

0000010010

[入力例]

10100100010000100000

01100011110000011111

[出力例]

00000000000000000111

[入力例]

100

1010110111100111110001110011011100011100011110011110101000001001101110110110111001000011101100101000

0100011101111010110001001111000100101011001000110010011111101111001100111010100100111011110111101011

[出力例]

0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001

[入力例]

500

00101101101010110000110011011001101111110111010111011000111011111100110111010101010011011010110000100001101011000001100011111100000111011010100111010111001110010000110100001100110100010010111111111101110000101111001000100101001110110000011110011100000010100111100101111111100011011010001011100101100110111110011110111101010001011000110101010010101101100110010001011110001100101011110010000111101011110100111101000100101000101101100001110110111110001110111100001111000110100101111010000011101101101101

11111000010110001010001110001111111101110000000001000001010010100000110011010010001010010010001110100101110100001110010010100101101001010001011001101000100111000001001100010111010110111100010000100010001101110110111000101110110111110111001001110000011011100110001111101100110001101110111110000110100101100100000100011011100011110101101010011000000110010001101010101011101111111011100000100101001010011111111011101010110011001111101101010010010110100110010010000001101100010101110100111111110101000101

[出力例]

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100001110000010100000001010000000001000101000

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

// 解き直し.
// https://atcoder.jp/contests/arc151/editorial/5010
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL MOD = 998244353;
LL mPowM[202020]; // M の 冪乗(MOD版)
int p[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    vvi G(N);
    rep(i, N){
        scanf("%d", &p[i]);
        --p[i];
        G[i].pb(p[i]);
        G[p[i]].pb(i);
    }
    
    // 2. M の 冪乗(MOD版) を 保存.
    mPowM[0] = 1;
    repx(i, 1, 202020) mPowM[i] = mPowM[i - 1] * M, mPowM[i] %= MOD;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* c, int l){
        // 空のキュー.
        queue<int> q;
        
        // 連結成分番号を設定.
        c[s] = l;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);
        }
    };
    int c[N], idx = 0;
    rep(i, N) c[i] = 0;
    rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);
    
    // 4. 集計.
    LL ans = mPowM[N];
    ans += MOD;
    ans -= mPowM[idx];
    ans %= MOD;
    ans *= 499122177;
    ans %= MOD;
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using LL = long long;

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

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

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

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

#define pb push_back

const LL MOD = 998244353;

LL mPowM[202020]; // M の冪乗(MOD版)

int p[202020];

int main(){

// 1. 入力情報.

int N, M;

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

vvi G(N);

rep(i, N){

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

--p[i];

G[i].pb(p[i]);

G[p[i]].pb(i);

}

// 2. M の冪乗(MOD版) を保存.

mPowM[0] = 1;

repx(i, 1, 202020) mPowM[i] = mPowM[i - 1] * M, mPowM[i] %= MOD;

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

// 連結成分番号を設定.

c[s] = l;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

for(auto &e : G[u]) if(!c[e] && e != s) c[e] = l, q.push(e);

}

};

int c[N], idx = 0;

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

rep(i, N) if(!c[i]) bfs(G, i, c, ++idx);

// 4. 集計.

LL ans = mPowM[N];

ans += MOD;

ans -= mPowM[idx];

ans %= MOD;

ans *= 499122177;

ans %= MOD;

// 5. 出力.

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

return 0;

}

[入力例]
4 2
4 1 3 2

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

[入力例]
1 1
1

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

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

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

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

[出力例]
8232

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

[出力例]
29511

[入力例]
50 20221022
30 8 20 22 28 36 17 24 43 14 15 35 11 5 37 23 50 27 39 25 40 47 32 42 2 4 26 19 16 12 1 44 18 49 34 6 48 45 21 3 29 13 46 10 7 41 33 31 38 9

[出力例]
783859669

[入力例]

4 2

4 1 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

※AtCoderのテストケースより

[入力例]

20 100000

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

[出力例]

55365742

※AtCoderのテストケースより

[入力例]

5 7

5 4 3 2 1

[出力例]

8232

[入力例]

10 3

3 1 2 5 6 4 8 9 10 7

[出力例]

29511

[入力例]

50 20221022

30 8 20 22 28 36 17 24 43 14 15 35 11 5 37 23 50 27 39 25 40 47 32 42 2 4 26 19 16 12 1 44 18 49 34 6 48 45 21 3 29 13 46 10 7 41 33 31 38 9

[出力例]

783859669

■参照サイト
AtCoder Regular Contest 151

2022年10月21日2022年10月22日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 実装に苦労したものの, 解説のロジックから, 計算できることに不思議な印象を受けた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc150/editorial/4865
// 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()
const LL MOD = 998244353;
LL f[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL K;
    char c[202020];
    scanf("%d %lld %s", &N, &K, c);
    string S(c);
    
    // 2. 反転させるか？
    int isFlip = 0;
    rep(i, N) isFlip += (S[i] == 'R') - (S[i] == 'L');
    if(isFlip < 0){
        reverse(all(S));
        rep(i, N) S[i] = (S[i] == 'L') ? 'R' : 'L';
    }
    
    // 3. 事前計算.
    rep(i, N) f[i + 1] = f[i] + (S[i] == 'R') - (S[i] == 'L');
    LL g = f[N] * K;
    LL k = 0;
    repx(i, 1, N + 1){
        if(f[i] > 0){
            k = i;
            break;
        }
    }
    
    // 4. 'L', 'R' の 個数 が 等しい.
    LL ans = 0;
    if(f[N] == 0){
        repx(i, 1, N + 1){
            // L の 場合.
            if(S[i - 1] == 'L' && f[i] >= 0){
                ans += K;
                ans %= MOD;
            }
            
            // R の 場合.
            if(S[i - 1] == 'R' && f[i] > 0){
                ans += K;
                ans %= MOD;
            }
        }
    }
    
    // 5. 'R' が 'L' の 個数 より 多い.
    if(f[N] != 0){
        repx(i, 1, N + 1){
            // L の 場合.
            if(S[i - 1] == 'L'){
                // 向きを 1 回 変える.
                ans += K;
                ans += MOD;
                
                // k 未満は, 向きを変えないので, 減算.
                ans -= (i < k);
                ans %= MOD;
            }
            
            // R の 場合.
            if(S[i - 1] == 'R'){
                LL cur = f[i] + (K - 1) * f[N];
                if(g < cur){
                    // g は 含めないので, 余りが 0 なら, 減算.
                    LL q = (cur - g) / f[N] + 1;
                    LL r = (cur - g) % f[N];
                    if(!r) --q;
                    
                    // 各 i で, K 人 を 超えない.
                    q = min(q, K);
                    
                    // 向きを 2 回 変える.
                    ans += 2 * q;
                    ans %= MOD;
                }
            }
        }
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc150/editorial/4865

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

const LL MOD = 998244353;

LL f[202020];

int main(){

// 1. 入力情報.

int N;

LL K;

char c[202020];

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

string S(c);

// 2. 反転させるか？

int isFlip = 0;

rep(i, N) isFlip += (S[i] == 'R') - (S[i] == 'L');

if(isFlip < 0){

reverse(all(S));

rep(i, N) S[i] = (S[i] == 'L') ? 'R' : 'L';

}

// 3. 事前計算.

rep(i, N) f[i + 1] = f[i] + (S[i] == 'R') - (S[i] == 'L');

LL g = f[N] * K;

LL k = 0;

repx(i, 1, N + 1){

if(f[i] > 0){

k = i;

break;

}

// 4. 'L', 'R' の個数が等しい.

LL ans = 0;

if(f[N] == 0){

repx(i, 1, N + 1){

// L の場合.

if(S[i - 1] == 'L' && f[i] >= 0){

ans += K;

ans %= MOD;

}

// R の場合.

if(S[i - 1] == 'R' && f[i] > 0){

ans += K;

ans %= MOD;

}

// 5. 'R' が 'L' の個数より多い.

if(f[N] != 0){

repx(i, 1, N + 1){

// L の場合.

if(S[i - 1] == 'L'){

// 向きを 1 回変える.

ans += K;

ans += MOD;

// k 未満は, 向きを変えないので, 減算.

ans -= (i < k);

ans %= MOD;

}

// R の場合.

if(S[i - 1] == 'R'){

LL cur = f[i] + (K - 1) * f[N];

if(g < cur){

// g は含めないので, 余りが 0 なら, 減算.

LL q = (cur - g) / f[N] + 1;

LL r = (cur - g) % f[N];

if(!r) --q;

// 各 i で, K 人を超えない.

q = min(q, K);

// 向きを 2 回変える.

ans += 2 * q;

ans %= MOD;

}

// 6. 出力.

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

return 0;

}

[入力例]
7 1
RRLRLLL

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

[入力例]
4 10
LLRR

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

[入力例]
23 200
RLRRRLLLLLLLLRRRLLRLRRR

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

[入力例]
7 5
RLLLRRR

[出力例]
15

[入力例]
30 7
LRLLRRLRLLRRLLRRRRLRLLLRRLLLRL

[出力例]
106

[入力例]
100 2022
RLLRLRRLLLLRRRLLLLLLRRRLLLRLRLRLLLLLLLRRRLLRRRRLLLRLRRLLLRLRLRRRLRLLLRLRRRLRRLRRLLLLLLRLRRLRLRRLRRLL

[出力例]
90994

[入力例]
500 1021
LRLRLRLLLRLRLLLLLRLLLLLRLLLRRRRLRRLLLRLRLLRLLRRLLRLRRRLLLRLLRLRLRRRLLLRRLLLLRLLLLLLLLLRRRRRRLLRLRRRRRLLRRLRLLLLRLRRRRRLRRRLRRRLRRLRRLLRLLLLRRRRLLLLLLLRRRLLRLRRLLLLLLRLRLRLRLLLLRRLLRLRRRLLRLLLRLLLRRRLRLLRRRLRRLLLRRRLLRLRLLRRLLLRRRLLLLRRRLLRRLLRRRRRRLRLLLLRRLRLLLRRLLLLRRLLLLRLLRLLRRLRLRLLLRLRRRLLRLLRRLLRRLRLRLLLLLLRLRLRRLLRLRLLLLRLRRLLLRLRLLRLRRRRRLLRLRRLLLLRRRLLRRLRRLRRRRLRRRLLLRRRLLLLRLRRLRRRLLRRLLRRLLLRLRLLRRLLRRLLLRLRLLLRLRRLLRRRRLLRRRRRLLRRLLRRLLRRLRRLLRRLRLLRLRRLLLRRLRLRRLLLLRRLRRLLLRRRRLRRL

[出力例]
240956

[入力例]

7 1

RRLRLLL

[出力例]

※AtCoderテストケースより

[入力例]

4 10

LLRR

[出力例]

※AtCoderテストケースより

[入力例]

23 200

RLRRRLLLLLLLLRRRLLRLRRR

[出力例]

2207

※AtCoderテストケースより

[入力例]

7 5

RLLLRRR

[出力例]

[入力例]

30 7

LRLLRRLRLLRRLLRRRRLRLLLRRLLLRL

[出力例]

106

[入力例]

100 2022

RLLRLRRLLLLRRRLLLLLLRRRLLLRLRLRLLLLLLLRRRLLRRRRLLLRLRRLLLRLRLRRRLRLLLRLRRRLRRLRRLLLLLLRLRRLRLRRLRRLL

[出力例]

90994

[入力例]

500 1021

LRLRLRLLLRLRLLLLLRLLLLLRLLLRRRRLRRLLLRLRLLRLLRRLLRLRRRLLLRLLRLRLRRRLLLRRLLLLRLLLLLLLLLRRRRRRLLRLRRRRRLLRRLRLLLLRLRRRRRLRRRLRRRLRRLRRLLRLLLLRRRRLLLLLLLRRRLLRLRRLLLLLLRLRLRLRLLLLRRLLRLRRRLLRLLLRLLLRRRLRLLRRRLRRLLLRRRLLRLRLLRRLLLRRRLLLLRRRLLRRLLRRRRRRLRLLLLRRLRLLLRRLLLLRRLLLLRLLRLLRRLRLRLLLRLRRRLLRLLRRLLRRLRLRLLLLLLRLRLRRLLRLRLLLLRLRRLLLRLRLLRLRRRRRLLRLRRLLLLRRRLLRRLRRLRRRRLRRRLLLRRRLLLLRLRRLRRRLLRRLLRRLLLRLRLLRRLLRRLLLRLRLLLRLRRLLRRRRLLRRRRRLLRRLLRRLLRRLRRLLRRLRLLRLRRLLLRRLRLRRLLLLRRLRRLLLRRRRLRRL

[出力例]

240956

■参照サイト
AtCoder Regular Contest 150

2022年10月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題D (Removing Gacha) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 幅優先探索の復習が出来たので, 非常に良かったと思う.
3. 解説のロジック(コンプガチャでの 1番目のアイテムを引く回数の期待値に等しいとの考え方)で, 期待値を計算できることに, 不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

// Fermat's little theorem から, 大きな冪乗の計算を行う.
// @param a: べき乗したい正整数.
// @param b: 指数.
// @return:  べき乗した計算結果(mod版).
LL mPow(LL a, LL b){
    LL t = 1;
    while(b){
        if(b & 1) t = (t * a) % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return t;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vvi G(N);
    repx(i, 1, N){
        int p;
        scanf("%d", &p);
        --p;
        G[i].pb(p);
        G[p].pb(i);
    }
    
    // 2. 事前計算.
    repx(i, 1, 202020) iCum[i] = (iCum[i - 1] + mPow(i, MOD - 2)) % MOD;
    
    // 3. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vvi &G, int s, int* d) {
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 隣接頂点をチェック.
            for(auto &e : G[u]) if(!d[e] && e != s) d[e] = d[u] + 1, q.push(e);
        }
    };
    
    // 4. 頂点 1 からの 最短距離.
    int d[N];
    rep(i, N) d[i] = 0;
    bfs(G, 0, d);
    
    // 5. 集計.
    LL ans = 0;
    rep(i, N) ans = (ans + iCum[d[i] + 1]) % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc150/editorial/4995

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

using LL = long long;

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

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

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

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

#define pb push_back

const LL MOD = 998244353;

LL iCum[202020];

// Fermat's little theorem から, 大きな冪乗の計算を行う.

// @param a: べき乗したい正整数.

// @param b: 指数.

// @return: べき乗した計算結果(mod版).

LL mPow(LL a, LL b){

LL t = 1;

while(b){

if(b & 1) t = (t * a) % MOD;

a = a * a % MOD;

b >>= 1;

}

return t;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vvi G(N);

repx(i, 1, N){

int p;

scanf("%d", &p);

--p;

G[i].pb(p);

G[p].pb(i);

}

// 2. 事前計算.

repx(i, 1, 202020) iCum[i] = (iCum[i - 1] + mPow(i, MOD - 2)) % MOD;

// 3. bfs.

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

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

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int u = q.front();

q.pop();

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

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

}

};

// 4. 頂点 1 からの最短距離.

int d[N];

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

bfs(G, 0, d);

// 5. 集計.

LL ans = 0;

rep(i, N) ans = (ans + iCum[d[i] + 1]) % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
4
1 1 3

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

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

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

[入力例]
3
1 1

[出力例]
4

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

[出力例]
15

[入力例]
20
1 1 1 4 4 3 7 7 2 2 10 10 6 6 12 12 12 18 18

[出力例]
415935186

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

[出力例]
853261302

[入力例]

1 1 3

[出力例]

831870300

※AtCoderテストケースより

[入力例]

1 2 1 1 4 5 3 3 5 10 3 6 3 13

[出力例]

515759610

※AtCoderテストケースより

[入力例]

1 1

[出力例]

[入力例]

1 2 2 1 5 5 2 5

[出力例]

[入力例]

1 1 1 4 4 3 7 7 2 2 10 10 6 6 12 12 12 18 18

[出力例]

415935186

[入力例]

1 2 3 1 5 6 6 7 9 4 11 11 13 13 10 10 8 8 17 17 20 20 20 15

[出力例]

853261302

■参照サイト
AtCoder Regular Contest 150

2022年10月17日2022年10月17日

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

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題C (Path and Subsequence) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc150/editorial/4867
// 01-BFSのちょっと丁寧な解説
// https://betrue12.hateblo.jp/entry/2018/12/08/000020
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
int a[101010], b[101010];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    vvi G(N + 1);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        G[u].pub(v);
        G[v].pub(u);
    }
    rep(i, N) scanf("%d", &a[i + 1]);
    rep(i, K) scanf("%d", &b[i + 1]);
    
    // 2. 01-BFS(解説通り).
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 01-BFS版へ修正.
    auto bfs01 = [&](int *d){
        // 空 の deque.
        deque<int> dq;
        
        // 未確定地点 を deque に追加.
        repx(i, 1, N + 1) dq.pub(i);
        
        // deque が 空 になるまで繰り返す.
        while(!dq.empty()){
            // deque から取り出す.
            int u = dq.front();
            dq.pof();
            
            // コスト更新(隣接頂点).
            for(auto &v : G[u]){
                // 整数列 A (要素) が, 整数列 B (要素) と一致しなかった.
                if(a[v] != b[d[u] + 1]){
                    if(d[v] > d[u] + 0){
                        d[v] = d[u] + 0;
                        dq.puf(v);
                    }
                }
                
                // 整数列 A (要素) が, 整数列 B (要素) と一致した.
                if(a[v] == b[d[u] + 1]){
                    if(d[v] > d[u] + 1){
                        d[v] = d[u] + 1;
                        dq.pub(v);
                    }
                }
            }
        }
    };
    int d[N + 1];
    rep(i, N + 1) d[i] = K + 1;
    d[1] = (a[1] == b[1]);
    bfs01(d);
    
    // 3. 出力.
    printf("%s\n", (d[N] == K) ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc150/editorial/4867

// 01-BFSのちょっと丁寧な解説

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

int a[101010], b[101010];

int main(){

// 1. 入力情報.

int N, M, K;

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

vvi G(N + 1);

rep(i, M){

int u, v;

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

G[u].pub(v);

G[v].pub(u);

}

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

rep(i, K) scanf("%d", &b[i + 1]);

// 2. 01-BFS(解説通り).

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

// -> 01-BFS版へ修正.

auto bfs01 = [&](int *d){

// 空の deque.

deque<int> dq;

// 未確定地点を deque に追加.

repx(i, 1, N + 1) dq.pub(i);

// deque が空になるまで繰り返す.

while(!dq.empty()){

// deque から取り出す.

int u = dq.front();

dq.pof();

// コスト更新(隣接頂点).

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

// 整数列 A (要素) が, 整数列 B (要素) と一致しなかった.

if(a[v] != b[d[u] + 1]){

if(d[v] > d[u] + 0){

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

dq.puf(v);

}

// 整数列 A (要素) が, 整数列 B (要素) と一致した.

if(a[v] == b[d[u] + 1]){

if(d[v] > d[u] + 1){

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

dq.pub(v);

}

};

int d[N + 1];

rep(i, N + 1) d[i] = K + 1;

d[1] = (a[1] == b[1]);

bfs01(d);

// 3. 出力.

printf("%s\n", (d[N] == K) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

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

[出力例]
Yes

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

[出力例]
Yes

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

[出力例]
Yes

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

[入力例]

6 6 3

1 2

1 3

2 4

3 5

4 6

5 6

1 2 4 5 2 6

1 2 6

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 5 3

1 2

2 3

3 4

4 5

2 5

1 2 3 5 2

1 3 2

[出力例]

※AtCoderのテストケースより

[入力例]

10 20 3

5 6

5 10

5 7

3 5

3 7

2 6

3 8

4 5

5 8

7 10

1 6

1 9

4 6

1 2

1 4

6 7

4 8

2 5

3 10

6 9

2 5 8 5 1 5 1 1 5 10

2 5 1

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

10 12 4

1 2

1 3

2 4

3 4

4 5

4 6

5 7

6 7

7 8

7 9

8 10

9 10

3 1 4 1 5 9 2 6 5 3

3 1 2 3

[出力例]

Yes

[入力例]

11 16 4

1 2

2 5

2 3

1 3

3 4

4 5

5 6

5 7

4 7

4 8

6 9

7 9

7 10

8 10

9 11

10 11

5 7 7 1 1 3 3 3 2 2 10

5 7 1 3 2 10

[出力例]

Yes

[入力例]

15 21 5

1 2

1 4

1 5

2 3

3 4

3 5

3 6

6 7

6 8

6 9

6 10

6 11

7 12

8 12

9 12

10 12

11 12

12 13

12 14

13 15

14 15

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

3 4 9 8 9

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 150
01-BFSのちょっと丁寧な解説

2022年10月15日2022年10月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題D (mod M Game) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, グラフの性質(完全マッチング)について, 学習できたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    map<int, int> m;
    rep(i, N * 2){
        int a;
        scanf("%d", &a);
        ++m[a];
    }
    
    // 2. マッチング(赤い辺).
    // -> 同じ数が書きこまれたものを, mod 2 で, 除外して, 残った数字(0 / 1 個)を拾ってくる.
    vi r;
    for(auto &p : m) rep(i, (p.b % 2)) r.pb(p.a);
    
    // 3. M が 奇数.
    // -> 完全マッチングが見つかったら, Bob勝ち と 見る.
    if(M & 1){
        printf("%s\n", r.size() ? "Alice" : "Bob");
        return 0;
    }
    
    // 4. M が 偶数.
    // -> M / 2 で, 分類し, 青い辺 の 使用本数 を 数える.
    m.clear();
    for(auto &p : r) ++m[p % M];
    int bUsed = 0;
    for(auto &p : m){
        int o = p.a + M / 2;
        if(p.b && m.count(o)){
            int s = min(p.b, m[o]);
            p.b -= s;
            m[o] -= s;
            bUsed += s;
        }
    }
    
    // 5. 完全マッチングか？
    bool isPerfectMatching = true;
    for(auto &p : m){
        if(p.b % 2){
            isPerfectMatching = false;
            break;
        }
    }
    
    // 6. 出力.
    printf("%s\n", (!(bUsed & 1) && isPerfectMatching) ? "Bob" : "Alice");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc148/editorial/4774

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, M;

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

map<int, int> m;

rep(i, N * 2){

int a;

scanf("%d", &a);

++m[a];

}

// 2. マッチング(赤い辺).

// -> 同じ数が書きこまれたものを, mod 2 で, 除外して, 残った数字(0 / 1 個)を拾ってくる.

vi r;

for(auto &p : m) rep(i, (p.b % 2)) r.pb(p.a);

// 3. M が奇数.

// -> 完全マッチングが見つかったら, Bob勝ちと見る.

if(M & 1){

printf("%s\n", r.size() ? "Alice" : "Bob");

return 0;

}

// 4. M が偶数.

// -> M / 2 で, 分類し, 青い辺の使用本数を数える.

m.clear();

for(auto &p : r) ++m[p % M];

int bUsed = 0;

for(auto &p : m){

int o = p.a + M / 2;

if(p.b && m.count(o)){

int s = min(p.b, m[o]);

p.b -= s;

m[o] -= s;

bUsed += s;

}

// 5. 完全マッチングか？

bool isPerfectMatching = true;

for(auto &p : m){

if(p.b % 2){

isPerfectMatching = false;

break;

}

// 6. 出力.

printf("%s\n", (!(bUsed & 1) && isPerfectMatching) ? "Bob" : "Alice");

return 0;

}

[入力例]
2 9
1 4 8 5

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

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

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

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

[出力例]
Alice

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

[出力例]
Alice

[入力例]
15 130
55 67 100 8 2 116 85 120 71 81 110 105 108 55 22 55 67 100 8 67 116 85 120 71 81 110 40 108 55 22

[出力例]
Bob

[入力例]

2 9

1 4 8 5

[出力例]

Alice

※AtCoderテストケースより

[入力例]

3 998244353

1 2 3 1 2 3

[出力例]

Bob

※AtCoderテストケースより

[入力例]

5 10

3 1 4 1 5 9 2 6 5 3

[出力例]

Alice

[入力例]

10 10

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

[出力例]

Alice

[入力例]

15 130

55 67 100 8 2 116 85 120 71 81 110 105 108 55 22 55 67 100 8 67 116 85 120 71 81 110 40 108 55 22

[出力例]

Bob

■参照サイト
AtCoder Regular Contest 148

2022年10月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題A (Continuous 1) ～問題B (Make Divisible) を解いてみた.

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

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

■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 T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        int N, K;
        scanf("%d %d", &N, &K);
        char c[N + 1];
        scanf("%s", c);
        string s(c);
        
        // 2-2. 累積和.
        int oCum[N + 1], qCum[N + 1];
        rep(j, N + 1) qCum[j] = oCum[j] = 0;
        rep(j, N){
            oCum[j + 1] = oCum[j] + (s[j] == '1');
            qCum[j + 1] = qCum[j] + (s[j] == '?');
        }
        
        // 2-3. 条件を満たすものがあるか？
        int cnt = 0;
        rep(j, N - K + 1){
            // 左.
            bool ok = (oCum[j] == 0);
            
            // 中.
            ok &= ((oCum[j + K] - oCum[j]) + (qCum[j + K] - qCum[j]) == K);
            
            // 右.
            ok &= (oCum[N] - oCum[j + K] == 0);
            
            // 集計.
            if(ok) ++cnt;
        }
        
        // 2-4. 出力.
        printf("%s\n", (cnt == 1) ? "Yes" : "No");
    }
    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 T;

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

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

int N, K;

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

char c[N + 1];

scanf("%s", c);

string s(c);

// 2-2. 累積和.

int oCum[N + 1], qCum[N + 1];

rep(j, N + 1) qCum[j] = oCum[j] = 0;

rep(j, N){

oCum[j + 1] = oCum[j] + (s[j] == '1');

qCum[j + 1] = qCum[j] + (s[j] == '?');

}

// 2-3. 条件を満たすものがあるか？

int cnt = 0;

rep(j, N - K + 1){

// 左.

bool ok = (oCum[j] == 0);

// 中.

ok &= ((oCum[j + K] - oCum[j]) + (qCum[j + K] - qCum[j]) == K);

// 右.

ok &= (oCum[N] - oCum[j + K] == 0);

// 集計.

if(ok) ++cnt;

}

// 2-4. 出力.

printf("%s\n", (cnt == 1) ? "Yes" : "No");

}

return 0;

}

[入力例]
4
3 2
1??
4 2
?1?0
6 3
011?1?
10 5
00?1???10?

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

[入力例]
5
5 1
??000
5 2
0??10
5 5
11111
7 5
001?1??
7 5
00101??

[出力例]
No
Yes
Yes
Yes
No

[入力例]
7
3 1
000
3 1
00?
3 1
0?1
3 1
1?1
5 3
1?100
10 5
00?11??110
13 7
0000?11??1?00

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

[入力例]

3 2

1??

4 2

?1?0

6 3

011?1?

10 5

00?1???10?

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

5 1

??000

5 2

0??10

5 5

11111

7 5

001?1??

7 5

00101??

[出力例]

Yes

[入力例]

3 1

000

3 1

00?

3 1

0?1

3 1

1?1

5 3

1?100

10 5

00?11??110

13 7

0000?11??1?00

[出力例]

Yes

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

// 解き直し.
// https://atcoder.jp/contests/arc150/editorial/4864
// 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 T;
    scanf("%d", &T);
    
    // 2. テストケース.
    rep(i, T){
        // 2-1. 各テストケース.
        LL A, B;
        scanf("%lld %lld", &A, &B);
        
        // 2-2. k が [1, sqrt(B - 1) + 1].
        LL ans = 202020202020202020;
        repx(k, 1, (int)sqrt(B - 1) + 1){
            LL q = (B - 1) / k;
            ans = min(ans, (k + 1) * max(0LL, q + 1 - A) + k * A - B);
        }
        
        // 2-3. k が [sqrt(B - 1) + 2, B].
        rep(q, (int)sqrt(B - 1) + 1){
            LL k = (B - 1) / (q + 1) + 1;
            ans = min(ans, (k + 1) * max(0LL, q + 1 - A) + k * A - B);
        }
        // 2-4. 出力.
        printf("%lld\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc150/editorial/4864

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

scanf("%d", &T);

// 2. テストケース.

rep(i, T){

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

LL A, B;

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

// 2-2. k が [1, sqrt(B - 1) + 1].

LL ans = 202020202020202020;

repx(k, 1, (int)sqrt(B - 1) + 1){

LL q = (B - 1) / k;

ans = min(ans, (k + 1) * max(0LL, q + 1 - A) + k * A - B);

}

// 2-3. k が [sqrt(B - 1) + 2, B].

rep(q, (int)sqrt(B - 1) + 1){

LL k = (B - 1) / (q + 1) + 1;

ans = min(ans, (k + 1) * max(0LL, q + 1 - A) + k * A - B);

}

// 2-4. 出力.

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

}

return 0;

}

[入力例]
5
11 23
8 16
4394 993298361
95392025 569922442
8399283 10293

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

[入力例]
30
30 53
869 1221
77 918
3358 2455
11064 9982
11500 390
8174 7609
4663 1829
67505 5630
54995 47547
6837 19968
12879 59160
30230 60342
46813 52697
98695 39214
62846 202020
27085 175622
369593 736366
748395 802632
303030 626363
6461788 12088026
11226373 406096
9616101 7777777
101900 12047210
4967027 7967424
7822686 268354
1730062 3281498
3629974 5738535
8019338 10092093
8256235 6467269

[出力例]
7
352
6
903
1082
11110
565
2834
61875
7448
543
1911
118
5884
59481
4494
2190
2820
54237
10153
835550
10820277
1838324
195
1966630
7554332
178626
1521413
2072755
1788966

[入力例]

11 23

8 16

4394 993298361

95392025 569922442

8399283 10293

[出力例]

2429708

8388990

※AtCoderのテストケースより

[入力例]

30 53

869 1221

77 918

3358 2455

11064 9982

11500 390

8174 7609

4663 1829

67505 5630

54995 47547

6837 19968

12879 59160

30230 60342

46813 52697

98695 39214

62846 202020

27085 175622

369593 736366

748395 802632

303030 626363

6461788 12088026

11226373 406096

9616101 7777777

101900 12047210

4967027 7967424

7822686 268354

1730062 3281498

3629974 5738535

8019338 10092093

8256235 6467269

[出力例]

352

903

1082

11110

565

2834

61875

7448

543

1911

118

5884

59481

4494

2190

2820

54237

10153

835550

10820277

1838324

195

1966630

7554332

178626

1521413

2072755

1788966

■参照サイト
AtCoder Regular Contest 150

2022年10月9日

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

C++の練習を兼ねて, AtCoder Beginner Contest 135 の問題F (Strings of Eternity) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/abc135/editorial.pdf
// 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. 入力情報.
    char c1[505050], c2[505050];
    scanf("%s %s", c1, c2);
    string s(c1), t(c2);
    int ss = s.size();
    int ts = t.size();
    
    // 2. 文字列 s の 拡張.
    string es = t + s + s;
    while(es.size() < 3 * ts) es += s;
    int ess = es.size();
    
    // 3. Z-Algorithm.
    // https://atcoder.jp/contests/abc257/editorial/4185
    // -> 解説プログラム一部変更.
    // ex.
    // S = abracadabra の 場合, 
    // f[i] = 11 0 0 1 0 1 0 4 0 0 1 
    // 
    // S = abcabc の 場合, 
    // f[i] = 6 0 0 3 0 0 
    auto z = [](string s, int ss, int* f){
        int l = 0, r = 1;
        f[0] = ss;
        repx(i, 1, ss){
            if(i > 1 && f[i - l] < r - i){
                f[i] = f[i - l];
                continue;
            }
            r = max(i, r);
            while(r < ss){
                if(s[r] == s[r - i]) ++r;
                else                 break;
            }
            f[i] = r - i;
            l = i;
        }
    };
    int zf[ess];
    rep(i, ess) zf[i] = 0;
    z(es, ess, zf);
    // rep(i, ess) printf("%d ", zf[i]);
    // puts("");
    
    // 4. match設定.
    bool m[ss];
    rep(i, ss) m[i] = 0;
    rep(i, ss) if(zf[i + ts] >= ts) m[i] = true;
    
    // 5. 有向グラフ作成.
    int p[ss], iDegree[ss], oDegree[ss];
    rep(i, ss){
        p[i] = -1;
        iDegree[i] = oDegree[i] = 0;
    }
    rep(i, ss){
        if(m[i]){
            int j = (i + ts) % ss;
            p[j] = i;
            ++iDegree[j];
            ++oDegree[i];
        }
    }
    
    // 6. 例外(ループあり).
    // -> 入次数: 1, 出次数: 1 の 頂点 が 1 個以上あって, 
    //    それ以外は, 入次数: 0, 出次数: 0 の 頂点 で構成される場合.
    int d00 = 0, d11 = 0;
    rep(i, ss){
        if(!iDegree[i] && !oDegree[i]) ++d00;
        if(iDegree[i] && oDegree[i]) ++d11;
    }
    if(d11 >= 1 && d00 + d11 == ss){
        puts("-1");
        return 0;
    }
    
    // 7. ループなし.
    int ans = 0;
    rep(i, ss){
        if(iDegree[i] && !oDegree[i]){
            // 最長パス候補は？
            int cur = i, d = 0;
            while(p[cur] != -1){
                cur = p[cur];
                ++d;
            }
            
            // 最大値更新.
            ans = max(ans, d);
        }
    }
    
    // 8. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解き直し.

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

// 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. 入力情報.

char c1[505050], c2[505050];

scanf("%s %s", c1, c2);

string s(c1), t(c2);

int ss = s.size();

int ts = t.size();

// 2. 文字列 s の拡張.

string es = t + s + s;

while(es.size() < 3 * ts) es += s;

int ess = es.size();

// 3. Z-Algorithm.

// https://atcoder.jp/contests/abc257/editorial/4185

// -> 解説プログラム一部変更.

// ex.

// S = abracadabra の場合,

// f[i] = 11 0 0 1 0 1 0 4 0 0 1

// S = abcabc の場合,

// f[i] = 6 0 0 3 0 0

auto z = [](string s, int ss, int* f){

int l = 0, r = 1;

f[0] = ss;

repx(i, 1, ss){

if(i > 1 && f[i - l] < r - i){

f[i] = f[i - l];

continue;

}

r = max(i, r);

while(r < ss){

if(s[r] == s[r - i]) ++r;

else break;

}

f[i] = r - i;

l = i;

}

};

int zf[ess];

rep(i, ess) zf[i] = 0;

z(es, ess, zf);

// rep(i, ess) printf("%d ", zf[i]);

// puts("");

// 4. match設定.

bool m[ss];

rep(i, ss) m[i] = 0;

rep(i, ss) if(zf[i + ts] >= ts) m[i] = true;

// 5. 有向グラフ作成.

int p[ss], iDegree[ss], oDegree[ss];

rep(i, ss){

p[i] = -1;

iDegree[i] = oDegree[i] = 0;

}

rep(i, ss){

if(m[i]){

int j = (i + ts) % ss;

p[j] = i;

++iDegree[j];

++oDegree[i];

}

// 6. 例外(ループあり).

// -> 入次数: 1, 出次数: 1 の頂点が 1 個以上あって,

// それ以外は, 入次数: 0, 出次数: 0 の頂点で構成される場合.

int d00 = 0, d11 = 0;

rep(i, ss){

if(!iDegree[i] && !oDegree[i]) ++d00;

if(iDegree[i] && oDegree[i]) ++d11;

}

if(d11 >= 1 && d00 + d11 == ss){

puts("-1");

return 0;

}

// 7. ループなし.

int ans = 0;

rep(i, ss){

if(iDegree[i] && !oDegree[i]){

// 最長パス候補は？

int cur = i, d = 0;

while(p[cur] != -1){

cur = p[cur];

++d;

}

// 最大値更新.

ans = max(ans, d);

}

// 8. 出力.

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

return 0;

}

[入力例]
abcabab
ab

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

[入力例]
aa
aaaaaaa

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

[入力例]
aba
baaab

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

[入力例]
ab
baba

[出力例]
-1

[入力例]
pqr
pqr

[出力例]
-1

[入力例]
abccabababcab
ab

[出力例]
3

[入力例]
pqryulzmwlyuqypqrzznspqrpqrpqrpqr
pqr

[出力例]
5

[入力例]
dpdpdpdpdpddddpdpddddpdpdddppddpdpddppdppddpddpdpdpdpdpdpddpppdpppddpdddppddppppddddppddppddpppddpdp
dp

[出力例]
7

[入力例]
deratcoderatcoderatcoderatcoderatcoderatcoderatcoderatcoderfqeluoqgtgfrdknbkruhnpglwoxfaesjqtobfwyiacxitikrlgbpedkofbabheyigovkybvygeatqyeisjzvjkgxfwvafkyledxiutjmedatcoderwznatcoderatcodervvtgcryerfpbzwwfaqksxxiepjtkjugzyfthzxexzehfxlqlvnbirejatqksjqztrpzamynpxavqlqkvsbwyamkxavdquqrgsuvatcoderatcoderatcoderatcoderatcoderonyhvvgyqmkskoxzwrdrcvuhpoyuwykplwomgnebqhthylhkxocfrbcgufzlyywpviqkqmofctqwmdhzmbnaqwpjehlkwaezntcqsfwbctagjuldzrmpzfylcezxdqdmasjluzexjfmjxetfbnxacewpcwlhsuoqjszkokatcoderatco
atcoder

[出力例]
10

[入力例]

abcabab

[出力例]

※AtCoderのテストケースより

[入力例]

aaaaaaa

[出力例]

-1

※AtCoderのテストケースより

[入力例]

aba

baaab

[出力例]

※AtCoderのテストケースより

[入力例]

baba

[出力例]

-1

[入力例]

pqr

[出力例]

-1

[入力例]

abccabababcab

[出力例]

[入力例]

pqryulzmwlyuqypqrzznspqrpqrpqrpqr

pqr

[出力例]

[入力例]

dpdpdpdpdpddddpdpddddpdpdddppddpdpddppdppddpddpdpdpdpdpdpddpppdpppddpdddppddppppddddppddppddpppddpdp

[出力例]

[入力例]

deratcoderatcoderatcoderatcoderatcoderatcoderatcoderatcoderfqeluoqgtgfrdknbkruhnpglwoxfaesjqtobfwyiacxitikrlgbpedkofbabheyigovkybvygeatqyeisjzvjkgxfwvafkyledxiutjmedatcoderwznatcoderatcodervvtgcryerfpbzwwfaqksxxiepjtkjugzyfthzxexzehfxlqlvnbirejatqksjqztrpzamynpxavqlqkvsbwyamkxavdquqrgsuvatcoderatcoderatcoderatcoderatcoderonyhvvgyqmkskoxzwrdrcvuhpoyuwykplwomgnebqhthylhkxocfrbcgufzlyywpviqkqmofctqwmdhzmbnaqwpjehlkwaezntcqsfwbctagjuldzrmpzfylcezxdqdmasjluzexjfmjxetfbnxacewpcwlhsuoqjszkokatcoderatco

atcoder

[出力例]

■参照サイト
AtCoder Beginner Contest 135

2022年10月9日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 個人的には, 場合分けなど, 実装に苦労したものの, 良い経験になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL K, X, Y;
    scanf("%lld %lld %lld", &K, &X, &Y);
    
    // 2. 該当する象限は？
    int q = 0;
    if(X >= 0) q = (Y >= 0) ? 1 : 4;
    else       q = (Y >= 0) ? 2 : 3;
    
    // 3. 例外.
    // -> K が 偶数, X + Y が 奇数.
    if(!(K & 1) && ((X + Y) & 1)){
        puts("-1");
        return 0;
    }
    
    // 4. 変換.
    // -> 出力時に, 逆変換したものを採用する.
    if(q == 2) X = -X;
    if(q == 3) X = -X, Y = -Y;
    if(q == 4) Y = -Y;
    
    // 5. 反転.
    // -> X >= Y となるように調整.
    bool flip = false;
    if(X < Y){
        swap(X, Y);
        flip = true;
    }
    
    // 6. 経路.
    auto f = [&]() -> vp {
        // ボールの動かし方を保存.
        vp res;
        
        // X + Y = K (n = 1).
        if(X + Y == K){
            res.pb({X, Y});
            return res;
        }
        
        // X + Y < K.
        if(X + Y < K){
            // タイプ B (n = 3).
            if((X + Y) & 1){
                res.pb({X, X - K});
                res.pb({X + (K + X - Y) / 2, (X + Y - K) / 2});
                res.pb({X, Y});
                return res;
            }
            
            // タイプ A (n = 2).
            res.pb({(X + Y) / 2, -K + (X + Y) / 2});
            res.pb({X, Y});
            return res;
        }
        
        // X + Y > K.
        // タイプ A.
        // c が 奇数 の 場合は, n に 1 加算.
        LL c = (K - (X + Y) % K) % K;
        LL n = (X + Y + K - 1) / K;
        if(c & 1) ++n;
        
        // 下へ.
        LL my = (K * n - X - Y) / 2;
        LL q1 = my / K;
        rep(i, q1) res.pb({0LL, K * i});
        
        // 右へ.
        LL r1 = (K * n - X - Y) / 2 - q1 * K;
        LL q2 = (X + r1) / K;
        rep(i, q2) res.pb({K * (i + 1) - r1, -my});
        
        // 上へ.
        LL r2 = X + r1 - K * q2;
        LL q3 = ((K * n - X + Y) / 2 + r2) / K;
        rep(i, q3) res.pb({X, K * (i + 1) - r2 - my});
        return res;
    };
    
    // 7. 出力.
    vp ans = f();
    printf("%d\n", ans.size());
    for(auto &p : ans){
        // 逆変換.
        P cur = p;
        if(flip) swap(cur.a, cur.b);
        if(q == 2) cur.a = -cur.a;
        if(q == 3) cur.a = -cur.a, cur.b = -cur.b;
        if(q == 4) cur.b = -cur.b;
        
        // 出力.
        printf("%lld %lld\n", cur.a, cur.b);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, LL>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

LL K, X, Y;

scanf("%lld %lld %lld", &K, &X, &Y);

// 2. 該当する象限は？

int q = 0;

if(X >= 0) q = (Y >= 0) ? 1 : 4;

else q = (Y >= 0) ? 2 : 3;

// 3. 例外.

// -> K が偶数, X + Y が奇数.

if(!(K & 1) && ((X + Y) & 1)){

puts("-1");

return 0;

}

// 4. 変換.

// -> 出力時に, 逆変換したものを採用する.

if(q == 2) X = -X;

if(q == 3) X = -X, Y = -Y;

if(q == 4) Y = -Y;

// 5. 反転.

// -> X >= Y となるように調整.

bool flip = false;

if(X < Y){

swap(X, Y);

flip = true;

}

// 6. 経路.

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

// ボールの動かし方を保存.

vp res;

// X + Y = K (n = 1).

if(X + Y == K){

res.pb({X, Y});

return res;

}

// X + Y < K.

if(X + Y < K){

// タイプ B (n = 3).

if((X + Y) & 1){

res.pb({X, X - K});

res.pb({X + (K + X - Y) / 2, (X + Y - K) / 2});

res.pb({X, Y});

return res;

}

// タイプ A (n = 2).

res.pb({(X + Y) / 2, -K + (X + Y) / 2});

res.pb({X, Y});

return res;

}

// X + Y > K.

// タイプ A.

// c が奇数の場合は, n に 1 加算.

LL c = (K - (X + Y) % K) % K;

LL n = (X + Y + K - 1) / K;

if(c & 1) ++n;

// 下へ.

LL my = (K * n - X - Y) / 2;

LL q1 = my / K;

rep(i, q1) res.pb({0LL, K * i});

// 右へ.

LL r1 = (K * n - X - Y) / 2 - q1 * K;

LL q2 = (X + r1) / K;

rep(i, q2) res.pb({K * (i + 1) - r1, -my});

// 上へ.

LL r2 = X + r1 - K * q2;

LL q3 = ((K * n - X + Y) / 2 + r2) / K;

rep(i, q3) res.pb({X, K * (i + 1) - r2 - my});

return res;

};

// 7. 出力.

vp ans = f();

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

for(auto &p : ans){

// 逆変換.

P cur = p;

if(flip) swap(cur.a, cur.b);

if(q == 2) cur.a = -cur.a;

if(q == 3) cur.a = -cur.a, cur.b = -cur.b;

if(q == 4) cur.b = -cur.b;

// 出力.

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

}

return 0;

}

[入力例]
11
-1 2

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

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

[入力例]
4600
52 149

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

[入力例]
4
9 9

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

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

[入力例]
1
-3 4

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

[入力例]
7
5 2

[出力例]
1
5 2

[入力例]
7
3 2

[出力例]
3
3 -4
7 -1
3 2

[入力例]
11
5 2

[出力例]
3
5 -6
12 -2
5 2

[入力例]
10
20 22

[出力例]
5
-4 6
-4 16
0 22
10 22
20 22

[入力例]
11
123 101

[出力例]
22
2 -9
13 -9
24 -9
35 -9
46 -9
57 -9
68 -9
79 -9
90 -9
101 -9
112 -9
123 -9
123 2
123 13
123 24
123 35
123 46
123 57
123 68
123 79
123 90
123 101

[入力例]
123
2022 2023

[出力例]
33
-7 116
-7 239
-7 362
-7 485
-7 608
-7 731
-7 854
-7 977
-7 1100
-7 1223
-7 1346
-7 1469
-7 1592
-7 1715
-7 1838
-7 1961
54 2023
177 2023
300 2023
423 2023
546 2023
669 2023
792 2023
915 2023
1038 2023
1161 2023
1284 2023
1407 2023
1530 2023
1653 2023
1776 2023
1899 2023
2022 2023

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

[入力例]

-1 2

[出力例]

7 4

2 10

-1 2

※AtCoderテストケースより

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

9 2

4 8

-1 2

[入力例]

4600

52 149

[出力例]

-1

※AtCoderテストケースより

[入力例]

9 9

[出力例]

1 3

4 2

4 6

6 8

9 9

※AtCoderテストケースより

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

3 -1

7 -1

9 1

9 5

9 9

[入力例]

-3 4

[出力例]

0 1

0 2

0 3

0 4

-1 4

-2 4

-3 4

[入力例]

5 2

[出力例]

5 2

[入力例]

3 2

[出力例]

3 -4

7 -1

3 2

[入力例]

5 2

[出力例]

5 -6

12 -2

5 2

[入力例]

20 22

[出力例]

-4 6

-4 16

0 22

10 22

20 22

[入力例]

123 101

[出力例]

2 -9

13 -9

24 -9

35 -9

46 -9

57 -9

68 -9

79 -9

90 -9

101 -9

112 -9

123 -9

123 2

123 13

123 24

123 35

123 46

123 57

123 68

123 79

123 90

123 101

[入力例]

123

2022 2023

[出力例]

-7 116

-7 239

-7 362

-7 485

-7 608

-7 731

-7 854

-7 977

-7 1100

-7 1223

-7 1346

-7 1469

-7 1592

-7 1715

-7 1838

-7 1961

54 2023

177 2023

300 2023

423 2023

546 2023

669 2023

792 2023

915 2023

1038 2023

1161 2023

1284 2023

1407 2023

1530 2023

1653 2023

1776 2023

1899 2023

2022 2023

■参照サイト
AtCoder Beginner Contest 135

2022年10月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 149 の問題C (Avoid Prime Sum) を解いてみた.

■感想.
1. 問題Cは, 解法の糸口を見つけることが出来たので, AC版に到達できた.
2. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int MAX = 2 * 1010 * 1010 + 1;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 素数を用意.
    vi p(MAX);
    repx(i, 2, MAX){
        if(p[i]) continue;
        repex(j, i * 2, MAX, i) ++p[j];
    }
    
    // 3. 評価関数.
    auto f = [&](vvi &a, int n) -> bool {
        // 3-1. 隣接二マス合計が, 素数ではない.
        rep(i, n){
            rep(j, n){
                // 現在地点.
                int cur = a[i][j];
                
                // 上.
                if(i && !p[cur + a[i - 1][j]]) return false;
                
                // 下.
                if(i < n - 1 && !p[cur + a[i + 1][j]]) return false;
                
                // 左.
                if(j && !p[cur + a[i][j - 1]]) return false;
                
                // 右.
                if(j < n - 1 && !p[cur + a[i][j + 1]]) return false;
            }
        }
        
        // 3-2. N * N 以下の正整数が, 一回ずつ出現する.
        set<int> st;
        rep(i, n) rep(j, n) st.insert(a[i][j]);
        if(st.size() != n * n) return false;
        
        // 3-3. 制約を満たしている.
        return true;
    };
    
    // 4. N = 3 の 場合.
    vvi ans(N, vi(N, 0));
    if(N == 3){
        // 1 行目.
        ans[0][0] = 5;
        ans[0][1] = 9;
        ans[0][2] = 1;
        
        // 2 行目.
        ans[1][0] = 3;
        ans[1][1] = 7;
        ans[1][2] = 8;
        
        // 3 行目.
        ans[2][0] = 6;
        ans[2][1] = 2;
        ans[2][2] = 4;
    }
    
    // 5. N = 5 の 場合.
    if(N == 5){
        // 1 行目.
        ans[0][0] = 11;
        ans[0][1] = 13;
        ans[0][2] = 15;
        ans[0][3] = 17;
        ans[0][4] = 19;
        
        // 2 行目.
        ans[1][0] = 21;
        ans[1][1] = 23;
        ans[1][2] = 25;
        ans[1][3] = 3;
        ans[1][4] = 5;
        
        // 3 行目.
        ans[2][0] = 7;
        ans[2][1] = 9;
        ans[2][2] = 1;
        ans[2][3] = 24;
        ans[2][4] = 10;
        
        // 4 行目.
        ans[3][0] = 8;
        ans[3][1] = 6;
        ans[3][2] = 14;
        ans[3][3] = 2;
        ans[3][4] = 4;
        
        // 5 行目.
        ans[4][0] = 12;
        ans[4][1] = 16;
        ans[4][2] = 18;
        ans[4][3] = 20;
        ans[4][4] = 22;
    }
    
    // 6. N が 偶数.
    if(!(N & 1)){
        int n = 0;
        set<int> e;
        rep(i, N * N) if(i & 1) e.insert(i + 1);
        
        // 1 と 隣接しても, 素数にならない偶数は？
        repex(i, 2 * N, N * N + 1, 2){
            if(p[i + 1]){
                n = i + 1;
                break;
            }
        }
        
        // 上半分(奇数).
        int cur = -1;
        rep(j, N) ans[N / 2 - 1][j] = (++cur) * 2 + 1;
        rep(i, N / 2 - 1) rep(j, N) ans[i][j] = (++cur) * 2 + 1;
        
        // 下半分(偶数).
        rep(j, N){
            ans[N / 2][j] = n - ans[N / 2 - 1][j];
            e.erase(ans[N / 2][j]);
        }
        repx(i, N / 2 + 1, N){
            rep(j, N){
                ans[i][j] = *e.begin();
                e.erase(ans[i][j]);
            }
        }
    }
    
    // 7. N が 5 より大きい奇数.
    if(N > 5 && (N & 1)){
        int n1 = 0, n2 = 0;
        set<int> e;
        rep(i, N * N) if(i & 1) e.insert(i + 1);
        
        // 1, 3 と 隣接しても, 素数にならない偶数は？
        repex(i, 2, N * N + 1, 2){
            if(p[i + 1] && p[i + 3]){
                n1 = i;
                break;
            }
        }
        
        // (n1 + 2 * N) 以上 で, 5 と 隣接しても, 素数にならない偶数は？
        repex(i, n1 + 2 * N, N * N + 1, 2){
            if(p[i + 5]){
                n2 = i + 5;
                break;
            }
        }
        
        // 上半分(奇数).
        int cur = -1;
        ans[N / 2][N / 2] = (++cur) * 2 + 1;
        repx(j, N / 2 + 1, N)       ans[N / 2 - 1][j] = (++cur) * 2 + 1;
        rep(j, N / 2)               ans[N / 2][j] = (++cur) * 2 + 1;
        rep(i, N / 2 - 1) rep(j, N) ans[i][j] = (++cur) * 2 + 1;
        rep(j, N / 2 + 1)           ans[N / 2 - 1][j] = (++cur) * 2 + 1;
        
        // 下半分(偶数).
        ans[N / 2][N / 2 + 1] = n1;
        e.erase(ans[N / 2][N / 2 + 1]);
        repx(j, N / 2 + 2, N){
            ans[N / 2][j] = n2 - ans[N / 2 - 1][j];
            e.erase(ans[N / 2][j]);
        }
        rep(j, N){
            ans[N / 2 + 1][j] = (j <= N / 2) ? (n2 - ans[N / 2][j]) : *e.begin();
            e.erase(ans[N / 2 + 1][j]);
        }
        repx(i, N / 2 + 2, N){
            rep(j, N){
                ans[i][j] = *e.begin();
                e.erase(ans[i][j]);
            }
        }
    }
    
    // 8. 制約チェック.
    assert(f(ans, N));
    
    // 9. 出力.
    rep(i, N) rep(j, N) printf("%d%s", ans[i][j], (j < N - 1) ? " " : "\n");
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

const int MAX = 2 * 1010 * 1010 + 1;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 素数を用意.

vi p(MAX);

repx(i, 2, MAX){

if(p[i]) continue;

repex(j, i * 2, MAX, i) ++p[j];

}

// 3. 評価関数.

auto f = [&](vvi &a, int n) -> bool {

// 3-1. 隣接二マス合計が, 素数ではない.

rep(i, n){

rep(j, n){

// 現在地点.

int cur = a[i][j];

// 上.

if(i && !p[cur + a[i - 1][j]]) return false;

// 下.

if(i < n - 1 && !p[cur + a[i + 1][j]]) return false;

// 左.

if(j && !p[cur + a[i][j - 1]]) return false;

// 右.

if(j < n - 1 && !p[cur + a[i][j + 1]]) return false;

}

// 3-2. N * N 以下の正整数が, 一回ずつ出現する.

set<int> st;

rep(i, n) rep(j, n) st.insert(a[i][j]);

if(st.size() != n * n) return false;

// 3-3. 制約を満たしている.

return true;

};

// 4. N = 3 の場合.

vvi ans(N, vi(N, 0));

if(N == 3){

// 1 行目.

ans[0][0] = 5;

ans[0][1] = 9;

ans[0][2] = 1;

// 2 行目.

ans[1][0] = 3;

ans[1][1] = 7;

ans[1][2] = 8;

// 3 行目.

ans[2][0] = 6;

ans[2][1] = 2;

ans[2][2] = 4;

}

// 5. N = 5 の場合.

if(N == 5){

// 1 行目.

ans[0][0] = 11;

ans[0][1] = 13;

ans[0][2] = 15;

ans[0][3] = 17;

ans[0][4] = 19;

// 2 行目.

ans[1][0] = 21;

ans[1][1] = 23;

ans[1][2] = 25;

ans[1][3] = 3;

ans[1][4] = 5;

// 3 行目.

ans[2][0] = 7;

ans[2][1] = 9;

ans[2][2] = 1;

ans[2][3] = 24;

ans[2][4] = 10;

// 4 行目.

ans[3][0] = 8;

ans[3][1] = 6;

ans[3][2] = 14;

ans[3][3] = 2;

ans[3][4] = 4;

// 5 行目.

ans[4][0] = 12;

ans[4][1] = 16;

ans[4][2] = 18;

ans[4][3] = 20;

ans[4][4] = 22;

}

// 6. N が偶数.

if(!(N & 1)){

int n = 0;

set<int> e;

rep(i, N * N) if(i & 1) e.insert(i + 1);

// 1 と隣接しても, 素数にならない偶数は？

repex(i, 2 * N, N * N + 1, 2){

if(p[i + 1]){

n = i + 1;

break;

}

// 上半分(奇数).

int cur = -1;

rep(j, N) ans[N / 2 - 1][j] = (++cur) * 2 + 1;

rep(i, N / 2 - 1) rep(j, N) ans[i][j] = (++cur) * 2 + 1;

// 下半分(偶数).

rep(j, N){

ans[N / 2][j] = n - ans[N / 2 - 1][j];

e.erase(ans[N / 2][j]);

}

repx(i, N / 2 + 1, N){

rep(j, N){

ans[i][j] = *e.begin();

e.erase(ans[i][j]);

}

// 7. N が 5 より大きい奇数.

if(N > 5 && (N & 1)){

int n1 = 0, n2 = 0;

set<int> e;

rep(i, N * N) if(i & 1) e.insert(i + 1);

// 1, 3 と隣接しても, 素数にならない偶数は？

repex(i, 2, N * N + 1, 2){

if(p[i + 1] && p[i + 3]){

n1 = i;

break;

}

// (n1 + 2 * N) 以上で, 5 と隣接しても, 素数にならない偶数は？

repex(i, n1 + 2 * N, N * N + 1, 2){

if(p[i + 5]){

n2 = i + 5;

break;

}

// 上半分(奇数).

int cur = -1;

ans[N / 2][N / 2] = (++cur) * 2 + 1;

repx(j, N / 2 + 1, N) ans[N / 2 - 1][j] = (++cur) * 2 + 1;

rep(j, N / 2) ans[N / 2][j] = (++cur) * 2 + 1;

rep(i, N / 2 - 1) rep(j, N) ans[i][j] = (++cur) * 2 + 1;

rep(j, N / 2 + 1) ans[N / 2 - 1][j] = (++cur) * 2 + 1;

// 下半分(偶数).

ans[N / 2][N / 2 + 1] = n1;

e.erase(ans[N / 2][N / 2 + 1]);

repx(j, N / 2 + 2, N){

ans[N / 2][j] = n2 - ans[N / 2 - 1][j];

e.erase(ans[N / 2][j]);

}

rep(j, N){

ans[N / 2 + 1][j] = (j <= N / 2) ? (n2 - ans[N / 2][j]) : *e.begin();

e.erase(ans[N / 2 + 1][j]);

}

repx(i, N / 2 + 2, N){

rep(j, N){

ans[i][j] = *e.begin();

e.erase(ans[i][j]);

}

// 8. 制約チェック.

assert(f(ans, N));

// 9. 出力.

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

return 0;

}

[入力例]
4

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

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

[入力例]
3

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

[入力例]
5

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

[入力例]
6

[出力例]
13 15 17 19 21 23
25 27 29 31 33 35
1 3 5 7 9 11
14 12 10 8 6 4
2 16 18 20 22 24
26 28 30 32 34 36

[入力例]
7

[出力例]
15 17 19 21 23 25 27
29 31 33 35 37 39 41
43 45 47 49 3 5 7
9 11 13 1 24 40 38
36 34 32 44 2 4 6
8 10 12 14 16 18 20
22 26 28 30 42 46 48

[入力例]
10

[出力例]
21 23 25 27 29 31 33 35 37 39
41 43 45 47 49 51 53 55 57 59
61 63 65 67 69 71 73 75 77 79
81 83 85 87 89 91 93 95 97 99
1 3 5 7 9 11 13 15 17 19
20 18 16 14 12 10 8 6 4 2
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

[入力例]
33

[出力例]
67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131
133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197
199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263
265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 321 323 325 327 329
331 333 335 337 339 341 343 345 347 349 351 353 355 357 359 361 363 365 367 369 371 373 375 377 379 381 383 385 387 389 391 393 395
397 399 401 403 405 407 409 411 413 415 417 419 421 423 425 427 429 431 433 435 437 439 441 443 445 447 449 451 453 455 457 459 461
463 465 467 469 471 473 475 477 479 481 483 485 487 489 491 493 495 497 499 501 503 505 507 509 511 513 515 517 519 521 523 525 527
529 531 533 535 537 539 541 543 545 547 549 551 553 555 557 559 561 563 565 567 569 571 573 575 577 579 581 583 585 587 589 591 593
595 597 599 601 603 605 607 609 611 613 615 617 619 621 623 625 627 629 631 633 635 637 639 641 643 645 647 649 651 653 655 657 659
661 663 665 667 669 671 673 675 677 679 681 683 685 687 689 691 693 695 697 699 701 703 705 707 709 711 713 715 717 719 721 723 725
727 729 731 733 735 737 739 741 743 745 747 749 751 753 755 757 759 761 763 765 767 769 771 773 775 777 779 781 783 785 787 789 791
793 795 797 799 801 803 805 807 809 811 813 815 817 819 821 823 825 827 829 831 833 835 837 839 841 843 845 847 849 851 853 855 857
859 861 863 865 867 869 871 873 875 877 879 881 883 885 887 889 891 893 895 897 899 901 903 905 907 909 911 913 915 917 919 921 923
925 927 929 931 933 935 937 939 941 943 945 947 949 951 953 955 957 959 961 963 965 967 969 971 973 975 977 979 981 983 985 987 989
991 993 995 997 999 1001 1003 1005 1007 1009 1011 1013 1015 1017 1019 1021 1023 1025 1027 1029 1031 1033 1035 1037 1039 1041 1043 1045 1047 1049 1051 1053 1055
1057 1059 1061 1063 1065 1067 1069 1071 1073 1075 1077 1079 1081 1083 1085 1087 1089 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33
35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 1 24 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 94 2 4 6 8 10 12 14 16 18 20 22 26 28 92 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 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 766 768 770 772 774 776 778 780 782 784 786 788 790 792 794 796 798 800 802 804 806 808 810 812 814 816 818 820 822 824
826 828 830 832 834 836 838 840 842 844 846 848 850 852 854 856 858 860 862 864 866 868 870 872 874 876 878 880 882 884 886 888 890
892 894 896 898 900 902 904 906 908 910 912 914 916 918 920 922 924 926 928 930 932 934 936 938 940 942 944 946 948 950 952 954 956
958 960 962 964 966 968 970 972 974 976 978 980 982 984 986 988 990 992 994 996 998 1000 1002 1004 1006 1008 1010 1012 1014 1016 1018 1020 1022
1024 1026 1028 1030 1032 1034 1036 1038 1040 1042 1044 1046 1048 1050 1052 1054 1056 1058 1060 1062 1064 1066 1068 1070 1072 1074 1076 1078 1080 1082 1084 1086 1088

100

101

102

103

104

105

106

107

108

109

[入力例]

[出力例]

15 11 16 12

13 3 6 9

14 7 8 1

4 2 10 5

※AtCoderのテストケースより

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

9 11 13 15

1 3 5 7

8 6 4 2

10 12 14 16

[入力例]

[出力例]

5 9 1

3 7 8

6 2 4

[入力例]

[出力例]

11 13 15 17 19

21 23 25 3 5

7 9 1 24 10

8 6 14 2 4

12 16 18 20 22

[入力例]

[出力例]

13 15 17 19 21 23

25 27 29 31 33 35

1 3 5 7 9 11

14 12 10 8 6 4

2 16 18 20 22 24

26 28 30 32 34 36

[入力例]

[出力例]

15 17 19 21 23 25 27

29 31 33 35 37 39 41

43 45 47 49 3 5 7

9 11 13 1 24 40 38

36 34 32 44 2 4 6

8 10 12 14 16 18 20

22 26 28 30 42 46 48

[入力例]

[出力例]

21 23 25 27 29 31 33 35 37 39

41 43 45 47 49 51 53 55 57 59

61 63 65 67 69 71 73 75 77 79

81 83 85 87 89 91 93 95 97 99

1 3 5 7 9 11 13 15 17 19

20 18 16 14 12 10 8 6 4 2

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

[入力例]

[出力例]

67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131

133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 183 185 187 189 191 193 195 197

199 201 203 205 207 209 211 213 215 217 219 221 223 225 227 229 231 233 235 237 239 241 243 245 247 249 251 253 255 257 259 261 263

265 267 269 271 273 275 277 279 281 283 285 287 289 291 293 295 297 299 301 303 305 307 309 311 313 315 317 319 321 323 325 327 329

331 333 335 337 339 341 343 345 347 349 351 353 355 357 359 361 363 365 367 369 371 373 375 377 379 381 383 385 387 389 391 393 395

397 399 401 403 405 407 409 411 413 415 417 419 421 423 425 427 429 431 433 435 437 439 441 443 445 447 449 451 453 455 457 459 461

463 465 467 469 471 473 475 477 479 481 483 485 487 489 491 493 495 497 499 501 503 505 507 509 511 513 515 517 519 521 523 525 527

529 531 533 535 537 539 541 543 545 547 549 551 553 555 557 559 561 563 565 567 569 571 573 575 577 579 581 583 585 587 589 591 593

595 597 599 601 603 605 607 609 611 613 615 617 619 621 623 625 627 629 631 633 635 637 639 641 643 645 647 649 651 653 655 657 659

661 663 665 667 669 671 673 675 677 679 681 683 685 687 689 691 693 695 697 699 701 703 705 707 709 711 713 715 717 719 721 723 725

727 729 731 733 735 737 739 741 743 745 747 749 751 753 755 757 759 761 763 765 767 769 771 773 775 777 779 781 783 785 787 789 791

793 795 797 799 801 803 805 807 809 811 813 815 817 819 821 823 825 827 829 831 833 835 837 839 841 843 845 847 849 851 853 855 857

859 861 863 865 867 869 871 873 875 877 879 881 883 885 887 889 891 893 895 897 899 901 903 905 907 909 911 913 915 917 919 921 923

925 927 929 931 933 935 937 939 941 943 945 947 949 951 953 955 957 959 961 963 965 967 969 971 973 975 977 979 981 983 985 987 989

991 993 995 997 999 1001 1003 1005 1007 1009 1011 1013 1015 1017 1019 1021 1023 1025 1027 1029 1031 1033 1035 1037 1039 1041 1043 1045 1047 1049 1051 1053 1055

1057 1059 1061 1063 1065 1067 1069 1071 1073 1075 1077 1079 1081 1083 1085 1087 1089 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33

35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 1 24 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 94 2 4 6 8 10 12 14 16 18 20 22 26 28 92 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 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 766 768 770 772 774 776 778 780 782 784 786 788 790 792 794 796 798 800 802 804 806 808 810 812 814 816 818 820 822 824

826 828 830 832 834 836 838 840 842 844 846 848 850 852 854 856 858 860 862 864 866 868 870 872 874 876 878 880 882 884 886 888 890

892 894 896 898 900 902 904 906 908 910 912 914 916 918 920 922 924 926 928 930 932 934 936 938 940 942 944 946 948 950 952 954 956

958 960 962 964 966 968 970 972 974 976 978 980 982 984 986 988 990 992 994 996 998 1000 1002 1004 1006 1008 1010 1012 1014 1016 1018 1020 1022

1024 1026 1028 1030 1032 1034 1036 1038 1040 1042 1044 1046 1048 1050 1052 1054 1056 1058 1060 1062 1064 1066 1068 1070 1072 1074 1076 1078 1080 1082 1084 1086 1088

■参照サイト
AtCoder Regular Contest 149

2022年10月6日

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

C++の練習を兼ねて, AtCoder Regular Contest 149 の問題A (Repdigit Number) ～問題B (Two LIS Sum) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc149/editorial/4869
// 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 N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 正整数 X は？
    int n = 0, d = 0;
    LL X = 0;
    repx(i, 1, 10){
        // 各桁が, i のみで構成される場合.
        X = i;
        repx(j, 1, N + 1){
            // 正整数 X の 最大値候補 となるか？
            if(X % M == 0 && n <= j){
                n = j;
                d = i;
            }
            
            // 次へ.
            X = (10 * X + i) % M;
        }
    }
    
    // 3. 例外.
    if(!n && !d){
        puts("-1");
        return 0;
    }
    
    // 4. 出力.
    rep(i, n) printf("%d", d);
    puts("");
    return 0;
    
}

// 解き直し.

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

// 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 N, M;

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

// 2. 正整数 X は？

int n = 0, d = 0;

LL X = 0;

repx(i, 1, 10){

// 各桁が, i のみで構成される場合.

X = i;

repx(j, 1, N + 1){

// 正整数 X の最大値候補となるか？

if(X % M == 0 && n <= j){

n = j;

d = i;

}

// 次へ.

X = (10 * X + i) % M;

}

// 3. 例外.

if(!n && !d){

puts("-1");

return 0;

}

// 4. 出力.

rep(i, n) printf("%d", d);

puts("");

return 0;

}

[入力例]
7 12

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

[入力例]
9 12

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

[入力例]
1 3

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

[入力例]
1000 25

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

[入力例]
30 1

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

[入力例]
20 22

[出力例]
88888888888888888888

[入力例]
314 159

[出力例]
999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

[入力例]
2022 1006

[出力例]
8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

[入力例]

7 12

[出力例]

888888

※AtCoderのテストケースより

[入力例]

9 12

[出力例]

888888888

※AtCoderのテストケースより

[入力例]

1 3

[出力例]

※AtCoderのテストケースより

[入力例]

1000 25

[出力例]

-1

※AtCoderのテストケースより

[入力例]

30 1

[出力例]

999999999999999999999999999999

※AtCoderのテストケースより

[入力例]

20 22

[出力例]

88888888888888888888

[入力例]

314 159

[出力例]

999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

[入力例]

2022 1006

[出力例]

8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888888

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vp v(N);
    rep(i, N) scanf("%d", &v[i].a);
    rep(i, N) scanf("%d", &v[i].b);
    
    // 2. sort.
    sort(all(v));
    
    // 3. 狭義単調増加な数列の長さの最大値は？
    // 以下の問題を参照.
    // https://atcoder.jp/contests/typical90/tasks/typical90_bh
    // -> LIS(Longest increase subsequence) を 利用.
    vi dp;
    for(auto &p : v){
        if(dp.size() == 0 || dp.back() < p.b){
            dp.pb(p.b);
            continue;
        }
        int at = lower_bound(all(dp), p.b) - dp.begin();
        dp[at] = p.b;
    }
    
    // 4. 出力.
    printf("%d\n", N + dp.size());
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vp v(N);

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

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

// 2. sort.

sort(all(v));

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

// 以下の問題を参照.

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

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

vi dp;

for(auto &p : v){

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

dp.pb(p.b);

continue;

}

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

dp[at] = p.b;

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

[出力例]
20

[入力例]
50
15 25 29 44 9 38 1 12 26 43 14 34 36 17 5 28 24 39 47 22 30 10 37 7 27 8 3 18 21 20 32 6 16 19 40 23 2 42 35 4 49 13 33 41 50 31 45 11 46 48
34 46 36 29 3 42 2 9 16 18 33 7 20 8 37 30 48 12 45 44 39 43 25 28 26 19 31 15 22 24 17 38 49 11 13 14 32 6 1 21 50 4 27 5 23 41 35 40 47 10

[出力例]
65

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

[出力例]
121

[入力例]

5 2 1 4 3

3 1 2 5 4

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 3 4 5

[出力例]

※AtCoderのテストケースより

[入力例]

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

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

[出力例]

[入力例]

15 25 29 44 9 38 1 12 26 43 14 34 36 17 5 28 24 39 47 22 30 10 37 7 27 8 3 18 21 20 32 6 16 19 40 23 2 42 35 4 49 13 33 41 50 31 45 11 46 48

34 46 36 29 3 42 2 9 16 18 33 7 20 8 37 30 48 12 45 44 39 43 25 28 26 19 31 15 22 24 17 38 49 11 13 14 32 6 1 21 50 4 27 5 23 41 35 40 47 10

[出力例]

[入力例]

100

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

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

[出力例]

121

■参照サイト
AtCoder Regular Contest 149

C++の練習を兼ねて, AtCoder Regular Contest 151 の 問題A (Equal Hamming Distances) ～ 問題B (A < AP) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 150 の 問題D (Removing Gacha) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 150 の 問題C (Path and Subsequence) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 148 の 問題D (mod M Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 150 の 問題A (Continuous 1) ～ 問題B (Make Divisible) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 135 の 問題F (Strings of Eternity) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 149 の 問題C (Avoid Prime Sum) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 149 の 問題A (Repdigit Number) ～ 問題B (Two LIS Sum) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 151 の問題A (Equal Hamming Distances) ～問題B (A < AP) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題D (Removing Gacha) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題C (Path and Subsequence) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 148 の問題D (mod M Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 150 の問題A (Continuous 1) ～問題B (Make Divisible) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 135 の問題F (Strings of Eternity) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 149 の問題C (Avoid Prime Sum) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 149 の問題A (Repdigit Number) ～問題B (Two LIS Sum) を解いてみた.