C++ | 個人用メモ帳

2022年2月15日

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

C++の練習を兼ねて, AtCoder Regular Contest 135 の問題C (XOR to All) を解いてみた.

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

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

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

// 解き直し.
// https://atcoder.jp/contests/arc135/editorial/3356
// 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 x[303030], d[33][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%lld", &x[i + 1]);
        rep(j, 30){
            if(x[i + 1] & (1 << j)) d[j][1]++; // 1 を カウント.
            else                    d[j][0]++; // 0 を カウント.
        }
    }
    
    // 2. 操作後の数列 B.
    LL ans = 0;
    rep(i, N + 1){
        // 2-1. 各 x で 計算.
        LL cur = 0;
        rep(j, 30){
            if(x[i] & (1 << j)) cur += (1LL << j) * d[j][0];
            else                cur += (1LL << j) * d[j][1];
        }
        
        // 2-2. 最大値更新.
        ans = max(ans, cur);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc135/editorial/3356

// 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 x[303030], d[33][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

rep(j, 30){

if(x[i + 1] & (1 << j)) d[j][1]++; // 1 をカウント.

else d[j][0]++; // 0 をカウント.

}

// 2. 操作後の数列 B.

LL ans = 0;

rep(i, N + 1){

// 2-1. 各 x で計算.

LL cur = 0;

rep(j, 30){

if(x[i] & (1 << j)) cur += (1LL << j) * d[j][0];

else cur += (1LL << j) * d[j][1];

}

// 2-2. 最大値更新.

ans = max(ans, cur);

}

// 3. 出力.

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

return 0;

}

[入力例]
5
1 2 3 4 5

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

[入力例]
5
10 10 10 10 10

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

[入力例]
5
3 1 4 1 5

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

[入力例]
10
58 53 36 53 71 45 79 56 91 64

[出力例]
736

[入力例]
50
11359 6089 6053 5356 4815 2314 5214 1971 11222 11632 1480 5775 9135 6597 4431 1028 10270 4920 1892 538 4805 6507 3228 5494 7929 7504 9109 5981 7001 11330 10230 4253 8590 4103 7524 7037 4356 9942 8591 7956 2185 8932 6956 12166 3423 10070 11659 3761 8262 10990

[出力例]
475341

[入力例]

1 2 3 4 5

[出力例]

※AtCoderのテストケースより

[入力例]

10 10 10 10 10

[出力例]

※AtCoderのテストケースより

[入力例]

3 1 4 1 5

[出力例]

※AtCoderのテストケースより

[入力例]

58 53 36 53 71 45 79 56 91 64

[出力例]

736

[入力例]

11359 6089 6053 5356 4815 2314 5214 1971 11222 11632 1480 5775 9135 6597 4431 1028 10270 4920 1892 538 4805 6507 3228 5494 7929 7504 9109 5981 7001 11330 10230 4253 8590 4103 7524 7037 4356 9942 8591 7956 2185 8932 6956 12166 3423 10070 11659 3761 8262 10990

[出力例]

475341

■参照サイト
AtCoder Regular Contest 135

2022年2月13日2022年2月13日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にある通り, X, Y方向で, 独立に数え上げできるという部分が, 面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc127/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--)
const LL MOD = 1e9 + 7;
const int LIMIT = 202020;
LL 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版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果(mod版).
LL combination(LL n, LL k){
    if(n < 0 || k < 0 || k > n) return 0LL;
    if(n == k || k == 0LL) return 1LL;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d %d", &N, &M, &K);
    
    // 2. 事前計算.
    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);
    
    // 3. 各座標ごとの差の絶対値の和.
    // -> 2マスを, 固定で選んだ場合の数, 差の絶対値 d を 乗ずることを忘れないこと!
    // 3-1. X方向.
    LL x = 0;
    repx(d, 1, N){
        x += (LL)(N - d) * (LL)M % MOD * (LL)M % MOD * (LL)d % MOD;
        x %= MOD;
    }
    
    // 3-2. Y方向.
    LL y = 0;
    repx(d, 1, M){
        y += (LL)(M - d) * (LL)N % MOD * (LL)N % MOD * (LL)d % MOD;
        y %= MOD;
    }
    
    // 4. (K - 2)マス選ぶ場合の数.
    // -> 固定で選んだ 2マス以外のマスの選び方(解説より).
    LL k2 = combination((LL)(N * M - 2), (LL)(K - 2));
    
    // 5. 集計.
    // -> X, Y方向は, 独立と考えて良いとのこと(解説より).
    LL ans = (x + y) % MOD * k2 % MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

const LL MOD = 1e9 + 7;

const int LIMIT = 202020;

LL 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版).

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

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

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

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

LL combination(LL n, LL k){

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

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

LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;

return ret;

}

int main(){

// 1. 入力情報.

int N, M, K;

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

// 2. 事前計算.

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

// 3. 各座標ごとの差の絶対値の和.

// -> 2マスを, 固定で選んだ場合の数, 差の絶対値 d を乗ずることを忘れないこと!

// 3-1. X方向.

LL x = 0;

repx(d, 1, N){

x += (LL)(N - d) * (LL)M % MOD * (LL)M % MOD * (LL)d % MOD;

x %= MOD;

}

// 3-2. Y方向.

LL y = 0;

repx(d, 1, M){

y += (LL)(M - d) * (LL)N % MOD * (LL)N % MOD * (LL)d % MOD;

y %= MOD;

}

// 4. (K - 2)マス選ぶ場合の数.

// -> 固定で選んだ 2マス以外のマスの選び方(解説より).

LL k2 = combination((LL)(N * M - 2), (LL)(K - 2));

// 5. 集計.

// -> X, Y方向は, 独立と考えて良いとのこと(解説より).

LL ans = (x + y) % MOD * k2 % MOD;

// 6. 出力.

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

return 0;

}

