C++ | 個人用メモ帳

2022年5月4日2022年5月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 125 の問題A (Dial Up) ～問題B (Squares) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc125/editorial/2490
// 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 s[202020], t[202020];

int main(){
    
    // 1. 入力情報.
    int N, M, s0 = 0, s1 = 0, t0 = 0, t1 = 0, x = -1, y = -1;
    scanf("%d %d", &N, &M);
    rep(i, N){
        scanf("%d", &s[i]);
        if(s[i] == 0) ++s0;
        if(s[i] == 1) ++s1;
        if(s[i] != s[0]){
            if(x == -1) x = i;
            y = i;
        }
    }
    rep(i, M){
        scanf("%d", &t[i]);
        if(t[i] == 0) ++t0;
        if(t[i] == 1) ++t1;
    }
    
    // 2. 例外(T が S1 のみからなる).
    if((!s[0] && t0 == M) || (s[0] && t1 == M)){
        printf("%d\n", M);
        return 0;
    }
    
    // 3. 例外(S に S1 と異なる文字が存在しない).
    if((s0 == N) || (s1 == N)){
        puts("-1");
        return 0;
    }
    
    // 4. 上記以外.
    // 4-1. x番目.
    int xAns = 0, bef = -1, cur = -1;
    bool ok = false;
    rep(i, M){
        // 今回分更新.
        cur = t[i];
        
        // すでに, S1と 異なる文字が, 出現済み.
        if(ok && bef != cur) ++xAns;
        
        // S1と 異なる文字が, はじめて出現した.
        if(!ok && cur != s[0]){
            ok = true;
            xAns += x;
        }
        
        // 文字追加.
        ++xAns;
        
        // 前回分更新.
        bef = cur;
    }
    
    // 4-2. y番目.
    int yAns = 0;
    bef = -1, cur = -1;
    ok = false;
    rep(i, M){
        // 今回分更新.
        cur = t[i];
        
        // すでに, S1と 異なる文字が, 出現済み.
        if(ok && bef != cur) ++yAns;
        
        // S1と 異なる文字が, はじめて出現した.
        if(!ok && cur != s[0]){
            ok = true;
            yAns += (N - y);
        }
        
        // 文字追加.
        ++yAns;
        
        // 前回分更新.
        bef = cur;
    }
    
    // 5. 出力.
    printf("%d\n", min(xAns, yAns));
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc125/editorial/2490

// 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 s[202020], t[202020];

int main(){

// 1. 入力情報.

int N, M, s0 = 0, s1 = 0, t0 = 0, t1 = 0, x = -1, y = -1;

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

rep(i, N){

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

if(s[i] == 0) ++s0;

if(s[i] == 1) ++s1;

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

if(x == -1) x = i;

y = i;

}

rep(i, M){

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

if(t[i] == 0) ++t0;

if(t[i] == 1) ++t1;

}

// 2. 例外(T が S1 のみからなる).

if((!s[0] && t0 == M) || (s[0] && t1 == M)){

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

return 0;

}

// 3. 例外(S に S1 と異なる文字が存在しない).

if((s0 == N) || (s1 == N)){

puts("-1");

return 0;

}

// 4. 上記以外.

// 4-1. x番目.

int xAns = 0, bef = -1, cur = -1;

bool ok = false;

rep(i, M){

// 今回分更新.

cur = t[i];

// すでに, S1と異なる文字が, 出現済み.

if(ok && bef != cur) ++xAns;

// S1と異なる文字が, はじめて出現した.

if(!ok && cur != s[0]){

ok = true;

xAns += x;

}

// 文字追加.

++xAns;

// 前回分更新.

bef = cur;

}

// 4-2. y番目.

int yAns = 0;

bef = -1, cur = -1;

ok = false;

rep(i, M){

// 今回分更新.

cur = t[i];

// すでに, S1と異なる文字が, 出現済み.

if(ok && bef != cur) ++yAns;

// S1と異なる文字が, はじめて出現した.

if(!ok && cur != s[0]){

ok = true;

yAns += (N - y);

}

// 文字追加.

++yAns;

// 前回分更新.

bef = cur;

}

// 5. 出力.

printf("%d\n", min(xAns, yAns));

return 0;

}

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

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

[入力例]
1 1
0
1

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

[入力例]
5 7
0 0 1 0 0
0 1 0 1 0 1 1

[出力例]
13

[入力例]
7 15
0 0 0 1 0 0 1
0 1 0 1 0 1 1 0 1 1 0 1 1 0 0

[出力例]
25

[入力例]

3 4

0 0 1

0 1 1 0

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

-1

※AtCoderのテストケースより

[入力例]

5 7

0 0 1 0 0

0 1 0 1 0 1 1

[出力例]

[入力例]

7 15

0 0 0 1 0 0 1

0 1 0 1 0 1 1 0 1 1 0 1 1 0 0

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/arc125/editorial/2498
// 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. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. 全探索.
    int n = (int)sqrt(N) + 2;
    LL ans = 0;
    repx(q, 1, n){
        // p の 上限.
        LL u = N / q;
        
        // q が 奇数.
        if(q & 1) ans += max(0LL, (LL)(u - q + 1 + (u & 1))) / 2;
        
        // q が 偶数.
        if(!(q & 1)) ans += max(0LL, (LL)(u - q + 1 + !(u & 1))) / 2;
        
        // MOD.
        ans %= MOD;
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc125/editorial/2498

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

LL N;

scanf("%lld", &N);

// 2. 全探索.

int n = (int)sqrt(N) + 2;

LL ans = 0;

repx(q, 1, n){

// p の上限.

LL u = N / q;

// q が奇数.

if(q & 1) ans += max(0LL, (LL)(u - q + 1 + (u & 1))) / 2;

// q が偶数.

if(!(q & 1)) ans += max(0LL, (LL)(u - q + 1 + !(u & 1))) / 2;

// MOD.

ans %= MOD;

}

// 3. 出力.

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

return 0;

}

[入力例]
3

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

[入力例]
10

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

[入力例]
10000000000

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

[入力例]
2022

[出力例]
3948

[入力例]
20220504

[出力例]
85821293

[入力例]
202108222300

[出力例]
453221394

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

10000000000

[出力例]

52583544

※AtCoderのテストケースより

[入力例]

2022

[出力例]

3948

[入力例]

20220504

[出力例]

85821293

[入力例]

202108222300

[出力例]

453221394

■参照サイト
AtCoder Regular Contest 125

2022年5月3日2022年5月3日

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

C++の練習を兼ねて, AtCoder Grand Contest 014 の問題C (Closed Rooms) を解いてみた.

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

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

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

// 解き直し.
// https://img.atcoder.jp/agc014/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vs = vector<string>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
constexpr int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int MAX = 808 * 808;

int main(){
    
    // 1. 入力情報.
    int H, W, K, sh = -1, sw = -1;
    scanf("%d %d %d", &H, &W, &K);
    vs G;
    rep(i, H){
        char c[808];
        scanf("%s", c);
        string s(c);
        rep(j, W){
            if(s[j] == 'S'){
                sh = i;
                sw = j;
                s[j] = '.';
            }
        }
        G.pb(s);
    }
    
    // 2. bfs.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d) -> void {
        // 空のキュー.
        queue<int> q;
        
        // 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // キューから取り出す.
            int v = q.front();
            q.pop();
            
            // 取り出した要素を処理.
            // x: 列方向, y: 行方向 で考える.
            int nx, ny, n;
            int cx = v % W , cy = v / W;
            rep(i, 4){
                nx = cx + dx[i];
                ny = cy + dy[i];
                n = nx + ny * W;
                
                // 訪問不可能なマス であれば, 処理をスキップ.
                if(s == n || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;
                
                // 訪問先のマスで, 訪問可能 かつ 未訪問 であれば, 最短距離 を 設定.
                if(G[ny][nx] == '.' && !d[n]) d[n] = d[v] + 1, q.push(n);
            }
        }
    };
    
    // 3. 今いる部屋から, 各部屋までの距離を計算.
    int d[MAX], s = sw + sh * W;
    rep(i, MAX) d[i] = 0;
    bfs(G, s, d);
    
    // 4. 最小回数は？
    int magic = 2020202020;
    rep(i, H * W){
        // 閉じられている部屋は, Skip.
        if(d[i] > K) continue;
        
        // 今いる部屋以外で, 距離 0 の 部屋を Skip.
        if(!d[i] && (i != s)) continue;
        
        // 到達先.
        int t = 2020202020, cx = i % W , cy = i / W;
        
        // 1行目, 1列目, H行目, W列目.
        t = min({t, cy, cx, H - 1 - cy, W - 1 - cx});
        
        // 最小値更新.
        magic = min(magic, 1 + (t + K - 1) / K);
    }
    
    // 5. 出力.
    printf("%d\n", magic);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

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

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

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

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

#define pb push_back

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

int MAX = 808 * 808;

int main(){

// 1. 入力情報.

int H, W, K, sh = -1, sw = -1;

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

vs G;

rep(i, H){

char c[808];

scanf("%s", c);

string s(c);

rep(j, W){

if(s[j] == 'S'){

sh = i;

sw = j;

s[j] = '.';

}

G.pb(s);

}

// 2. bfs.

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

auto bfs = [&](vs &G, int s, int* d) -> void {

// 空のキュー.

queue<int> q;

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

q.push(s);

while(!q.empty()){

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

int v = q.front();

q.pop();

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

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

int nx, ny, n;

int cx = v % W , cy = v / W;

rep(i, 4){

nx = cx + dx[i];

ny = cy + dy[i];

n = nx + ny * W;

// 訪問不可能なマスであれば, 処理をスキップ.

if(s == n || nx < 0 || nx >= W || ny < 0 || ny >= H) continue;

// 訪問先のマスで, 訪問可能かつ未訪問であれば, 最短距離を設定.

if(G[ny][nx] == '.' && !d[n]) d[n] = d[v] + 1, q.push(n);

}

};

// 3. 今いる部屋から, 各部屋までの距離を計算.

int d[MAX], s = sw + sh * W;

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

bfs(G, s, d);

// 4. 最小回数は？

int magic = 2020202020;

rep(i, H * W){

// 閉じられている部屋は, Skip.

if(d[i] > K) continue;

// 今いる部屋以外で, 距離 0 の部屋を Skip.

if(!d[i] && (i != s)) continue;

// 到達先.

int t = 2020202020, cx = i % W , cy = i / W;

// 1行目, 1列目, H行目, W列目.

t = min({t, cy, cx, H - 1 - cy, W - 1 - cx});

// 最小値更新.

magic = min(magic, 1 + (t + K - 1) / K);

}

// 5. 出力.

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

return 0;

}

[入力例]
3 3 3
#.#
#S.
###

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

[入力例]
3 3 3
###
#S#
###

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

[入力例]
7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

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

[入力例]
20 22 5
######################
######################
######################
######################
###########.##########
##########.#.#########
#########.###.########
########.#####.#######
#######.#.....#.######
######.##.#.#.##.#####
#####.###..S..###.####
######.##.#.#.##.#####
#######.#.....#.######
########.#####.#######
#########.###.########
##########.#.#########
###########.##########
######################
######################
######################

[出力例]
3

[入力例]
55 50 5
.#..####.#.#.####.#.#..######..##...#...#..###..#.
..###.#...#.###.##..###..##.##..##.#.#.####...###.
.#######..#.#.####.###...##..###..#.........#....#
###.......#...#.##.#..#.##.#..#.#.#.#.##.##.#.####
###.##.#####.#.##.##.##.###.######.#....####.....#
#####.....####.......#.##.#..#..##.##.#...#.#.##.#
###.#.#..##..#....#..##...##..###..##.##.#.....#.#
..##.##.#..#.###..#......####.##....#..#.##..#...#
...#..####.#######.#..###..#.###.#..#.##.#...#..#.
#.###.##...#.###.#..####.#.##.....##...#.#.#..#..#
#.##.#########.###..#.##...#..#..#..#.##.####..#..
.##..#.#.....#######.###.#########..#.#.....#.##.#
.....##.#....##.###..........#.#..##..###.##.#.##.
#######..##.#..#...#..#...##.##.##.#.####.#.#.#...
...#####.#.#...#..##...#.##..##.#...##.#...#.....#
.#.#.##...#..##...#..##.##.##..#.###...#....#....#
....#.#.##...##...#.###.##..#..##.#..#..##.##....#
..##.###.#...##.#.#....#.##.####.#####.####..#####
#..#..##.###..#...##.#.#......#.#....##.#.###.##..
#..##..#.###.....####.##..#..#.#.##.#.##.###.###..
##...#....#.###..#.#..#.......###.#.#..##....#..#.
.####.##...####..####....#....#.#.#...##.##.#.#..#
..##...##.#..###..######..##.##.##.#...##....###..
.#.#..#.#.###.##.###..#.#.##.##..##..#..#.###..#.#
.#.#.#.######.#.#...#.....##.....##.##...#.#.##..#
....#.#..####..###.####...##.#.#..#.#.####..#.###.
##..##...#.......###...#.##.#......#.#.##...##.#..
##...#.#.#.#..##.......#.#.#.#.#.#...#.##.#.......
...####.##.#.#...#.#####S.########.#......###.####
....####...#.....#.....#....#.#.#.#..#.#..####..##
#.........#.#.##.#.##..#.##.##......#.#.#....#..##
#..#..####...###.###.#......#...##.#.....####.#...
##.#.##..#..####...#..####.##..####...##..###....#
..######.##.#####...##..###..#.#........##.#.###.#
....###.#.#..#####..#.####.##.#.##..#.###..##.####
.....#..#.##.#.###..#..###.###.#.#...#.#####.#....
..#.#..###...##.##.#.#..##......###..###.#.#...#..
#####..##.##..#..#.#......####.##..##..#####.#.#..
...#.#.###..#.##.#...###...#.#...##...#..#.####...
##.###.#.#.#.....###.#.#.##.##..##..#.#.#.#.#..#.#
##.##.....#....#...#.#...#..##...##..#..##..#...#.
...###...#.###...#.#####..####....#..#.#...#..#.##
##.##...####..#.#####..#.##.#.....#.####.#...#....
#..#.####.#.#.##...#.##....#######..###..####..##.
##.#.###.###..##....####..#...#..#.#.###.###....##
.##...#.###.###..##.##...####..##.....#....#.####.
#.#...####.#...##.#.###...#...##..#.###.##...#..#.
....#.###.#.#..#..##.####.#..##.#..##....#.#...#..
..##..#.##..#..#.########.#.#.#.####..#.##...#.##.
.##...#...#.#....####.##..##..#...###.#####..##..#
##..###.####..#####.#.#.#...##..##..#....##.....#.
....#..##.##..#..#..####..####..##...###.##.#####.
#....##....###..#.####.##....#..#.....#####..##.#.
#.#..####....##..#..#.#.#.###.###.#.###.###..##.##
#.#.#.#.##.#####..#######..#.#...#.#...###.#..#.##

[出力例]
6

[入力例]
110 100 5
......#.#...###...####..#.#..###..#.##.#.#.##.##.##..##...#..#.###.#.##.#..#.###.###..##.....#...#..
#...##.#.#...####..#.#..#.##.##.###...#....##....##....####.#.###....#.##.##.#.##.##.#...#.#####..##
..#..##.#.##...#..#.#..###.###..#.#.####....#..#.###.###.#.#..#.#...##.#...#...##.#.###..#.#.#....##
#...#.###.###.#.####.#..##.#..#...##.####.#.#.###.....#.####..##.....#####.###..#.#.#.......#...###.
...##.####.#.#.#.#########.#......##.###..#..###..#..#....###.##....#.############.###..##..#......#
#.##..##...######.##..#...####..##.####..#.#.###.#.###.#####..#..#..####..##...#..######..#.##...#..
#.#.....###..##.####.#.#...#.#.#......####.....##......#..#...##..##..#######..###....#...##.#.###..
#.#.####..#...#.##...####.#.#....#.#.....#..##..###...#.#######..####..##.#....##.#.######....#...#.
##.##...##..#.####...#....#..#..#....#.####.#####.#...##.#...##..##.....#.#.#..#.#..#.#.#.#.##...#..
#.##.#......#.####...#.##.#.#..#...###.#...#.#.##.#.#...##..#.#.#.#.#####..###.####.#...##.#.....#..
..##.#....##.#.###.###..###.##.####.#.#....#..##.##.#.#######...###########.####.#...#.####.....###.
#.#.#####.#.##.###..#.####.#...#..###.#..#.#..#.##.##....#...###.#...#...###.##.#.#.#.###...#.#..#.#
.###....##..#...###.#...#.######....#.#.....##.###.####.#.##...###.#.##.##.###.#####..#.......#.###.
..###..#.#.#.##......##....##.##......#.#.#..#...##.....##.#.#..##.##..#############.#.###....#####.
#.#.####.###.##.....##.####.#.##....#.#..#.#.##.###...##.###.....###....##.##....###.##.#.#...##.#..
...##.#.#.........##..#.###.#.#....#...#..#.....#..#.#.....##....##.##..#..#...##.#.###...###.######
###.#...#..#.#....##.#.##.##.####.###.#....##.#..#..####...##..##..###...#.###....##.......##.#.##..
..##.########.#.##..##.####..#.#.##..###..###.###..#...##..#...##..#####.....##..#......#.#....###..
###..##.##.###..#####...###...#..#..#....#.#..##.###.##..##.##.##....#..........##..#######..#......
##..##.....#.....#..#####.##.#.###...#...#...######.......##...##....##.#..#.#########..##.###.###..
.###.##.##..#.#.#..#..#..####...#....#...##..##..#...#..#....##..#.#.....#....#.##.#.###...##.#....#
#..#.#.#.##.......##.#.#.........##..#.............###.###.#.#.####..##.##.####.##.##.##....#.#.##..
#.#...#.....###.#...#.#.##...##.###.#.#####.#..########.......#..#......##...##.###.#..#.##.....#...
.#......##..#..#...#...#..###.#.#...###....####..###.#.......#.#.#.....##.#....#######.....#.....#..
#.##..####..#.#.#.#....#.##..##########.##..#.#.#.##.##.#.#.#.#####.##..#####.##....#..###..####.#.#
#....###...#.#.##.#.####.##.#..#.#.#.####......###.....#.#.#....#.#.##.....####.####.........##.#..#
#.#..#.#....##..#.#.###...#.#.....###.#.#.####.##########....##..#....#...###.###.####.####.#.##..#.
.#..#.###...##.#....####.#.##.#.###..##.....##..#...##...##.####..##...#####.#####...##..#.#.#...###
##.#...##....#..#..#..##.#....#.##...#.#.#..##.#..#.###.....##.#.####..##.#.#.#####.....#####.####..
...#.#.#.#####..#..##...##.#.#...#.##.#..#.#..####.#.....###.#.##..###.#...#...#.....#####.#..##.#..
##......#.#.#.#..#..######...#####.##..#..#..#.#.#.###......#.####..##....#.#..###......##.##.#..#.#
####.##.#######..#.#....#.#...###.###.#.#....#..#.###...###..#.#..##.##.#.##....###...#...##.#.#...#
..######.#.#...#..##.##.####...#####...####..#####..#.#...#.#...#.###.#.#.####...#..##.#.##.#..#....
#####..#.####.#..#...##.#....##....####.#...#...##.#.#####.####..#.####..##..###..##...###..#.##.#..
#..###.........##.#.#...#..##.##..##...#.##....##...#......#.#..#..#.#.#.##...##.##..#####...###...#
##.##.##...####...#.#####....#.####..#.###...#.###.#.##..##..####.##...#..#.#####..##.#..####...#...
..###.....##.#.#####.###..##.#..##..##.#.###.##.#.#..#..#.#.###..##.###.##.##...######.##.#...##.#..
...#.#....#.#.#.....####.##..###..####.#.#..#.#..#.##.#.#.#..#...#.#.#.#.##..##......####.######.#..
#.#...#..#######....##.#.#######.#.##.##.....#...#.####..#.##..#..##.#.#.#...#..#.####..#.#.#####..#
##.#.....##...#...#.###...###.####.######.###.##..###..#...##..###...#..###..#..###..###..#..#...#.#
.#.##..####.#.#....##.#..#..##...##......####.#####.##...#########..#..##...##.#..##...#...#.#####..
.#.#####.#...#...#..##.#.......####.###.##.#.#....##...###..#...#.#.#.#.#...##.#....#..#.....##..#..
...##..#####.#..........#..##.#.##.#..###.####.#.##..###.###...#####.##.#....#####.#.##..#.##.#....#
#....##.##..#....##..#.#.##.#.#.#..#..###.####.#.###.#.##.####..##..#..#..#..#..#.##...####..#.##.#.
#..#..#..#..####.#.#.#.#.##..##...#..#........#...#.#..#.##.......#.##...##..#.#.##....#....#..###.#
.#.#.##...###...##....###....##..#.#..#.##.##..####..#.##.#.....#..#####......#...##....#..##.#...##
#...#..##......##......#....##..#.#....#..##..#.##..#.##.###.###.##..#..#....##...#.#....##.##..##.#
##...#..##..#..#.#.##.###.##.#..###.##.#####.##.####..#..##.#..#.#.#....#.####.....##.##.######.#.#.
####..#..#.##..#.###.##.###.##.##..#.#.#..#..#####.#..#.#...##..#...#.##.##....##....#.#..#..####.#.
##...#.###..#..###.###...#.#..##.#....###.##..#.#.#S#.#...###.#.###.###.##.#.#.....#.......#....#..#
..##.#.###..###...###.#....#...#...#.##.#.....##.#..##..#.####..##.##..##...#.##.#.#...#....#.#.....
####.###..##.##....##.##...##..###..###..#.#..##..####..#.#.....###.#.##...##..#.########..#.####..#
..#..######.##.###.####..#.#.##.#...##.....#..........##.##.#.....#.###.###..#.....##.#..#...####...
#.#.....####..##..#..#..#...###.##..#...#...########.#.###.#.....#####...#...#..##......###.##..#...
###.#.....##..#..##.....##.##.#######...#.....##....##.##....#.##..##.##.#..##.##.###.#.#.#...#.####
..#.#####.#...#.#.###....#.###..##..##.####.....##.####.##.#..###################.#.#.####.....###.#
#..####.##.#..##...#..###..#####.#..#...#.#.#...#...####.#.#.##.##.#...#...##..###.#..#...#.#.#.####
#####.##.#..###..#...#..#.#...#.###.##..#.#.#......#..#.#.#.#...##.###.##.####...###.##.####...#...#
#....#.##.#..#..###.#.######...##.###..####.##.#.#.##.#.##.##.###.##...###...##..#.#.#.#....##..#..#
.##.....#######...#....#...#####...#.#####.##..#...#..#....##..#####..##.##.#...#..##.###.#####...#.
#.#.##..#.#.#.####.###.#.##...#.####.....##..###..#.#..##..#..##.#..#.#######.###.#...##..#####..#..
..#.....###...#..#.#...#..##...##.#.......#...#...#..#.#.#....#..#....##.#..##.##..#.##..##..####.##
###.##.#.##..##..#..###.##.#.####..#..#.##....#.###.#.#...#..#..#..##...##.##..#.##...####...####..#
..##......#.##.###.#...#.########.....#####.###.###.#.#..#.##.#..##..####.#..#...#..#.#..#.###.##...
...####.......###.###.....##...#.#.####.....#########.#..#..#.####..###......#....#.##.....###..###.
.#...#.#..##.###.#.###...###..#.###..####.##.##...#.#.#.....#.#.#..#####....########.#.#.##.#....#..
###.......##.##.#..####.###.##.#####.#.#.....#..####..##..##.######.#...#..#.#.....#....#...#..##..#
.#..#....###.#....###..##...###...###..#.#..#.#.#####.#...#.##..#.#...##.###.####..#.#..#.#..#.#.###
....###....#..#.##...#####........##..##.#...####..##......#.#......#.#.##.###..####.#...##..#...#..
#######...#.........###.####.#.#...###.#.#.###.###.##..#.#....##.###..##...##.##..###..####.#.##.##.
.####.#.##.#..#...#.##.#..#.#.##.#...##...###.#.##...#....#####.#.##..#.#.####...#..#.#####.#.####.#
..###.#...#..#######.####.###.#..###.#.#.#####...##.###.#..#..#.....#.###.##.##...##..#.#.##.#.#...#
#....#..###.##...##.#.#.###.#..##..#.##.#...##.......#.#..#.#...##.#...#..#.#....#...#...#......##..
.#.....####.#.####..#..#####.####..######.#..#...##..#######.#########.#.##....#.#.....##.####.#..##
#....##..###.##..##...##....######..###..#.#.#.#...#.##..###.#..#.######.#####.#.####..#.##..#.##..#
....#..#..###.#.#..##.####.#####.####.######..#####.##.#.#.#...#..##..##.##.#.##.....#.#.#.##.##..#.
#.#.##..###.####......#....#.#.#..#.....###.#..##........##.##.########.#.##.###.#..#.##.#.#..#.####
#..###..#.....##...##....###..#.##.#.#..#....###.##..######.....#.#.##.##.#..##...#...#.....###.####
#...#.#..#.#.......#........###.####...#.#.#...#...######...#.####.#...##..###....##.###...###.#...#
#....#..###.#.###.##.#..####..#..#######..#.##..##.#.#####.#..##.#.##..##...#.######..###.#..#...##.
.#.#..###..#..##..###.....##..#.#.#.#..#.#.####.#..####....#...#..######.###.##..##.#.##.###.##..##.
..##.##..##..#....##..##.........#######.#.#.#..##.#.#....####.#.#.##.#.####.#..###.####..####.#..#.
..#.#..####.#..##..........#..###..####..#.######.#.#.#.####.#####..######.##.#.####....###.##..#..#
##.....#..##.##.###..#.###########.#.#.#..#.####.##....##..##.##...#..#####...#...#######....#....#.
...#.##.....##.#..##...#.....#.#..####....#.#.#...#.###.#.##..###...#...#.##.#..####..###.###...#.##
###.#..#.##...#.##.##...##...##.###.#.#######.#....#.#.#.#.....#..#..#..##..##..#.#..#.#.##.#...##..
.##.#.#.#.#.#.##.##.#.###.....#.#..#.###.#.####...#.##...#..###.#.###..###.....#...#..#.######.#..#.
.#...#.#..###.##.#.#..####.#..##.###.##...#.##.##..#...###..#.....#...#.##.#....#..#.####..#.#.##..#
#.##.....###.#...##.....#..#.#..#.##.....####.#.##.##...###...#.##.#.#.##.###..#####.###.##...#####.
........###..####....##.##.#.......#..###.##....#..###.#.##.##.#####.#.##.#....###.....##.#.##...###
##..##..##.##.#.#.#.#########.#.##..#.#.##..##..############..#..#.#.##..##.###.#.#####...#####...#.
.#..##.#...###..##...###.#####.##..#######.####.#..#.##.###.##.....##.###.....##.####...##.#.#.#.#.#
...#...####.#......##.####..##.#.#.###.#.#.##...#..##.#.##.##....##..#..##.#....#######.#.###..#.#..
..###.##.###..#.####.##.##....##.##.##.#.##.#####...###...##...##.#.#..#.##..........#..##.#..#....#
###.#..#...####.###.#.######......#...#....##.#.##..#.#..######.##.###.#.#.#....##.##.##...#.....###
.#.##..#..###.....#.###...#.#...#.#.#.#..........##.##....##.###.##.###.###..#...#..####..####..##.#
###..####.#..#..#......#.##..#...#...#.....###.#..##..#....##..###.#..##.......#.###.#.....#.#####.#
.#.#..#..#....#...#..#####...##.#.#....#....##..####..###..###...#.#..#...######.#..#.##..#..#...###
.#.##.#......#..####....#..#.#.#.#..#.#...#.....###.##.##..##..#...##........##.##..#.#####.##.##.#.
..#.#.##.##.####.#.###..#######..####.#..####....#.##.#.....#.#..######....##.#..#.##.#.####.######.
####.##....#...####..#######..##.#.#..##.##.###..#.#.##..###.##.#......#.....#....#.#..###.....##...
...#..#..#......##.#.##.#.#######...####.#..#.#.#.#.##..#####.....##....#.#..#..#..#.##.#.#.####..#.
.###.##..##..###..#..#.#####.##...########..#.#.#...#######.#..#.###.#.#.#...#.#.#.###.#.#######....
..###...##..#.#.##..#..#..#####..#..#...##..#.#....#...#..#..#..#..##.#.#.#.#.##....#.#...#.#####.##
.#....#....#.##.###..#..##...#....##..#.####.##.#..##.##..#.##.....##..#...#.#......#..###..##..##..
##..##..#...#.###.#.#.##.####.#...##..#..##.###.##..#.#...##....#.######.#..#.....#..#..#....#######
.####.###.#######.#.#####..###.#####.##...##.###...#..#.#......##.....#####.#..#..#.#####.#..###.###
.##.#..#.#####..#.#.####...#.#..#....#..#...##...###..#........######...#..####.#..#.#.#.#...####.#.
....#.#.##...#.#..###...#....###.###.#.#..#.#....#.#.####.....####..#.#####.....#...#.##.####.##....
#.#..#####.....#.###..#.#######.###......##.##.#...##.##..##....#....#...####..###.#.#.####...#.#.##

[出力例]
11

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

[入力例]

3 3 3

#.#

#S.

###

[出力例]

※AtCoderテストケースより

[入力例]

3 3 3

###

#S#

###

[出力例]

※AtCoderテストケースより

[入力例]

7 7 2

#######

##...##

###S###

##.#.##

###.###

#######

[出力例]

※AtCoderテストケースより

[入力例]

20 22 5

######################

###########.##########

##########.#.#########

#########.###.########

########.#####.#######

#######.#.....#.######

######.##.#.#.##.#####

#####.###..S..###.####

######.##.#.#.##.#####

#######.#.....#.######

########.#####.#######

#########.###.########

##########.#.#########

###########.##########

######################

[出力例]

[入力例]

55 50 5

.#..####.#.#.####.#.#..######..##...#...#..###..#.

..###.#...#.###.##..###..##.##..##.#.#.####...###.

.#######..#.#.####.###...##..###..#.........#....#

###.......#...#.##.#..#.##.#..#.#.#.#.##.##.#.####

###.##.#####.#.##.##.##.###.######.#....####.....#

#####.....####.......#.##.#..#..##.##.#...#.#.##.#

###.#.#..##..#....#..##...##..###..##.##.#.....#.#

..##.##.#..#.###..#......####.##....#..#.##..#...#

...#..####.#######.#..###..#.###.#..#.##.#...#..#.

#.###.##...#.###.#..####.#.##.....##...#.#.#..#..#

#.##.#########.###..#.##...#..#..#..#.##.####..#..

.##..#.#.....#######.###.#########..#.#.....#.##.#

.....##.#....##.###..........#.#..##..###.##.#.##.

#######..##.#..#...#..#...##.##.##.#.####.#.#.#...

...#####.#.#...#..##...#.##..##.#...##.#...#.....#

.#.#.##...#..##...#..##.##.##..#.###...#....#....#

....#.#.##...##...#.###.##..#..##.#..#..##.##....#

..##.###.#...##.#.#....#.##.####.#####.####..#####

#..#..##.###..#...##.#.#......#.#....##.#.###.##..

#..##..#.###.....####.##..#..#.#.##.#.##.###.###..

##...#....#.###..#.#..#.......###.#.#..##....#..#.

.####.##...####..####....#....#.#.#...##.##.#.#..#

..##...##.#..###..######..##.##.##.#...##....###..

.#.#..#.#.###.##.###..#.#.##.##..##..#..#.###..#.#

.#.#.#.######.#.#...#.....##.....##.##...#.#.##..#

....#.#..####..###.####...##.#.#..#.#.####..#.###.

##..##...#.......###...#.##.#......#.#.##...##.#..

##...#.#.#.#..##.......#.#.#.#.#.#...#.##.#.......

...####.##.#.#...#.#####S.########.#......###.####

....####...#.....#.....#....#.#.#.#..#.#..####..##

#.........#.#.##.#.##..#.##.##......#.#.#....#..##

#..#..####...###.###.#......#...##.#.....####.#...

##.#.##..#..####...#..####.##..####...##..###....#

..######.##.#####...##..###..#.#........##.#.###.#

....###.#.#..#####..#.####.##.#.##..#.###..##.####

.....#..#.##.#.###..#..###.###.#.#...#.#####.#....

..#.#..###...##.##.#.#..##......###..###.#.#...#..

#####..##.##..#..#.#......####.##..##..#####.#.#..

...#.#.###..#.##.#...###...#.#...##...#..#.####...

##.###.#.#.#.....###.#.#.##.##..##..#.#.#.#.#..#.#

##.##.....#....#...#.#...#..##...##..#..##..#...#.

...###...#.###...#.#####..####....#..#.#...#..#.##

##.##...####..#.#####..#.##.#.....#.####.#...#....

#..#.####.#.#.##...#.##....#######..###..####..##.

##.#.###.###..##....####..#...#..#.#.###.###....##

.##...#.###.###..##.##...####..##.....#....#.####.

#.#...####.#...##.#.###...#...##..#.###.##...#..#.

....#.###.#.#..#..##.####.#..##.#..##....#.#...#..

..##..#.##..#..#.########.#.#.#.####..#.##...#.##.

.##...#...#.#....####.##..##..#...###.#####..##..#

##..###.####..#####.#.#.#...##..##..#....##.....#.

....#..##.##..#..#..####..####..##...###.##.#####.

#....##....###..#.####.##....#..#.....#####..##.#.

#.#..####....##..#..#.#.#.###.###.#.###.###..##.##

#.#.#.#.##.#####..#######..#.#...#.#...###.#..#.##

[出力例]

[入力例]

110 100 5

......#.#...###...####..#.#..###..#.##.#.#.##.##.##..##...#..#.###.#.##.#..#.###.###..##.....#...#..

#...##.#.#...####..#.#..#.##.##.###...#....##....##....####.#.###....#.##.##.#.##.##.#...#.#####..##

..#..##.#.##...#..#.#..###.###..#.#.####....#..#.###.###.#.#..#.#...##.#...#...##.#.###..#.#.#....##

#...#.###.###.#.####.#..##.#..#...##.####.#.#.###.....#.####..##.....#####.###..#.#.#.......#...###.

...##.####.#.#.#.#########.#......##.###..#..###..#..#....###.##....#.############.###..##..#......#

#.##..##...######.##..#...####..##.####..#.#.###.#.###.#####..#..#..####..##...#..######..#.##...#..

#.#.....###..##.####.#.#...#.#.#......####.....##......#..#...##..##..#######..###....#...##.#.###..

#.#.####..#...#.##...####.#.#....#.#.....#..##..###...#.#######..####..##.#....##.#.######....#...#.

##.##...##..#.####...#....#..#..#....#.####.#####.#...##.#...##..##.....#.#.#..#.#..#.#.#.#.##...#..

#.##.#......#.####...#.##.#.#..#...###.#...#.#.##.#.#...##..#.#.#.#.#####..###.####.#...##.#.....#..

..##.#....##.#.###.###..###.##.####.#.#....#..##.##.#.#######...###########.####.#...#.####.....###.

#.#.#####.#.##.###..#.####.#...#..###.#..#.#..#.##.##....#...###.#...#...###.##.#.#.#.###...#.#..#.#

.###....##..#...###.#...#.######....#.#.....##.###.####.#.##...###.#.##.##.###.#####..#.......#.###.

..###..#.#.#.##......##....##.##......#.#.#..#...##.....##.#.#..##.##..#############.#.###....#####.

#.#.####.###.##.....##.####.#.##....#.#..#.#.##.###...##.###.....###....##.##....###.##.#.#...##.#..

...##.#.#.........##..#.###.#.#....#...#..#.....#..#.#.....##....##.##..#..#...##.#.###...###.######

###.#...#..#.#....##.#.##.##.####.###.#....##.#..#..####...##..##..###...#.###....##.......##.#.##..

..##.########.#.##..##.####..#.#.##..###..###.###..#...##..#...##..#####.....##..#......#.#....###..

###..##.##.###..#####...###...#..#..#....#.#..##.###.##..##.##.##....#..........##..#######..#......

##..##.....#.....#..#####.##.#.###...#...#...######.......##...##....##.#..#.#########..##.###.###..

.###.##.##..#.#.#..#..#..####...#....#...##..##..#...#..#....##..#.#.....#....#.##.#.###...##.#....#

#..#.#.#.##.......##.#.#.........##..#.............###.###.#.#.####..##.##.####.##.##.##....#.#.##..

#.#...#.....###.#...#.#.##...##.###.#.#####.#..########.......#..#......##...##.###.#..#.##.....#...

.#......##..#..#...#...#..###.#.#...###....####..###.#.......#.#.#.....##.#....#######.....#.....#..

#.##..####..#.#.#.#....#.##..##########.##..#.#.#.##.##.#.#.#.#####.##..#####.##....#..###..####.#.#

#....###...#.#.##.#.####.##.#..#.#.#.####......###.....#.#.#....#.#.##.....####.####.........##.#..#

#.#..#.#....##..#.#.###...#.#.....###.#.#.####.##########....##..#....#...###.###.####.####.#.##..#.

.#..#.###...##.#....####.#.##.#.###..##.....##..#...##...##.####..##...#####.#####...##..#.#.#...###

##.#...##....#..#..#..##.#....#.##...#.#.#..##.#..#.###.....##.#.####..##.#.#.#####.....#####.####..

...#.#.#.#####..#..##...##.#.#...#.##.#..#.#..####.#.....###.#.##..###.#...#...#.....#####.#..##.#..

##......#.#.#.#..#..######...#####.##..#..#..#.#.#.###......#.####..##....#.#..###......##.##.#..#.#

####.##.#######..#.#....#.#...###.###.#.#....#..#.###...###..#.#..##.##.#.##....###...#...##.#.#...#

..######.#.#...#..##.##.####...#####...####..#####..#.#...#.#...#.###.#.#.####...#..##.#.##.#..#....

#####..#.####.#..#...##.#....##....####.#...#...##.#.#####.####..#.####..##..###..##...###..#.##.#..

#..###.........##.#.#...#..##.##..##...#.##....##...#......#.#..#..#.#.#.##...##.##..#####...###...#

##.##.##...####...#.#####....#.####..#.###...#.###.#.##..##..####.##...#..#.#####..##.#..####...#...

..###.....##.#.#####.###..##.#..##..##.#.###.##.#.#..#..#.#.###..##.###.##.##...######.##.#...##.#..

...#.#....#.#.#.....####.##..###..####.#.#..#.#..#.##.#.#.#..#...#.#.#.#.##..##......####.######.#..

#.#...#..#######....##.#.#######.#.##.##.....#...#.####..#.##..#..##.#.#.#...#..#.####..#.#.#####..#

##.#.....##...#...#.###...###.####.######.###.##..###..#...##..###...#..###..#..###..###..#..#...#.#

.#.##..####.#.#....##.#..#..##...##......####.#####.##...#########..#..##...##.#..##...#...#.#####..

.#.#####.#...#...#..##.#.......####.###.##.#.#....##...###..#...#.#.#.#.#...##.#....#..#.....##..#..

...##..#####.#..........#..##.#.##.#..###.####.#.##..###.###...#####.##.#....#####.#.##..#.##.#....#

#....##.##..#....##..#.#.##.#.#.#..#..###.####.#.###.#.##.####..##..#..#..#..#..#.##...####..#.##.#.

#..#..#..#..####.#.#.#.#.##..##...#..#........#...#.#..#.##.......#.##...##..#.#.##....#....#..###.#

.#.#.##...###...##....###....##..#.#..#.##.##..####..#.##.#.....#..#####......#...##....#..##.#...##

#...#..##......##......#....##..#.#....#..##..#.##..#.##.###.###.##..#..#....##...#.#....##.##..##.#

##...#..##..#..#.#.##.###.##.#..###.##.#####.##.####..#..##.#..#.#.#....#.####.....##.##.######.#.#.

####..#..#.##..#.###.##.###.##.##..#.#.#..#..#####.#..#.#...##..#...#.##.##....##....#.#..#..####.#.

##...#.###..#..###.###...#.#..##.#....###.##..#.#.#S#.#...###.#.###.###.##.#.#.....#.......#....#..#

..##.#.###..###...###.#....#...#...#.##.#.....##.#..##..#.####..##.##..##...#.##.#.#...#....#.#.....

####.###..##.##....##.##...##..###..###..#.#..##..####..#.#.....###.#.##...##..#.########..#.####..#

..#..######.##.###.####..#.#.##.#...##.....#..........##.##.#.....#.###.###..#.....##.#..#...####...

#.#.....####..##..#..#..#...###.##..#...#...########.#.###.#.....#####...#...#..##......###.##..#...

###.#.....##..#..##.....##.##.#######...#.....##....##.##....#.##..##.##.#..##.##.###.#.#.#...#.####

..#.#####.#...#.#.###....#.###..##..##.####.....##.####.##.#..###################.#.#.####.....###.#

#..####.##.#..##...#..###..#####.#..#...#.#.#...#...####.#.#.##.##.#...#...##..###.#..#...#.#.#.####

#####.##.#..###..#...#..#.#...#.###.##..#.#.#......#..#.#.#.#...##.###.##.####...###.##.####...#...#

#....#.##.#..#..###.#.######...##.###..####.##.#.#.##.#.##.##.###.##...###...##..#.#.#.#....##..#..#

.##.....#######...#....#...#####...#.#####.##..#...#..#....##..#####..##.##.#...#..##.###.#####...#.

#.#.##..#.#.#.####.###.#.##...#.####.....##..###..#.#..##..#..##.#..#.#######.###.#...##..#####..#..

..#.....###...#..#.#...#..##...##.#.......#...#...#..#.#.#....#..#....##.#..##.##..#.##..##..####.##

###.##.#.##..##..#..###.##.#.####..#..#.##....#.###.#.#...#..#..#..##...##.##..#.##...####...####..#

..##......#.##.###.#...#.########.....#####.###.###.#.#..#.##.#..##..####.#..#...#..#.#..#.###.##...

...####.......###.###.....##...#.#.####.....#########.#..#..#.####..###......#....#.##.....###..###.

.#...#.#..##.###.#.###...###..#.###..####.##.##...#.#.#.....#.#.#..#####....########.#.#.##.#....#..

###.......##.##.#..####.###.##.#####.#.#.....#..####..##..##.######.#...#..#.#.....#....#...#..##..#

.#..#....###.#....###..##...###...###..#.#..#.#.#####.#...#.##..#.#...##.###.####..#.#..#.#..#.#.###

....###....#..#.##...#####........##..##.#...####..##......#.#......#.#.##.###..####.#...##..#...#..

#######...#.........###.####.#.#...###.#.#.###.###.##..#.#....##.###..##...##.##..###..####.#.##.##.

.####.#.##.#..#...#.##.#..#.#.##.#...##...###.#.##...#....#####.#.##..#.#.####...#..#.#####.#.####.#

..###.#...#..#######.####.###.#..###.#.#.#####...##.###.#..#..#.....#.###.##.##...##..#.#.##.#.#...#

#....#..###.##...##.#.#.###.#..##..#.##.#...##.......#.#..#.#...##.#...#..#.#....#...#...#......##..

.#.....####.#.####..#..#####.####..######.#..#...##..#######.#########.#.##....#.#.....##.####.#..##

#....##..###.##..##...##....######..###..#.#.#.#...#.##..###.#..#.######.#####.#.####..#.##..#.##..#

....#..#..###.#.#..##.####.#####.####.######..#####.##.#.#.#...#..##..##.##.#.##.....#.#.#.##.##..#.

#.#.##..###.####......#....#.#.#..#.....###.#..##........##.##.########.#.##.###.#..#.##.#.#..#.####

#..###..#.....##...##....###..#.##.#.#..#....###.##..######.....#.#.##.##.#..##...#...#.....###.####

#...#.#..#.#.......#........###.####...#.#.#...#...######...#.####.#...##..###....##.###...###.#...#

#....#..###.#.###.##.#..####..#..#######..#.##..##.#.#####.#..##.#.##..##...#.######..###.#..#...##.

.#.#..###..#..##..###.....##..#.#.#.#..#.#.####.#..####....#...#..######.###.##..##.#.##.###.##..##.

..##.##..##..#....##..##.........#######.#.#.#..##.#.#....####.#.#.##.#.####.#..###.####..####.#..#.

..#.#..####.#..##..........#..###..####..#.######.#.#.#.####.#####..######.##.#.####....###.##..#..#

##.....#..##.##.###..#.###########.#.#.#..#.####.##....##..##.##...#..#####...#...#######....#....#.

...#.##.....##.#..##...#.....#.#..####....#.#.#...#.###.#.##..###...#...#.##.#..####..###.###...#.##

###.#..#.##...#.##.##...##...##.###.#.#######.#....#.#.#.#.....#..#..#..##..##..#.#..#.#.##.#...##..

.##.#.#.#.#.#.##.##.#.###.....#.#..#.###.#.####...#.##...#..###.#.###..###.....#...#..#.######.#..#.

.#...#.#..###.##.#.#..####.#..##.###.##...#.##.##..#...###..#.....#...#.##.#....#..#.####..#.#.##..#

#.##.....###.#...##.....#..#.#..#.##.....####.#.##.##...###...#.##.#.#.##.###..#####.###.##...#####.

........###..####....##.##.#.......#..###.##....#..###.#.##.##.#####.#.##.#....###.....##.#.##...###

##..##..##.##.#.#.#.#########.#.##..#.#.##..##..############..#..#.#.##..##.###.#.#####...#####...#.

.#..##.#...###..##...###.#####.##..#######.####.#..#.##.###.##.....##.###.....##.####...##.#.#.#.#.#

...#...####.#......##.####..##.#.#.###.#.#.##...#..##.#.##.##....##..#..##.#....#######.#.###..#.#..

..###.##.###..#.####.##.##....##.##.##.#.##.#####...###...##...##.#.#..#.##..........#..##.#..#....#

###.#..#...####.###.#.######......#...#....##.#.##..#.#..######.##.###.#.#.#....##.##.##...#.....###

.#.##..#..###.....#.###...#.#...#.#.#.#..........##.##....##.###.##.###.###..#...#..####..####..##.#

###..####.#..#..#......#.##..#...#...#.....###.#..##..#....##..###.#..##.......#.###.#.....#.#####.#

.#.#..#..#....#...#..#####...##.#.#....#....##..####..###..###...#.#..#...######.#..#.##..#..#...###

.#.##.#......#..####....#..#.#.#.#..#.#...#.....###.##.##..##..#...##........##.##..#.#####.##.##.#.

..#.#.##.##.####.#.###..#######..####.#..####....#.##.#.....#.#..######....##.#..#.##.#.####.######.

####.##....#...####..#######..##.#.#..##.##.###..#.#.##..###.##.#......#.....#....#.#..###.....##...

...#..#..#......##.#.##.#.#######...####.#..#.#.#.#.##..#####.....##....#.#..#..#..#.##.#.#.####..#.

.###.##..##..###..#..#.#####.##...########..#.#.#...#######.#..#.###.#.#.#...#.#.#.###.#.#######....

..###...##..#.#.##..#..#..#####..#..#...##..#.#....#...#..#..#..#..##.#.#.#.#.##....#.#...#.#####.##

.#....#....#.##.###..#..##...#....##..#.####.##.#..##.##..#.##.....##..#...#.#......#..###..##..##..

##..##..#...#.###.#.#.##.####.#...##..#..##.###.##..#.#...##....#.######.#..#.....#..#..#....#######

.####.###.#######.#.#####..###.#####.##...##.###...#..#.#......##.....#####.#..#..#.#####.#..###.###

.##.#..#.#####..#.#.####...#.#..#....#..#...##...###..#........######...#..####.#..#.#.#.#...####.#.

....#.#.##...#.#..###...#....###.###.#.#..#.#....#.#.####.....####..#.#####.....#...#.##.####.##....

#.#..#####.....#.###..#.#######.###......##.##.#...##.##..##....#....#...####..###.#.#.####...#.#.##

[出力例]

■参照サイト
AtCoder Grand Contest 014

2022年5月1日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う(※).
※ dp更新式のイメージがつかなかったので, 手計算してから実装している.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc238/editorial/3354
// 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 p[303], q[303], a[303];
LL dp[303][303], pd[303][303];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &p[i]);
    rep(i, N) scanf("%d", &q[i]);
    
    // 2. 入力情報の加工.
    rep(i, N) a[p[i]] = q[i];
    // rep(i, N + 1) printf("%d ", a[i]);
    // puts("");
    
    // 3. 初期化.
    pd[1][N + 1] = dp[1][N + 1] = 1;
    pd[0][a[1]] = dp[0][a[1]] = 1;
    
    // 4. dp更新.
    // ex.
    // 5 3
    // 3 5 4 1 2
    // 2 3 1 5 4
    // 
    // -> 順位情報の読み替え.
    // 1回目: 1 2 3 4 5
    // 2回目: 5 4 2 1 3
    // 
    // -> dp更新.
    // [1人目(初期化)]
    // (選ぶ)
    // dp[1][1][6] = 1
    // 
    // (選ばない)
    // dp[1][0][5] = 1
    // 
    // [2人目]
    // (選ぶ)
    // dp[2][2][6] = dp[1][1][6] -> dp[2][2][6] = 1
    // dp[2][1][5] = dp[1][0][5] -> dp[2][1][5] = 1
    // 
    // (選ばない)
    // dp[2][1][4] = dp[1][1][6] -> dp[2][1][4] = 1
    // dp[2][0][4] = dp[1][0][5] -> dp[2][0][4] = 1
    // 
    // [3人目]
    // (選ぶ)
    // dp[3][3][6] = dp[2][2][6] -> dp[3][3][6] = 1
    // dp[3][2][5] = dp[2][1][5] -> dp[3][2][5] = 1
    // dp[3][2][4] = dp[2][1][4] -> dp[3][2][4] = 1
    // dp[3][1][4] = dp[2][0][4] -> dp[3][1][4] = 1
    // 
    // (選ばない)
    // dp[3][2][2] = dp[2][2][6] -> dp[3][2][2] = 1
    // dp[3][1][2] = dp[2][1][5] 
    //             + dp[2][1][4] -> dp[3][1][2] = 2
    // dp[3][0][2] = dp[2][0][4] -> dp[3][0][2] = 1
    // 
    // [4人目]
    // (選ぶ)
    // dp[4][4][6] = dp[3][3][6] -> dp[4][4][6] = 1
    // dp[4][3][5] = dp[3][2][5] -> dp[4][3][5] = 1
    // dp[4][3][4] = dp[3][2][4] -> dp[4][3][4] = 1
    // dp[4][2][4] = dp[3][1][4] -> dp[4][2][4] = 1
    // dp[4][3][2] = dp[3][2][2] -> dp[4][3][2] = 1
    // dp[4][2][2] = dp[3][1][2] -> dp[4][2][2] = 2
    // dp[4][1][2] = dp[3][0][2] -> dp[4][1][2] = 1
    // 
    // (選ばない)
    // dp[4][3][1] = dp[3][3][6] -> dp[4][3][1] = 1
    // dp[4][2][1] = dp[3][2][5] 
    //             + dp[3][2][4] 
    //             + dp[3][2][2] -> dp[4][2][1] = 3
    // dp[4][1][1] = dp[3][1][4] 
    //             + dp[3][1][2] -> dp[4][1][1] = 3
    // dp[4][0][1] = dp[3][0][2] -> dp[4][0][1] = 1
    // 
    // [5人目]
    // (選ぶ)
    // dp[5][5][6] = dp[4][4][6] -> dp[5][5][6] = 1
    // dp[5][4][5] = dp[4][3][5] -> dp[5][4][5] = 1
    // dp[5][4][4] = dp[4][3][4] -> dp[5][4][4] = 1
    // dp[5][3][4] = dp[4][2][4] -> dp[5][3][4] = 1
    // 
    // dp[4][3][2], dp[4][2][2], dp[4][1][2], dp[4][3][1], dp[4][2][1], 
    // dp[4][1][1], dp[4][0][1] からの遷移は, 不可(第三引数が, 3 よりも小さいため).
    // 
    // (選ばない)
    // dp[5][4][3] = dp[4][4][6] -> dp[5][4][3] = 1
    // dp[5][3][3] = dp[4][3][5] 
    //             + dp[4][3][4] -> dp[5][3][3] = 2
    // dp[5][3][2] = dp[4][3][2] -> dp[5][3][2] = 1
    // dp[5][3][1] = dp[4][3][1] -> dp[5][3][1] = 1
    // dp[5][2][3] = dp[4][2][4] -> dp[5][2][3] = 1
    // dp[5][2][2] = dp[4][2][2] -> dp[5][2][2] = 2
    // dp[5][2][1] = dp[4][2][1] -> dp[5][2][1] = 3
    // dp[5][1][2] = dp[4][1][2] -> dp[5][1][2] = 1
    // dp[5][1][1] = dp[4][1][1] -> dp[5][1][1] = 3
    // dp[5][0][1] = dp[4][0][1] -> dp[5][0][1] = 1
    // 
    // -> 以上の結果から, dp[5][3][X] の 合計を計算すると, 
    // dp[5][3][X] = dp[5][3][4] + dp[5][3][3] + dp[5][3][2] + dp[5][3][1] = 1 + 2 + 1 + 1 = 5.
    repx(i, 2, N + 1){
        // 初期化.
        int p = a[i];
        rep(j, N + 1) rep(k, N + 2) dp[j][k] = 0;
        
        // 今回分更新.
        rep(j, i){
            // i人目 を 選ぶ.
            repx(k, p + 1, N + 2){
                dp[j + 1][k] += pd[j][k];
                dp[j + 1][k] %= MOD;
            }
            
            // i人目 を 選ばない.
            repx(k, 1, N + 2){
                int q = min(p, k);
                dp[j][q] += pd[j][k];
                dp[j][q] %= MOD;
            }
        }
        
        // 前回分更新.
        rep(j, N + 1) rep(k, N + 2) pd[j][k] = dp[j][k];
    }
    /*
    rep(j, N + 1){
        rep(k, N + 2) printf("%lld ", dp[j][k]);
        puts("");
    }
    */
    
    // 5. 集計.
    LL ans = 0;
    rep(k, N + 2) ans = (ans + dp[K][k]) % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

// 解き直し.

// https://atcoder.jp/contests/abc238/editorial/3354

// 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 p[303], q[303], a[303];

LL dp[303][303], pd[303][303];

int main(){

// 1. 入力情報.

int N, K;

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

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

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

// 2. 入力情報の加工.

rep(i, N) a[p[i]] = q[i];

// rep(i, N + 1) printf("%d ", a[i]);

// puts("");

// 3. 初期化.

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

pd[0][a[1]] = dp[0][a[1]] = 1;

// 4. dp更新.

// ex.

// 5 3

// 3 5 4 1 2

// 2 3 1 5 4

// -> 順位情報の読み替え.

// 1回目: 1 2 3 4 5

// 2回目: 5 4 2 1 3

// -> dp更新.

// [1人目(初期化)]

// (選ぶ)

// dp[1][1][6] = 1

// (選ばない)

// dp[1][0][5] = 1

// [2人目]

// (選ぶ)

// dp[2][2][6] = dp[1][1][6] -> dp[2][2][6] = 1

// dp[2][1][5] = dp[1][0][5] -> dp[2][1][5] = 1

// (選ばない)

// dp[2][1][4] = dp[1][1][6] -> dp[2][1][4] = 1

// dp[2][0][4] = dp[1][0][5] -> dp[2][0][4] = 1

// [3人目]

// (選ぶ)

// dp[3][3][6] = dp[2][2][6] -> dp[3][3][6] = 1

// dp[3][2][5] = dp[2][1][5] -> dp[3][2][5] = 1

// dp[3][2][4] = dp[2][1][4] -> dp[3][2][4] = 1

// dp[3][1][4] = dp[2][0][4] -> dp[3][1][4] = 1

// (選ばない)

// dp[3][2][2] = dp[2][2][6] -> dp[3][2][2] = 1

// dp[3][1][2] = dp[2][1][5]

// + dp[2][1][4] -> dp[3][1][2] = 2

// dp[3][0][2] = dp[2][0][4] -> dp[3][0][2] = 1

// [4人目]

// (選ぶ)

// dp[4][4][6] = dp[3][3][6] -> dp[4][4][6] = 1

// dp[4][3][5] = dp[3][2][5] -> dp[4][3][5] = 1

// dp[4][3][4] = dp[3][2][4] -> dp[4][3][4] = 1

// dp[4][2][4] = dp[3][1][4] -> dp[4][2][4] = 1

// dp[4][3][2] = dp[3][2][2] -> dp[4][3][2] = 1

// dp[4][2][2] = dp[3][1][2] -> dp[4][2][2] = 2

// dp[4][1][2] = dp[3][0][2] -> dp[4][1][2] = 1

// (選ばない)

// dp[4][3][1] = dp[3][3][6] -> dp[4][3][1] = 1

// dp[4][2][1] = dp[3][2][5]

// + dp[3][2][4]

// + dp[3][2][2] -> dp[4][2][1] = 3

// dp[4][1][1] = dp[3][1][4]

// + dp[3][1][2] -> dp[4][1][1] = 3

// dp[4][0][1] = dp[3][0][2] -> dp[4][0][1] = 1

// [5人目]

// (選ぶ)

// dp[5][5][6] = dp[4][4][6] -> dp[5][5][6] = 1

// dp[5][4][5] = dp[4][3][5] -> dp[5][4][5] = 1

// dp[5][4][4] = dp[4][3][4] -> dp[5][4][4] = 1

// dp[5][3][4] = dp[4][2][4] -> dp[5][3][4] = 1

// dp[4][3][2], dp[4][2][2], dp[4][1][2], dp[4][3][1], dp[4][2][1],

// dp[4][1][1], dp[4][0][1] からの遷移は, 不可(第三引数が, 3 よりも小さいため).

// (選ばない)

// dp[5][4][3] = dp[4][4][6] -> dp[5][4][3] = 1

// dp[5][3][3] = dp[4][3][5]

// + dp[4][3][4] -> dp[5][3][3] = 2

// dp[5][3][2] = dp[4][3][2] -> dp[5][3][2] = 1

// dp[5][3][1] = dp[4][3][1] -> dp[5][3][1] = 1

// dp[5][2][3] = dp[4][2][4] -> dp[5][2][3] = 1

// dp[5][2][2] = dp[4][2][2] -> dp[5][2][2] = 2

// dp[5][2][1] = dp[4][2][1] -> dp[5][2][1] = 3

// dp[5][1][2] = dp[4][1][2] -> dp[5][1][2] = 1

// dp[5][1][1] = dp[4][1][1] -> dp[5][1][1] = 3

// dp[5][0][1] = dp[4][0][1] -> dp[5][0][1] = 1

// -> 以上の結果から, dp[5][3][X] の合計を計算すると,

// dp[5][3][X] = dp[5][3][4] + dp[5][3][3] + dp[5][3][2] + dp[5][3][1] = 1 + 2 + 1 + 1 = 5.

repx(i, 2, N + 1){

// 初期化.

int p = a[i];

rep(j, N + 1) rep(k, N + 2) dp[j][k] = 0;

// 今回分更新.

rep(j, i){

// i人目を選ぶ.

repx(k, p + 1, N + 2){

dp[j + 1][k] += pd[j][k];

dp[j + 1][k] %= MOD;

}

// i人目を選ばない.

repx(k, 1, N + 2){

int q = min(p, k);

dp[j][q] += pd[j][k];

dp[j][q] %= MOD;

}

// 前回分更新.

rep(j, N + 1) rep(k, N + 2) pd[j][k] = dp[j][k];

}

rep(j, N + 1){

rep(k, N + 2) printf("%lld ", dp[j][k]);

puts("");

}

// 5. 集計.

LL ans = 0;

rep(k, N + 2) ans = (ans + dp[K][k]) % MOD;

// 6. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
5

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

[出力例]
21

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

[出力例]
1055

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

[出力例]
3314

[入力例]

4 2

2 4 3 1

2 1 4 3

[出力例]

※AtCoderテストケースより

[入力例]

33 16

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

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

[出力例]

168558757

※AtCoderテストケースより

[入力例]

15 7

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

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

[出力例]

※AtCoderテストケースより

[入力例]

5 3

3 5 4 1 2

2 3 1 5 4

[出力例]

[入力例]

10 5

3 10 1 4 2 8 6 5 9 7

5 7 10 3 9 4 1 8 2 6

[出力例]

[入力例]

50 10

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

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

[出力例]

1055

[入力例]

100 20

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

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

[出力例]

3314

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

2022年4月30日

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

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

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 組み合わせ計算が, 第二項の小さいパターン(200以下)であるため, ロジックを修正して対応した.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/arc134/editorial/3328
// 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;
const int LIMIT = 202;
LL a[101010], FAC[LIMIT], INV[LIMIT];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, int k){
    if(n < 0 || k < 0 || (LL)k > n) return 0LL;
    if(n == (LL)k || k == 0) return 1LL;
    LL ret = INV[k];
    rep(i, k) ret = ret * (n - i) % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%lld", &a[i]);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);
    
    // 2. 1 が 書かれたボールを調整.
    LL resA = a[0] - 1;
    repx(i, 1, N) resA -= a[i];
    
    // 3. 場合の数.
    LL ans = combination(resA, K - 1);
    repx(i, 1, N) ans = ans * combination(a[i] + K - 1, K - 1) % MOD;
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc134/editorial/3328

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

const int LIMIT = 202;

LL a[101010], FAC[LIMIT], INV[LIMIT];

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

}

// 組み合わせ(nCk)計算用(mod版).

// ※配列INV は, 事前に計算済のものを使う.

// @param n: 対象となる要素の個数.

// @param k: 選択する要素の個数.

// @return: 組み合わせ(nCk)の計算結果(mod版).

LL combination(LL n, int k){

if(n < 0 || k < 0 || (LL)k > n) return 0LL;

if(n == (LL)k || k == 0) return 1LL;

LL ret = INV[k];

rep(i, k) ret = ret * (n - i) % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, K;

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

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

FAC[0] = 1;

repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;

rep(i, LIMIT) INV[i] = mPow(FAC[i], MOD - 2);

// 2. 1 が書かれたボールを調整.

LL resA = a[0] - 1;

repx(i, 1, N) resA -= a[i];

// 3. 場合の数.

LL ans = combination(resA, K - 1);

repx(i, 1, N) ans = ans * combination(a[i] + K - 1, K - 1) % MOD;

// 4. 出力.

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

return 0;

}

[入力例]
2 2
3 1

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

[入力例]
2 1
1 100

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

[入力例]
20 100
1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325

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

[入力例]
3 2
7 3 2

[出力例]
12

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

[出力例]
972

[入力例]
10 5
108 3 8 2 21 8 7 10 10 23

[出力例]
601922667

[入力例]

2 2

3 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 1

1 100

[出力例]

※AtCoderのテストケースより

[入力例]

20 100

1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325

[出力例]

313918676

※AtCoderのテストケースより

[入力例]

3 2

7 3 2

[出力例]

[入力例]

5 3

10 1 2 2 1

[出力例]

972

[入力例]

10 5

108 3 8 2 21 8 7 10 10 23

[出力例]

601922667

■参照サイト
AtCoder Regular Contest 134

2022年4月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題D (Differ by K bits) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説および解説プログラムを参考に実装して, AC版に到達出来た.
2. 但し, AC版に, なかなか到達できなかったため, 調査したところ, XOR基底の計算方法が, 誤っていたと推測し, XOR基底の計算部分は, 解説プログラムを参考にして, 差し替えた(※).
※ popcount が K となる Nbit整数を一つ取って来て, これを, 1bitずつスライドする方法は, 正しくないとのこと.
現象としては, 数列 b のサイズが, 期待した値よりも小さくなり, 数列 b の作成時に, 重複要素が発生することから推定した.
3. 個人的には, 特殊な性質を持つ数列を抽出するロジックが, 非常に面白く感じたとともに, XOR基底の計算方法について, 新たな知識が増えたと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. Gray code.
    // https://ja.wikipedia.org/wiki/グレイコード
    vi a;
    int n = 1 << N;
    rep(i, n) a.pb(i ^ (i >> 1));
    // for(auto &p : a) printf("%d ", p);
    // puts("");
    
    // 3. K = 1.
    if(K == 1){
        puts("Yes");
        rep(i, n) printf("%d%s", a[i], (i < n - 1) ? " " : "\n");
        return 0;
    }
    
    // 4. 例外(01-010.txt などのWA回避のため, ロジック修正).
    if(!(K & 1) || K == N){
        puts("No");
        return 0;
    }
    
    // 5. XOR基底.
    /*
    // 以下のロジック(1 bitずつスライド)では, N bit の XOR基底にならない, とのこと.
    int x = (1 << K) - 1;
    vi z;
    rep(i, N){
        z.pb(x);
        x <<= 1;
        x %= n;
        if(__builtin_popcount(x) < K) ++x;
    }
    */
    // 解説プログラム参照(01-015.txt などのWA回避のため, ロジック修正).
    // https://atcoder.jp/contests/arc138/submissions/30615329
    vi z;
    int m1 = (1 << (K + 1)) - 1;
    int m2 = (1 << (K - 1)) - 1;
    rep(i, N){
        if(i < K - 1) z.pb(m1 ^ (1 << i));
        else          z.pb(m2 ^ (1 << i));
    }
    // for(auto &p : z) printf("%d ", p);
    // puts("");
    
    // 6. 数列 b.
    vi b;
    set<int> st;
    for(auto &p : a){
        // 数列 a (Gray code) で, bit が 1 となっている位置を元に, 数列 b を 計算.
        int cur = 0;
        rep(j, N) if(p & (1 << (N - 1 - j))) cur ^= z[j];
        b.pb(cur);
        st.insert(cur);
    }
    // printf("st.size()=%d b.size()=%d\n", st.size(), b.size());
    
    // 7. 出力.
    puts("Yes");
    rep(i, n) printf("%d%s", b[i], (i < n - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc138/editorial/3741

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, K;

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

// 2. Gray code.

// https://ja.wikipedia.org/wiki/グレイコード

vi a;

int n = 1 << N;

rep(i, n) a.pb(i ^ (i >> 1));

// for(auto &p : a) printf("%d ", p);

// puts("");

// 3. K = 1.

if(K == 1){

puts("Yes");

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

return 0;

}

// 4. 例外(01-010.txt などのWA回避のため, ロジック修正).

if(!(K & 1) || K == N){

puts("No");

return 0;

}

// 5. XOR基底.

// 以下のロジック(1 bitずつスライド)では, N bit の XOR基底にならない, とのこと.

int x = (1 << K) - 1;

vi z;

rep(i, N){

z.pb(x);

x <<= 1;

x %= n;

if(__builtin_popcount(x) < K) ++x;

}

// 解説プログラム参照(01-015.txt などのWA回避のため, ロジック修正).

// https://atcoder.jp/contests/arc138/submissions/30615329

vi z;

int m1 = (1 << (K + 1)) - 1;

int m2 = (1 << (K - 1)) - 1;

rep(i, N){

if(i < K - 1) z.pb(m1 ^ (1 << i));

else z.pb(m2 ^ (1 << i));

}

// for(auto &p : z) printf("%d ", p);

// puts("");

// 6. 数列 b.

vi b;

set<int> st;

for(auto &p : a){

// 数列 a (Gray code) で, bit が 1 となっている位置を元に, 数列 b を計算.

int cur = 0;

rep(j, N) if(p & (1 << (N - 1 - j))) cur ^= z[j];

b.pb(cur);

st.insert(cur);

}

// printf("st.size()=%d b.size()=%d\n", st.size(), b.size());

// 7. 出力.

puts("Yes");

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

return 0;

}

[入力例]
3 1

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

[入力例]
2 2

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

[入力例]
5 3

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

[入力例]
5 4

[出力例]
No

[入力例]
7 5

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

[入力例]
10 7

[出力例]
Yes
0 575 768 319 384 959 640 191 192 767 960 511 320 895 576 127 160 671 928 415 288 799 544 31 96 607 864 351 480 991 736 223 48 527 816 271 432 911 688 143 240 719 1008 463 368 847 624 79 144 687 912 431 272 815 528 47 80 623 848 367 464 1007 720 239 24 551 792 295 408 935 664 167 216 743 984 487 344 871 600 103 184 647 952 391 312 775 568 7 120 583 888 327 504 967 760 199 40 535 808 279 424 919 680 151 232 727 1000 471 360 855 616 87 136 695 904 439 264 823 520 55 72 631 840 375 456 1015 712 247 12 563 780 307 396 947 652 179 204 755 972 499 332 883 588 115 172 659 940 403 300 787 556 19 108 595 876 339 492 979 748 211 60 515 828 259 444 899 700 131 252 707 1020 451 380 835 636 67 156 675 924 419 284 803 540 35 92 611 860 355 476 995 732 227 20 555 788 299 404 939 660 171 212 747 980 491 340 875 596 107 180 651 948 395 308 779 564 11 116 587 884 331 500 971 756 203 36 539 804 283 420 923 676 155 228 731 996 475 356 859 612 91 132 699 900 443 260 827 516 59 68 635 836 379 452 1019 708 251 6 569 774 313 390 953 646 185 198 761 966 505 326 889 582 121 166 665 934 409 294 793 550 25 102 601 870 345 486 985 742 217 54 521 822 265 438 905 694 137 246 713 1014 457 374 841 630 73 150 681 918 425 278 809 534 41 86 617 854 361 470 1001 726 233 30 545 798 289 414 929 670 161 222 737 990 481 350 865 606 97 190 641 958 385 318 769 574 1 126 577 894 321 510 961 766 193 46 529 814 273 430 913 686 145 238 721 1006 465 366 849 622 81 142 689 910 433 270 817 526 49 78 625 846 369 462 1009 718 241 10 565 778 309 394 949 650 181 202 757 970 501 330 885 586 117 170 661 938 405 298 789 554 21 106 597 874 341 490 981 746 213 58 517 826 261 442 901 698 133 250 709 1018 453 378 837 634 69 154 677 922 421 282 805 538 37 90 613 858 357 474 997 730 229 18 557 786 301 402 941 658 173 210 749 978 493 338 877 594 109 178 653 946 397 306 781 562 13 114 589 882 333 498 973 754 205 34 541 802 285 418 925 674 157 226 733 994 477 354 861 610 93 130 701 898 445 258 829 514 61 66 637 834 381 450 1021 706 253 3 572 771 316 387 956 643 188 195 764 963 508 323 892 579 124 163 668 931 412 291 796 547 28 99 604 867 348 483 988 739 220 51 524 819 268 435 908 691 140 243 716 1011 460 371 844 627 76 147 684 915 428 275 812 531 44 83 620 851 364 467 1004 723 236 27 548 795 292 411 932 667 164 219 740 987 484 347 868 603 100 187 644 955 388 315 772 571 4 123 580 891 324 507 964 763 196 43 532 811 276 427 916 683 148 235 724 1003 468 363 852 619 84 139 692 907 436 267 820 523 52 75 628 843 372 459 1012 715 244 15 560 783 304 399 944 655 176 207 752 975 496 335 880 591 112 175 656 943 400 303 784 559 16 111 592 879 336 495 976 751 208 63 512 831 256 447 896 703 128 255 704 1023 448 383 832 639 64 159 672 927 416 287 800 543 32 95 608 863 352 479 992 735 224 23 552 791 296 407 936 663 168 215 744 983 488 343 872 599 104 183 648 951 392 311 776 567 8 119 584 887 328 503 968 759 200 39 536 807 280 423 920 679 152 231 728 999 472 359 856 615 88 135 696 903 440 263 824 519 56 71 632 839 376 455 1016 711 248 5 570 773 314 389 954 645 186 197 762 965 506 325 890 581 122 165 666 933 410 293 794 549 26 101 602 869 346 485 986 741 218 53 522 821 266 437 906 693 138 245 714 1013 458 373 842 629 74 149 682 917 426 277 810 533 42 85 618 853 362 469 1002 725 234 29 546 797 290 413 930 669 162 221 738 989 482 349 866 605 98 189 642 957 386 317 770 573 2 125 578 893 322 509 962 765 194 45 530 813 274 429 914 685 146 237 722 1005 466 365 850 621 82 141 690 909 434 269 818 525 50 77 626 845 370 461 1010 717 242 9 566 777 310 393 950 649 182 201 758 969 502 329 886 585 118 169 662 937 406 297 790 553 22 105 598 873 342 489 982 745 214 57 518 825 262 441 902 697 134 249 710 1017 454 377 838 633 70 153 678 921 422 281 806 537 38 89 614 857 358 473 998 729 230 17 558 785 302 401 942 657 174 209 750 977 494 337 878 593 110 177 654 945 398 305 782 561 14 113 590 881 334 497 974 753 206 33 542 801 286 417 926 673 158 225 734 993 478 353 862 609 94 129 702 897 446 257 830 513 62 65 638 833 382 449 1022 705 254

[入力例]

3 1

[出力例]

Yes

0 1 3 2 6 7 5 4

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

5 3

[出力例]

Yes

0 19 24 11 12 31 20 7 10 25 18 1 6 21 30 13 3 16 27 8 15 28 23 4 9 26 17 2 5 22 29 14

[入力例]

5 4

[出力例]

[入力例]

7 5

[出力例]

Yes

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

[入力例]

10 7

[出力例]

Yes

0 575 768 319 384 959 640 191 192 767 960 511 320 895 576 127 160 671 928 415 288 799 544 31 96 607 864 351 480 991 736 223 48 527 816 271 432 911 688 143 240 719 1008 463 368 847 624 79 144 687 912 431 272 815 528 47 80 623 848 367 464 1007 720 239 24 551 792 295 408 935 664 167 216 743 984 487 344 871 600 103 184 647 952 391 312 775 568 7 120 583 888 327 504 967 760 199 40 535 808 279 424 919 680 151 232 727 1000 471 360 855 616 87 136 695 904 439 264 823 520 55 72 631 840 375 456 1015 712 247 12 563 780 307 396 947 652 179 204 755 972 499 332 883 588 115 172 659 940 403 300 787 556 19 108 595 876 339 492 979 748 211 60 515 828 259 444 899 700 131 252 707 1020 451 380 835 636 67 156 675 924 419 284 803 540 35 92 611 860 355 476 995 732 227 20 555 788 299 404 939 660 171 212 747 980 491 340 875 596 107 180 651 948 395 308 779 564 11 116 587 884 331 500 971 756 203 36 539 804 283 420 923 676 155 228 731 996 475 356 859 612 91 132 699 900 443 260 827 516 59 68 635 836 379 452 1019 708 251 6 569 774 313 390 953 646 185 198 761 966 505 326 889 582 121 166 665 934 409 294 793 550 25 102 601 870 345 486 985 742 217 54 521 822 265 438 905 694 137 246 713 1014 457 374 841 630 73 150 681 918 425 278 809 534 41 86 617 854 361 470 1001 726 233 30 545 798 289 414 929 670 161 222 737 990 481 350 865 606 97 190 641 958 385 318 769 574 1 126 577 894 321 510 961 766 193 46 529 814 273 430 913 686 145 238 721 1006 465 366 849 622 81 142 689 910 433 270 817 526 49 78 625 846 369 462 1009 718 241 10 565 778 309 394 949 650 181 202 757 970 501 330 885 586 117 170 661 938 405 298 789 554 21 106 597 874 341 490 981 746 213 58 517 826 261 442 901 698 133 250 709 1018 453 378 837 634 69 154 677 922 421 282 805 538 37 90 613 858 357 474 997 730 229 18 557 786 301 402 941 658 173 210 749 978 493 338 877 594 109 178 653 946 397 306 781 562 13 114 589 882 333 498 973 754 205 34 541 802 285 418 925 674 157 226 733 994 477 354 861 610 93 130 701 898 445 258 829 514 61 66 637 834 381 450 1021 706 253 3 572 771 316 387 956 643 188 195 764 963 508 323 892 579 124 163 668 931 412 291 796 547 28 99 604 867 348 483 988 739 220 51 524 819 268 435 908 691 140 243 716 1011 460 371 844 627 76 147 684 915 428 275 812 531 44 83 620 851 364 467 1004 723 236 27 548 795 292 411 932 667 164 219 740 987 484 347 868 603 100 187 644 955 388 315 772 571 4 123 580 891 324 507 964 763 196 43 532 811 276 427 916 683 148 235 724 1003 468 363 852 619 84 139 692 907 436 267 820 523 52 75 628 843 372 459 1012 715 244 15 560 783 304 399 944 655 176 207 752 975 496 335 880 591 112 175 656 943 400 303 784 559 16 111 592 879 336 495 976 751 208 63 512 831 256 447 896 703 128 255 704 1023 448 383 832 639 64 159 672 927 416 287 800 543 32 95 608 863 352 479 992 735 224 23 552 791 296 407 936 663 168 215 744 983 488 343 872 599 104 183 648 951 392 311 776 567 8 119 584 887 328 503 968 759 200 39 536 807 280 423 920 679 152 231 728 999 472 359 856 615 88 135 696 903 440 263 824 519 56 71 632 839 376 455 1016 711 248 5 570 773 314 389 954 645 186 197 762 965 506 325 890 581 122 165 666 933 410 293 794 549 26 101 602 869 346 485 986 741 218 53 522 821 266 437 906 693 138 245 714 1013 458 373 842 629 74 149 682 917 426 277 810 533 42 85 618 853 362 469 1002 725 234 29 546 797 290 413 930 669 162 221 738 989 482 349 866 605 98 189 642 957 386 317 770 573 2 125 578 893 322 509 962 765 194 45 530 813 274 429 914 685 146 237 722 1005 466 365 850 621 82 141 690 909 434 269 818 525 50 77 626 845 370 461 1010 717 242 9 566 777 310 393 950 649 182 201 758 969 502 329 886 585 118 169 662 937 406 297 790 553 22 105 598 873 342 489 982 745 214 57 518 825 262 441 902 697 134 249 710 1017 454 377 838 633 70 153 678 921 422 281 806 537 38 89 614 857 358 473 998 729 230 17 558 785 302 401 942 657 174 209 750 977 494 337 878 593 110 177 654 945 398 305 782 561 14 113 590 881 334 497 974 753 206 33 542 801 286 417 926 673 158 225 734 993 478 353 862 609 94 129 702 897 446 257 830 513 62 65 638 833 382 449 1022 705 254

■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

2022年4月30日

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

C++の練習を兼ねて, AtCoder Regular Contest 134 の問題A (Bridge and Sheets) ～問題B (Reserve or Reverse) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 問題Bは, 実装に苦労したものの, 個人的には, 解説にあるロジックで, 辞書順最小の文字列を抽出できることが, 非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

■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--)
LL a[101010];

int main(){
    
    // 1. 入力情報.
    int N;
    LL L, W;
    scanf("%d %lld %lld", &N, &L, &W);
    rep(i, N) scanf("%lld", &a[i]);
    a[N] = L;
    
    // 2. シートの枚数は？
    LL ans = 0, cur = 0;
    rep(i, N + 1){
        // 現在位置が, 設置位置より左側にあるケース.
        if(cur < a[i]){
            LL q = (a[i] - cur) / W;
            LL r = (a[i] - cur) % W;
            ans += q + (r > 0);
            cur += (q + (r > 0)) * W;
            cur = max(cur, a[i] + W);
            continue;
        }
        
        // 現在位置が, 設置位置より右側にあるケース.
        if(cur >= a[i]) cur = max(cur, a[i] + W);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[101010];

int main(){

// 1. 入力情報.

int N;

LL L, W;

scanf("%d %lld %lld", &N, &L, &W);

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

a[N] = L;

// 2. シートの枚数は？

LL ans = 0, cur = 0;

rep(i, N + 1){

// 現在位置が, 設置位置より左側にあるケース.

if(cur < a[i]){

LL q = (a[i] - cur) / W;

LL r = (a[i] - cur) % W;

ans += q + (r > 0);

cur += (q + (r > 0)) * W;

cur = max(cur, a[i] + W);

continue;

}

// 現在位置が, 設置位置より右側にあるケース.

if(cur >= a[i]) cur = max(cur, a[i] + W);

}

// 3. 出力.

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

return 0;

}

[入力例]
2 10 3
3 5

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

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

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

[入力例]
12 1000000000 5
18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402

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

[入力例]
5 40 5
11 17 18 25 35

[出力例]
6

[入力例]
15 111 7
5 11 23 25 33 40 52 58 70 78 86 87 91 101 108

[出力例]
8

[入力例]

2 10 3

3 5

[出力例]

※AtCoderのテストケースより

[入力例]

5 10 3

0 1 4 6 7

[出力例]

※AtCoderのテストケースより

[入力例]

12 1000000000 5

18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402

[出力例]

199999992

※AtCoderのテストケースより

[入力例]

5 40 5

11 17 18 25 35

[出力例]

[入力例]

15 111 7

5 11 23 25 33 40 52 58 70 78 86 87 91 101 108

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/arc134/editorial/3326
// 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 sCum[202020][26];

int main(){
    
    // 1. 入力情報.
    int N;
    char c[202020];
    scanf("%d %s", &N, c);
    string s(c);
    
    // 2. 累積和.
    repx(i, 1, N + 1){
        ++sCum[i][s[i - 1] - 'a'];
        rep(j, 26) sCum[i][j] += sCum[i - 1][j];
    }
    /*
    rep(i, N + 1){
        rep(j, 26) printf("%d ", sCum[i][j]);
        puts("");
    }
    */
    
    // 3. 貪欲法.
    int q = N - 1;
    rep(p, N){
        // 終了条件.
        if(q <= p) break;
        
        // p文字目.
        int cur = s[p] - 'a';
        
        // p文字目より最も右側で, 最小となる文字があるか？
        int m = -1;
        rep(j, cur){
            if(sCum[q + 1][j] - sCum[p + 1][j] > 0){
                m = j;
                break;
            }
        }
        
        // 次へ.
        if(m == -1) continue;
        
        // 最小の文字を探す.
        int at = q + 1;
        repr(j, q, p + 1){
            if(m == s[j] - 'a'){
                at = j;
                break;
            }
        }
        
        // 次へ.
        if(at == q + 1) continue;
        
        // q を 更新し, スワップ.
        q = at;
        swap(s[p], s[q]);
        
        // デクリメント.
        --q;
    }
    
    // 4. 出力.
    printf("%s\n", s.c_str());
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc134/editorial/3326

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

int main(){

// 1. 入力情報.

int N;

char c[202020];

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

string s(c);

// 2. 累積和.

repx(i, 1, N + 1){

++sCum[i][s[i - 1] - 'a'];

rep(j, 26) sCum[i][j] += sCum[i - 1][j];

}

rep(i, N + 1){

rep(j, 26) printf("%d ", sCum[i][j]);

puts("");

}

// 3. 貪欲法.

int q = N - 1;

rep(p, N){

// 終了条件.

if(q <= p) break;

// p文字目.

int cur = s[p] - 'a';

// p文字目より最も右側で, 最小となる文字があるか？

int m = -1;

rep(j, cur){

if(sCum[q + 1][j] - sCum[p + 1][j] > 0){

m = j;

break;

}

// 次へ.

if(m == -1) continue;

// 最小の文字を探す.

int at = q + 1;

repr(j, q, p + 1){

if(m == s[j] - 'a'){

at = j;

break;

}

// 次へ.

if(at == q + 1) continue;

// q を更新し, スワップ.

q = at;

swap(s[p], s[q]);

// デクリメント.

--q;

}

// 4. 出力.

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

return 0;

}

[入力例]
4
dcab

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

[入力例]
2
ab

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

[入力例]
16
cabaaabbbabcbaba

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

[入力例]
17
snwfpfwipeusiwkzo

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

[入力例]
11
abracadabra

[出力例]
aaaaacdrbrb

[入力例]
50
ubjclqgsqnnudgnfwfisikuqcdcmybvkwdomjbpocumfjngqid

[出力例]
bbbcccdnnqsuggnfwfisikuqqdlmyjvkwdomjupocumfjngqid

[入力例]
100
huswufokysasxnrhpwweddrnmylmnzpmkbyuublhnmujpsrexqpedbhiixcsavgbsejichvoywvpjgyvcxtqopdvibcarjqecacp

[出力例]
aaaafuokyswsxnrhpwweddrnmylmnzpmkbyuublhnmujpsrexqpedbhiixcssvgbsejichvoywvpjgyvcxtqopdvibcurjqechcp

[入力例]
200
illytageazvxvvoiaboenviyjwvuknebmhsrovungfmnokumfrfwxruqwurwpgraocrerihmeotxmimbqaztonpanphijkbxyloxlkjgftaafqiuhbuytlfprvhzokuvwfaqbeioepgusidicsbswdicapnvusytkytmznytbykwinzslruwpsgmedyzjjiefufmkohj

[出力例]
aaaaaaaaaaiovvxvzboenviyjwvuknebmhsrovungfmnokumfrfwxruqwurwpgreocrerihmeotxmimbqgztonptnphijkbxyloxlkjgftylfqiuhbuytlfprvhzokuvwflqbeioepgusidicsbswdicipnvusytkytmznytbykwinzslruwpsgmedyzjjiefufmkohj

[入力例]
500
mwdhquqkdffqifgnzsdfmbvduibxldjttgvezqejsslmcflwvdlkmcweiocuoahtlepjkxpiidsrilcvrunvbvrdtkzazbemysumysirvztrojokdkoevtuixeihianwnhrczfpvsfsdlphxvblirgkjipkrdvrprbkdjhijzwgfzwmgiqaodlukkixszbrurdfviwgvsgwkayfsitbzvszurzvsupuerqdwjejkohkrolhfgygybwtqrufhiyeodeaijlomynekfgvfydpbivdioydjjpvqeqvlxgrrqanpewlvpulpdaharhxtiywdvpdkqjkkbefwiobnmvijusfscpzssrkiumerprhqbgbpvugvmvtudrjmfrwqozmhcxhlyadeztkafdpyvwitnyuynideaubnbstzlmhthsorlzyuqstgdoskpvvpglvasuyldsohqgeetqnpsloryothuigwugtsrohfxhndxoekqfcencvq

[出力例]
aaaaaaaaaaaaabbdsznfmgvduifxldjttgvezqejsslmcflwvdlkmcweiocuoihtlepjkxpiidsrilcvrunvbvrdtkzqzbemysumysirvztrojokdkoevtuixeihifnwnhrczfpvsfsdlphxvblirgkjipkrdvrprbkdjhijzwgfzwmgiqfodlukkixszbrurdfviwgvsgwkdyfsitbzvszurzvsupuerqdwjejkohkrolhfgygybwtqrufhiyeodekijlomynekfgvfydpbivdioydjjpvqeqvlxgrrqqnpewlvpulpduhqrhxtiywdvpdkqjkkbefwiobnmvijusfscpzssrkiumerprhqbgbpvugvmvtudrjmfrwqozmhcxhlyhdeztkdfdpyvwitnyuynidewubnbstzlmhthsorlzyuqstgdoskpvvpglvmsuyldsohqgeetqnpsloryothuigwugtsrohfxhndxoekqfcencvq

[入力例]

dcab

[出力例]

acdb

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

cabaaabbbabcbaba

[出力例]

aaaaaaabbbbcbbbc

※AtCoderのテストケースより

[入力例]

snwfpfwipeusiwkzo

[出力例]

effwpnwipsusiwkzo

※AtCoderのテストケースより

[入力例]

abracadabra

[出力例]

aaaaacdrbrb

[入力例]

ubjclqgsqnnudgnfwfisikuqcdcmybvkwdomjbpocumfjngqid

[出力例]

bbbcccdnnqsuggnfwfisikuqqdlmyjvkwdomjupocumfjngqid

[入力例]

100

huswufokysasxnrhpwweddrnmylmnzpmkbyuublhnmujpsrexqpedbhiixcsavgbsejichvoywvpjgyvcxtqopdvibcarjqecacp

[出力例]

aaaafuokyswsxnrhpwweddrnmylmnzpmkbyuublhnmujpsrexqpedbhiixcssvgbsejichvoywvpjgyvcxtqopdvibcurjqechcp

[入力例]

200

illytageazvxvvoiaboenviyjwvuknebmhsrovungfmnokumfrfwxruqwurwpgraocrerihmeotxmimbqaztonpanphijkbxyloxlkjgftaafqiuhbuytlfprvhzokuvwfaqbeioepgusidicsbswdicapnvusytkytmznytbykwinzslruwpsgmedyzjjiefufmkohj

[出力例]

aaaaaaaaaaiovvxvzboenviyjwvuknebmhsrovungfmnokumfrfwxruqwurwpgreocrerihmeotxmimbqgztonptnphijkbxyloxlkjgftylfqiuhbuytlfprvhzokuvwflqbeioepgusidicsbswdicipnvusytkytmznytbykwinzslruwpsgmedyzjjiefufmkohj

[入力例]

500

mwdhquqkdffqifgnzsdfmbvduibxldjttgvezqejsslmcflwvdlkmcweiocuoahtlepjkxpiidsrilcvrunvbvrdtkzazbemysumysirvztrojokdkoevtuixeihianwnhrczfpvsfsdlphxvblirgkjipkrdvrprbkdjhijzwgfzwmgiqaodlukkixszbrurdfviwgvsgwkayfsitbzvszurzvsupuerqdwjejkohkrolhfgygybwtqrufhiyeodeaijlomynekfgvfydpbivdioydjjpvqeqvlxgrrqanpewlvpulpdaharhxtiywdvpdkqjkkbefwiobnmvijusfscpzssrkiumerprhqbgbpvugvmvtudrjmfrwqozmhcxhlyadeztkafdpyvwitnyuynideaubnbstzlmhthsorlzyuqstgdoskpvvpglvasuyldsohqgeetqnpsloryothuigwugtsrohfxhndxoekqfcencvq

[出力例]

aaaaaaaaaaaaabbdsznfmgvduifxldjttgvezqejsslmcflwvdlkmcweiocuoihtlepjkxpiidsrilcvrunvbvrdtkzqzbemysumysirvztrojokdkoevtuixeihifnwnhrczfpvsfsdlphxvblirgkjipkrdvrprbkdjhijzwgfzwmgiqfodlukkixszbrurdfviwgvsgwkdyfsitbzvszurzvsupuerqdwjejkohkrolhfgygybwtqrufhiyeodekijlomynekfgvfydpbivdioydjjpvqeqvlxgrrqqnpewlvpulpduhqrhxtiywdvpdkqjkkbefwiobnmvijusfscpzssrkiumerprhqbgbpvugvmvtudrjmfrwqozmhcxhlyhdeztkdfdpyvwitnyuynidewubnbstzlmhthsorlzyuqstgdoskpvvpglvmsuyldsohqgeetqnpsloryothuigwugtsrohfxhndxoekqfcencvq

■参照サイト
AtCoder Regular Contest 134

2022年4月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 118 の問題A (Tax Included Price) ～問題B (Village of M People) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc118/editorial/1200
// 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 t, N;
    scanf("%d %d", &t, &N);
    --N;
    
    // 2. 税込み価格として現れないものは？
    LL bef = 0, cur = 0;
    vl v;
    rep(a, 100){
        // 今回分計算.
        cur = (LL)((100 + t) * (a + 1) / 100);
        
        // 差分が, 1 より大きいものは？
        if(cur - bef > 1) v.pb(cur - 1);
        
        // 前回分保存.
        bef = cur;
    }
    // for(auto &p : v) printf("%lld\n", p);
    
    // 3. 周期性.
    int f = (LL)v.size();
    LL q = N / f;
    int r = N % f;
    
    // 4. N番目の金額は？
    LL ans = q * (LL)(100 + t) + v[r];
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc118/editorial/1200

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

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

--N;

// 2. 税込み価格として現れないものは？

LL bef = 0, cur = 0;

vl v;

rep(a, 100){

// 今回分計算.

cur = (LL)((100 + t) * (a + 1) / 100);

// 差分が, 1 より大きいものは？

if(cur - bef > 1) v.pb(cur - 1);

// 前回分保存.

bef = cur;

}

// for(auto &p : v) printf("%lld\n", p);

// 3. 周期性.

int f = (LL)v.size();

LL q = N / f;

int r = N % f;

// 4. N番目の金額は？

LL ans = q * (LL)(100 + t) + v[r];

// 5. 出力.

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

return 0;

}

[入力例]
10 1

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

[入力例]
3 5

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

[入力例]
1 1000000000

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

[入力例]
22 20210509

[出力例]
112076458

[入力例]
35 20220428

[出力例]
77993079

[入力例]

10 1

[出力例]

※AtCoderのテストケースより

[入力例]

3 5

[出力例]

171

※AtCoderのテストケースより

[入力例]

1 1000000000

[出力例]

100999999999

※AtCoderのテストケースより

[入力例]

22 20210509

[出力例]

112076458

[入力例]

35 20220428

[出力例]

77993079

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

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

int main(){
    
    // 1. 入力情報.
    int K;
    LL N, M;
    scanf("%d %lld %lld", &K, &N, &M);
    rep(i, K) scanf("%lld", &a[i]);
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. B[i] の 設定(※ L[i] を ベース).
        LL t = 0;
        vl b(K);
        rep(i, K){
            LL p = (max(0LL, M * a[i] - m) + (N - 1)) / N;
            b[i] = p;
            t += p;
        }
        
        // 2-2. B[i] の 設定(※ R[i] を ベース).
        rep(i, K){
            LL q = (M * a[i] + m) / N;
            LL d = max(0LL, min(q - b[i], M - t));
            if(d){
                b[i] += d;
                t += d;
            }
        }
        
        // 2-3. 判定結果(t < M だと, 02_rand_01.txtなどで, WAとなるように見える).
        return (t == M);
    };
    
    // 3. 二分探索で確認してみる(※01_sample_02.txt などのWA回避のため, l = 0 を l = 1 に 修正).
    LL l = 1, h = 2e16 + 1;
    while(l + 1 < h){
        LL m = (h + l) >> 1LL;
        if(f(m)) h = m;
        else     l = m;
        // printf("h=%lld l=%lld m=%lld\n", h, l, m);
    }
    
    // 4. 復元.
    // 4-1. B[i] の 設定(※ L[i] を ベース).
    LL t = 0;
    vl ans(K);
    rep(i, K){
        LL p = (max(0LL, M * a[i] - h) + (N - 1)) / N;
        ans[i] = p;
        t += p;
    }
    
    // 4-2. B[i] の 設定(※ R[i] を ベース).
    rep(i, K){
        LL q = (M * a[i] + h) / N;
        LL d = max(0LL, min(q - ans[i], M - t));
        if(d){
            ans[i] += d;
            t += d;
        }
    }
    assert(t == M);
    
    // 5. 出力.
    rep(i, K) printf("%lld%s", ans[i], (i < K - 1) ? " " : "\n");
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc118/editorial/1226

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vl = vector<LL>;

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

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

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

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

LL a[101010];

int main(){

// 1. 入力情報.

int K;

LL N, M;

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

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

// 2. 評価関数.

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

// 2-1. B[i] の設定(※ L[i] をベース).

LL t = 0;

vl b(K);

rep(i, K){

LL p = (max(0LL, M * a[i] - m) + (N - 1)) / N;

b[i] = p;

t += p;

}

// 2-2. B[i] の設定(※ R[i] をベース).

rep(i, K){

LL q = (M * a[i] + m) / N;

LL d = max(0LL, min(q - b[i], M - t));

if(d){

b[i] += d;

t += d;

}

// 2-3. 判定結果(t < M だと, 02_rand_01.txtなどで, WAとなるように見える).

return (t == M);

};

// 3. 二分探索で確認してみる(※01_sample_02.txt などのWA回避のため, l = 0 を l = 1 に修正).

LL l = 1, h = 2e16 + 1;

while(l + 1 < h){

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

if(f(m)) h = m;

else l = m;

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

}

// 4. 復元.

// 4-1. B[i] の設定(※ L[i] をベース).

LL t = 0;

vl ans(K);

rep(i, K){

LL p = (max(0LL, M * a[i] - h) + (N - 1)) / N;

ans[i] = p;

t += p;

}

// 4-2. B[i] の設定(※ R[i] をベース).

rep(i, K){

LL q = (M * a[i] + h) / N;

LL d = max(0LL, min(q - ans[i], M - t));

if(d){

ans[i] += d;

t += d;

}

assert(t == M);

// 5. 出力.

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

return 0;

}

[入力例]
3 7 20
1 2 4

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

[入力例]
3 3 100
1 1 1

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

[入力例]
6 10006 10
10000 3 2 1 0 0

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

[入力例]
7 78314 1000
53515 10620 7271 3817 1910 956 225

[出力例]
683 136 93 49 24 12 3
※AtCoderテストケースより

[入力例]
5 55 111
5 7 9 11 23

[出力例]
10 14 18 22 47

[入力例]
24 2022 20210509
314 159 265 358 97 9 323 84 62 64 33 83 27 9 50 28 8 4 19 7 1 6 9 3

[出力例]
3138526 1589254 2648756 3578320 969545 89958 3228484 839606 619709 639700 329845 829610 269873 89958 499765 279868 79962 39981 189911 69967 9995 59972 89958 29986

[入力例]
50 33333 20220429
780 375 1010 1215 759 999 1038 370 381 366 40 321 1149 896 987 794 734 1143 452 579 284 276 204 635 264 47 37 768 1234 332 572 1002 320 1169 201 738 526 453 895 1090 798 774 411 1143 1086 685 194 931 1035 841

[出力例]
473163 227482 612685 737042 460424 606012 629670 224449 231122 222023 24265 194725 697005 543531 598733 481655 445258 693365 274192 351232 172280 167427 123750 385203 160147 28511 22445 465883 748568 201398 346986 607832 194118 709138 121930 447685 319082 274798 542924 661215 484082 469523 249320 693365 658788 415534 117684 564762 627851 510167

[入力例]
100 777777 1000000000
5526 6946 12205 9758 7777 11193 5678 2804 12305 6582 7081 10594 6520 12118 13896 12845 9471 5550 3456 550 3305 3349 3310 2056 12466 10186 15169 10686 8320 9999 3829 12188 7777 4003 6666 15007 824 11590 4772 7330 3839 2093 1535 7847 2997 3699 14379 5615 14035 10732 1991 439 8622 5877 14232 10831 10438 10039 7959 1907 8696 9839 10527 12638 9289 3129 4332 2765 2345 7397 12379 10160 12263 10541 9308 13260 13176 7980 5000 1285 3559 7560 956 7814 10833 5501 13091 10596 11873 15246 7777 1796 4315 12627 11846 2597 15154 3257 6950 3327

[出力例]
7104864 8930580 15692159 12546013 9999010 14391014 7300293 3605146 15820730 8462580 9104152 13620871 8382866 15580301 17866304 16515016 12177012 7135721 4443433 707144 4249290 4305861 4255719 2643431 16027730 13096299 19503019 13739157 10697154 12855870 4923005 15670301 9999010 5146719 8570580 19294734 1059430 14901443 6135435 9424295 4935862 2691003 1973573 10089010 3853290 4755862 18487304 7219293 18045018 13798299 2559860 564429 11085440 7556150 18298304 13925585 13420299 12907299 10233010 2451860 11180583 12650155 13534728 16248873 11943012 4023004 5569720 3555004 3015003 9510438 15915873 13062870 15766730 13552728 11967441 17048588 16940588 10260010 6428578 1652144 4575862 9720010 1229144 10046581 13928157 7072721 16831303 13623442 15265301 19602020 9999010 2309145 5547863 16234731 15230587 3339003 19483734 4187576 8935723 4277576

[入力例]

3 7 20

1 2 4

[出力例]

3 6 11

※AtCoderテストケースより

[入力例]

3 3 100

1 1 1

[出力例]

34 33 33

※AtCoderテストケースより

[入力例]

6 10006 10

10000 3 2 1 0 0

[出力例]

10 0 0 0 0 0

※AtCoderテストケースより

[入力例]

7 78314 1000

53515 10620 7271 3817 1910 956 225

[出力例]

683 136 93 49 24 12 3

※AtCoderテストケースより

[入力例]

5 55 111

5 7 9 11 23

[出力例]

10 14 18 22 47

[入力例]

24 2022 20210509

314 159 265 358 97 9 323 84 62 64 33 83 27 9 50 28 8 4 19 7 1 6 9 3

[出力例]

3138526 1589254 2648756 3578320 969545 89958 3228484 839606 619709 639700 329845 829610 269873 89958 499765 279868 79962 39981 189911 69967 9995 59972 89958 29986

[入力例]

50 33333 20220429

780 375 1010 1215 759 999 1038 370 381 366 40 321 1149 896 987 794 734 1143 452 579 284 276 204 635 264 47 37 768 1234 332 572 1002 320 1169 201 738 526 453 895 1090 798 774 411 1143 1086 685 194 931 1035 841

[出力例]

473163 227482 612685 737042 460424 606012 629670 224449 231122 222023 24265 194725 697005 543531 598733 481655 445258 693365 274192 351232 172280 167427 123750 385203 160147 28511 22445 465883 748568 201398 346986 607832 194118 709138 121930 447685 319082 274798 542924 661215 484082 469523 249320 693365 658788 415534 117684 564762 627851 510167

[入力例]

100 777777 1000000000

5526 6946 12205 9758 7777 11193 5678 2804 12305 6582 7081 10594 6520 12118 13896 12845 9471 5550 3456 550 3305 3349 3310 2056 12466 10186 15169 10686 8320 9999 3829 12188 7777 4003 6666 15007 824 11590 4772 7330 3839 2093 1535 7847 2997 3699 14379 5615 14035 10732 1991 439 8622 5877 14232 10831 10438 10039 7959 1907 8696 9839 10527 12638 9289 3129 4332 2765 2345 7397 12379 10160 12263 10541 9308 13260 13176 7980 5000 1285 3559 7560 956 7814 10833 5501 13091 10596 11873 15246 7777 1796 4315 12627 11846 2597 15154 3257 6950 3327

[出力例]

7104864 8930580 15692159 12546013 9999010 14391014 7300293 3605146 15820730 8462580 9104152 13620871 8382866 15580301 17866304 16515016 12177012 7135721 4443433 707144 4249290 4305861 4255719 2643431 16027730 13096299 19503019 13739157 10697154 12855870 4923005 15670301 9999010 5146719 8570580 19294734 1059430 14901443 6135435 9424295 4935862 2691003 1973573 10089010 3853290 4755862 18487304 7219293 18045018 13798299 2559860 564429 11085440 7556150 18298304 13925585 13420299 12907299 10233010 2451860 11180583 12650155 13534728 16248873 11943012 4023004 5569720 3555004 3015003 9510438 15915873 13062870 15766730 13552728 11967441 17048588 16940588 10260010 6428578 1652144 4575862 9720010 1229144 10046581 13928157 7072721 16831303 13623442 15265301 19602020 9999010 2309145 5547863 16234731 15230587 3339003 19483734 4187576 8935723 4277576

■参照サイト
AtCoder Regular Contest 118

2022年4月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題C (Rotate and Play Game) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc138/editorial/3742
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<int, int>;
using vp = vector<P>;
using vi = vector<int>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define 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 a(N);
    rep(i, N){
        int x;
        scanf("%d", &x);
        a[i].a = x;
        a[i].b = i;
    }
    
    // 2. sort.
    sort(all(a));
    
    // 3. 数列 B.
    // -> スコアも計算.
    int n = N / 2;
    LL s = 0;
    vi b(N);
    rep(i, N){
        // (N / 2)番目以内.
        if(i < n) b[a[i].b] = 1;
        
        // (N / 2)番目以降.
        if(i >= n){
            b[a[i].b] = -1;
            s += (LL)a[i].a;
        }
    }
    
    // 4. 数列 C.
    // -> 最小値となるインデックスは？
    int k = 0, c = 0, minC = 202020;
    rep(i, N){
        // 最小値更新.
        if(c + b[i] < minC){
            k = (i + 1) % N;
            minC = c + b[i];
        }
        
        // 今回分更新.
        c += b[i];
    }
    
    // 5. 出力.
    printf("%d %lld\n", k, s);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc138/editorial/3742

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<int, int>;

using vp = vector<P>;

using vi = vector<int>;

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

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

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

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

#define 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 a(N);

rep(i, N){

int x;

scanf("%d", &x);

a[i].a = x;

a[i].b = i;

}

// 2. sort.

sort(all(a));

// 3. 数列 B.

// -> スコアも計算.

int n = N / 2;

LL s = 0;

vi b(N);

rep(i, N){

// (N / 2)番目以内.

if(i < n) b[a[i].b] = 1;

// (N / 2)番目以降.

if(i >= n){

b[a[i].b] = -1;

s += (LL)a[i].a;

}

// 4. 数列 C.

// -> 最小値となるインデックスは？

int k = 0, c = 0, minC = 202020;

rep(i, N){

// 最小値更新.

if(c + b[i] < minC){

k = (i + 1) % N;

minC = c + b[i];

}

// 今回分更新.

c += b[i];

}

// 5. 出力.

printf("%d %lld\n", k, s);

return 0;

}

[入力例]
4
3 4 1 2

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

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

[入力例]
2
1 1

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

[入力例]
10
716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694

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

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

[出力例]
0 15

[入力例]
12
1013 538 447 674 357 329 568 353 696 179 645 725

[出力例]
1 4321

[入力例]
20
753 884 884 330 396 725 80 764 1234 238 692 908 853 703 243 434 990 690 86 893

[出力例]
3 8888

[入力例]
50
14171 512 35734 81510 94315 101494 96412 47947 31037 35709 1912 62854 84105 88611 77352 66746 71920 4992 19770 72343 100939 6871 5426 7667 84424 121076 91207 97000 11428 84719 7528 11896 18788 85486 2310 95702 90159 85633 73139 34002 121751 9944 32220 39321 54771 80595 112730 26602 12880 25621

[出力例]
39 2222222

[入力例]
100
8105207 10037090 14275267 4568301 18687560 2454909 7415311 16233053 21981661 19339463 12971006 14994431 21267523 20377604 3500626 16887598 13295099 39219 19554687 20238813 19575053 12852952 11243842 6103085 5668456 13795830 6646141 1073694 630192 11113919 2432917 4263296 10570151 12088838 6970113 7371129 18602246 16466811 1815862 5243355 2988231 7869573 16094918 22824922 16286695 1965058 8662710 21405609 11243782 8013341 13680674 19343455 11621265 9165034 17780853 15688446 5221807 15029016 21234126 7720848 1543581 8785894 4855221 22097803 21326531 21644858 18338488 8907523 7847179 23223607 67424 18222629 6039054 23456724 13817234 3428852 12902509 1544292 21322070 13563115 8289581 9986151 8919649 18875876 17771885 9628056 6610780 17061539 15894359 17502701 13838430 6991829 11837503 11865139 22013613 2272876 18933803 135733 22361766 3433853

[出力例]
22 888888888

[入力例]

3 4 1 2

[出力例]

1 7

※AtCoderのテストケースより

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

2 7

[入力例]

1 1

[出力例]

0 1

※AtCoderのテストケースより

[入力例]

716893678 779607519 555600775 393111963 950925400 636571379 912411962 44228139 15366410 2063694

[出力例]

7 3996409938

※AtCoderのテストケースより

[入力例]

1 2 3 4 5 6

[出力例]

0 15

[入力例]

1013 538 447 674 357 329 568 353 696 179 645 725

[出力例]

1 4321

[入力例]

753 884 884 330 396 725 80 764 1234 238 692 908 853 703 243 434 990 690 86 893

[出力例]

3 8888

[入力例]

14171 512 35734 81510 94315 101494 96412 47947 31037 35709 1912 62854 84105 88611 77352 66746 71920 4992 19770 72343 100939 6871 5426 7667 84424 121076 91207 97000 11428 84719 7528 11896 18788 85486 2310 95702 90159 85633 73139 34002 121751 9944 32220 39321 54771 80595 112730 26602 12880 25621

[出力例]

39 2222222

[入力例]

100

8105207 10037090 14275267 4568301 18687560 2454909 7415311 16233053 21981661 19339463 12971006 14994431 21267523 20377604 3500626 16887598 13295099 39219 19554687 20238813 19575053 12852952 11243842 6103085 5668456 13795830 6646141 1073694 630192 11113919 2432917 4263296 10570151 12088838 6970113 7371129 18602246 16466811 1815862 5243355 2988231 7869573 16094918 22824922 16286695 1965058 8662710 21405609 11243782 8013341 13680674 19343455 11621265 9165034 17780853 15688446 5221807 15029016 21234126 7720848 1543581 8785894 4855221 22097803 21326531 21644858 18338488 8907523 7847179 23223607 67424 18222629 6039054 23456724 13817234 3428852 12902509 1544292 21322070 13563115 8289581 9986151 8919649 18875876 17771885 9628056 6610780 17061539 15894359 17502701 13838430 6991829 11837503 11865139 22013613 2272876 18933803 135733 22361766 3433853

[出力例]

22 888888888

■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

2022年4月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 249 の問題C (Just K) ～問題D (Index Trio) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達出来た.
2. 問題Dで, 同じ整数が複数回登場する場合の数え上げ方法について, 非常に参考になったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vs v;
    rep(i, N){
        char c[33];
        scanf("%s", c);
        string s(c);
        for(auto &x : s) ++a[i][x - 'a'];
        v.pb(s);
    }
    
    // 2. カウント.
    int ans = 0;
    rep(i, 1 << N){
        // 文字列(インデックス)を選択.
        vi ss;
        rep(j, N) if(i & (1 << (N - 1 - j))) ss.pb(j);
        
        // 各文字列で出現した英文字があれば, カウント.
        int p[26];
        rep(j, 26) p[j] = 0;
        for(auto &s : ss) rep(j, 26) if(a[s][j]) ++p[j];
        
        // 種類数のカウント.
        int k = 0;
        rep(j, 26) if(p[j] == K) ++k;
        
        // 最大値更新.
        ans = max(ans, k);
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vs = vector<string>;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int a[22][26];

int main(){

// 1. 入力情報.

int N, K;

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

vs v;

rep(i, N){

char c[33];

scanf("%s", c);

string s(c);

for(auto &x : s) ++a[i][x - 'a'];

v.pb(s);

}

// 2. カウント.

int ans = 0;

rep(i, 1 << N){

// 文字列(インデックス)を選択.

vi ss;

rep(j, N) if(i & (1 << (N - 1 - j))) ss.pb(j);

// 各文字列で出現した英文字があれば, カウント.

int p[26];

rep(j, 26) p[j] = 0;

for(auto &s : ss) rep(j, 26) if(a[s][j]) ++p[j];

// 種類数のカウント.

int k = 0;

rep(j, 26) if(p[j] == K) ++k;

// 最大値更新.

ans = max(ans, k);

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2
abi
aef
bc
acg

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

[入力例]
2 2
a
b

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

[入力例]
5 2
abpqxyz
az
pq
bc
cy

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

[入力例]
10 3
mibloxjeq
aimen
gcdue
bzlh
xd
zflryd
tmd
ku
ntpz
fwi

[出力例]
6

[入力例]
15 5
efaqtsdry
rdyxq
jgwso
nuxt
ja
ukefyh
rxa
autvidzl
udzp
tjq
axtmope
cxnfw
d
jhtlmqu
apxwkyrmsu

[出力例]
5

[入力例]

4 2

abi

aef

acg

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

5 2

abpqxyz

[出力例]

※AtCoderテストケースより

[入力例]

10 3

mibloxjeq

aimen

gcdue

bzlh

zflryd

tmd

ntpz

fwi

[出力例]

[入力例]

15 5

efaqtsdry

rdyxq

jgwso

nuxt

ukefyh

rxa

autvidzl

udzp

tjq

axtmope

cxnfw

jhtlmqu

apxwkyrmsu

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc249/editorial/3786
// 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];

int main(){
    
    // 1. 入力情報.
    int N, aMax = 0;
    scanf("%d", &N);
    rep(i, N){
        int x;
        scanf("%d", &x);
        ++a[x];
        aMax = max(aMax, x);
    }
    
    // 2. 条件を満たすペアは？
    LL ans = 0;
    repx(q, 1, aMax + 1){
        repx(r, 1, aMax / q + 1){
            int p = q * r;
            ans += a[p] * a[q] * a[r];
        }
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc249/editorial/3786

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

int main(){

// 1. 入力情報.

int N, aMax = 0;

scanf("%d", &N);

rep(i, N){

int x;

scanf("%d", &x);

++a[x];

aMax = max(aMax, x);

}

// 2. 条件を満たすペアは？

LL ans = 0;

repx(q, 1, aMax + 1){

repx(r, 1, aMax / q + 1){

int p = q * r;

ans += a[p] * a[q] * a[r];

}

// 3. 出力.

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

return 0;

}

[入力例]
3
6 2 3

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

[入力例]
1
2

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

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

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

[入力例]
5
1 1 2 2 4

[出力例]
32

[入力例]
20
7 3 11 4 7 7 12 3 11 12 5 7 12 7 12 7 7 11 5 5

[出力例]
16

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

[出力例]
504

[入力例]

6 2 3

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

1 3 2 4 6 8 2 2 3 7

[出力例]

※AtCoderテストケースより

[入力例]

1 1 2 2 4

[出力例]

[入力例]

7 3 11 4 7 7 12 3 11 12 5 7 12 7 12 7 7 11 5 5

[出力例]

[入力例]

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

[出力例]

504

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

2022年4月24日2022年4月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題B (01 Generation) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 実装に苦労したものの, 解説を参考に実装して, AC版に到達出来た.
2. 解説上の整数列S は, 配列インデックスが小さい順で, 見ていくものと仮定して, 実装している.
※配列インデックスが大きい順で見ていく場合は, 不正解になるように見える.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, z = -1, one = 0;
    scanf("%d", &N);
    vi a(N);
    rep(i, N){
        scanf("%d", &a[i]);
        
        // Filp.
        if(i & 1) a[i] ^= 1;
        
        // 1 の 個数.
        one += a[i];
        
        // 先頭に最も近い 1 の場所は？
        if(z == -1 && a[i]) z = i;
    }
    
    // 2. 01文字列作成(デバッグ用).
    // -> 操作 A, 操作 B を 適当に実行して, 01文字列 を 生成.
    auto g01 = [&](int n) -> string {
        string ret = "";
        random_device seed;
        rep(i, n){
            // 乱数.
            mt19937 engine(seed());
            int r = engine() % 2;
            
            // 操作 A.
            if(r){
                string t = "0";
                rep(j, ret.size()) t.pb(((ret[j] - '0') ^ 1) + '0');
                swap(t, ret);
            }
            
            // 操作 B.
            if(!r) ret.pb('0');
        }
        return ret;
    };
    // string s = g01(111);
    // printf("%s\n", s.c_str());
    
    // 3. 例外(先頭 が, 0 でない).
    if(a[0]){
        puts("No");
        return 0;
    }
    
    // 4. 例外(Filp後 の 整数列 A が, すべて 0).
    if(!one){
        puts("Yes");
        return 0;
    }
    
    // 5. 部分列 S の 切り出し.
    deque<int> dq;
    repx(i, z, N) dq.pb(a[i]);
    
    // 6. 部分列 S の チェック.
    // -> 先頭から見ていき, 末尾(pos = (int)dq.size() - 1)まで到達できるか？.
    int zero = 0, pos = -1;
    bool ok = true;
    rep(i, (int)dq.size()){
        // 終了条件.
        if(!ok) break;
        
        // 今回分設定.
        pos = i;
        int l = pos + zero;
        
        // 現在地点 が 0.
        if(!dq[i]){
            // 長さが奇数だった.
            if(l & 1){
                if(zero < z) ++zero;
                else         ok = false;
            }
        }
        
        // 現在地点 が 1.
        if(dq[i]){
            // 長さが偶数だった.
            if(!(l & 1)){
                if(zero < z) ++zero;
                else         ok = false;
            }
        }
    }
    
    // 7. 出力.
    printf("%s\n", (ok && (pos == (int)dq.size() - 1)) ? "Yes" : "No");
    return 0;
    
}

100

101

102

103

104

105

106

107

108

// 解き直し.

// https://atcoder.jp/contests/arc138/editorial/3743

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, z = -1, one = 0;

scanf("%d", &N);

vi a(N);

rep(i, N){

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

// Filp.

if(i & 1) a[i] ^= 1;

// 1 の個数.

one += a[i];

// 先頭に最も近い 1 の場所は？

if(z == -1 && a[i]) z = i;

}

// 2. 01文字列作成(デバッグ用).

// -> 操作 A, 操作 B を適当に実行して, 01文字列を生成.

auto g01 = [&](int n) -> string {

string ret = "";

random_device seed;

rep(i, n){

// 乱数.

mt19937 engine(seed());

int r = engine() % 2;

// 操作 A.

if(r){

string t = "0";

rep(j, ret.size()) t.pb(((ret[j] - '0') ^ 1) + '0');

swap(t, ret);

}

// 操作 B.

if(!r) ret.pb('0');

}

return ret;

};

// string s = g01(111);

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

// 3. 例外(先頭が, 0 でない).

if(a[0]){

puts("No");

return 0;

}

// 4. 例外(Filp後の整数列 A が, すべて 0).

if(!one){

puts("Yes");

return 0;

}

// 5. 部分列 S の切り出し.

deque<int> dq;

repx(i, z, N) dq.pb(a[i]);

// 6. 部分列 S のチェック.

// -> 先頭から見ていき, 末尾(pos = (int)dq.size() - 1)まで到達できるか？.

int zero = 0, pos = -1;

bool ok = true;

rep(i, (int)dq.size()){

// 終了条件.

if(!ok) break;

// 今回分設定.

pos = i;

int l = pos + zero;

// 現在地点が 0.

if(!dq[i]){

// 長さが奇数だった.

if(l & 1){

if(zero < z) ++zero;

else ok = false;

}

// 現在地点が 1.

if(dq[i]){

// 長さが偶数だった.

if(!(l & 1)){

if(zero < z) ++zero;

else ok = false;

}

// 7. 出力.

printf("%s\n", (ok && (pos == (int)dq.size() - 1)) ? "Yes" : "No");

return 0;

}

[入力例]
4
0 1 1 0

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

[入力例]
4
1 0 0 0

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

[入力例]
4
0 0 0 1

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

[入力例]
4
0 1 1 1

[出力例]
Yes

[入力例]
8
0 1 1 0 0 1 1 0

[出力例]
No

[入力例]
9
0 1 1 1 0 1 0 0 0

[出力例]
No

[入力例]
12
0 1 0 1 0 1 0 1 1 1 1 1

[出力例]
Yes

[入力例]
20
0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0

[出力例]
Yes

[入力例]
30
0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0

[出力例]
No

[入力例]
111
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0

[出力例]
Yes

[入力例]
1234
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0

[出力例]
Yes

[入力例]

0 1 1 0

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 0 0 0

[出力例]

※AtCoderのテストケースより

[入力例]

0 0 0 1

[出力例]

※AtCoderのテストケースより

[入力例]

0 1 1 1

[出力例]

Yes

[入力例]

0 1 1 0 0 1 1 0

[出力例]

[入力例]

0 1 1 1 0 1 0 0 0

[出力例]

[入力例]

0 1 0 1 0 1 0 1 1 1 1 1

[出力例]

Yes

[入力例]

0 1 0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0

[出力例]

Yes

[入力例]

0 1 1 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0

[出力例]

[入力例]

111

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0

[出力例]

Yes

[入力例]

1234

0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 1 1 0 0

[出力例]

Yes

■参照サイト
大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

C++の練習を兼ねて, AtCoder Regular Contest 125 の 問題A (Dial Up) ～ 問題B (Squares) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 014 の 問題C (Closed Rooms) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題D (Differ by K bits) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 134 の 問題A (Bridge and Sheets) ～ 問題B (Reserve or Reverse) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 118 の 問題A (Tax Included Price) ～ 問題B (Village of M People) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題C (Rotate and Play Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 249 の 問題C (Just K) ～ 問題D (Index Trio) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 138 の 問題B (01 Generation) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 125 の問題A (Dial Up) ～問題B (Squares) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 014 の問題C (Closed Rooms) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題D (Differ by K bits) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 134 の問題A (Bridge and Sheets) ～問題B (Reserve or Reverse) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 118 の問題A (Tax Included Price) ～問題B (Village of M People) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題C (Rotate and Play Game) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 249 の問題C (Just K) ～問題D (Index Trio) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 138 の問題B (01 Generation) を解いてみた.