C++ | 個人用メモ帳

2021年2月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 193 の問題C (Unexpressed) ～問題D (Poker) を解いてみた.

■感想.
1. 久しぶりに, 解説見る前に, 解法の糸口が見つけることが出来たと思う.
2. 確率・組み合わせ関連は, 全般的に苦手なので, 今後も, 過去問を通して, 少しずつ理解を深めていきたいと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. a, b の 組み合わせをカウント.
    int ans = 0, n = (int)sqrt(N) + 1;
    set<LL> st;
    repx(i, 2, n){
        LL a = (LL)i;
        LL c = a;
        while(1){
            c *= a;
            if(c <= N) st.insert(c);
            else       break;
        }
    }
    
    // 3. 出力.
    printf("%lld\n", N - (LL)(st.size()));
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. a, b の組み合わせをカウント.

int ans = 0, n = (int)sqrt(N) + 1;

set<LL> st;

repx(i, 2, n){

LL a = (LL)i;

LL c = a;

while(1){

c *= a;

if(c <= N) st.insert(c);

else break;

}

// 3. 出力.

printf("%lld\n", N - (LL)(st.size()));

return 0;

}

[入力例]
8

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

[入力例]
100000

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

[入力例]
16

[出力例]
12

[入力例]
25

[出力例]
20

[入力例]
2021

[出力例]
1966

[入力例]
20210227

[出力例]
20205442

[入力例]
10000000000

[出力例]
9999897770

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100000

[出力例]

99634

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

2021

[出力例]

1966

[入力例]

20210227

[出力例]

20205442

[入力例]

10000000000

[出力例]

9999897770

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

// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int cPow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int cs[10], ct[10];

int main(){
    
    // 1. 入力情報.
    int K;
    char S[11], T[11];
    scanf("%d %s %s", &K, S, T);
    
    // 2. 表向きのカードに関する得点情報.
    rep(i, 4) cs[S[i] - '0']++, ct[T[i] - '0']++;
    
    // 3. 確定している得点情報.
    int sFix = 0, tFix = 0;
    repx(i, 1, 10) sFix += i * cPow10[cs[i]], tFix += i * cPow10[ct[i]];
    
    // 4. 5文字目の組み合わせを全探索.
    auto score = [&](int* c, int i, int base){
        int ret = base;
        ret -= i * cPow10[c[i]];
        ret += i * cPow10[c[i] + 1];
        return ret;
    };
    LL total = 0, win = 0;
    repx(i, 1, 10){
        repx(j, 1, 10){
            // 4-1. 異なる数字の場合.
            if(i != j){
                // 手札のパターンとしてありうるか.
                if(cs[i] + ct[i] >= K) continue;
                if(cs[j] + ct[j] >= K) continue;
                
                // 高橋くんの得点.
                int t = score(cs, i, sFix);
                
                // 青木くんの得点.
                int a = score(ct, j, tFix);
                
                // 評価.
                LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[j] - ct[j]);
                if(t > a) win += count;
                total += count;
            }
            
            // 4-2. 同じ数字の場合.
            if(i == j){
                // 手札のパターンとしてありうるか.
                if(cs[i] + ct[i] + 1 >= K) continue;
                
                // 高橋くんの得点.
                int t = score(cs, i, sFix);
                
                // 青木くんの得点.
                int a = score(ct, j, tFix);
                
                // 評価.
                LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[i] - ct[i] - 1);
                if(t > a) win += count;
                total += count;
            }
        }
    }
    
    // 5. 出力.
    printf("%.16lf\n", (double)win / (double)total);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const int cPow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000};

int cs[10], ct[10];