[入力例]
2 2 2

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

[入力例]
4 5 4

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

[入力例]
100 100 5000

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

[入力例]
3 4 5

[出力例]
18480

[入力例]
7 8 3

[出力例]
415800

[入力例]
202 203 12345

[出力例]
906503729

[入力例]

2 2 2

[出力例]

※AtCoderテストケースより

[入力例]

4 5 4

[出力例]

87210

※AtCoderテストケースより

[入力例]

100 100 5000

[出力例]

817260251

※AtCoderテストケースより

[入力例]

3 4 5

[出力例]

18480

[入力例]

7 8 3

[出力例]

415800

[入力例]

202 203 12345

[出力例]

906503729

■参照サイト
AtCoder Beginner Contest 127

2022年2月11日

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

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

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 個人的には, 数え上げする種類数が, アルファベットの出現数にのみ依存するという部分が, 不思議な印象を受けた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc234/editorial/3223
// 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;
LL C[5050][5050], dp[27][5050];
int freq[26];

int main(){
    
    // 1. 入力情報.
    char s[5050];
    scanf("%s", s);
    string S(s);
    int N = S.size();
    
    // 2. 出現数('a' ～ 'z').
    rep(i, N) rep(j, 26) freq[j] = freq[j] + (S[i] == ('a' + j));
    
    // 3. パスカルの三角形.
    C[0][0] = 1;
    repx(i, 1, 5050){
        rep(j, 5050){
            C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];
            C[i][j] %= MOD;
        }
    }
    
    // 4. dp更新(index注意, j は 0 ～ N までの範囲を動くとのこと).
    dp[0][0] = 1;
    rep(i, 26){
        rep(j, N + 1){
            rep(k, min(j, freq[i]) + 1){
                dp[i + 1][j] += dp[i][j - k] * C[j][k];
                dp[i + 1][j] %= MOD;
            }
        }
    }
    
    // 5. 集計.
    LL ans = 0;
    repx(j, 1, N + 1) ans += dp[26][j], ans %= MOD;
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc234/editorial/3223

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

LL C[5050][5050], dp[27][5050];

int freq[26];

int main(){

// 1. 入力情報.

char s[5050];

scanf("%s", s);

string S(s);

int N = S.size();

// 2. 出現数('a' ～ 'z').

rep(i, N) rep(j, 26) freq[j] = freq[j] + (S[i] == ('a' + j));

// 3. パスカルの三角形.

C[0][0] = 1;

repx(i, 1, 5050){

rep(j, 5050){

C[i][j] = (!j || j == i) ? 1LL : C[i - 1][j - 1] + C[i - 1][j];

C[i][j] %= MOD;

}

// 4. dp更新(index注意, j は 0 ～ N までの範囲を動くとのこと).

dp[0][0] = 1;

rep(i, 26){

rep(j, N + 1){

rep(k, min(j, freq[i]) + 1){

dp[i + 1][j] += dp[i][j - k] * C[j][k];

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

}

// 5. 集計.

LL ans = 0;

repx(j, 1, N + 1) ans += dp[26][j], ans %= MOD;

// 6. 出力.

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

return 0;

}

[入力例]
aab

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

[入力例]
aaa

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

[入力例]
abcdefghijklmnopqrstuvwxyz

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

[入力例]
abc

[出力例]
15

[入力例]
abracadabra

[出力例]
257589

[入力例]
jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol
magicalspell

[出力例]
985106188

[入力例]

aab

[出力例]

※AtCoderテストケースより

[入力例]

aaa

[出力例]

※AtCoderテストケースより

[入力例]

abcdefghijklmnopqrstuvwxyz

[出力例]

149621752

※AtCoderテストケースより

[入力例]

abc

[出力例]

[入力例]

abracadabra

[出力例]

257589

[入力例]

jugemujugemugokonosurikirekaijarisuigyonosuigyomatsuunraimatsufuraimatsukunerutokoronisumutokoroyaburakojinoburakojipaipopaipopaiponoshuringanshuringannogurindaigurindainopompokopinopompokonanochokyumeinochosukezyugemuzyugemugokonosurikirekaizyarisuigyonosuigyomatuunraimatuhuraimatukuunerutokoronisumutokorol

magicalspell

[出力例]

985106188

■参照サイト
AtCoder Beginner Contest 234

2022年2月11日

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

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

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

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

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

// 解き直し.
// https://atcoder.jp/contests/abc237/editorial/3346
// 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 = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // コスト.
    bool operator < (const edge &E) const{ return c > E.c; }
};

vector<edge> G[202020];
LL h[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &h[i]);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        u--;
        v--;
        
        // 辺のコストは, 広場間の標高差の絶対値(解説通り).
        G[u].pb(edge{v, abs(h[v] - h[u])});
        G[v].pb(edge{u, abs(h[v] - h[u])});
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s, LL* d, int* memo){
        // 2-1. 初期化.
        priority_queue<edge> pq;
        
        // 2-2. 始点設定.
        d[s] = 0;
        pq.push({s, 0LL});
        
        // 2-3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 2-4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 2-5. 訪問済みフラグ設定.
            if(memo[cn]) continue;
            memo[cn]++;
            
            // 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.
            for(auto &g : G[cn]){
                // 移動コスト更新.
                int nn = g.n;
                LL nc = cc + g.c;
                if(d[nn] > nc) d[nn] = nc, pq.push({nn, nc});
            }
        }
    };
    
    // 3. 各広場までの, 最小コスト.
    LL d[N];
    int memo[N];
    rep(i, N) d[i] = INF, memo[i] = 0;
    dijkstra(0, d, memo);
    
    // 4. 楽しさの最大値は？
    // -> 数式計算で取得した値と比較(解説通り).
    //    解説上 の d[i], H[i] - H[1] は, 偶奇が一致するので, 展開した式は, 2 で 割り切れるはず.
    LL ans = 0;
    rep(i, N) ans = max(ans, (- d[i] - 3 * h[i] + 3 * h[0])/ 2);
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc237/editorial/3346

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

struct edge{

int n; // 次の頂点.

LL c; // コスト.

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

};

vector<edge> G[202020];

LL h[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

rep(i, M){

int u, v;

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

u--;

v--;

// 辺のコストは, 広場間の標高差の絶対値(解説通り).

G[u].pb(edge{v, abs(h[v] - h[u])});

G[v].pb(edge{u, abs(h[v] - h[u])});

}

// 2. ダイクストラ法.

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

auto dijkstra = [&](int s, LL* d, int* memo){

// 2-1. 初期化.

priority_queue<edge> pq;

// 2-2. 始点設定.

d[s] = 0;

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

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

while(!pq.empty()){

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

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 2-5. 訪問済みフラグ設定.

if(memo[cn]) continue;

memo[cn]++;

// 2-6. 各隣接する頂点について, 距離を確認し, 移動コストを更新.

for(auto &g : G[cn]){

// 移動コスト更新.

int nn = g.n;

LL nc = cc + g.c;

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

}

};

// 3. 各広場までの, 最小コスト.

LL d[N];

int memo[N];

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

dijkstra(0, d, memo);

// 4. 楽しさの最大値は？

// -> 数式計算で取得した値と比較(解説通り).

// 解説上の d[i], H[i] - H[1] は, 偶奇が一致するので, 展開した式は, 2 で割り切れるはず.

LL ans = 0;

rep(i, N) ans = max(ans, (- d[i] - 3 * h[i] + 3 * h[0])/ 2);

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2 1
0 10
1 2

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

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

[出力例]
5

[入力例]
10 16
314 159 265 358 979 323 846 264 338 327
1 2
1 3
2 4
2 5
3 5
3 6
4 8
4 9
5 7
5 8
6 7
6 10
7 8
7 10
8 9
9 10

[出力例]
155

[入力例]

4 4

10 8 12 5

1 2

1 3

2 3

3 4

[出力例]

※AtCoderテストケースより

[入力例]

2 1

0 10

1 2

[出力例]

※AtCoderテストケースより

[入力例]

5 7

12 7 13 10 8

1 2

1 4

1 5

2 3

2 4

2 5

3 5

[出力例]

[入力例]

10 16

314 159 265 358 979 323 846 264 338 327

1 2

1 3

2 4

2 5

3 5

3 6

4 8

4 9

5 7

5 8

6 7

6 10

7 8

7 10

8 9

9 10

[出力例]

155

■参照サイト
AtCoder Beginner Contest 237

2022年2月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 085 の問題D (Katana Thrower) を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説にあるロジック(投げ刀, 強い投げ刀, 振り刀に分けて考える)が, 非常に面白く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    int N, H;
    scanf("%d %d", &N, &H);
    vp v;
    int a, b, maxA = 0;
    rep(i, N){
        scanf("%d %d", &a, &b);
        v.pb({a, 0}); // 振り刀.
        v.pb({b, 1}); // 投げ刀.
        maxA = max(maxA, a); // 攻撃力最大の振り刀.
    }
    
    // 2. sort.
    sort(all(v));
    reverse(all(v));
    
    // 3. 攻撃パターン 1.
    // 強い投げ刀を投げる.
    int ans = 0;
    rep(i, N * 2){
        if(H > 0 && v[i].b && v[i].a >= maxA){
            H -= v[i].a;
            ans++;
        }
    }
    
    // 4. 攻撃パターン 2.
    // 攻撃力最大の振り刀を振り続ける.
    if(H > 0) ans += (H + maxA - 1) / maxA;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

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

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

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

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

#define a first

#define b second

#define pb push_back

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

int main(){

// 1. 入力情報.

int N, H;

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

vp v;

int a, b, maxA = 0;

rep(i, N){

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

v.pb({a, 0}); // 振り刀.

v.pb({b, 1}); // 投げ刀.

maxA = max(maxA, a); // 攻撃力最大の振り刀.

}

// 2. sort.

sort(all(v));

reverse(all(v));

// 3. 攻撃パターン 1.

// 強い投げ刀を投げる.

int ans = 0;

rep(i, N * 2){

if(H > 0 && v[i].b && v[i].a >= maxA){

H -= v[i].a;

ans++;

}

// 4. 攻撃パターン 2.

// 攻撃力最大の振り刀を振り続ける.

if(H > 0) ans += (H + maxA - 1) / maxA;

// 5. 出力.

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

return 0;

}

[入力例]
1 10
3 5

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

[入力例]
2 10
3 5
2 6

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

[入力例]
4 1000000000
1 1
1 10000000
1 30000000
1 99999999

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

[入力例]
5 500
35 44
28 83
46 62
31 79
40 43

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

[入力例]
10 12345
100 222
72 194
108 211
76 172
85 144
28 51
40 126
8 50
19 120
26 84

[出力例]
111

[入力例]
30 20220210
941 9675
723 8610
873 9340
133 8728
286 9696
343 9739
369 9549
715 8992
665 9378
127 7592
313 9120
141 9167
69 8934
999 9174
985 9922
862 8752
455 9665
969 8218
705 7940
519 9332
859 9772
47 8968
333 9603
427 8878
710 7646
272 9973
145 8972
375 7253
45 9815
930 8493

[出力例]
20000

[入力例]

1 10

3 5

[出力例]

※AtCoderテストケースより

[入力例]

2 10

3 5

2 6

[出力例]

※AtCoderテストケースより

[入力例]

4 1000000000

1 1

1 10000000

1 30000000

1 99999999

[出力例]

860000004

※AtCoderテストケースより

[入力例]

5 500

35 44

28 83

46 62

31 79

40 43

[出力例]

※AtCoderテストケースより

[入力例]

10 12345

100 222

72 194

108 211

76 172

85 144

28 51

40 126

8 50

19 120

26 84

[出力例]

111

[入力例]

30 20220210

941 9675

723 8610

873 9340

133 8728

286 9696

343 9739

369 9549

715 8992

665 9378

127 7592

313 9120

141 9167

69 8934

999 9174

985 9922

862 8752

455 9665

969 8218

705 7940

519 9332

859 9772

47 8968

333 9603

427 8878

710 7646

272 9973

145 8972

375 7253

45 9815

930 8493

[出力例]

20000

■参照サイト
AtCoder Beginner Contest 085

2022年2月9日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 最初, TLE版で実装したが, 計算量の削減方法が分からず, dp更新式に渡す鍵情報を, AtCoder Beginner Contest 142 (解説プログラム)を参考に修正している.
4. 個人的には, 動的計画法に関する理解を, 深めることが出来たように感じた.
現状, TLE版と AC版との違いは, 本質的には, 鍵情報の捉え方の違いにあると理解している.
→ 具体的には, 鍵情報が, {宝箱1, 宝箱2, 宝箱3} だった場合に, TLE版では, {宝箱1}, {宝箱2}, {宝箱3}, {宝箱1, 宝箱2}, {宝箱1, 宝箱3}, {宝箱2, 宝箱3}, {宝箱1, 宝箱2, 宝箱3} の 7通りの鍵情報で, dp更新を行っているが, AC版では, {宝箱1, 宝箱2, 宝箱3} の 1通りの鍵情報で, dp計算を行っているため, 計算量に違いが現れたと理解している.
→ さらに, TLE版と AC版は, dp配列の途中部分は, 差分が生じるものの, 最終的に必要な情報は, すべての宝箱を, 開けることが出来るかどうか(および, 最小費用)であるため, 各鍵毎に, 常に, 1通りの鍵情報(ここでは, {宝箱1, 宝箱2, 宝箱3})を見れば十分という点について, なるほどと, 改めて感じた.
5. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/abc142/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
int dp[1010][1 << 12];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 初期化.
    rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;
    dp[0][0] = 0;
    
    // 3. dp更新.
    rep(i, M){
        // i個目の鍵情報.
        // ex.
        // 鍵 1, 3, 7 が 手に入った場合, 
        // 集合 {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, {1, 3, 7} の 組み合わせで, 見る必要があることに注意.
        int t[1 << N];
        rep(j, 1 << N) t[j] = 0;
        t[0] = 1;
        int a, b, c;
        scanf("%d %d", &a, &b);
        rep(j, b){
            scanf("%d", &c);
            repr(j, (1 << N) - 1, 0) if(t[j]) t[j + (1 << (N - c))] = 1;
        }
        
        // 鍵情報の組み合わせ保存.
        vi key;
        repx(j, 1, 1 << N) if(t[j]) key.pb(j);
        // for(auto &k : key) printf("%d ", k);
        // puts("\n----------");
        
        // 前回分反映.
        rep(j, 1 << N) dp[i + 1][j] = dp[i][j];
        
        // 宝箱を開けるための最小コスト.
        // -> 状態 j は, 開いている宝箱情報と見る.
        // ex. 
        // N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が 開いていると見る.
        rep(j, 1 << N) for(auto &k : key) dp[i + 1][j | k] = min({dp[i + 1][j | k], dp[i][j | k], dp[i][j] + a});
        // rep(j, 1 << N) printf("%d ", dp[i + 1][j]);
        // puts("\n----------");
    }
    
    // 4. 集計.
    int ans = dp[M][(1 << N) - 1];
    if(ans == 2020202020) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

int dp[1010][1 << 12];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 初期化.

rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;

dp[0][0] = 0;

// 3. dp更新.

rep(i, M){

// i個目の鍵情報.

// ex.

// 鍵 1, 3, 7 が手に入った場合,

// 集合 {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, {1, 3, 7} の組み合わせで, 見る必要があることに注意.

int t[1 << N];

rep(j, 1 << N) t[j] = 0;

t[0] = 1;

int a, b, c;

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

rep(j, b){

scanf("%d", &c);

repr(j, (1 << N) - 1, 0) if(t[j]) t[j + (1 << (N - c))] = 1;

}

// 鍵情報の組み合わせ保存.

vi key;

repx(j, 1, 1 << N) if(t[j]) key.pb(j);

// for(auto &k : key) printf("%d ", k);

// puts("\n----------");

// 前回分反映.

rep(j, 1 << N) dp[i + 1][j] = dp[i][j];

// 宝箱を開けるための最小コスト.

// -> 状態 j は, 開いている宝箱情報と見る.

// ex.

// N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が開いていると見る.

rep(j, 1 << N) for(auto &k : key) dp[i + 1][j | k] = min({dp[i + 1][j | k], dp[i][j | k], dp[i][j] + a});

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

// puts("\n----------");

}

// 4. 集計.

int ans = dp[M][(1 << N) - 1];

if(ans == 2020202020) ans = -1;

// 5. 出力.

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

return 0;

}

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

// 解き直し.
// https://img.atcoder.jp/abc142/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
int dp[1010][1 << 12];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    
    // 2. 初期化.
    rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;
    dp[0][0] = 0;
    
    // 3. dp更新(01-handmade-07 で, TLE版だったため, ロジック修正).
    rep(i, M){
        // i個目の鍵情報.
        // -> 状態 j は, 開いている宝箱情報と見る.
        // ex. 
        // N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が 開いていると見る.
        int a, b, c, key = 0;
        scanf("%d %d", &a, &b);
        rep(j, b){
            scanf("%d", &c);
            key |= (1 << (N - c));
        }
        
        // 前回分反映.
        rep(j, 1 << N) dp[i + 1][j] = dp[i][j];
        
        // 宝箱を開けるための最小コスト.
        rep(j, 1 << N) dp[i + 1][j | key] = min({dp[i + 1][j | key], dp[i][j | key], dp[i][j] + a});
    }
    
    // 4. 集計.
    int ans = dp[M][(1 << N) - 1];
    if(ans == 2020202020) ans = -1;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int dp[1010][1 << 12];

int main(){

// 1. 入力情報.

int N, M;

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

// 2. 初期化.

rep(i, 1010) rep(j, 1 << N) dp[i][j] = 2020202020;

dp[0][0] = 0;

// 3. dp更新(01-handmade-07 で, TLE版だったため, ロジック修正).

rep(i, M){

// i個目の鍵情報.

// -> 状態 j は, 開いている宝箱情報と見る.

// ex.

// N = 12 で, j = 100010100011 は, 宝箱 = {1, 2, 6, 8, 12} が開いていると見る.

int a, b, c, key = 0;

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

rep(j, b){

scanf("%d", &c);

key |= (1 << (N - c));

}

// 前回分反映.

rep(j, 1 << N) dp[i + 1][j] = dp[i][j];

// 宝箱を開けるための最小コスト.

rep(j, 1 << N) dp[i + 1][j | key] = min({dp[i + 1][j | key], dp[i][j | key], dp[i][j] + a});

}

// 4. 集計.

int ans = dp[M][(1 << N) - 1];

if(ans == 2020202020) ans = -1;

// 5. 出力.

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

return 0;

}

[入力例]
2 3
10 1
1
15 1
2
30 2
1 2

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

[入力例]
12 1
100000 1
2

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

[入力例]
4 6
67786 3
1 3 4
3497 1
2
44908 3
2 3 4
2156 3
2 3 4
26230 1
2
86918 1
3

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

[入力例]
5 7
83 3
1 2 3
93 1
4
10 1
1
114 2
2 5
119 1
3
84 2
4 5
17 2
2 5

[出力例]
167

[入力例]
12 15
13483 2
1 5
5458 1
6
10474 6
2 3 7 8 10 11
3974 3
9 11 12
11592 3
1 2 3
12856 3
4 5 6
3538 4
7 8 9 10
2999 1
11
3780 3
1 11 12
9159 2
5 6
2890 3
7 9 10
11778 4
3 5 8 9
11169 5
1 2 5 7 11
12798 5
3 4 7 8 9
9578 1
2

[出力例]
30000

[入力例]

2 3

10 1

15 1

30 2

1 2

[出力例]

※AtCoderテストケースより

[入力例]

12 1

100000 1

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 6

67786 3

1 3 4

3497 1

44908 3

2 3 4

2156 3

2 3 4

26230 1

86918 1

[出力例]

69942

※AtCoderテストケースより

[入力例]

5 7

83 3

1 2 3

93 1

10 1

114 2

2 5

119 1

84 2

4 5

17 2

2 5

[出力例]

167

[入力例]

12 15

13483 2

1 5

5458 1

10474 6

2 3 7 8 10 11

3974 3

9 11 12

11592 3

1 2 3

12856 3

4 5 6

3538 4

7 8 9 10

2999 1

3780 3

1 11 12

9159 2

5 6

2890 3

7 9 10

11778 4

3 5 8 9

11169 5

1 2 5 7 11

12798 5

3 4 7 8 9

9578 1

[出力例]

30000

■参照サイト
AtCoder Beginner Contest 142
AtCoder Beginner Contest 142 (解説プログラム)

2022年2月8日

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

C++の練習を兼ねて, 競プロ典型 90 問の問題025 (Digit Product Equation) を解いてみた.

■感想.
1. 問題025は, 方針が見えなかったので, (問題025 (Digit Product Equation) 解説) を参考に実装したところ, AC版に到達出来た.
2. 個人的には, 深さ優先探索の訓練を積めたので, 非常に良かったと思う.
3. 手強い問題が非常に多い気もするけど, 時間を見つけて, 引き続き, 取り組んでいきたいと思う.

詳細は, 本家のサイト(GitHub) 競プロ典型 90 問の問題025 をご覧下さい.

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

// 解き直し.
// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/025.jpg
// 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 a first
#define b second
#define pb push_back
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    LL N, B;
    scanf("%lld %lld", &N, &B);
    
    // 2. N の 桁数.
    string ns = to_string(N);
    int n = ns.size();
    
    // 3. B に '0' が 含まれるか？
    int ans = 0;
    bool b = false;
    string nb = to_string(B);
    rep(i, nb.size()) if(nb[i] == '0') b = true;
    if(b && (N >= B)) ans++;
    
    // 4. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    map<string, int> memo;
    auto dfs = [&](auto&& self, string fBef, int d) -> void {
        // 2-1. 終了条件.
        if(d == 0) return;
        
        // 2-2. '1' ～ '9' を 追加.
        // 今回分反映.
        repx(i, 1, 10){
            // 整数を生成.
            string fCur = fBef;
            fCur.pb('0' + i);
            
            // sort.
            sort(all(fCur));
            
            // 探索済か？
            if(!memo.count(fCur)){
                // 訪問済みを設定.
                memo[fCur]++;
                
                // 条件を満たす整数があるか？
                // -> m を 生成して, 文字列化したものが, fCur と 等しいか？
                LL fm = 1;
                rep(j, fCur.size()) fm *= (LL)(fCur[j] - '0');
                LL m = fm + B;
                string sm = to_string(m);
                sort(all(sm));
                
                // in12.txt などで, WA版となったので, ロジック修正(※m <= N 追加).
                if(m <= N && fCur == sm) ans++;
                
                // 次へ.
                self(self, fCur, d - 1);
            }
        } 
    };
    dfs(dfs, "", n);
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://github.com/E869120/kyopro_educational_90/blob/main/editorial/025.jpg

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

#define b second

#define pb push_back

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

int main(){

// 1. 入力情報.

LL N, B;

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

// 2. N の桁数.

string ns = to_string(N);

int n = ns.size();

// 3. B に '0' が含まれるか？

int ans = 0;

bool b = false;

string nb = to_string(B);

rep(i, nb.size()) if(nb[i] == '0') b = true;

if(b && (N >= B)) ans++;

// 4. dfs.

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

map<string, int> memo;

auto dfs = [&](auto&& self, string fBef, int d) -> void {

// 2-1. 終了条件.

if(d == 0) return;

// 2-2. '1' ～ '9' を追加.

// 今回分反映.

repx(i, 1, 10){

// 整数を生成.

string fCur = fBef;

fCur.pb('0' + i);

// sort.

sort(all(fCur));

// 探索済か？

if(!memo.count(fCur)){

// 訪問済みを設定.

memo[fCur]++;

// 条件を満たす整数があるか？

// -> m を生成して, 文字列化したものが, fCur と等しいか？

LL fm = 1;

rep(j, fCur.size()) fm *= (LL)(fCur[j] - '0');

LL m = fm + B;

string sm = to_string(m);

sort(all(sm));

// in12.txt などで, WA版となったので, ロジック修正(※m <= N 追加).

if(m <= N && fCur == sm) ans++;

// 次へ.

self(self, fCur, d - 1);

}

};

dfs(dfs, "", n);

// 5. 出力.

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

return 0;

}

[入力例]
999 434

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

[入力例]
255 15

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

[入力例]
9999999999 1

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

[入力例]
1 1

[出力例]
0

[入力例]
123 234

[出力例]
0

[入力例]
2022 208

[出力例]
4

[入力例]
25252525 31415

[出力例]
3

[入力例]
333333333 5050

[出力例]
2

[入力例]
32100123 252525

[出力例]
2

[入力例]

999 434

[出力例]

※AtCoderテストケースより

[入力例]

255 15

[出力例]

※AtCoderテストケースより

[入力例]

9999999999 1

[出力例]

※AtCoderテストケースより

[入力例]

1 1

[出力例]

[入力例]

123 234

[出力例]

[入力例]

2022 208

[出力例]

[入力例]

25252525 31415

[出力例]

[入力例]

333333333 5050

[出力例]

[入力例]

32100123 252525

[出力例]

■参照サイト
025 – Digit Product Equation
問題025 (Digit Product Equation) 解説

2022年2月7日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 個人的には, 解説にあるロジックで, 整数列の和が, 特定できるか否かを判定できる点が, 非常に面白いと感じた..
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc238/editorial/3360
// 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--)

// https://github.com/atcoder/live_library/blob/master/uf.cpp
// UnionFind
// coding: https://youtu.be/TdR816rqc3s?t=726
// comment: https://youtu.be/TdR816rqc3s?t=6822
// -> 一部改変.
struct UnionFind{
    vi d;
    UnionFind(int n = 0): d(n, -1) {}
    int find(int x){
        return (d[x] < 0) ? x : (d[x] = find(d[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x, y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    int size(int x){
        return -d[find(x)];
    }
};

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. グラフ構築.
    UnionFind uf(N + 2);
    rep(i, Q){
        int l, r;
        scanf("%d %d", &l, &r);
        l--;
        uf.unite(l, r);
    }
    
    // 3. 出力.
    printf("%s\n", uf.same(0, N) ? "Yes" : "No");
    return 0;
    
}

// 解き直し.

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

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

// https://github.com/atcoder/live_library/blob/master/uf.cpp

// UnionFind

// coding: https://youtu.be/TdR816rqc3s?t=726

// comment: https://youtu.be/TdR816rqc3s?t=6822

// -> 一部改変.

struct UnionFind{

vi d;

UnionFind(int n = 0): d(n, -1) {}

int find(int x){

return (d[x] < 0) ? x : (d[x] = find(d[x]));

}

bool unite(int x, int y){

x = find(x);

y = find(y);

if(x == y) return false;

if(d[x] > d[y]) swap(x, y);

d[x] += d[y];

d[y] = x;

return true;

}

bool same(int x, int y){

return find(x) == find(y);

}

int size(int x){

return -d[find(x)];

}

};

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. グラフ構築.

UnionFind uf(N + 2);

rep(i, Q){

int l, r;

scanf("%d %d", &l, &r);

l--;

uf.unite(l, r);

}

// 3. 出力.

printf("%s\n", uf.same(0, N) ? "Yes" : "No");

return 0;

}

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

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

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

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

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

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

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

[出力例]
No

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

[出力例]
Yes

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

[出力例]
Yes

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

[出力例]
No

[入力例]
25 5
1 5
6 10
11 15
16 20
21 25

[出力例]
Yes

[入力例]

3 3

1 2

2 3

2 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

4 3

1 3

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 1

2 2

3 3

1 4

[出力例]

Yes

※AtCoderテストケースより

[入力例]

5 3

1 2

2 3

3 4

[出力例]

[入力例]

6 3

1 2

3 4

5 6

[出力例]

Yes

[入力例]

10 6

1 2

3 3

4 5

6 7

8 8

9 10

[出力例]

Yes

[入力例]

20 18

1 3

2 4

3 5

4 6

5 7

6 8

7 9

8 10

9 11

10 12

11 13

12 14

13 15

14 16

15 17

16 18

17 19

18 20

[出力例]

[入力例]

25 5

1 5

6 10

11 15

16 20

21 25

[出力例]

Yes

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

2022年2月6日

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

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

■感想.
1. 問題Cは, 方針が絞り込めたので, AC版に到達できたと思う.
2. 実装に苦労した(※1. ～ 2.)ものの, 尺取り法の復習ができたので非常に良かったと思う.
※1. 左端の要素を, 要素の積に反映する時に, (右側で反映済みのケースがあるので)二重に, 積を反映してしまわないように, 注意する必要がある点.
※2. 右端の要素が, 最終要素まで到達してしまった場合の処理も考慮する必要がある点.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int N, zero = 0;
    LL K;
    scanf("%d %lld", &N, &K);
    rep(i, N){
        scanf("%lld", &s[i]);
        if(!s[i]) zero++;
    }
    
    // 2. 例外.
    // -> ゼロが含まれる場合は, N を 返却.
    if(zero){
        printf("%d\n", N);
        return 0;
    }
    
    // 3. しゃくとり法.
    int ans = 0, l = 0, r = 0;
    LL cur = 1;
    while(l < N){
        // 要素を乗ずる.
        if(r <= l) cur *= s[l];
        
        // 要素の積が, K以下か？
        if(cur > K){
            ans = max(ans, r - l);
            cur /= s[l];
            ++l;
            continue;
        }
        
        // 更新(右端).
        r = max(r, l + 1);
        
        // 要素の積が, K以下か？
        while(r < N){
            cur *= s[r];
            if(cur > K){
                ans = max(ans, r - l);
                cur /= s[r];
                break;
            }
            ++r;
        }
        
        // 最終要素.
        if(r == N) ans = max(ans, r - l);
        
        // 更新(左端).
        cur /= s[l];
        ++l;
    }
    
    // 4. 出力.
    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--)

LL s[101010];

int main(){

// 1. 入力情報.

int N, zero = 0;

LL K;

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

rep(i, N){

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

if(!s[i]) zero++;

}

// 2. 例外.

// -> ゼロが含まれる場合は, N を返却.

if(zero){

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

return 0;

}

// 3. しゃくとり法.

int ans = 0, l = 0, r = 0;

LL cur = 1;

while(l < N){

// 要素を乗ずる.

if(r <= l) cur *= s[l];

// 要素の積が, K以下か？

if(cur > K){

ans = max(ans, r - l);

cur /= s[l];

++l;

continue;

}

// 更新(右端).

r = max(r, l + 1);

// 要素の積が, K以下か？

while(r < N){

cur *= s[r];

if(cur > K){

ans = max(ans, r - l);

cur /= s[r];

break;

}

++r;

}

// 最終要素.

if(r == N) ans = max(ans, r - l);

// 更新(左端).

cur /= s[l];

++l;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
6 10
10
10
10
10
0
10

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

[入力例]
6 9
10
10
10
10
10
10

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

[入力例]
4 0
1
2
3
4

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

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

[出力例]
4

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

[出力例]
5

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

[出力例]
8

[入力例]
16 30
1
6
6
2
7
6
2
1
5
1
1
2
3
2
1
1

[出力例]
7

[入力例]
30 2022
8
1
2
3
7
3
6
2
1
1
3
1
9
5
2
1
2
3
9
2
5
5
1
2
1
6
8
1
3
5

[出力例]
10

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

[入力例]

7 6

[出力例]

※AtCoderテストケースより

[入力例]

6 10

[出力例]

※AtCoderテストケースより

[入力例]

6 9

[出力例]

※AtCoderテストケースより

[入力例]

4 0

[出力例]

※AtCoderテストケースより

[入力例]

11 12

[出力例]

[入力例]

5 13

[出力例]

[入力例]

12 15

[出力例]

[入力例]

16 30

[出力例]

[入力例]

30 2022

[出力例]

■参照サイト
AtCoder Beginner Contest 032

2022年2月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 238 の問題C (digitnum) ～問題D (AND and SUM) を解いてみた.

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

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

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

// 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
const LL MOD = 998244353;

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. Σf(x).
    // ex.
    // N = 1234
    // 4桁 … 1000 ～ 1234 から, (1 + 235) * 235 / 2 =  27730.
    // 3桁 …  100 ～  999 から, (1 + 900) * 900 / 2 = 405450.
    // 2桁 …   10 ～   99 から, (1 +  90) *  90 / 2 =   4095.
    // 1桁 …    1 ～    9 から, (1 +   9) *   9 / 2 =     45.
    // -> 合計 437320 の はず.
    auto sf = [&](LL x) -> LL {
        // 2-1. 10 の 冪乗.
        vl cPow10;
        cPow10.pb(1);
        while(cPow10.size() <= 18) cPow10.pb(10 * cPow10.back());
        
        // 2-2. 各桁ごとに集計.
        LL ret = 0, cur = x;
        repr(i, cPow10.size() - 1, 0){
            if(cPow10[i] <= cur){
                // cur と 桁数 が 同じものがいくつあるか？
                LL t = (cur - cPow10[i] + 2) % MOD;
                t *= (cur - cPow10[i] + 1) % MOD;
                t %= MOD;
                t *= 499122177;
                t %= MOD;
                
                // 集計.
                ret += t;
                ret %= MOD;
                
                // 次へ.
                cur = cPow10[i] - 1;
            }
        }
        
        // 2-3. 返却.
        return ret;
    };
    
    // 3. 出力.
    printf("%lld\n", sf(N));
    return 0;
    
}

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

const LL MOD = 998244353;

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. Σf(x).

// ex.

// N = 1234

// 4桁 … 1000 ～ 1234 から, (1 + 235) * 235 / 2 = 27730.

// 3桁 … 100 ～ 999 から, (1 + 900) * 900 / 2 = 405450.

// 2桁 … 10 ～ 99 から, (1 + 90) * 90 / 2 = 4095.

// 1桁 … 1 ～ 9 から, (1 + 9) * 9 / 2 = 45.

// -> 合計 437320 のはず.

auto sf = [&](LL x) -> LL {

// 2-1. 10 の冪乗.

vl cPow10;

cPow10.pb(1);

while(cPow10.size() <= 18) cPow10.pb(10 * cPow10.back());

// 2-2. 各桁ごとに集計.

LL ret = 0, cur = x;

repr(i, cPow10.size() - 1, 0){

if(cPow10[i] <= cur){

// cur と桁数が同じものがいくつあるか？

LL t = (cur - cPow10[i] + 2) % MOD;

t *= (cur - cPow10[i] + 1) % MOD;

t %= MOD;

t *= 499122177;

t %= MOD;

// 集計.

ret += t;

ret %= MOD;

// 次へ.

cur = cPow10[i] - 1;

}

// 2-3. 返却.

return ret;

};

// 3. 出力.

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

return 0;

}

[入力例]
16

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

[入力例]
238

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

[入力例]
999999999999999999

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

[入力例]
99

[出力例]
4140

[入力例]
1234

[出力例]
437320

[入力例]
2022

[出力例]
933366

[入力例]
20220206

[出力例]
216690071

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

238

[出力例]

13870

※AtCoderテストケースより

[入力例]

999999999999999999

[出力例]

762062362

※AtCoderテストケースより

[入力例]

[出力例]

4140

[入力例]

1234

[出力例]

437320

[入力例]

2022

[出力例]

933366

[入力例]

20220206

[出力例]

216690071

■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--)

int main(){
    
    // 1. 入力情報.
    int T;
    scanf("%d", &T);
    
    // 2. クエリ回答.
    rep(i, T){
        // 2-1. クエリ入力情報.
        LL a, s;
        scanf("%lld %lld", &a, &s);
        
        // 2-2. 条件を満たす 非負整数の組 (x, y) が 存在するか？
        bool ok = false;
        if(a <= s){
            LL x = a;
            LL y = s - a;
            ok = ((x & y) == a);
        }
        
        // 2-3. 出力.
        printf("%s\n", ok ? "Yes" : "No");
    }
    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. 入力情報.

int T;

scanf("%d", &T);

// 2. クエリ回答.

rep(i, T){

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

LL a, s;

scanf("%lld %lld", &a, &s);

// 2-2. 条件を満たす非負整数の組 (x, y) が存在するか？

bool ok = false;

if(a <= s){

LL x = a;

LL y = s - a;

ok = ((x & y) == a);

}

// 2-3. 出力.

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

}

return 0;

}

[入力例]
2
1 8
4 2

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

[入力例]
4
201408139683277485 381410962404666524
360288799186493714 788806911317182736
18999951915747344 451273909320288229
962424162689761932 1097438793187620758

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

[入力例]
5
7 5
6 13
9 5
2 7
4 11

[出力例]
No
Yes
No
No
Yes

[入力例]
7
1 4
3 14
10 20
18 36
5 50
38 93
37 156

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

[入力例]

1 8

4 2

[出力例]

Yes

※AtCoderテストケースより

[入力例]

201408139683277485 381410962404666524

360288799186493714 788806911317182736

18999951915747344 451273909320288229

962424162689761932 1097438793187620758

[出力例]

Yes

※AtCoderテストケースより

[入力例]

7 5

6 13

9 5

2 7

4 11

[出力例]

Yes

[入力例]

1 4

3 14

10 20

18 36

5 50

38 93

37 156

[出力例]

Yes

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

C++の練習を兼ねて, AtCoder Regular Contest 135 の 問題C (XOR to All) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 085 の 問題D (Katana Thrower) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問 の 問題025 (Digit Product Equation) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 238 の 問題C (digitnum) ～ 問題D (AND and SUM) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 135 の問題C (XOR to All) を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 085 の問題D (Katana Thrower) を解いてみた.

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

C++の練習を兼ねて, 競プロ典型 90 問の問題025 (Digit Product Equation) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 238 の問題C (digitnum) ～問題D (AND and SUM) を解いてみた.