int main(){

// 1. 入力情報.

int K;

char S[11], T[11];

scanf("%d %s %s", &K, S, T);

// 2. 表向きのカードに関する得点情報.

rep(i, 4) cs[S[i] - '0']++, ct[T[i] - '0']++;

// 3. 確定している得点情報.

int sFix = 0, tFix = 0;

repx(i, 1, 10) sFix += i * cPow10[cs[i]], tFix += i * cPow10[ct[i]];

// 4. 5文字目の組み合わせを全探索.

auto score = [&](int* c, int i, int base){

int ret = base;

ret -= i * cPow10[c[i]];

ret += i * cPow10[c[i] + 1];

return ret;

};

LL total = 0, win = 0;

repx(i, 1, 10){

repx(j, 1, 10){

// 4-1. 異なる数字の場合.

if(i != j){

// 手札のパターンとしてありうるか.

if(cs[i] + ct[i] >= K) continue;

if(cs[j] + ct[j] >= K) continue;

// 高橋くんの得点.

int t = score(cs, i, sFix);

// 青木くんの得点.

int a = score(ct, j, tFix);

// 評価.

LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[j] - ct[j]);

if(t > a) win += count;

total += count;

}

// 4-2. 同じ数字の場合.

if(i == j){

// 手札のパターンとしてありうるか.

if(cs[i] + ct[i] + 1 >= K) continue;

// 高橋くんの得点.

int t = score(cs, i, sFix);

// 青木くんの得点.

int a = score(ct, j, tFix);

// 評価.

LL count = (LL)(K - cs[i] - ct[i]) * (LL)(K - cs[i] - ct[i] - 1);

if(t > a) win += count;

total += count;

}

// 5. 出力.

printf("%.16lf\n", (double)win / (double)total);

return 0;

}

[入力例]
2
1144#
2233#

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

[入力例]
2
9988#
1122#

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

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

[入力例]
6
1122#
2228#

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

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

[入力例]
100000
3226#
3597#

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

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

[入力例]
3
1234#
2345#

[出力例]
0.2076023391812865

[入力例]
5
3141#
5926#

[出力例]
0.3048048048048048

[入力例]
98765
6789#
8765#

[出力例]
0.6543216265631461

[入力例]

1144#

2233#

[出力例]

0.4444444444444444

※AtCoderテストケースより

[入力例]

9988#

1122#

[出力例]

1.0

※AtCoderテストケースより

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

1.0000000000000000

[入力例]

1122#

2228#

[出力例]

0.001932367149758454

※AtCoderテストケースより

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

0.0019323671497585

[入力例]

100000

3226#

3597#

[出力例]

0.6296297942426154

※AtCoderテストケースより

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

0.6296297942426156

[入力例]

1234#

2345#

[出力例]

0.2076023391812865

[入力例]

3141#

5926#

[出力例]

0.3048048048048048

[入力例]

98765

6789#

8765#

[出力例]

0.6543216265631461

■参照サイト
キャディプログラミングコンテスト2021(AtCoder Beginner Contest 193)

2021年2月26日2021年2月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 087 の問題E (Prefix-free Game) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, ようやく, AC版に到達できた.
2. 普段使わない自己参照構造体による実装だったため, 実装に苦労したものの, Trie木という新しい知識が増えたので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc087/editorial.pdf
// 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

struct Trie{
    int d;             // ノードまでの深さ.
    int c;             // 子ノードの個数.
    int v;             // 訪問済みフラグ.
    struct Trie *t[2]; // 子ノード.
};

Trie *makeTrie(){
    Trie *t = new Trie;
    t->d = 0;
    t->c = 0;
    t->v = 0;
    t->t[0] = NULL;
    t->t[1] = NULL;
    return t;
}

int main(){
    
    // 1. 入力情報.
    int N;
    LL L;
    scanf("%d %lld", &N, &L);
    vector<string> s;
    Trie *root = makeTrie();
    rep(i, N){
        // 1-1. 入力情報保存.
        char c[101010];
        scanf("%s", c);
        string t(c);
        s.pb(t);
        
        // 1-2. トライ木 を 一つ固定.
        Trie *cur = root;
        
        // 1-3. 固定したトライ木 に 子ノード追加.
        rep(j, t.size()){
            // j文字目が, '0' の 場合.
            if(t[j] == '0'){
                if(cur->t[0] == NULL){
                    Trie *nt = makeTrie();
                    cur->t[0] = nt;
                    cur->c++;
                }
                cur = cur->t[0];
            }
            
            // j文字目が, '1' の 場合.
            if(t[j] == '1'){
                if(cur->t[1] == NULL){
                    Trie *nt = makeTrie();
                    cur->t[1] = nt;
                    cur->c++;
                }
                cur = cur->t[1];
            }
            
            // 深さ, 訪問済みフラグ を 設定.
            cur->d = j + 1;
            cur->v = 0;
        }
    }
    
    // Trie Test.
    // ex.
    // 5 10
    // 0
    // 01
    // 101
    // 1000
    // 1001
    // 
    // root c=2 d=0                          -> OK.
    // root->t[0] c=1 d=1                    -> OK.
    // root->t[1] c=1 d=1                    -> OK.
    // root->t[0]->t[1] c=0 d=2              -> OK.
    // root->t[1]->t[0] c=2 d=2              -> OK.
    // root->t[1]->t[0]->t[0] c=2 d=3        -> OK.
    // root->t[1]->t[0]->t[1] c=0 d=3        -> OK.
    // root->t[1]->t[0]->t[0]->t[0] c=0 d=4  -> OK.
    // root->t[1]->t[0]->t[0]->t[1] c=0 d=4  -> OK.
    // 
    // printf("root c=%d d=%d\n", root->c, root->d);
    // printf("root->t[0] c=%d d=%d\n", root->t[0]->c, root->t[0]->d);
    // printf("root->t[1] c=%d d=%d\n", root->t[1]->c, root->t[1]->d);
    // printf("root->t[0]->t[1] c=%d d=%d\n", root->t[0]->t[1]->c, root->t[0]->t[1]->d);
    // printf("root->t[1]->t[0] c=%d d=%d\n", root->t[1]->t[0]->c, root->t[1]->t[0]->d);
    // printf("root->t[1]->t[0]->t[0] c=%d d=%d\n", root->t[1]->t[0]->t[0]->c, root->t[1]->t[0]->t[0]->d);
    // printf("root->t[1]->t[0]->t[1] c=%d d=%d\n", root->t[1]->t[0]->t[1]->c, root->t[1]->t[0]->t[1]->d);
    // printf("root->t[1]->t[0]->t[0]->t[0] c=%d d=%d\n", root->t[1]->t[0]->t[0]->t[0]->c, root->t[1]->t[0]->t[0]->t[0]->d);
    // printf("root->t[1]->t[0]->t[0]->t[1] c=%d d=%d\n", root->t[1]->t[0]->t[0]->t[1]->c, root->t[1]->t[0]->t[0]->t[1]->d);
    
    // 2. 初期状態の完全二分木.
    // ex.
    // 入力値が, 01010 だった場合は, 01011 が, 初期状態の完全二分木であるかを確認.
    vl level;
    for(auto &t : s){
        // 2-1. トライ木 を 一つ固定.
        Trie *cur = root;
        
        // 2-2. 固定したトライ木 の 子ノードをチェック.
        int tl = t.size();
        rep(i, tl){
            if(t[i] == '0'){
                // 訪問済みフラグの更新を行うこと.
                if(cur->c == 1 && cur->v == 0) level.pb(L - (LL)i), cur->v++;
                
                // 子ノードに移動.
                if(i < tl - 1) cur = cur->t[0];
            }
            if(t[i] == '1'){
                // 訪問済みフラグの更新を行うこと.
                if(cur->c == 1 && cur->v == 0) level.pb(L - (LL)i), cur->v++;
                
                // 子ノードに移動.
                if(i < tl - 1) cur = cur->t[1];
            }
        }
    }
    
    // 3. Grundy数 の 総XOR を 計算.
    LL ans = 0;
    for(auto &l : level){
        // 3-1. 2で最大何回割り切れるか.
        LL grundy = 1;
        while(l % grundy == 0) grundy <<= 1;
        if((grundy > 1) && (l % grundy != 0)) grundy >>= 1;
        
        // 3-2. XOR演算子.
        ans ^= grundy;
    }
    
    // 4. 出力.
    printf("%s\n", (ans == 0) ? "Bob" : "Alice");
    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

// 解き直し.

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

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

struct Trie{

int d; // ノードまでの深さ.

int c; // 子ノードの個数.

int v; // 訪問済みフラグ.

struct Trie *t[2]; // 子ノード.

};

Trie *makeTrie(){

Trie *t = new Trie;

t->d = 0;

t->c = 0;

t->v = 0;

t->t[0] = NULL;

t->t[1] = NULL;

return t;

}

int main(){

// 1. 入力情報.

int N;

LL L;

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

vector<string> s;

Trie *root = makeTrie();

rep(i, N){

// 1-1. 入力情報保存.

char c[101010];

scanf("%s", c);

string t(c);

s.pb(t);

// 1-2. トライ木を一つ固定.

Trie *cur = root;

// 1-3. 固定したトライ木に子ノード追加.

rep(j, t.size()){

// j文字目が, '0' の場合.

if(t[j] == '0'){

if(cur->t[0] == NULL){

Trie *nt = makeTrie();

cur->t[0] = nt;

cur->c++;

}

cur = cur->t[0];

}

// j文字目が, '1' の場合.

if(t[j] == '1'){

if(cur->t[1] == NULL){

Trie *nt = makeTrie();

cur->t[1] = nt;

cur->c++;

}

cur = cur->t[1];

}

// 深さ, 訪問済みフラグを設定.

cur->d = j + 1;

cur->v = 0;

}

// Trie Test.

// ex.

// 5 10

// 0

// 01

// 101

// 1000

// 1001

// root c=2 d=0 -> OK.

// root->t[0] c=1 d=1 -> OK.

// root->t[1] c=1 d=1 -> OK.

// root->t[0]->t[1] c=0 d=2 -> OK.

// root->t[1]->t[0] c=2 d=2 -> OK.

// root->t[1]->t[0]->t[0] c=2 d=3 -> OK.

// root->t[1]->t[0]->t[1] c=0 d=3 -> OK.

// root->t[1]->t[0]->t[0]->t[0] c=0 d=4 -> OK.

// root->t[1]->t[0]->t[0]->t[1] c=0 d=4 -> OK.

// printf("root c=%d d=%d\n", root->c, root->d);

// printf("root->t[0] c=%d d=%d\n", root->t[0]->c, root->t[0]->d);

// printf("root->t[1] c=%d d=%d\n", root->t[1]->c, root->t[1]->d);

// printf("root->t[0]->t[1] c=%d d=%d\n", root->t[0]->t[1]->c, root->t[0]->t[1]->d);

// printf("root->t[1]->t[0] c=%d d=%d\n", root->t[1]->t[0]->c, root->t[1]->t[0]->d);

// printf("root->t[1]->t[0]->t[0] c=%d d=%d\n", root->t[1]->t[0]->t[0]->c, root->t[1]->t[0]->t[0]->d);

// printf("root->t[1]->t[0]->t[1] c=%d d=%d\n", root->t[1]->t[0]->t[1]->c, root->t[1]->t[0]->t[1]->d);

// printf("root->t[1]->t[0]->t[0]->t[0] c=%d d=%d\n", root->t[1]->t[0]->t[0]->t[0]->c, root->t[1]->t[0]->t[0]->t[0]->d);

// printf("root->t[1]->t[0]->t[0]->t[1] c=%d d=%d\n", root->t[1]->t[0]->t[0]->t[1]->c, root->t[1]->t[0]->t[0]->t[1]->d);

// 2. 初期状態の完全二分木.

// ex.

// 入力値が, 01010 だった場合は, 01011 が, 初期状態の完全二分木であるかを確認.

vl level;

for(auto &t : s){

// 2-1. トライ木を一つ固定.

Trie *cur = root;

// 2-2. 固定したトライ木の子ノードをチェック.

int tl = t.size();

rep(i, tl){

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

// 訪問済みフラグの更新を行うこと.

if(cur->c == 1 && cur->v == 0) level.pb(L - (LL)i), cur->v++;

// 子ノードに移動.

if(i < tl - 1) cur = cur->t[0];

}

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

// 訪問済みフラグの更新を行うこと.

if(cur->c == 1 && cur->v == 0) level.pb(L - (LL)i), cur->v++;

// 子ノードに移動.

if(i < tl - 1) cur = cur->t[1];

}

// 3. Grundy数の総XOR を計算.

LL ans = 0;

for(auto &l : level){

// 3-1. 2で最大何回割り切れるか.

LL grundy = 1;

while(l % grundy == 0) grundy <<= 1;

if((grundy > 1) && (l % grundy != 0)) grundy >>= 1;

// 3-2. XOR演算子.

ans ^= grundy;

}

// 4. 出力.

printf("%s\n", (ans == 0) ? "Bob" : "Alice");

return 0;

}

[入力例]
2 2
00
01

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

[入力例]
2 2
00
11

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

[入力例]
3 3
0
10
110

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

[入力例]
2 1
0
1

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

[入力例]
1 2
11

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

[入力例]
2 3
101
11

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

[入力例]
5 10
0
01
101
1000
1001

[出力例]
Bob

[入力例]
10 15
0
01
101
1000
1001
10011
101000
10101011
1000100000
10101010101

[出力例]
Alice

[入力例]

2 2

[出力例]

Alice

※AtCoderのテストケースより

[入力例]

2 2

[出力例]

Bob

※AtCoderのテストケースより

[入力例]

3 3

110

[出力例]

Alice

※AtCoderのテストケースより

[入力例]

2 1

[出力例]

Bob

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

Alice

※AtCoderのテストケースより

[入力例]

2 3

101

[出力例]

Bob

※AtCoderのテストケースより

[入力例]

5 10

101

1000

1001

[出力例]

Bob

[入力例]

10 15

101

1000

1001

10011

101000

10101011

1000100000

10101010101

[出力例]

Alice

■参照サイト
AtCoder Regular Contest 087

2021年2月24日

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

C++の練習を兼ねて, AtCoder Regular Contest 113 の問題D (Sky Reflector) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    LL N, M, K;
    scanf("%lld %lld %lld", &N, &M, &K);
    
    // 2. 例外ケース.
    // 2-1. N が 1.
    if(N == 1){
        printf("%lld\n", mPow(K, M));
        return 0;
    }
    
    // 2-2. M が 1.
    if(M == 1){
        printf("%lld\n", mPow(K, N));
        return 0;
    }
    
    // 3. M, N が 2以上の場合.
    LL ans = 0;
    repx(x, 1, (int)(K + 1)){
        // x の N乗.
        LL a = mPow((LL)x, N);
        
        // (x - 1) の N乗.
        LL b = mPow((LL)((x - 1 + MOD) % MOD), N);
        
        // (K - x + 1) の M乗.
        LL c = mPow((LL)((K - x + 1 + MOD) % MOD), M);
        
        // 集計.
        ans = (ans + (a - b + MOD) * c) % MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc113/editorial/709

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

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

}

int main(){

// 1. 入力情報.

LL N, M, K;

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

// 2. 例外ケース.

// 2-1. N が 1.

if(N == 1){

printf("%lld\n", mPow(K, M));

return 0;

}

// 2-2. M が 1.

if(M == 1){

printf("%lld\n", mPow(K, N));

return 0;

}

// 3. M, N が 2以上の場合.

LL ans = 0;

repx(x, 1, (int)(K + 1)){

// x の N乗.

LL a = mPow((LL)x, N);

// (x - 1) の N乗.

LL b = mPow((LL)((x - 1 + MOD) % MOD), N);

// (K - x + 1) の M乗.

LL c = mPow((LL)((K - x + 1 + MOD) % MOD), M);

// 集計.

ans = (ans + (a - b + MOD) * c) % MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
2 2 2

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

[入力例]
1 1 100

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

[入力例]
31415 92653 58979

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

[入力例]
3 3 2

[出力例]
15

[入力例]
4 3 2

[出力例]
23

[入力例]
12345 23456 34567

[出力例]
134323523

[入力例]

2 2 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 1 100

[出力例]

100

※AtCoderのテストケースより

[入力例]

31415 92653 58979

[出力例]

469486242

※AtCoderのテストケースより

[入力例]

3 3 2

[出力例]

[入力例]

4 3 2

[出力例]

[入力例]

12345 23456 34567

[出力例]

134323523

■参照サイト
AtCoder Regular Contest 113

2021年2月22日

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

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

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 不思議な数え上げ方をする感じがして, 個人的には, 非常に面白い問題に感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char c[202020];
    scanf("%s", c);
    string S(c);
    
    // 2. 本質的なブロックの位置を保存.
    vi vl, vr;
    char bef = S[0], cur, befBlock = '#', curBlock = '#';
    int cnt = 1;
    S.pub('#'); // 番兵(追加).
    repx(i, 1, S.size()){
        // 2-1. 今回分更新.
        cur = S[i];
        
        // 2-2. 評価.
        if(bef == cur){
            // インクリメント.
            cnt++;
            
            // 今回のブロックを保存.
            curBlock = cur;
        }else{
            if(cnt > 1){
                // 前回のブロックと異なれば, 登録.
                if(befBlock != curBlock){
                    // 今回のブロックの出現位置を保存.
                    vl.pub(i - cnt);
                    vr.pub(i - 1);
                    
                    // 前回のブロックを保存.
                    befBlock = bef;
                }
            }
            
            // 初期化.
            cnt = 1;
        }
        
        // 2-3. 前回分更新.
        bef = cur;
    }
    S.pob(); // 番兵(削除).
    
    // 3. 各本質的なブロックに対するポテンシャルを計算し, 加算.
    LL ans = 0;
    int vlSize = vl.size(), sl = S.size();
    rep(i, vlSize){
        // 3-1. 一番最後でない本質的なブロック.
        LL p = 0;
        if(i < vlSize - 1){
            // (vr[i] + 1) ～ (vl[i + 1] - 1)文字目で, B の文字 と異なるもの.
            char B = S[vr[i]];
            repx(j, vr[i] + 1, vl[i + 1]) if(B != S[j]) p++;
            
            // vl[i + 1] ～ 文字列 S の 末尾まで.
            p += (LL)sl - (LL)vl[i + 1];
        }
        
        // 3-2. 一番最後の本質的なブロック.
        if(i == vlSize - 1){
            // (vr[i] + 1) ～ 文字列 S の 末尾までで, B の文字 と異なるもの.
            char B = S[vr[i]];
            repx(j, vr[i] + 1, sl) if(B != S[j]) p++;
        }
        
        // 3-3. 集計.
        ans += p;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc113/editorial/710

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

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

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

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

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

#define pub push_back

#define pob pop_back

int main(){

// 1. 入力情報.

char c[202020];

scanf("%s", c);

string S(c);

// 2. 本質的なブロックの位置を保存.

vi vl, vr;

char bef = S[0], cur, befBlock = '#', curBlock = '#';

int cnt = 1;

S.pub('#'); // 番兵(追加).

repx(i, 1, S.size()){

// 2-1. 今回分更新.

cur = S[i];

// 2-2. 評価.

if(bef == cur){

// インクリメント.

cnt++;

// 今回のブロックを保存.

curBlock = cur;

}else{

if(cnt > 1){

// 前回のブロックと異なれば, 登録.

if(befBlock != curBlock){

// 今回のブロックの出現位置を保存.

vl.pub(i - cnt);

vr.pub(i - 1);

// 前回のブロックを保存.

befBlock = bef;

}

// 初期化.

cnt = 1;

}

// 2-3. 前回分更新.

bef = cur;

}

S.pob(); // 番兵(削除).

// 3. 各本質的なブロックに対するポテンシャルを計算し, 加算.

LL ans = 0;

int vlSize = vl.size(), sl = S.size();

rep(i, vlSize){

// 3-1. 一番最後でない本質的なブロック.

LL p = 0;

if(i < vlSize - 1){

// (vr[i] + 1) ～ (vl[i + 1] - 1)文字目で, B の文字と異なるもの.

char B = S[vr[i]];

repx(j, vr[i] + 1, vl[i + 1]) if(B != S[j]) p++;

// vl[i + 1] ～文字列 S の末尾まで.

p += (LL)sl - (LL)vl[i + 1];

}

// 3-2. 一番最後の本質的なブロック.

if(i == vlSize - 1){

// (vr[i] + 1) ～文字列 S の末尾までで, B の文字と異なるもの.

char B = S[vr[i]];

repx(j, vr[i] + 1, sl) if(B != S[j]) p++;

}

// 3-3. 集計.

ans += p;

}

// 4. 出力.

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

return 0;

}

[入力例]
accept

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

[入力例]
atcoder

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

[入力例]
anerroroccurred

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

[入力例]
jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoroni

[出力例]
28

[入力例]
fnmgqmvyzllkwafhvhbsghxfnthbvxqxzyolcflkofndhdrdmdkyklpwperzvhupkvjfropbglivpkqijhppipnyurjaxffcsonfqmcnbbrkeszfngkwysaudpumenkyyqzokaieootkngnpunkvvo

[出力例]
332

[入力例]
gwvgigonsomqaoxokvrekkdysazfhnultxnllhknycptocjeroqogzmvltybuizxykbxzcgwjvtrptachepcxgaggzigfnmhoajcxbrqrqndiaxaeyrnuffnlvvgqnxtmazocowkeitvsqoqxbbmanpfoczjxlxhczhjvgwqsqadtiygxsiqtodiyzmifubgqjvkffgzzxmquflrsmifsujqjuhvtykkxbvnokxfnbpcnnryiyywvewsbzzrsezsnvueilqsevxacomiywlviuvjhdzvxegceocklfacloph

[出力例]
1701

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

atcoder

[出力例]

※AtCoderのテストケースより

[入力例]

anerroroccurred

[出力例]

※AtCoderのテストケースより

[入力例]

jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoroni

[出力例]

[入力例]

fnmgqmvyzllkwafhvhbsghxfnthbvxqxzyolcflkofndhdrdmdkyklpwperzvhupkvjfropbglivpkqijhppipnyurjaxffcsonfqmcnbbrkeszfngkwysaudpumenkyyqzokaieootkngnpunkvvo

[出力例]

332

[入力例]

gwvgigonsomqaoxokvrekkdysazfhnultxnllhknycptocjeroqogzmvltybuizxykbxzcgwjvtrptachepcxgaggzigfnmhoajcxbrqrqndiaxaeyrnuffnlvvgqnxtmazocowkeitvsqoqxbbmanpfoczjxlxhczhjvgwqsqadtiygxsiqtodiyzmifubgqjvkffgzzxmquflrsmifsujqjuhvtykkxbvnokxfnbpcnnryiyywvewsbzzrsezsnvueilqsevxacomiywlviuvjhdzvxegceocklfacloph

[出力例]

1701

■参照サイト
AtCoder Regular Contest 113

2021年2月21日

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

C++の練習を兼ねて, AtCoder Beginner Contest 192 の問題C (Kaprekar Number) ～問題D (Base n) を解いてみた.

■感想.
1. 久しぶりに解説見る前に, AC版に到達できたので, 良かったと思う
2. とはいえ, 正しく実装するために, 非常に苦労したように思う.
3. 二分探索の復習が出来たので, 非常に良かったと思う.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    
    // 2. a[K] を 出力.
    // -> random_01.txt などで, WA版となったため, 修正.
    // -> 降順ソートの場合は, 末尾のゼロが並ぶことが許容される(仮定を追加).
    auto f = [&](int n){
        string sg1 = to_string(n);
        sort(all(sg1));
        reverse(all(sg1));
        string sg2 = "";
        repr(i, sg1.size() - 1, 0) if(sg1[i] != '0') sg2.pb(sg1[i]);
        sort(all(sg2));
        int g1 = (sg1.size() == 0) ? 0 : stoi(sg1);
        int g2 = (sg2.size() == 0) ? 0 : stoi(sg2);
        return g1 - g2;
    };
    int ans = N;
    rep(i, K) ans = f(ans);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

#define pb push_back

int main(){

// 1. 入力情報.

int N, K;

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

// 2. a[K] を出力.

// -> random_01.txt などで, WA版となったため, 修正.

// -> 降順ソートの場合は, 末尾のゼロが並ぶことが許容される(仮定を追加).

auto f = [&](int n){

string sg1 = to_string(n);

sort(all(sg1));

reverse(all(sg1));

string sg2 = "";

repr(i, sg1.size() - 1, 0) if(sg1[i] != '0') sg2.pb(sg1[i]);

sort(all(sg2));

int g1 = (sg1.size() == 0) ? 0 : stoi(sg1);

int g2 = (sg2.size() == 0) ? 0 : stoi(sg2);

return g1 - g2;

};

int ans = N;

rep(i, K) ans = f(ans);

// 3. 出力.

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

return 0;

}

[入力例]
314 2

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

[入力例]
1000000000 100

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

[入力例]
6174 100000

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

[入力例]
100 1

[出力例]
99

[入力例]
100 2

[出力例]
0

[入力例]
2021 220

[出力例]
6174

[入力例]
20210220 1

[出力例]
22208778

[入力例]
20210220 2

[出力例]
86544432

[入力例]
20210220 22

[出力例]
43208766

[入力例]

314 2

[出力例]

693

※AtCoderテストケースより

[入力例]

1000000000 100

[出力例]

※AtCoderテストケースより

[入力例]

6174 100000

[出力例]

6174

※AtCoderテストケースより

[入力例]

100 1

[出力例]

[入力例]

100 2

[出力例]

[入力例]

2021 220

[出力例]

6174

[入力例]

20210220 1

[出力例]

22208778

[入力例]

20210220 2

[出力例]

86544432

[入力例]

20210220 22

[出力例]

43208766

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

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

int main(){
    
    // 1. 入力情報.
    char x[111];
    LL M;
    scanf("%s %lld", x, &M);
    string X(x);
    int sx = X.size();
    
    // 2. X に 含まれる最大の数字は？
    int d = 0;
    rep(i, sx) d = max(d, X[i] - '0');
    
    // 3. X が 一桁 の 場合.
    if(sx == 1){
        // -> one_digit_01.txt などで, WA版となったため, 修正.
        // printf("%lld\n", max(0LL, M - (X[0] - '0')));
        // -> X が 一桁 の 場合は, (d + 1)以上の整数を選べない？(仮定 -> 誤り).
        // puts("0");
        // -> X が 一桁 の 場合は, M が, (d + 1)以上の場合は, 1通り？(仮定 -> 誤り, one_digit_01.txtなど).
        // printf("%d\n", (M > (LL)d) ? 1 : 0);
        // -> X が 一桁 の 場合は, M が, d以上の場合は, 1通り？(仮定).
        printf("%d\n", (M >= (LL)d) ? 1 : 0);
        return 0;
    }
    
    // 4. X が 二桁 の 場合.
    if(sx == 2){
        LL s = (LL)max(X[0] - '0', X[1] - '0');
        LL e = (M - (X[1] - '0')) / (X[0] - '0');
        printf("%lld\n", max(0LL, e - s));
        return 0;
    }
    
    // 5. X が 三桁 の 場合.
    if(sx == 3){
        LL x0 = X[0] - '0', x1 = X[1] - '0', x2 = X[2] - '0';
        LL s = max({x0, x1, x2});
        // 二分探索で確認してみる.
        LL l = s, h = 1e9 + 1, m;
        while(l + 1 < h){
            m = (h + l) >> 1;
            if(m * m * x0 + m * x1 + x2 > M) h = m;
            else                             l = m;
            // printf("h=%lld l=%lld m=%lld\n", h, l, m);
        }
        LL e = l;
        printf("%lld\n", max(0LL, e - s));
        return 0;
    }
    
    // 6. M以下をカウントする.
    int ans = 0;
    auto f = [&](int l){
        // 6-1. l の 冪乗 を 計算.
        vector<LL> mPow;
        mPow.pb(1);
        repx(i, 1, sx){
            LL p = (LL)l * mPow[i - 1];
            if(p > M) return false;
            mPow.pb(p);
        }
        
        // 6-2. X を l進数 で, 表記.
        LL lx = 0;
        repr(i, sx - 1, 0){
            lx += (LL)(X[i] - '0') * mPow[sx - 1 - i];
            if(lx > M) return false;
        }
        return true;
    };
    repx(i, d + 1, 1010101){
        if(f(i)) ans++;
        else     break;
    }
    
    // 7. 出力.
    printf("%d\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--)

#define pb push_back

int main(){

// 1. 入力情報.

char x[111];

LL M;

scanf("%s %lld", x, &M);

string X(x);

int sx = X.size();

// 2. X に含まれる最大の数字は？

int d = 0;

rep(i, sx) d = max(d, X[i] - '0');

// 3. X が一桁の場合.

if(sx == 1){

// -> one_digit_01.txt などで, WA版となったため, 修正.

// printf("%lld\n", max(0LL, M - (X[0] - '0')));

// -> X が一桁の場合は, (d + 1)以上の整数を選べない？(仮定 -> 誤り).

// puts("0");

// -> X が一桁の場合は, M が, (d + 1)以上の場合は, 1通り？(仮定 -> 誤り, one_digit_01.txtなど).

// printf("%d\n", (M > (LL)d) ? 1 : 0);

// -> X が一桁の場合は, M が, d以上の場合は, 1通り？(仮定).

printf("%d\n", (M >= (LL)d) ? 1 : 0);

return 0;

}

// 4. X が二桁の場合.

if(sx == 2){

LL s = (LL)max(X[0] - '0', X[1] - '0');

LL e = (M - (X[1] - '0')) / (X[0] - '0');

printf("%lld\n", max(0LL, e - s));

return 0;

}

// 5. X が三桁の場合.

if(sx == 3){

LL x0 = X[0] - '0', x1 = X[1] - '0', x2 = X[2] - '0';

LL s = max({x0, x1, x2});

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

LL l = s, h = 1e9 + 1, m;

while(l + 1 < h){

m = (h + l) >> 1;

if(m * m * x0 + m * x1 + x2 > M) h = m;

else l = m;

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

}

LL e = l;

printf("%lld\n", max(0LL, e - s));

return 0;

}

// 6. M以下をカウントする.

int ans = 0;

auto f = [&](int l){

// 6-1. l の冪乗を計算.

vector<LL> mPow;

mPow.pb(1);

repx(i, 1, sx){

LL p = (LL)l * mPow[i - 1];

if(p > M) return false;

mPow.pb(p);

}

// 6-2. X を l進数で, 表記.

LL lx = 0;

repr(i, sx - 1, 0){

lx += (LL)(X[i] - '0') * mPow[sx - 1 - i];

if(lx > M) return false;

}

return true;

};

repx(i, d + 1, 1010101){

if(f(i)) ans++;

else break;

}

// 7. 出力.

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

return 0;

}

[入力例]
22
10

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

[入力例]
999
1500

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

[入力例]
100000000000000000000000000000000000000000000000000000000000
1000000000000000000

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

[入力例]
1
1

[出力例]
1

[入力例]
2
1

[出力例]
0

[入力例]
7
10

[出力例]
1

[入力例]
12
15

[出力例]
11

[入力例]
99
15

[出力例]
0

[入力例]
123
1000000000000000000

[出力例]
999999995

[入力例]
234
1000000000000000000

[出力例]
707106776

[入力例]
567
1000000000000000000

[出力例]
447213587

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

999

1500

[出力例]

※AtCoderテストケースより

[入力例]

100000000000000000000000000000000000000000000000000000000000

1000000000000000000

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

[出力例]

[入力例]

123

1000000000000000000

[出力例]

999999995

[入力例]

234

1000000000000000000

[出力例]

707106776

[入力例]

567

1000000000000000000

[出力例]

447213587

■参照サイト
SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)

2021年2月20日2021年2月20日

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

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

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. とはいえ, 正しく実装するために, 非常に苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc089/editorial.pdf
// 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
const int D = 2020;
int b1Cum[D][D], b2Cum[D][D], w1Cum[D][D], w2Cum[D][D], bCum[D][D], wCum[D][D];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vi b1x, b2x, b1y, b2y; // 黒 (x, y) (x + K, y + K) を保存(仮定).
    vi w1x, w2x, w1y, w2y; // 白 (x + K, y) (x, y + K) を保存(仮定).
    int K2 = 2 * K;
    rep(i, N){
        int tx, ty;
        char tc[11];
        scanf("%d %d %s", &tx, &ty, tc);
        tx %= K2;
        ty %= K2;
        
        // 黒 に 関する処理.
        if(tc[0] == 'B'){
            b1x.pb(tx);
            b1y.pb(ty);
            b2x.pb((tx + K) % K2);
            b2y.pb((ty + K) % K2);
        }
        
        // 白 に 関する処理.
        if(tc[0] == 'W'){
            w1x.pb(tx);
            w1y.pb((ty + K) % K2);
            w2x.pb((tx + K) % K2);
            w2y.pb(ty);
        }
    }
    
    // 2. N個の入力情報について, 差分を設定.
    // -> x方向, y方向を, それぞれ, 行方向, 列方向 と 見る.
    // 
    // ex.
    // 1 3
    // 2 3 B
    // -> 黒, K = 3 の 場合(①, ② を合成し, ③ を作成, mod 6 で, 読み替え).
    // ①(2, 3)       ②(2 + 3, 3 + 3)   ③
    //  0 0 0 0 0 0    1 1 1 0 0 0        1 1 1 0 0 0
    //  0 0 0 0 0 0    1 1 1 0 0 0        1 1 1 0 0 0
    //  0 0 0 1 1 1    0 0 0 0 0 0        0 0 0 1 1 1
    //  0 0 0 1 1 1    0 0 0 0 0 0        0 0 0 1 1 1
    //  0 0 0 1 1 1    0 0 0 0 0 0        0 0 0 1 1 1
    //  0 0 0 0 0 0    1 1 1 0 0 0        1 1 1 0 0 0
    //
    // ex.
    // 1 4
    // 1 2 W
    // -> 白, K = 4 の 場合(①, ② を合成し, ③ を作成, mod 8 で, 読み替え).
    // ①(1 + 4, 2)       ②(1, 2 + 4)       ③
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    // 
    auto f = [&](vi &px, vi &py, int l, int (&pCum)[D][D]){
        rep(i, l){
            int x = px[i], y = py[i];
            int xk = (x + K) % K2, yk = (y + K) % K2;
            // 2-1. 左上(解説上の左下, 基準となる座標(x, y)と見る).
            pCum[x][y]++;
            
            // 2-2. 右下(解説上の右上).
            if(x + K < K2){
                if(y + K < K2) pCum[xk][yk]++;
                if(y + K >= K2){
                    pCum[xk][0]--;
                    pCum[xk][yk]++;
                }
            }
            if(x + K >= K2){
                if(y + K < K2){
                    pCum[0][yk]--;
                    pCum[xk][yk]++;
                }
                if(y + K >= K2){
                    pCum[0][0]++;
                    pCum[xk][0]--;
                    pCum[0][yk]--;
                    pCum[xk][yk]++;
                }
            }
            
            // 2-3. 右上(解説上の左上).
            if(y + K < K2) pCum[x][yk]--;
            if(y + K >= K2){
                pCum[x][0]++;
                pCum[x][yk]--;
            }
            
            // 2-4. 左下(解説上の右下).
            if(x + K < K2) pCum[xk][y]--;
            if(x + K >= K2){
                pCum[0][y]++;
                pCum[xk][y]--;
            }
        }
        return;
    };
    f(b1x, b1y, b1x.size(), b1Cum);
    f(b2x, b2y, b2x.size(), b2Cum);
    f(w1x, w1y, w1x.size(), w1Cum);
    f(w2x, w2y, w2x.size(), w2Cum);
    
    // 3. 黒, 白 の 合計値を保存.
    // -> 2. で目標としていた, ③ を 算出するための準備処理.
    rep(i, K2 + 1) rep(j, K2 + 1) bCum[i][j] = b1Cum[i][j] + b2Cum[i][j];
    rep(i, K2 + 1) rep(j, K2 + 1) wCum[i][j] = w1Cum[i][j] + w2Cum[i][j];
    
    // 4. 累積和.
    auto g = [&](int (&pCum)[D][D]){
        // 3-1. 列方向.
        rep(i, K2) rep(j, K2) pCum[i][j + 1] += pCum[i][j];
        
        // 3-2. 行方向.
        rep(j, K2) rep(i, K2) pCum[i + 1][j] += pCum[i][j];
        return;
    };
    g(bCum);
    g(wCum);
    
    // 5. 最大値は？
    int ans = 0;
    rep(i, K2 + 1) rep(j, K2 + 1) ans = max(ans, bCum[i][j] + wCum[i][j]);
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

// 解き直し.

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

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

const int D = 2020;

int b1Cum[D][D], b2Cum[D][D], w1Cum[D][D], w2Cum[D][D], bCum[D][D], wCum[D][D];

int main(){

// 1. 入力情報.

int N, K;

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

vi b1x, b2x, b1y, b2y; // 黒 (x, y) (x + K, y + K) を保存(仮定).

vi w1x, w2x, w1y, w2y; // 白 (x + K, y) (x, y + K) を保存(仮定).

int K2 = 2 * K;

rep(i, N){

int tx, ty;

char tc[11];

scanf("%d %d %s", &tx, &ty, tc);

tx %= K2;

ty %= K2;

// 黒に関する処理.

if(tc[0] == 'B'){

b1x.pb(tx);

b1y.pb(ty);

b2x.pb((tx + K) % K2);

b2y.pb((ty + K) % K2);

}

// 白に関する処理.

if(tc[0] == 'W'){

w1x.pb(tx);

w1y.pb((ty + K) % K2);

w2x.pb((tx + K) % K2);

w2y.pb(ty);

}

// 2. N個の入力情報について, 差分を設定.

// -> x方向, y方向を, それぞれ, 行方向, 列方向と見る.

// ex.

// 1 3

// 2 3 B

// -> 黒, K = 3 の場合(①, ② を合成し, ③ を作成, mod 6 で, 読み替え).

// ①(2, 3) ②(2 + 3, 3 + 3) ③

// 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0

// 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1

// 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0

// ex.

// 1 4

// 1 2 W

// -> 白, K = 4 の場合(①, ② を合成し, ③ を作成, mod 8 で, 読み替え).

// ①(1 + 4, 2) ②(1, 2 + 4) ③

// 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0

// 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1

// 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0

auto f = [&](vi &px, vi &py, int l, int (&pCum)[D][D]){

rep(i, l){

int x = px[i], y = py[i];

int xk = (x + K) % K2, yk = (y + K) % K2;

// 2-1. 左上(解説上の左下, 基準となる座標(x, y)と見る).

pCum[x][y]++;

// 2-2. 右下(解説上の右上).

if(x + K < K2){

if(y + K < K2) pCum[xk][yk]++;

if(y + K >= K2){

pCum[xk][0]--;

pCum[xk][yk]++;

}

if(x + K >= K2){

if(y + K < K2){

pCum[0][yk]--;

pCum[xk][yk]++;

}

if(y + K >= K2){

pCum[0][0]++;

pCum[xk][0]--;

pCum[0][yk]--;

pCum[xk][yk]++;

}

// 2-3. 右上(解説上の左上).

if(y + K < K2) pCum[x][yk]--;

if(y + K >= K2){

pCum[x][0]++;

pCum[x][yk]--;

}

// 2-4. 左下(解説上の右下).

if(x + K < K2) pCum[xk][y]--;

if(x + K >= K2){

pCum[0][y]++;

pCum[xk][y]--;

}

return;

};

f(b1x, b1y, b1x.size(), b1Cum);

f(b2x, b2y, b2x.size(), b2Cum);

f(w1x, w1y, w1x.size(), w1Cum);

f(w2x, w2y, w2x.size(), w2Cum);

// 3. 黒, 白の合計値を保存.

// -> 2. で目標としていた, ③ を算出するための準備処理.

rep(i, K2 + 1) rep(j, K2 + 1) bCum[i][j] = b1Cum[i][j] + b2Cum[i][j];

rep(i, K2 + 1) rep(j, K2 + 1) wCum[i][j] = w1Cum[i][j] + w2Cum[i][j];

// 4. 累積和.

auto g = [&](int (&pCum)[D][D]){

// 3-1. 列方向.

rep(i, K2) rep(j, K2) pCum[i][j + 1] += pCum[i][j];

// 3-2. 行方向.

rep(j, K2) rep(i, K2) pCum[i + 1][j] += pCum[i][j];

return;

};

g(bCum);

g(wCum);

// 5. 最大値は？

int ans = 0;

rep(i, K2 + 1) rep(j, K2 + 1) ans = max(ans, bCum[i][j] + wCum[i][j]);

// 6. 出力.

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

return 0;

}

■C++版プログラム(問題D／AC版, すこし高速化版).

// コメント修正, 高速化.
// 解き直し.
// https://img.atcoder.jp/arc089/editorial.pdf
// 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
const int D = 2020;
int bCum[D][D], wCum[D][D];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    vi bx, by; // 黒 (x, y) (x + K, y + K) を保存(仮定).
    vi wx, wy; // 白 (x + K, y) (x, y + K) を保存(仮定).
    int K2 = 2 * K;
    rep(i, N){
        int tx, ty;
        char tc[11];
        scanf("%d %d %s", &tx, &ty, tc);
        tx %= K2;
        ty %= K2;
        
        // 1-1. 黒 に 関する処理.
        if(tc[0] == 'B'){
            bx.pb(tx);
            by.pb(ty);
            bx.pb((tx + K) % K2);
            by.pb((ty + K) % K2);
        }
        
        // 1-2. 白 に 関する処理.
        if(tc[0] == 'W'){
            wx.pb(tx);
            wy.pb((ty + K) % K2);
            wx.pb((tx + K) % K2);
            wy.pb(ty);
        }
    }
    
    // 2. N個の入力情報について, 差分を設定.
    // -> x方向, y方向を, それぞれ, 行方向, 列方向 と 見る.
    // -> 黒同士, 白同士 であれば, まとめて計算できるはず(仮定).
    // 
    // ex.
    // 1 3
    // 2 3 B
    // -> 黒, K = 3 の 場合(①, ② を合成し, ③ を作成, mod 6 で, 読み替え).
    // ①(2, 3)       ②(2 + 3, 3 + 3)   ③
    //  0 0 0 0 0 0    1 1 1 0 0 0        1 1 1 0 0 0
    //  0 0 0 0 0 0    1 1 1 0 0 0        1 1 1 0 0 0
    //  0 0 0 1 1 1    0 0 0 0 0 0        0 0 0 1 1 1
    //  0 0 0 1 1 1    0 0 0 0 0 0        0 0 0 1 1 1
    //  0 0 0 1 1 1    0 0 0 0 0 0        0 0 0 1 1 1
    //  0 0 0 0 0 0    1 1 1 0 0 0        1 1 1 0 0 0
    //
    // ex.
    // 1 4
    // 1 2 W
    // -> 白, K = 4 の 場合(①, ② を合成し, ③ を作成, mod 8 で, 読み替え).
    // ①(1 + 4, 2)       ②(1, 2 + 4)       ③
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 0 0 0 0 0 0    1 1 0 0 0 0 1 1   1 1 0 0 0 0 1 1
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    //  0 0 1 1 1 1 0 0    0 0 0 0 0 0 0 0   0 0 1 1 1 1 0 0
    // 
    auto f = [&](vi &px, vi &py, int l, int (&pCum)[D][D]){
        rep(i, l){
            int x = px[i], y = py[i];
            int xk = (x + K) % K2, yk = (y + K) % K2;
            // 2-1. 左上(解説上の左下, 基準となる座標(x, y)と見る).
            pCum[x][y]++;
            
            // 2-2. 右下(解説上の右上).
            if(x + K < K2){
                if(y + K < K2) pCum[xk][yk]++;
                if(y + K >= K2){
                    pCum[xk][0]--;
                    pCum[xk][yk]++;
                }
            }
            if(x + K >= K2){
                if(y + K < K2){
                    pCum[0][yk]--;
                    pCum[xk][yk]++;
                }
                if(y + K >= K2){
                    pCum[0][0]++;
                    pCum[xk][0]--;
                    pCum[0][yk]--;
                    pCum[xk][yk]++;
                }
            }
            
            // 2-3. 右上(解説上の左上).
            if(y + K < K2) pCum[x][yk]--;
            if(y + K >= K2){
                pCum[x][0]++;
                pCum[x][yk]--;
            }
            
            // 2-4. 左下(解説上の右下).
            if(x + K < K2) pCum[xk][y]--;
            if(x + K >= K2){
                pCum[0][y]++;
                pCum[xk][y]--;
            }
        }
        return;
    };
    f(bx, by, bx.size(), bCum);
    f(wx, wy, wx.size(), wCum);
    
    // 3. 累積和.
    auto g = [&](int (&pCum)[D][D]){
        // 3-1. 列方向.
        rep(i, K2) rep(j, K2) pCum[i][j + 1] += pCum[i][j];
        
        // 3-2. 行方向.
        rep(j, K2) rep(i, K2) pCum[i + 1][j] += pCum[i][j];
        return;
    };
    g(bCum);
    g(wCum);
    
    // 4. 最大値は？
    int ans = 0;
    rep(i, K2 + 1) rep(j, K2 + 1) ans = max(ans, bCum[i][j] + wCum[i][j]);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

// コメント修正, 高速化.

// 解き直し.

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

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

const int D = 2020;

int bCum[D][D], wCum[D][D];

int main(){

// 1. 入力情報.

int N, K;

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

vi bx, by; // 黒 (x, y) (x + K, y + K) を保存(仮定).

vi wx, wy; // 白 (x + K, y) (x, y + K) を保存(仮定).

int K2 = 2 * K;

rep(i, N){

int tx, ty;

char tc[11];

scanf("%d %d %s", &tx, &ty, tc);

tx %= K2;

ty %= K2;

// 1-1. 黒に関する処理.

if(tc[0] == 'B'){

bx.pb(tx);

by.pb(ty);

bx.pb((tx + K) % K2);

by.pb((ty + K) % K2);

}

// 1-2. 白に関する処理.

if(tc[0] == 'W'){

wx.pb(tx);

wy.pb((ty + K) % K2);

wx.pb((tx + K) % K2);

wy.pb(ty);

}

// 2. N個の入力情報について, 差分を設定.

// -> x方向, y方向を, それぞれ, 行方向, 列方向と見る.

// -> 黒同士, 白同士であれば, まとめて計算できるはず(仮定).

// ex.

// 1 3

// 2 3 B

// -> 黒, K = 3 の場合(①, ② を合成し, ③ を作成, mod 6 で, 読み替え).

// ①(2, 3) ②(2 + 3, 3 + 3) ③

// 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0

// 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1

// 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0

// ex.

// 1 4

// 1 2 W

// -> 白, K = 4 の場合(①, ② を合成し, ③ を作成, mod 8 で, 読み替え).

// ①(1 + 4, 2) ②(1, 2 + 4) ③

// 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0

// 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1

// 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0

auto f = [&](vi &px, vi &py, int l, int (&pCum)[D][D]){

rep(i, l){

int x = px[i], y = py[i];

int xk = (x + K) % K2, yk = (y + K) % K2;

// 2-1. 左上(解説上の左下, 基準となる座標(x, y)と見る).

pCum[x][y]++;

// 2-2. 右下(解説上の右上).

if(x + K < K2){

if(y + K < K2) pCum[xk][yk]++;

if(y + K >= K2){

pCum[xk][0]--;

pCum[xk][yk]++;

}

if(x + K >= K2){

if(y + K < K2){

pCum[0][yk]--;

pCum[xk][yk]++;

}

if(y + K >= K2){

pCum[0][0]++;

pCum[xk][0]--;

pCum[0][yk]--;

pCum[xk][yk]++;

}

// 2-3. 右上(解説上の左上).

if(y + K < K2) pCum[x][yk]--;

if(y + K >= K2){

pCum[x][0]++;

pCum[x][yk]--;

}

// 2-4. 左下(解説上の右下).

if(x + K < K2) pCum[xk][y]--;

if(x + K >= K2){

pCum[0][y]++;

pCum[xk][y]--;

}

return;

};

f(bx, by, bx.size(), bCum);

f(wx, wy, wx.size(), wCum);

// 3. 累積和.

auto g = [&](int (&pCum)[D][D]){

// 3-1. 列方向.

rep(i, K2) rep(j, K2) pCum[i][j + 1] += pCum[i][j];

// 3-2. 行方向.

rep(j, K2) rep(i, K2) pCum[i + 1][j] += pCum[i][j];

return;

};

g(bCum);

g(wCum);

// 4. 最大値は？

int ans = 0;

rep(i, K2 + 1) rep(j, K2 + 1) ans = max(ans, bCum[i][j] + wCum[i][j]);

// 5. 出力.

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

return 0;

}

[入力例]
4 3
0 1 W
1 2 W
5 3 B
5 4 B

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

[入力例]
2 1000
0 0 B
0 1 W

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

[入力例]
6 2
1 2 B
2 1 W
2 2 B
1 0 B
0 6 W
4 5 W

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

[入力例]
25 7
82 65 B
89 120 W
49 95 B
22 121 B
116 64 W
16 87 W
92 108 B
53 90 W
87 65 B
37 78 B
115 26 B
30 106 W
103 9 W
107 46 B
62 71 B
75 101 W
88 51 W
113 5 B
93 89 B
67 115 W
71 99 B
54 121 W
78 17 B
121 55 B
31 113 W

[出力例]
17

[入力例]

4 3

0 1 W

1 2 W

5 3 B

5 4 B

[出力例]

※AtCoderテストケースより

[入力例]

2 1000

0 0 B

0 1 W

[出力例]

※AtCoderテストケースより

[入力例]

6 2

1 2 B

2 1 W

2 2 B

1 0 B

0 6 W

4 5 W

[出力例]

※AtCoderテストケースより

[入力例]

25 7

82 65 B

89 120 W

49 95 B

22 121 B

116 64 W

16 87 W

92 108 B

53 90 W

87 65 B

37 78 B

115 26 B

30 106 W

103 9 W

107 46 B

62 71 B

75 101 W

88 51 W

113 5 B

93 89 B

67 115 W

71 99 B

54 121 W

78 17 B

121 55 B

31 113 W

[出力例]

■参照サイト
AtCoder Regular Contest 089

2021年2月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 094 の問題D (Binomial Coefficients)を解いてみた.

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

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

// 解き直し.
// https://img.atcoder.jp/arc095/editorial.pdf
// 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;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. sort.
    sort(a, a + N);
    
    // 3. 最大値は？
    LL n = a[N - 1];
    
    // 4. 最大値の半分 に 近い整数 を チェック.
    // 4-1. 基準となる場所を決める.
    int h = n / 2;
    int at = lower_bound(a, a + N, h) - a;
    LL r = a[at];
    
    // 4-2. 基準となる場所から, index が 1つ小さい場合.
    if(at){
        LL d1 = abs(h - a[at]);
        LL d2 = abs(h - a[at - 1]);
        if(d2 < d1 || n == r) r = a[at - 1]; // sample2.txt の WA対策.
    }
    
    // 4-3. 基準となる場所から, index が 1つ大きい場合.
    if(at < N - 1){
        LL d1 = abs(h - a[at]);
        LL d2 = abs(h - a[at + 1]);
        if(d2 < d1) r = a[at + 1];
    }
    
    // 5. 出力.
    printf("%lld %lld\n", n, r);
    return 0;
    
}

// 解き直し.

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

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

scanf("%d", &N);

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

// 2. sort.

sort(a, a + N);

// 3. 最大値は？

LL n = a[N - 1];

// 4. 最大値の半分に近い整数をチェック.

// 4-1. 基準となる場所を決める.

int h = n / 2;

int at = lower_bound(a, a + N, h) - a;

LL r = a[at];

// 4-2. 基準となる場所から, index が 1つ小さい場合.

if(at){

LL d1 = abs(h - a[at]);

LL d2 = abs(h - a[at - 1]);

if(d2 < d1 || n == r) r = a[at - 1]; // sample2.txt の WA対策.

}

// 4-3. 基準となる場所から, index が 1つ大きい場合.

if(at < N - 1){

LL d1 = abs(h - a[at]);

LL d2 = abs(h - a[at + 1]);

if(d2 < d1) r = a[at + 1];

}

// 5. 出力.

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

return 0;

}

[入力例]
5
6 9 4 2 11

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

[入力例]
2
100 0

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

[入力例]
2
99 100

[出力例]
100 99

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

[出力例]
15 7

[入力例]
12
8 1 3 16 7 13 15 18 11 9 6 12

[出力例]
18 9

[入力例]
12
8 1 3 16 7 13 15 18 11 5 6 12

[出力例]
18 8

[入力例]

6 9 4 2 11

[出力例]

11 6

※AtCoderテストケースより

[入力例]

100 0

[出力例]

100 0

※AtCoderテストケースより

[入力例]

99 100

[出力例]

100 99

[入力例]

12 5 13 4 8 6 1 9 7 15

[出力例]

15 7

[入力例]

8 1 3 16 7 13 15 18 11 9 6 12

[出力例]

18 9

[入力例]

8 1 3 16 7 13 15 18 11 5 6 12

[出力例]

18 8

■参照サイト
AtCoder Beginner Contest 094

2021年2月17日

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

C++の練習を兼ねて, AtCoder Beginner Contest 074 の問題D (Restoring Road Network)を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. Warshall–Floyd法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc083/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const int MAX = 333;
const LL INF = 101010101010101010;
LL a[MAX][MAX], b[MAX][MAX];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, MAX) rep(j, MAX) if(i != j) b[i][j] = INF;
    rep(i, N) rep(j, N) scanf("%lld", &a[i][j]);
    
    // 2. Warshall–Floyd法(※各頂点間の最短距離を保存).
    rep(k, N) rep(i, N) rep(j, N) b[i][j] = min(b[i][j], a[i][k] + a[k][j]);
    
    // 3. 条件を満たす道路の構造が存在するか？
    bool ok = true;
    rep(i, N){
        rep(j, N){
            if(b[i][j] < a[i][j]){
                ok = false;
                break;
            }
        }
    }
    
    // 4. 条件を満たさない場合.
    if(!ok){
        puts("-1");
        return 0;
    }
    
    // 5. 道路の長さの和の最小値を計算.
    LL ans = 0;
    rep(i, N){
        repx(j, i + 1, N){
            bool f = false;
            rep(k, N){
                if(k != i && k != j && a[i][j] == b[i][k] + b[k][j]){
                    f = true;
                    break;
                }
            }
            // 最短距離が, 表 A に存在している場合は, 加算しない(※).
            // ※Warshall–Floyd法で求めた経路で到達できるため.
            if(!f) ans += b[i][j];
        }
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

const int MAX = 333;

const LL INF = 101010101010101010;

LL a[MAX][MAX], b[MAX][MAX];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, MAX) rep(j, MAX) if(i != j) b[i][j] = INF;

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

// 2. Warshall–Floyd法(※各頂点間の最短距離を保存).

rep(k, N) rep(i, N) rep(j, N) b[i][j] = min(b[i][j], a[i][k] + a[k][j]);

// 3. 条件を満たす道路の構造が存在するか？

bool ok = true;

rep(i, N){

rep(j, N){

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

ok = false;

break;

}

// 4. 条件を満たさない場合.

if(!ok){

puts("-1");

return 0;

}

// 5. 道路の長さの和の最小値を計算.

LL ans = 0;

rep(i, N){

repx(j, i + 1, N){

bool f = false;

rep(k, N){

if(k != i && k != j && a[i][j] == b[i][k] + b[k][j]){

f = true;

break;

}

// 最短距離が, 表 A に存在している場合は, 加算しない(※).

// ※Warshall–Floyd法で求めた経路で到達できるため.

if(!f) ans += b[i][j];

}

// 6. 出力.

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

return 0;

}

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

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

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

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

[入力例]
5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0

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

[入力例]
3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0

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

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

[出力例]
-1

[入力例]
5
0 5 8 12 15
5 0 3 7 10
8 3 0 4 7
12 7 4 0 3
15 10 7 3 0

[出力例]
15

[入力例]

0 1 3

1 0 2

3 2 0

[出力例]

※AtCoderテストケースより

[入力例]

0 1 3

1 0 1

3 1 0

[出力例]

-1

※AtCoderテストケースより

[入力例]

0 21 18 11 28

21 0 13 10 26

18 13 0 23 13

11 10 23 0 17

28 26 13 17 0

[出力例]

※AtCoderテストケースより

[入力例]

0 1000000000 1000000000

1000000000 0 1000000000

1000000000 1000000000 0

[出力例]

3000000000

※AtCoderテストケースより

[入力例]

0 3 6 7 9

3 0 3 2 6

6 3 0 1 3

7 2 1 0 2

9 6 3 2 0

[出力例]

-1

[入力例]

0 5 8 12 15

5 0 3 7 10

8 3 0 4 7

12 7 4 0 3

15 10 7 3 0

[出力例]

■参照サイト
AtCoder Beginner Contest 074

2021年2月14日2021年2月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題D (トレジャーハント)を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/abc035
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
const LL INF = 101010101010101010;

struct edge{
    int n; // 次の頂点.
    LL c;  // 移動時間.
    bool operator < (const edge &E) const{ return c > E.c; }
};

LL a[101010];  // 所持金.
LL d1[101010]; // 1 -> i の 最短移動時間.
LL di[101010]; // i -> 1 の 最短移動時間.
vector<edge> G[2][101010]; // 第一成分: 往路／復路, 第二成分: 各グラフ情報.

// https://ja.wikipedia.org/wiki/ダイクストラ法
// @param s: 今回探索する頂点番号.
// @param d: 最短距離を保存.
// @param f: 往路／復路の区分.
// @return: 特に無し.
void dijkstra(int s, LL* d, int f){
    // 1. 初期化.
    priority_queue<edge> pq;
    
    // 2. 始点設定.
    d[s] = 0;
    pq.push({s, 0LL});
    
    // 3. キュー pq が 空になるまで, 探索.
    while(!pq.empty()){
        // 4. 探索を継続するために, 頂点を取得.
        edge e = pq.top();
        pq.pop();
        int cn = e.n;
        LL cc = e.c;
        
        // 5. 各隣接する頂点について, 移動時間の確認／更新.
        rep(i, G[f][cn].size()){
            edge ne = G[f][cn][i];
            int nn = ne.n;
            LL nc = cc + ne.c;
            
            // 6. 移動時間更新.
            if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
        }
    }
    return;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    LL T, ans = 0;
    scanf("%d %d %lld", &N, &M, &T);
    rep(i, N) scanf("%lld", &a[i]);
    rep(i, M){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        a--, b--;
        
        // 往路.
        edge ef;
        ef.n = b;
        ef.c = c;
        G[0][a].pb(ef);
        
        // 復路.
        edge eb;
        eb.n = a;
        eb.c = c;
        G[1][b].pb(eb);
    }
    rep(i, 101010) d1[i] = di[i] = INF;
    
    // 2. 頂点 1 から 各頂点までの, 最短経路(往路／復路)を求める.
    dijkstra(0, d1, 0);
    dijkstra(0, di, 1);
    
    // 3. 所持金の最大値は？
    rep(i, N){
        LL m = a[i] * max(0LL, T - d1[i] - di[i]);
        ans = max(ans, m);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://www.slideshare.net/chokudai/abc035

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

#define pb push_back

const LL INF = 101010101010101010;

struct edge{

int n; // 次の頂点.

LL c; // 移動時間.

bool operator < (const edge &E) const{ return c > E.c; }

};

LL a[101010]; // 所持金.

LL d1[101010]; // 1 -> i の最短移動時間.

LL di[101010]; // i -> 1 の最短移動時間.

vector<edge> G[2][101010]; // 第一成分: 往路／復路, 第二成分: 各グラフ情報.

// https://ja.wikipedia.org/wiki/ダイクストラ法

// @param s: 今回探索する頂点番号.

// @param d: 最短距離を保存.

// @param f: 往路／復路の区分.

// @return: 特に無し.

void dijkstra(int s, LL* d, int f){

// 1. 初期化.

priority_queue<edge> pq;

// 2. 始点設定.

d[s] = 0;

pq.push({s, 0LL});

// 3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 5. 各隣接する頂点について, 移動時間の確認／更新.

rep(i, G[f][cn].size()){

edge ne = G[f][cn][i];

int nn = ne.n;

LL nc = cc + ne.c;

// 6. 移動時間更新.

if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});

}

return;

}

int main(){

// 1. 入力情報.

int N, M;

LL T, ans = 0;

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

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

rep(i, M){

int a, b;

LL c;

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

a--, b--;

// 往路.

edge ef;

ef.n = b;

ef.c = c;

G[0][a].pb(ef);

// 復路.

edge eb;

eb.n = a;

eb.c = c;

G[1][b].pb(eb);

}

rep(i, 101010) d1[i] = di[i] = INF;

// 2. 頂点 1 から各頂点までの, 最短経路(往路／復路)を求める.

dijkstra(0, d1, 0);

dijkstra(0, di, 1);

// 3. 所持金の最大値は？

rep(i, N){

LL m = a[i] * max(0LL, T - d1[i] - di[i]);

ans = max(ans, m);

}

// 4. 出力.

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

return 0;

}

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

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

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

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

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

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

[入力例]
11 20 345
7 1 7 1 4 7 5 2 7 2 11
6 4 7
8 3 19
2 8 15
6 8 2
7 10 9
8 11 8
4 9 17
6 7 10
9 10 3
8 5 18
9 8 25
11 7 24
3 7 17
11 6 2
2 7 16
7 5 24
5 9 2
4 10 24
4 1 1
7 3 3

[出力例]
2415

[入力例]
23 32 2021
3 15 14 17 1 4 21 19 41 52 83 77 9 16 70 10 27 55 66 22 15 13 61
1 10 38
16 14 37
5 1 55
19 7 42
20 23 36
13 1 50
5 22 31
21 9 58
10 12 58
19 2 29
20 13 65
2 19 73
17 2 61
22 5 24
15 16 29
10 9 72
12 15 61
4 21 36
15 12 56
16 6 37
12 7 71
1 5 40
7 1 25
10 2 50
20 15 34
1 3 39
17 20 23
10 7 38
17 14 35
7 9 60
3 5 59
21 8 53

[出力例]
140833

100

101

102

103

104

105

106

107

108

[入力例]

2 2 5

1 3

1 2 2

2 1 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2 3

1 3

1 2 2

2 1 1

[出力例]

※AtCoderテストケースより

[入力例]

8 15 120

1 2 6 16 1 3 11 9

1 8 1

7 3 14

8 2 13

3 5 4

5 7 5

6 4 1

6 8 17

7 8 5

1 4 2

4 7 1

6 1 3

3 1 10

2 6 5

2 4 12

5 1 30

[出力例]

1488

※AtCoderテストケースより

[入力例]

11 20 345

7 1 7 1 4 7 5 2 7 2 11

6 4 7

8 3 19

2 8 15

6 8 2

7 10 9

8 11 8

4 9 17

6 7 10

9 10 3

8 5 18

9 8 25

11 7 24

3 7 17

11 6 2

2 7 16

7 5 24

5 9 2

4 10 24

4 1 1

7 3 3

[出力例]

2415

[入力例]

23 32 2021

3 15 14 17 1 4 21 19 41 52 83 77 9 16 70 10 27 55 66 22 15 13 61

1 10 38

16 14 37

5 1 55

19 7 42

20 23 36

13 1 50

5 22 31

21 9 58

10 12 58

19 2 29

20 13 65

2 19 73

17 2 61

22 5 24

15 16 29

10 9 72

12 15 61

4 21 36

15 12 56

16 6 37

12 7 71

1 5 40

7 1 25

10 2 50

20 15 34

1 3 39

17 20 23

10 7 38

17 14 35

7 9 60

3 5 59

21 8 53

[出力例]

140833

■参照サイト
AtCoder Beginner Contest 035

2021年2月13日

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

C++の練習を兼ねて, AtCoder Regular Contest 087 の問題D (FT Robot)を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 個人的には, 不思議な感じがする, 非常に面白い問題に感じた.
3. 苦手な, dpの訓練が出来たので, 非常に良かったと思った.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc087/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
// const int MAX = 22;
const int MAX = 20202;
const int HMAX = MAX / 2;
bool dpX[2][MAX], dpY[2][MAX];

int main(){
    
    // 1. 入力情報.
    char c[8080];
    int x, y;
    scanf("%s %d %d", c, &x, &y);
    string S(c);
    S.pb('T'); // 番兵.
    
    // 2. 命令列を分割.
    vs o;
    int sl = S.size();
    string t;
    rep(i, sl){
        int tl = t.size();
        if(S[i] == 'T') o.pb(t), t = "";
        if(S[i] == 'F') t.pb(S[i]);
    }
    // for(auto &p : o) printf("%s\n", p.c_str());
    
    // 3. dpX, dpY更新.
    int ol = o.size();
    if(ol){
        dpX[0][HMAX + o[0].size()] = true;
        dpY[0][HMAX] = true;
    }
    repx(i, 1, ol){
        int oil = o[i].size();
        // 3-1. 左右.
        if(!(i & 1)){
            // 3-2. 今回情報初期化.
            rep(j, MAX) dpX[1][j] = false;
            
            // 3-3. dpX更新.
            rep(j, MAX){
                if(j - oil >= 0)  dpX[1][j - oil] |= dpX[0][j];
                if(j + oil < MAX) dpX[1][j + oil] |= dpX[0][j];
            }
            
            // 3-4. 前回情報更新.
            rep(j, MAX) dpX[0][j] = dpX[1][j];
        }
        
        // 3-5. 上下.
        if(i & 1){
            // 3-6. 今回情報初期化.
            rep(j, MAX) dpY[1][j] = false;
            
            // 3-7. dpY更新..
            rep(j, MAX){
                if(j - oil >= 0)  dpY[1][j - oil] |= dpY[0][j];
                if(j + oil < MAX) dpY[1][j + oil] |= dpY[0][j];
            }
            
            // 3-8. 前回情報更新.
            rep(j, MAX) dpY[0][j] = dpY[1][j];
        }
    }
    
    // 4. 出力.
    printf("%s", (dpX[0][HMAX + x] && dpY[0][HMAX + y]) ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/arc087/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

// const int MAX = 22;

const int MAX = 20202;

const int HMAX = MAX / 2;

bool dpX[2][MAX], dpY[2][MAX];

int main(){

// 1. 入力情報.

char c[8080];

int x, y;

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

string S(c);

S.pb('T'); // 番兵.

// 2. 命令列を分割.

vs o;

int sl = S.size();

string t;

rep(i, sl){

int tl = t.size();

if(S[i] == 'T') o.pb(t), t = "";

if(S[i] == 'F') t.pb(S[i]);

}

// for(auto &p : o) printf("%s\n", p.c_str());

// 3. dpX, dpY更新.

int ol = o.size();

if(ol){

dpX[0][HMAX + o[0].size()] = true;

dpY[0][HMAX] = true;

}

repx(i, 1, ol){

int oil = o[i].size();

// 3-1. 左右.

if(!(i & 1)){

// 3-2. 今回情報初期化.

rep(j, MAX) dpX[1][j] = false;

// 3-3. dpX更新.

rep(j, MAX){

if(j - oil >= 0) dpX[1][j - oil] |= dpX[0][j];

if(j + oil < MAX) dpX[1][j + oil] |= dpX[0][j];

}

// 3-4. 前回情報更新.

rep(j, MAX) dpX[0][j] = dpX[1][j];

}

// 3-5. 上下.

if(i & 1){

// 3-6. 今回情報初期化.

rep(j, MAX) dpY[1][j] = false;

// 3-7. dpY更新..

rep(j, MAX){

if(j - oil >= 0) dpY[1][j - oil] |= dpY[0][j];

if(j + oil < MAX) dpY[1][j + oil] |= dpY[0][j];

}

// 3-8. 前回情報更新.

rep(j, MAX) dpY[0][j] = dpY[1][j];

}

// 4. 出力.

printf("%s", (dpX[0][HMAX + x] && dpY[0][HMAX + y]) ? "Yes" : "No");

return 0;

}

[入力例]
FTFFTFFF
4 2

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

[入力例]
FTFFTFFF
-2 -2

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

[入力例]
FF
1 0

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

[入力例]
TF
1 0

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

[入力例]
FFTTFF
0 0

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

[入力例]
TTTT
1 0

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

[入力例]
FTFTFTFTTTFTFTFTFFFT
-1 2

[出力例]
No

[入力例]
FTTTFTTFFTFFFTFTTTFTTFTFTTTTTTTFTTTFTFFTTFTTFTTTFT
5 7

[出力例]
Yes

[入力例]
TTTFTTTTFFTTFFFFTFTFTTFTTFTTTTTTTTFFTFTTTFTTTTTFFFFTTFFFFFFFFTFFFTFTTTTTTFTTTTFTTTTTFTFFFFTTTTFTTTTTTTFTTFFTTTTTTFFFTTTTTTTTTFFTTTFTTFFTTTTFTFTTTTFTTTTTFTFTFTTFTTFTFTFTFTFFFFTTFFTTTFFFTFTFTTFTTTFTFFFT
31 28

[出力例]
Yes

[入力例]

FTFFTFFF

4 2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

FTFFTFFF

-2 -2

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

1 0

[出力例]

※AtCoderのテストケースより

[入力例]

1 0

[出力例]

※AtCoderのテストケースより

[入力例]

FFTTFF

0 0

[出力例]

Yes

※AtCoderのテストケースより

[入力例]

TTTT

1 0

[出力例]

※AtCoderのテストケースより

[入力例]

FTFTFTFTTTFTFTFTFFFT

-1 2

[出力例]

[入力例]

FTTTFTTFFTFFFTFTTTFTTFTFTTTTTTTFTTTFTFFTTFTTFTTTFT

5 7

[出力例]

Yes

[入力例]

TTTFTTTTFFTTFFFFTFTFTTFTTFTTTTTTTTFFTFTTTFTTTTTFFFFTTFFFFFFFFTFFFTFTTTTTTFTTTTFTTTTTFTFFFFTTTTFTTTTTTTFTTFFTTTTTTFFFTTTTTTTTTFFTTTFTTFFTTTTFTFTTTTFTTTTTFTFTFTTFTTFTFTFTFTFFFFTTFFTTTFFFTFTFTTFTTTFTFFFT

31 28

[出力例]

Yes

■参照サイト
AtCoder Regular Contest 087

C++の練習を兼ねて, AtCoder Beginner Contest 193 の 問題C (Unexpressed) ～ 問題D (Poker) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 087 の 問題E (Prefix-free Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 113 の 問題D (Sky Reflector) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 192 の 問題C (Kaprekar Number) ～ 問題D (Base n) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 094 の 問題D (Binomial Coefficients)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 074 の 問題D (Restoring Road Network)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 035 の 問題D (トレジャーハント)を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 087 の 問題D (FT Robot)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 193 の問題C (Unexpressed) ～問題D (Poker) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 087 の問題E (Prefix-free Game) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 113 の問題D (Sky Reflector) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 192 の問題C (Kaprekar Number) ～問題D (Base n) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 094 の問題D (Binomial Coefficients)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 074 の問題D (Restoring Road Network)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 035 の問題D (トレジャーハント)を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 087 の問題D (FT Robot)を解いてみた.