C++ | 個人用メモ帳

2022年9月10日

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

C++の練習を兼ねて, AtCoder Beginner Contest 141 の問題E (Who Says a Pun?) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    char s[5050];
    scanf("%d %s", &N, s);
    string S(s);
    
    // 2. Z-Algorithm.
    // https://atcoder.jp/contests/abc257/editorial/4185
    // -> 解説プログラム一部変更.
    // ex.
    // S = aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa の 場合, 
    // f[i] = 50 2 1 0 0 0 0 0 5 2 1 0 0 3 2 1 0 6 2 1 0 0 0 14 2 1 0 0 0 0 0 5 2 1 0 0 1 0 0 0 7 2 1 0 0 0 0 3 2 1 
    // 
    // S = abcabc の 場合, 
    // f[i] = 6 0 0 3 0 0 
    auto z = [](string s, int ss, int* f){
        int l = 0, r = 1;
        f[0] = ss;
        repx(i, 1, ss){
            if(i > 1 && f[i - l] < r - i){
                f[i] = f[i - l];
                continue;
            }
            r = max(i, r);
            while(r < ss){
                if(s[r] == s[r - i]) ++r;
                else                 break;
            }
            f[i] = r - i;
            l = i;
        }
    };
    
    // 3. 正整数 len の 最大値は？
    int ans = 0;
    rep(i, N){
        // i 番目以降の文字列.
        int ss = N - i;
        int f[ss];
        rep(j, ss) f[j] = 0;
        z(S.substr(i, ss), ss, f);
        
        // 最大値更新.
        repx(j, 1, ss) if(f[j] <= j) ans = max(ans, f[j]);
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

int main(){

// 1. 入力情報.

int N;

char s[5050];

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

string S(s);

// 2. Z-Algorithm.

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

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

// ex.

// S = aaabbcddaaabbaaaeaaabbcaaabbcddaaabbaefgaaabbcdaaa の場合,

// f[i] = 50 2 1 0 0 0 0 0 5 2 1 0 0 3 2 1 0 6 2 1 0 0 0 14 2 1 0 0 0 0 0 5 2 1 0 0 1 0 0 0 7 2 1 0 0 0 0 3 2 1

// S = abcabc の場合,

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

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

int l = 0, r = 1;

f[0] = ss;

repx(i, 1, ss){

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

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

continue;

}

r = max(i, r);

while(r < ss){

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

else break;

}

f[i] = r - i;

l = i;

}

};

// 3. 正整数 len の最大値は？

int ans = 0;

rep(i, N){

// i 番目以降の文字列.

int ss = N - i;

int f[ss];

rep(j, ss) f[j] = 0;

z(S.substr(i, ss), ss, f);

// 最大値更新.

repx(j, 1, ss) if(f[j] <= j) ans = max(ans, f[j]);

}

// 4. 出力.

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

return 0;

}

[入力例]
5
ababa

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

[入力例]
2
xy

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

[入力例]
13
strangeorange

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

[入力例]
10
appleapple

[出力例]
5

[入力例]
50
qoegblueberrytfdgltfeggiqmblueberrypakjjkdcoljbsao

[出力例]
9

[入力例]
300
wemqhrlpzviirohanihohetochirinuruowakayotaresotsunenaramuuinookuyamakefukoeteasakiyumemishiehimosesunaximyyhuutwyudtkllpdoanfasozfvirohanihohetochirinuruowakayotaresotsunenaramuuinookuyamakefukoeteasakiyumemishiehimosesunxkjutklqwguoqcdekfapclwtixbiholikqqvwzztimogyutcyeybxplgzvssielxiqzhrzvteybyvpl

[出力例]
90

[入力例]

ababa

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

strangeorange

[出力例]

※AtCoderテストケースより

[入力例]

appleapple

[出力例]

[入力例]

qoegblueberrytfdgltfeggiqmblueberrypakjjkdcoljbsao

[出力例]

[入力例]

300

wemqhrlpzviirohanihohetochirinuruowakayotaresotsunenaramuuinookuyamakefukoeteasakiyumemishiehimosesunaximyyhuutwyudtkllpdoanfasozfvirohanihohetochirinuruowakayotaresotsunenaramuuinookuyamakefukoeteasakiyumemishiehimosesunxkjutklqwguoqcdekfapclwtixbiholikqqvwzztimogyutcyeybxplgzvssielxiqzhrzvteybyvpl

[出力例]

■参照サイト
AtCoder Beginner Contest 141

2022年9月8日2022年9月9日

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

C++の練習を兼ねて, 第１０回アルゴリズム実技検定過去問の問題H (連結成分) を解いてみた.

■感想.
1. 問題Hは, 方針を絞り込めたので, AC版に到達できたと思う
2. Union-Find木の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 初めは, 深さ優先探索の方針で, 提出したものの TLE版(test_10.txt ～ test_12.txt)となったので, Union-Find木を利用して, 随時, 頂点情報を, マージする方針に変更した背景がある.
但し, マージの際に, 根に相当する頂点で, 場合分けしないと, TLE版(test_07.txt)となったので, 注意が必要と感じた.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第１０回アルゴリズム実技検定過去問の解説の各リンクをご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    
    // 2. dfs.
    // https://ja.wikipedia.org/wiki/深さ優先探索
    auto dfs = [&](auto&& self, int cur, int bef, set<int> &st) -> void {
        // 訪問済みチェック.
        if(st.count(cur)) return;
        
        // 訪問済設定.
        st.insert(cur);
        
        // 隣接頂点.
        for(auto &nex : G[cur]) if(nex != bef) self(self, nex, cur, st);
    };
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int t;
        scanf("%d", &t);
        
        // 3-2. クエリ 1.
        if(t == 1){
            int u, v;
            scanf("%d %d", &u, &v);
            --u;
            --v;
            G[u].insert(v);
            G[v].insert(u);
        }
        
        // 3-3. クエリ 2.
        if(t == 2){
            int u;
            scanf("%d", &u);
            --u;
            
            // 訪問経路保存.
            set<int> st;
            dfs(dfs, u, -1, st);
            
            // 出力.
            vi ans;
            for(auto &x : st) ans.pb(x);
            int n = ans.size();
            rep(i, n) printf("%d%s", ans[i] + 1, (i < n - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

set<int> G[202020];

int main(){

// 1. 入力情報.

int N, Q;

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

// 2. dfs.

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

auto dfs = [&](auto&& self, int cur, int bef, set<int> &st) -> void {

// 訪問済みチェック.

if(st.count(cur)) return;

// 訪問済設定.

st.insert(cur);

// 隣接頂点.

for(auto &nex : G[cur]) if(nex != bef) self(self, nex, cur, st);

};

// 3. クエリ回答.

rep(i, Q){

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

int t;

scanf("%d", &t);

// 3-2. クエリ 1.

if(t == 1){

int u, v;

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

--u;

--v;

G[u].insert(v);

G[v].insert(u);

}

// 3-3. クエリ 2.

if(t == 2){

int u;

scanf("%d", &u);

--u;

// 訪問経路保存.

set<int> st;

dfs(dfs, u, -1, st);

// 出力.

vi ans;

for(auto &x : st) ans.pb(x);

int n = ans.size();

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

}

return 0;

}

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

// 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
set<int> st[202020];

// 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, N){
        uf.unite(i, i);
        st[i].insert(i);
    }
    
    // 3. クエリ回答.
    rep(i, Q){
        // 3-1. クエリ入力情報.
        int t;
        scanf("%d", &t);
        
        // 3-2. クエリ 1.
        if(t == 1){
            int u, v;
            scanf("%d %d", &u, &v);
            --u;
            --v;
            
            // 連結の場合は, 次へ.
            if(uf.same(u, v)) continue;
            
            // 連結でなかった場合は, マージ.
            st[u].insert(v);
            st[v].insert(u);
            int ou = uf.find(u);
            int ov = uf.find(v);
            uf.unite(u, v);
            int o = uf.find(u);
            
            // マージ.
            // o = ou.
            if(o == ou){
                for(auto &x : st[ov]) st[o].insert(x);
                st[ov].clear();
                continue;
            }
            
            // o != ou (o = ov を 想定).
            for(auto &x : st[ou]) st[o].insert(x);
            st[ou].clear();
        }
        
        // 3-3. クエリ 2.
        if(t == 2){
            int u;
            scanf("%d", &u);
            --u;
            int o = uf.find(u);
            
            // 出力.
            vi ans;
            for(auto &x : st[o]) ans.pb(x);
            int n = ans.size();
            rep(i, n) printf("%d%s", ans[i] + 1, (i < n - 1) ? " " : "\n");
        }
    }
    return 0;
    
}

100

101

102

103

104

105

106

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

set<int> st[202020];

// 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, N){

uf.unite(i, i);

st[i].insert(i);

}

// 3. クエリ回答.

rep(i, Q){

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

int t;

scanf("%d", &t);

// 3-2. クエリ 1.

if(t == 1){

int u, v;

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

--u;

--v;

// 連結の場合は, 次へ.

if(uf.same(u, v)) continue;

// 連結でなかった場合は, マージ.

st[u].insert(v);

st[v].insert(u);

int ou = uf.find(u);

int ov = uf.find(v);

uf.unite(u, v);

int o = uf.find(u);

// マージ.

// o = ou.

if(o == ou){

for(auto &x : st[ov]) st[o].insert(x);

st[ov].clear();

continue;

}

// o != ou (o = ov を想定).

for(auto &x : st[ou]) st[o].insert(x);

st[ou].clear();

}

// 3-3. クエリ 2.

if(t == 2){

int u;

scanf("%d", &u);

--u;

int o = uf.find(u);

// 出力.

vi ans;

for(auto &x : st[o]) ans.pb(x);

int n = ans.size();

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

}

return 0;

}

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

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

[入力例]
1 2
2 1
2 1

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

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

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

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

[出力例]
1 2
1 2 3
1 2 3

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

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

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

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

100

[入力例]

5 7

1 1 2

2 2

1 3 4

2 5

1 1 4

2 1

2 4

[出力例]

1 2

1 2 3 4

※AtCoderテストケースより

[入力例]

1 2

2 1

[出力例]

※AtCoderテストケースより

[入力例]

3 3

1 1 2

2 1

1 1 2

[出力例]

1 2

※AtCoderテストケースより

[入力例]

3 7

1 1 2

2 1

1 1 2

1 1 3

2 1

1 2 3

2 2

[出力例]

1 2

1 2 3

[入力例]

7 10

1 1 7

2 7

1 1 4

1 5 6

1 2 3

2 1

1 2 5

2 3

1 1 3

2 1

[出力例]

1 7

1 4 7

2 3 5 6

1 2 3 4 5 6 7

[入力例]

10 18

2 1

1 1 2

1 3 4

2 2

1 5 6

1 1 2

1 7 8

2 5

1 9 10

1 1 3

1 7 8

2 3

1 7 9

2 8

1 2 5

2 4

1 6 8

2 10

[出力例]

1 2

5 6

1 2 3 4

7 8 9 10

1 2 3 4 5 6

1 2 3 4 5 6 7 8 9 10

■参照サイト
第１０回アルゴリズム実技検定過去問
 Union-Find木

2022年9月7日2022年9月7日

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

C++の練習を兼ねて, 第１０回アルゴリズム実技検定過去問の問題G (方程式) を解いてみた.

■感想.
1. 問題Gは, 方針を絞り込めたので, AC版に到達できたと思う
2. 個人的には, ニュートン法について, 学習できたので, 良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

本家のサイト第１０回アルゴリズム実技検定過去問の解説の各リンクをご覧下さい.

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

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

int main(){
    
    // 1. 入力情報.
    double a, b, c;
    scanf("%lf %lf %lf", &a, &b, &c);
    
    // 2. 方程式.
    auto f = [&](double x){
        return a * x * x * x * x * x + b * x + c;
    };
    
    // 3. 導関数.
    auto g = [&](double x){
        return 5.0 * a * x * x * x * x + b;
    };
    
    // 4. ニュートン法.
    // x[n + 1] = x[n] - f[x[n]] / f'[x[n]]
    double ans = 1.5;
    rep(i, 32) ans -= f(ans) / g(ans);
    
    // 5. 出力.
    printf("%.18lf\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--)

int main(){

// 1. 入力情報.

double a, b, c;

scanf("%lf %lf %lf", &a, &b, &c);

// 2. 方程式.

auto f = [&](double x){

return a * x * x * x * x * x + b * x + c;

};

// 3. 導関数.

auto g = [&](double x){

return 5.0 * a * x * x * x * x + b;

};

// 4. ニュートン法.

// x[n + 1] = x[n] - f[x[n]] / f'[x[n]]

double ans = 1.5;

rep(i, 32) ans -= f(ans) / g(ans);

// 5. 出力.

printf("%.18lf\n", ans);

return 0;

}

[入力例]
32 2 -246

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

[入力例]
12 3 -45

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

[入力例]
1 1 -3

[出力例]
1.132997565885065283

[入力例]
1 2 -5

[出力例]
1.208917813386894968

[入力例]
12345678 23456789 -200000000

[出力例]
1.670925787919859573

[入力例]

32 2 -246

[出力例]

1.500000000000000000

※AtCoderのテストケースより

[入力例]

12 3 -45

[出力例]

1.279562760087743278

※AtCoderのテストケースより

[入力例]

1 1 -3

[出力例]

1.132997565885065283

[入力例]

1 2 -5

[出力例]

1.208917813386894968

[入力例]

12345678 23456789 -200000000

[出力例]

1.670925787919859573

■参照サイト
第１０回アルゴリズム実技検定過去問

2022年9月6日

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

C++の練習を兼ねて, AtCoder Grand Contest 023 の問題C (Painting Machines) を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 但し, このような内容を解答で説明されているだろう, と推測した内容(重複カウントの除外など)をもとに, 実装している.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc023/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 LL MOD = 1e9 + 7;
const int LIMIT = 1010101;
LL FAC[LIMIT];
LL 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 0;
    LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 事前準備.
    FAC[0] = INV[0] = 1;
    repx(i, 1, LIMIT){
        FAC[i] = i * FAC[i - 1] % MOD;
        INV[i] = mPow(FAC[i], MOD - 2) % MOD;
    }
    
    // 3. 例外(N = 2).
    if(N == 2){
        puts("1");
        return 0;
    }
    
    // 4. 例外(N = 3).
    if(N == 3){
        puts("4");
        return 0;
    }
    
    // 5. N > 3.
    LL ans = 0, bef = 0;
    repx(k, 2, N){
        // 今回分更新.
        LL cur = combination(k - 1, N - 1 - k);
        cur %= MOD;
        cur *= FAC[k];
        cur %= MOD;
        cur *= FAC[N - 1 - k];
        cur %= MOD;
        
        // スコア化.
        // -> スコア化には, マシンの稼働回数を反映させる必要があるので, k を 設定.
        LL e = (LL)k;
        
        // 重複カウント削除.
        // -> k 回マシンを稼働したときの場合の数は, (k - 1) 回マシンを稼働した場合の数を, 
        // 重複カウントしているため, 除外する必要がある.
        e *= (cur + MOD - bef);
        e %= MOD;
        
        // 集計.
        ans += e;
        ans %= MOD;
        
        // 前回分更新.
        bef = cur;
    }
    
    // 6. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

100

// 解き直し.

// https://img.atcoder.jp/agc023/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 LL MOD = 1e9 + 7;

const int LIMIT = 1010101;

LL FAC[LIMIT];

LL 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 0;

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

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 事前準備.

FAC[0] = INV[0] = 1;

repx(i, 1, LIMIT){

FAC[i] = i * FAC[i - 1] % MOD;

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

}

// 3. 例外(N = 2).

if(N == 2){

puts("1");

return 0;

}

// 4. 例外(N = 3).

if(N == 3){

puts("4");

return 0;

}

// 5. N > 3.

LL ans = 0, bef = 0;

repx(k, 2, N){

// 今回分更新.

LL cur = combination(k - 1, N - 1 - k);

cur %= MOD;

cur *= FAC[k];

cur %= MOD;

cur *= FAC[N - 1 - k];

cur %= MOD;

// スコア化.

// -> スコア化には, マシンの稼働回数を反映させる必要があるので, k を設定.

LL e = (LL)k;

// 重複カウント削除.

// -> k 回マシンを稼働したときの場合の数は, (k - 1) 回マシンを稼働した場合の数を,

// 重複カウントしているため, 除外する必要がある.

e *= (cur + MOD - bef);

e %= MOD;

// 集計.

ans += e;

ans %= MOD;

// 前回分更新.

bef = cur;

}

// 6. 出力.

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

return 0;

}

[入力例]
4

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

[入力例]
2

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

[入力例]
5

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

[入力例]
100000

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

[入力例]
3

[出力例]
4

[入力例]
6

[出力例]
516

[入力例]
7

[出力例]
3696

[入力例]
10

[出力例]
2786400

[入力例]
11

[出力例]
31000320

[入力例]
2022

[出力例]
810002666

[入力例]
1000000

[出力例]
128397156

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100000

[出力例]

341429644

※AtCoderテストケースより

[入力例]

[出力例]

[入力例]

[出力例]

516

[入力例]

[出力例]

3696

[入力例]

[出力例]

2786400

[入力例]

[出力例]

31000320

[入力例]

2022

[出力例]

810002666

[入力例]

1000000

[出力例]

128397156

■参照サイト
AtCoder Grand Contest 023

2022年9月6日

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

C++の練習を兼ねて, AtCoder Beginner Contest 215 の問題C (One More aab aba baa) ～問題D (Coprime 2) を解いてみた.

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

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

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

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

int main(){
    
    // 1. 入力情報.
    char c[11];
    int K;
    scanf("%s %d", c, &K);
    string s(c);
    
    // 2. 分離後の二数の積を全探索.
    int n = s.size();
    vi z(n);
    iota(all(z), 0);
    set<string> st;
    do{
        // 並び替え.
        string cur;
        rep(i, n) cur.pb(s[z[i]]);
        
        // 保存.
        st.insert(cur);
    }while(next_permutation(all(z)));
    
    // 3. K 番目は？
    int d = 0;
    string ans;
    for(auto &x : st){
        if(++d == K){
            ans = x;
            break;
        }
    }
    
    // 4. 出力.
    printf("%s\n", ans.c_str());
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

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

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

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

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

#define pb push_back

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

int main(){

// 1. 入力情報.

char c[11];

int K;

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

string s(c);

// 2. 分離後の二数の積を全探索.

int n = s.size();

vi z(n);

iota(all(z), 0);

set<string> st;

do{

// 並び替え.

string cur;

rep(i, n) cur.pb(s[z[i]]);

// 保存.

st.insert(cur);

}while(next_permutation(all(z)));

// 3. K 番目は？

int d = 0;

string ans;

for(auto &x : st){

if(++d == K){

ans = x;

break;

}

// 4. 出力.

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

return 0;

}

[入力例]
aab 2

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

[入力例]
baba 4

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

[入力例]
ydxwacbz 40320

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

[入力例]
atcoder 2022

[出力例]
drtaoec

[入力例]
graph 99

[出力例]
rahgp

[入力例]
algorithm 202020

[出力例]
magolitrh
※文字列 S が, 問題文の制約条件から範囲外であるケース.

[入力例]

aab 2

[出力例]

aba

※AtCoderテストケースより

[入力例]

baba 4

[出力例]

baab

※AtCoderテストケースより

[入力例]

ydxwacbz 40320

[出力例]

zyxwdcba

※AtCoderテストケースより

[入力例]

atcoder 2022

[出力例]

drtaoec

[入力例]

graph 99

[出力例]

rahgp

[入力例]

algorithm 202020

[出力例]

magolitrh

※文字列 S が, 問題文の制約条件から範囲外であるケース.

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

// 解き直し.
// https://atcoder.jp/contests/abc215/editorial/2482
// 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 a first
#define b second
int a[101010], memo[101010];

// Efficient program to print all prime factors of a given number
// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/
// 与えられた正整数についての素因数分解を計算.
// @param X: 素因数分解を行う整数.
// @return ret: 素因数分解 の 結果 を 返却.
map<int, int> div(int X){
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<int, int> ret;
    while(!(X % 2)) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    repex(i, 3, sqrt(X) + 1, 2){
        while(!(X % i)){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 出力.
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 初期化.
    set<int> ans;
    rep(i, M) ans.insert(i + 1);
    
    // 3. 素因数分解.
    rep(i, N){
        map<int, int> m = div(a[i]);
        for(auto &x : m){
            int p = x.a;
            if(!memo[p]){
                ++memo[p];
                repex(j, p, M + 1, p) ans.erase(j);
            }
        }
    }
    
    // 4. 出力.
    printf("%d\n", ans.size());
    for(auto &x : ans) printf("%d\n", x);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc215/editorial/2482

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

#define b second

int a[101010], memo[101010];

// Efficient program to print all prime factors of a given number

// https://www.geeksforgeeks.org/print-all-prime-factors-of-a-given-number/

// 与えられた正整数についての素因数分解を計算.

// @param X: 素因数分解を行う整数.

// @return ret: 素因数分解の結果を返却.

map<int, int> div(int X){

// 1. X を 2で割り切れなくなるまで割っていく.

map<int, int> ret;

while(!(X % 2)) ret[2]++, X >>= 1;

// 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.

repex(i, 3, sqrt(X) + 1, 2){

while(!(X % i)){

ret[i]++;

X /= i;

}

// 3. X が 2 より大きな素数であれば, 追加.

if(X > 2) ret[X]++;

// 4. 出力.

return ret;

}

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 初期化.

set<int> ans;

rep(i, M) ans.insert(i + 1);

// 3. 素因数分解.

rep(i, N){

map<int, int> m = div(a[i]);

for(auto &x : m){

int p = x.a;

if(!memo[p]){

++memo[p];

repex(j, p, M + 1, p) ans.erase(j);

}

// 4. 出力.

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

for(auto &x : ans) printf("%d\n", x);

return 0;

}

[入力例]
3 12
6 1 5

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

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

[出力例]
5
1
7
11
13
17

[入力例]
20 100
13 23 35 77 121 61 31 29 49 83 19 37 43 125 25 17 41 19 11 23

[出力例]
30
1
2
3
4
6
8
9
12
16
18
24
27
32
36
47
48
53
54
59
64
67
71
72
73
79
81
89
94
96
97

[入力例]

3 12

6 1 5

[出力例]

※AtCoderテストケースより

[入力例]

5 17

3 1 4 1 5

[出力例]

[入力例]

20 100

13 23 35 77 121 61 31 29 49 83 19 37 43 125 25 17 41 19 11 23

[出力例]

■参照サイト
AtCoder Beginner Contest 215

2022年9月5日

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

C++の練習を兼ねて, AtCoder Regular Contest 147 の問題A (Max Mod Min) ～問題B (Swap to Sort) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 問題B で, 解説上の不一致度に着目するロジックが, 興味深く感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
#define all(x) x.begin(), x.end()

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi a(N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. sort.
    sort(all(a));
    
    // 3. 初期化.
    deque<int> dq;
    rep(i, N) dq.pub(a[i]);
    
    // 4. 操作.
    int ans = 0;
    while(dq.size() > 1){
        int f = dq.front();
        int b = dq.back();
        int o = b % f;
        dq.pob();
        if(o) dq.puf(o);
        ++ans;
    }
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

#define pob pop_back

#define pub push_back

#define puf push_front

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi a(N);

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

// 2. sort.

sort(all(a));

// 3. 初期化.

deque<int> dq;

rep(i, N) dq.pub(a[i]);

// 4. 操作.

int ans = 0;

while(dq.size() > 1){

int f = dq.front();

int b = dq.back();

int o = b % f;

dq.pob();

if(o) dq.puf(o);

++ans;

}

// 5. 出力.

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

return 0;

}

[入力例]
3
2 3 6

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

[入力例]
6
1232 452 23491 34099 57341 21488

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

[入力例]
30
690839 681001 673615 114111 1173455 293172 906181 441519 317712 908733 1064265 878123 887479 667932 1051871 199356 431790 921027 926847 604481 1083959 314196 986396 198435 1079681 611949 102587 1037040 152797 571464

[出力例]
40

[入力例]
100
804525 118689 861132 422425 442375 257878 324931 704557 388539 1178755 437841 1177023 841380 148310 609048 14604 338624 131234 949468 1060690 178261 884195 907106 1135753 595559 866150 952572 390385 1019422 1180183 1025298 859197 1202522 795301 1102581 1176448 837332 295121 658009 866628 51756 505419 1065818 981407 122347 1114513 863223 176961 688853 1157438 714453 941949 133985 1103419 1182513 133395 924468 598392 782989 486935 216707 386947 580800 78067 663205 613537 1026505 71693 264315 504372 880813 1134919 1049543 338607 311239 412742 625586 994282 288497 404511 613004 1138285 610335 441416 1044753 130813 877580 992152 1122477 1061120 412998 303249 101010 1090380 1317832 982051 216534 699552 242477 978562

[出力例]
110

[入力例]
500
6779880 4971835 1015574 5352268 7070513 133441 8063840 10165894 10282398 11735140 7233410 11930946 11998886 3686385 8805484 4380571 7663517 11150208 7033995 2709335 1225454 495240 4525625 3173211 11271375 1205730 6677011 4829422 38186 2713695 10975492 5989794 2477361 6136054 4899823 1043044 7797391 6936257 11578227 6624862 8205359 8211221 6495623 4702766 9912380 8369740 5892730 3833142 10766361 790833 10508324 1142773 10129891 5235871 4996111 9477247 9115308 1213596 7227510 4493695 6985174 6095392 6600088 10302078 10514013 1826723 8748030 5103427 676617 5866650 10995329 8051169 2941351 4055602 508507 7419978 1170090 1463329 6470294 5808928 12194451 2344569 5411184 4452500 2469784 7947911 9934457 89185 9227252 6166318 4488795 11802055 8873635 6922597 4466650 5672410 10276288 3613278 2790632 9588031 896984 2325282 4605286 6048279 4344211 5664883 12289498 5634070 9966767 6543977 1962906 7624026 7824737 10853653 576718 5345231 2403229 4342226 10698482 10615315 2205578 3477321 1335700 3399911 1259451 8554750 8597987 7428304 4348887 4714576 4854819 7769133 926019 5596565 9161746 1526518 5645554 10575143 1739227 6307843 3304803 6789105 7886528 10858263 8734277 10164080 8895929 2337264 9209984 8549624 8608802 8628478 1641259 6266505 12174668 9686538 8208237 5255801 9777633 4137268 8020764 5463636 7641320 5574332 1611485 877627 2015614 265698 6181038 11487466 12002025 7226935 2049999 3066412 4745798 9651668 11441578 11510689 11392212 10313420 5362176 5467048 10606961 11559198 1026100 6486690 3585947 4289959 11177730 1563326 11875610 2539551 10524993 8074300 5629925 7356279 5986558 3021430 3042290 3023834 4073337 6109827 3447682 10663442 12329494 7408066 11066595 2215619 7886572 7702171 4912185 1212681 6357945 5305069 3772778 4668361 8925585 10530751 5739199 742173 70608848 7193524 7508657 347424 2851569 7147124 8076428 1699238 2412066 474361 9586071 1544585 900798 5011709 11568782 4624258 4047041 7866591 558011 12036468 4093305 3376693 4921964 1166065 1227564 10091356 4251395 4009801 9609174 1781296 2449601 433300 12020798 4561616 6444084 10989545 11433414 4491088 4175041 4101520 9751204 1411766 2931193 452652 8971040 703969 7261895 2365041 10019442 7824936 2738109 10743088 10131240 7116344 6908719 3351197 10652117 9979493 709422 5165045 3708986 10074236 3439944 9094454 4471097 3533551 1776052 12176435 11753268 8736835 11376227 12038239 1014104 628217 1665200 4692997 223742 1209022 2904028 1060070 4104362 8489825 9850826 8230595 3713250 5527162 902871 9863328 12302627 8801524 3095526 6883962 11140169 4531025 3216820 4258442 7730184 3535142 4980098 5981875 5373657 2784460 11292626 3146466 223716 8524830 3453136 4959252 11893591 497386 3129823 5409059 9572767 7034018 9201240 6335836 901817 12249987 2450342 10142141 4537381 9536295 8595477 9737932 3179766 8727207 9129442 9747369 2266677 7797706 3153061 7468753 4328422 6741557 7787271 2485820 128138 3585965 11974447 10743505 7256222 11481815 11987140 9060049 12119747 7401180 5741522 2942874 6493068 9206507 12093427 10933262 6954035 10965770 4646600 7540211 8439219 6153431 10112487 8600815 7981071 11364639 3714169 3056881 2571597 8366519 7063781 8051912 11388485 4937513 10945729 6827511 3326916 11193809 2570591 7634336 2637634 3087939 5606320 12051638 3842599 12221131 1808203 8544302 1228357 3476303 9164674 7737172 6022409 1585621 3651445 3872367 9623297 9849870 2850729 6427217 9780809 11513981 2007995 4843343 5833389 8351766 8925060 1136895 706898 1860852 5508373 11023490 2860900 9343123 4769002 3152618 2504216 1725735 8308050 3607069 1311706 11301077 3142780 9200852 9248901 7574290 6059147 5883443 83770 1390120 9810233 8822867 1106626 10217929 4454732 6625713 3891056 4526185 121713503 2373259 9348404 10152689 3132226 4085007 3900658 9434021 1737495 2210026 7536394 7374497 11324217 12285723 8123861 4541797 6245306 8295958 424095 4799787 12020867 9874591 9705068 9102631 12089867 310680 4324117 7702818 8007148 11756467 3357439 2202436 1605567 7013801 3174623 7487433 1541473 9029428 9079914 1039420 487580 1566390 3683100 7634560 10486548 3797205

[出力例]
515

[入力例]

2 3 6

[出力例]

※AtCoderのテストケースより

[入力例]

1232 452 23491 34099 57341 21488

[出力例]

※AtCoderのテストケースより

[入力例]

690839 681001 673615 114111 1173455 293172 906181 441519 317712 908733 1064265 878123 887479 667932 1051871 199356 431790 921027 926847 604481 1083959 314196 986396 198435 1079681 611949 102587 1037040 152797 571464

[出力例]

[入力例]

100

804525 118689 861132 422425 442375 257878 324931 704557 388539 1178755 437841 1177023 841380 148310 609048 14604 338624 131234 949468 1060690 178261 884195 907106 1135753 595559 866150 952572 390385 1019422 1180183 1025298 859197 1202522 795301 1102581 1176448 837332 295121 658009 866628 51756 505419 1065818 981407 122347 1114513 863223 176961 688853 1157438 714453 941949 133985 1103419 1182513 133395 924468 598392 782989 486935 216707 386947 580800 78067 663205 613537 1026505 71693 264315 504372 880813 1134919 1049543 338607 311239 412742 625586 994282 288497 404511 613004 1138285 610335 441416 1044753 130813 877580 992152 1122477 1061120 412998 303249 101010 1090380 1317832 982051 216534 699552 242477 978562

[出力例]

110

[入力例]

500

6779880 4971835 1015574 5352268 7070513 133441 8063840 10165894 10282398 11735140 7233410 11930946 11998886 3686385 8805484 4380571 7663517 11150208 7033995 2709335 1225454 495240 4525625 3173211 11271375 1205730 6677011 4829422 38186 2713695 10975492 5989794 2477361 6136054 4899823 1043044 7797391 6936257 11578227 6624862 8205359 8211221 6495623 4702766 9912380 8369740 5892730 3833142 10766361 790833 10508324 1142773 10129891 5235871 4996111 9477247 9115308 1213596 7227510 4493695 6985174 6095392 6600088 10302078 10514013 1826723 8748030 5103427 676617 5866650 10995329 8051169 2941351 4055602 508507 7419978 1170090 1463329 6470294 5808928 12194451 2344569 5411184 4452500 2469784 7947911 9934457 89185 9227252 6166318 4488795 11802055 8873635 6922597 4466650 5672410 10276288 3613278 2790632 9588031 896984 2325282 4605286 6048279 4344211 5664883 12289498 5634070 9966767 6543977 1962906 7624026 7824737 10853653 576718 5345231 2403229 4342226 10698482 10615315 2205578 3477321 1335700 3399911 1259451 8554750 8597987 7428304 4348887 4714576 4854819 7769133 926019 5596565 9161746 1526518 5645554 10575143 1739227 6307843 3304803 6789105 7886528 10858263 8734277 10164080 8895929 2337264 9209984 8549624 8608802 8628478 1641259 6266505 12174668 9686538 8208237 5255801 9777633 4137268 8020764 5463636 7641320 5574332 1611485 877627 2015614 265698 6181038 11487466 12002025 7226935 2049999 3066412 4745798 9651668 11441578 11510689 11392212 10313420 5362176 5467048 10606961 11559198 1026100 6486690 3585947 4289959 11177730 1563326 11875610 2539551 10524993 8074300 5629925 7356279 5986558 3021430 3042290 3023834 4073337 6109827 3447682 10663442 12329494 7408066 11066595 2215619 7886572 7702171 4912185 1212681 6357945 5305069 3772778 4668361 8925585 10530751 5739199 742173 70608848 7193524 7508657 347424 2851569 7147124 8076428 1699238 2412066 474361 9586071 1544585 900798 5011709 11568782 4624258 4047041 7866591 558011 12036468 4093305 3376693 4921964 1166065 1227564 10091356 4251395 4009801 9609174 1781296 2449601 433300 12020798 4561616 6444084 10989545 11433414 4491088 4175041 4101520 9751204 1411766 2931193 452652 8971040 703969 7261895 2365041 10019442 7824936 2738109 10743088 10131240 7116344 6908719 3351197 10652117 9979493 709422 5165045 3708986 10074236 3439944 9094454 4471097 3533551 1776052 12176435 11753268 8736835 11376227 12038239 1014104 628217 1665200 4692997 223742 1209022 2904028 1060070 4104362 8489825 9850826 8230595 3713250 5527162 902871 9863328 12302627 8801524 3095526 6883962 11140169 4531025 3216820 4258442 7730184 3535142 4980098 5981875 5373657 2784460 11292626 3146466 223716 8524830 3453136 4959252 11893591 497386 3129823 5409059 9572767 7034018 9201240 6335836 901817 12249987 2450342 10142141 4537381 9536295 8595477 9737932 3179766 8727207 9129442 9747369 2266677 7797706 3153061 7468753 4328422 6741557 7787271 2485820 128138 3585965 11974447 10743505 7256222 11481815 11987140 9060049 12119747 7401180 5741522 2942874 6493068 9206507 12093427 10933262 6954035 10965770 4646600 7540211 8439219 6153431 10112487 8600815 7981071 11364639 3714169 3056881 2571597 8366519 7063781 8051912 11388485 4937513 10945729 6827511 3326916 11193809 2570591 7634336 2637634 3087939 5606320 12051638 3842599 12221131 1808203 8544302 1228357 3476303 9164674 7737172 6022409 1585621 3651445 3872367 9623297 9849870 2850729 6427217 9780809 11513981 2007995 4843343 5833389 8351766 8925060 1136895 706898 1860852 5508373 11023490 2860900 9343123 4769002 3152618 2504216 1725735 8308050 3607069 1311706 11301077 3142780 9200852 9248901 7574290 6059147 5883443 83770 1390120 9810233 8822867 1106626 10217929 4454732 6625713 3891056 4526185 121713503 2373259 9348404 10152689 3132226 4085007 3900658 9434021 1737495 2210026 7536394 7374497 11324217 12285723 8123861 4541797 6245306 8295958 424095 4799787 12020867 9874591 9705068 9102631 12089867 310680 4324117 7702818 8007148 11756467 3357439 2202436 1605567 7013801 3174623 7487433 1541473 9029428 9079914 1039420 487580 1566390 3683100 7634560 10486548 3797205

[出力例]

515

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

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

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vi p(N + 1);
    rep(i, N) scanf("%d", &p[i + 1]);
    
    // 2. sort.
    // 2-1. 操作 B(悪いインデックスを端に集める).
    vp ans;
    vi d(N + 1);
    repx(i, 1, N + 1) if((i + p[i]) % 2 != 0) d[i] = 1;
    bool ok = false;
    while(!ok){
        ok = true;
        repr(i, N, 2){
            if(i > 2 && !d[i - 2] && d[i]){
                ok = false;
                ans.pb({1, i - 2});
                swap(p[i - 2], p[i]);
                swap(d[i - 2], d[i]);
            }
        }
    }
    
    // 2-2. 操作 A(不一致度を 0 にする).
    repex(i, 1, N + 1, 2){
        if(d[i]){
            ans.pb({0, i});
            swap(p[i], p[i + 1]);
        }
    }
    
    // 2-3. 操作 B(p[i] > p[i + 2] を 入れ替え).
    ok = false;
    while(!ok){
        ok = true;
        repx(i, 1, N - 1){
            if(p[i] > p[i + 2]){
                ok = false;
                ans.pb({1, i});
                swap(p[i], p[i + 2]);
            }
        }
    }
    vi z(N + 1);
    iota(all(z), 0);
    assert(z == p);
    
    // 3. 出力.
    printf("%d\n", ans.size());
    for(auto &p : ans) printf("%s %d\n", p.a ? "B" : "A", p.b);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/arc147/editorial/4668

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, int>;

using vp = vector<P>;

using vi = vector<int>;

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

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

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

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

#define pb push_back

#define a first

#define b second

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

vi p(N + 1);

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

// 2. sort.

// 2-1. 操作 B(悪いインデックスを端に集める).

vp ans;

vi d(N + 1);

repx(i, 1, N + 1) if((i + p[i]) % 2 != 0) d[i] = 1;

bool ok = false;

while(!ok){

ok = true;

repr(i, N, 2){

if(i > 2 && !d[i - 2] && d[i]){

ok = false;

ans.pb({1, i - 2});

swap(p[i - 2], p[i]);

swap(d[i - 2], d[i]);

}

// 2-2. 操作 A(不一致度を 0 にする).

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

if(d[i]){

ans.pb({0, i});

swap(p[i], p[i + 1]);

}

// 2-3. 操作 B(p[i] > p[i + 2] を入れ替え).

ok = false;

while(!ok){

ok = true;

repx(i, 1, N - 1){

if(p[i] > p[i + 2]){

ok = false;

ans.pb({1, i});

swap(p[i], p[i + 2]);

}

vi z(N + 1);

iota(all(z), 0);

assert(z == p);

// 3. 出力.

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

for(auto &p : ans) printf("%s %d\n", p.a ? "B" : "A", p.b);

return 0;

}

[入力例]
4
3 2 4 1

[出力例]
4
A 3
B 1
B 2
B 2
※AtCoderテストケースより

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

[入力例]
3
1 2 3

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

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

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

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

[出力例]
27
B 7
B 4
B 2
B 1
B 6
B 4
B 3
B 8
B 6
B 5
A 1
A 3
A 5
B 1
B 4
B 5
B 6
B 7
B 8
B 2
B 3
B 4
B 5
B 6
B 1
B 2
B 3

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

[出力例]
31
B 8
B 7
B 6
B 3
B 2
B 1
B 10
B 9
B 8
B 5
B 4
B 3
B 7
B 6
B 5
A 1
A 3
A 5
B 3
B 5
B 6
B 7
B 8
B 10
B 1
B 3
B 5
B 6
B 8
B 6
B 4

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

[出力例]
171
B 23
B 22
B 21
B 20
B 19
B 18
B 16
B 14
B 11
B 10
B 7
B 5
B 4
B 3
B 2
B 25
B 24
B 23
B 22
B 21
B 20
B 18
B 16
B 13
B 12
B 9
B 7
B 6
B 5
B 4
B 26
B 24
B 22
B 20
B 18
B 15
B 14
B 11
B 9
B 8
B 7
B 6
B 28
B 26
B 24
B 22
B 20
B 17
B 16
B 13
B 11
B 10
B 9
B 8
B 19
B 18
B 15
B 13
B 12
B 11
B 10
B 17
B 15
B 14
B 13
B 12
B 16
B 14
A 1
A 3
A 5
A 7
A 9
A 11
A 13
B 1
B 2
B 4
B 5
B 6
B 7
B 8
B 9
B 10
B 11
B 12
B 13
B 14
B 15
B 16
B 17
B 18
B 20
B 21
B 22
B 23
B 24
B 25
B 26
B 27
B 28
B 4
B 5
B 6
B 7
B 8
B 9
B 10
B 13
B 15
B 16
B 18
B 19
B 20
B 23
B 24
B 25
B 26
B 2
B 3
B 6
B 7
B 8
B 11
B 13
B 14
B 16
B 17
B 22
B 23
B 24
B 1
B 6
B 11
B 12
B 14
B 15
B 20
B 21
B 22
B 4
B 9
B 10
B 12
B 13
B 18
B 19
B 20
B 2
B 7
B 8
B 10
B 11
B 16
B 17
B 18
B 5
B 9
B 14
B 15
B 16
B 3
B 12
B 13
B 14
B 10
B 11
B 12
B 8
B 9
B 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

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

[入力例]

3 2 4 1

[出力例]

A 3

B 1

B 2

※AtCoderテストケースより

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

B 2

B 1

A 1

B 2

[入力例]

1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

2 1 4 3 6 5

[出力例]

A 1

A 3

A 5

※AtCoderテストケースより

[入力例]

1 2 8 6 10 7 3 5 4 9

[出力例]

B 7

B 4

B 2

B 1

B 6

B 4

B 3

B 8

B 6

B 5

A 1

A 3

A 5

B 1

B 4

B 5

B 6

B 7

B 8

B 2

B 3

B 4

B 5

B 6

B 1

B 2

B 3

[入力例]

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

[出力例]

B 8

B 7

B 6

B 3

B 2

B 1

B 10

B 9

B 8

B 5

B 4

B 3

B 7

B 6

B 5

A 1

A 3

A 5

B 3

B 5

B 6

B 7

B 8

B 10

B 1

B 3

B 5

B 6

B 8

B 6

B 4

[入力例]

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

[出力例]

171

B 23

B 22

B 21

B 20

B 19

B 18

B 16

B 14

B 11

B 10

B 7

B 5

B 4

B 3

B 2

B 25

B 24

B 23

B 22

B 21

B 20

B 18

B 16

B 13

B 12

B 9

B 7

B 6

B 5

B 4

B 26

B 24

B 22

B 20

B 18

B 15

B 14

B 11

B 9

B 8

B 7

B 6

B 28

B 26

B 24

B 22

B 20

B 17

B 16

B 13

B 11

B 10

B 9

B 8

B 19

B 18

B 15

B 13

B 12

B 11

B 10

B 17

B 15

B 14

B 13

B 12

B 16

B 14

A 1

A 3

A 5

A 7

A 9

A 11

A 13

B 1

B 2

B 4

B 5

B 6

B 7

B 8

B 9

B 10

B 11

B 12

B 13

B 14

B 15

B 16

B 17

B 18

B 20

B 21

B 22

B 23

B 24

B 25

B 26

B 27

B 28

B 4

B 5

B 6

B 7

B 8

B 9

B 10

B 13

B 15

B 16

B 18

B 19

B 20

B 23

B 24

B 25

B 26

B 2

B 3

B 6

B 7

B 8

B 11

B 13

B 14

B 16

B 17

B 22

B 23

B 24

B 1

B 6

B 11

B 12

B 14

B 15

B 20

B 21

B 22

B 4

B 9

B 10

B 12

B 13

B 18

B 19

B 20

B 2

B 7

B 8

B 10

B 11

B 16

B 17

B 18

B 5

B 9

B 14

B 15

B 16

B 3

B 12

B 13

B 14

B 10

B 11

B 12

B 8

B 9

B 10

■参照サイト
AtCoder Regular Contest 147

2022年9月4日2022年9月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 267 の問題B (Split?) ～問題E (Erasing Vertices 2) を解いてみた.

■感想.
1. 問題D, Eは, いったん実装してみたものの, 方針が誤っていたので, 解説を参考に, AC版に到達できたと思う.
2. 問題D で, 苦手な動的計画法の訓練を積めたので, 非常に良かったと思う.
3. 実装に苦労したものの問題Eで, 二分探索の復習が出来たので, 非常に良かったと思う.
4. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

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

int main(){
    
    // 1. 入力情報.
    char c[22];
    scanf("%s", c);
    string s(c);
    
    // 2. 出力.
    // 2-1. ピン 1 が 立っている.
    if(s[0] == '1'){
        puts("No");
        return 0;
    }
    
    // 2-2. ピン 4 が 倒れている.
    if(s[3] == '0'){
        // ピン 7.
        int l = s[6] - '0';
        
        // ピン 2, 3, 5, 6, 8, 9, 10.
        int r = s[1] - '0';
        r += s[2] - '0';
        r += s[4] - '0';
        r += s[5] - '0';
        r += s[7] - '0';
        r += s[8] - '0';
        r += s[9] - '0';
        
        // スプリット.
        if(l && r){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-3. ピン 2, 8 が 倒れている.
    if(s[1] == '0' && s[7] == '0'){
        // ピン 4, 7.
        int l = s[3] - '0';
        l += s[6] - '0';
        
        // ピン 3, 5, 6, 9, 10.
        int r = s[2] - '0';
        r += s[4] - '0';
        r += s[5] - '0';
        r += s[8] - '0';
        r += s[9] - '0';
        
        // スプリット.
        if(l && r){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-4. ピン 1, 5 が 倒れている.
    if(s[4] == '0'){
        // ピン 2, 4, 7, 8.
        int l = s[1] - '0';
        l += s[3] - '0';
        l += s[6] - '0';
        l += s[7] - '0';
        
        // ピン 3, 6, 9, 10.
        int r = s[2] - '0';
        r += s[5] - '0';
        r += s[8] - '0';
        r += s[9] - '0';
        
        // スプリット.
        if(l && r){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-5. ピン 3, 9 が 倒れている.
    if(s[2] == '0' && s[8] == '0'){
        // ピン 2, 4, 5, 7, 8.
        int l = s[1] - '0';
        l += s[3] - '0';
        l += s[4] - '0';
        l += s[6] - '0';
        l += s[7] - '0';
        
        // ピン 6, 10.
        int r = s[5] - '0';
        r += s[9] - '0';
        
        // スプリット.
        if(l && r){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-6. ピン 6 が 倒れている.
    if(s[5] == '0'){
        // ピン 2, 3, 4, 5, 7, 8, 9.
        int l = s[1] - '0';
        l += s[2] - '0';
        l += s[3] - '0';
        l += s[4] - '0';
        l += s[6] - '0';
        l += s[7] - '0';
        l += s[8] - '0';
        
        // ピン 10.
        int r = s[9] - '0';
        
        // スプリット.
        if(l && r){
            puts("Yes");
            return 0;
        }
    }
    
    // 2-7. 上記以外.
    puts("No");
    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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

char c[22];

scanf("%s", c);

string s(c);

// 2. 出力.

// 2-1. ピン 1 が立っている.

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

puts("No");

return 0;

}

// 2-2. ピン 4 が倒れている.

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

// ピン 7.

int l = s[6] - '0';

// ピン 2, 3, 5, 6, 8, 9, 10.

int r = s[1] - '0';

r += s[2] - '0';

r += s[4] - '0';

r += s[5] - '0';

r += s[7] - '0';

r += s[8] - '0';

r += s[9] - '0';

// スプリット.

if(l && r){

puts("Yes");

return 0;

}

// 2-3. ピン 2, 8 が倒れている.

if(s[1] == '0' && s[7] == '0'){

// ピン 4, 7.

int l = s[3] - '0';

l += s[6] - '0';

// ピン 3, 5, 6, 9, 10.

int r = s[2] - '0';

r += s[4] - '0';

r += s[5] - '0';

r += s[8] - '0';

r += s[9] - '0';

// スプリット.

if(l && r){

puts("Yes");

return 0;

}

// 2-4. ピン 1, 5 が倒れている.

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

// ピン 2, 4, 7, 8.

int l = s[1] - '0';

l += s[3] - '0';

l += s[6] - '0';

l += s[7] - '0';

// ピン 3, 6, 9, 10.

int r = s[2] - '0';

r += s[5] - '0';

r += s[8] - '0';

r += s[9] - '0';

// スプリット.

if(l && r){

puts("Yes");

return 0;

}

// 2-5. ピン 3, 9 が倒れている.

if(s[2] == '0' && s[8] == '0'){

// ピン 2, 4, 5, 7, 8.

int l = s[1] - '0';

l += s[3] - '0';

l += s[4] - '0';

l += s[6] - '0';

l += s[7] - '0';

// ピン 6, 10.

int r = s[5] - '0';

r += s[9] - '0';

// スプリット.

if(l && r){

puts("Yes");

return 0;

}

// 2-6. ピン 6 が倒れている.

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

// ピン 2, 3, 4, 5, 7, 8, 9.

int l = s[1] - '0';

l += s[2] - '0';

l += s[3] - '0';

l += s[4] - '0';

l += s[6] - '0';

l += s[7] - '0';

l += s[8] - '0';

// ピン 10.

int r = s[9] - '0';

// スプリット.

if(l && r){

puts("Yes");

return 0;

}

// 2-7. 上記以外.

puts("No");

return 0;

}

[入力例]
0101110101

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

[入力例]
0100101001

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

[入力例]
0000100110

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

[入力例]
1101110101

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

[入力例]
0101010101

[出力例]
Yes

[入力例]
0110110110

[出力例]
No

[入力例]

0101110101

[出力例]

Yes

※AtCoderテストケースより

[入力例]

0100101001

[出力例]

Yes

※AtCoderテストケースより

[入力例]

0000100110

[出力例]

※AtCoderテストケースより

[入力例]

1101110101

[出力例]

※AtCoderテストケースより

[入力例]

0101010101

[出力例]

Yes

[入力例]

0110110110

[出力例]

■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 a[202020], aCum[202020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    LL cur = 0;
    rep(i, N){
        scanf("%lld", &a[i]);
        aCum[i + 1] = aCum[i] + a[i];
        if(i < M) cur += a[i] * (LL)(i + 1);
    }
    
    // 2. 最大値は？
    LL ans = cur;
    repx(i, 1, N - M + 1){
        cur += a[i - 1 + M] * (LL)M;
        cur -= (aCum[i - 1 + M] - aCum[i - 1]);
        ans = max(ans, cur);
    }
    
    // 3. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

LL a[202020], aCum[202020];

int main(){

// 1. 入力情報.

int N, M;

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

LL cur = 0;

rep(i, N){

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

aCum[i + 1] = aCum[i] + a[i];

if(i < M) cur += a[i] * (LL)(i + 1);

}

// 2. 最大値は？

LL ans = cur;

repx(i, 1, N - M + 1){

cur += a[i - 1 + M] * (LL)M;

cur -= (aCum[i - 1 + M] - aCum[i - 1]);

ans = max(ans, cur);

}

// 3. 出力.

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

return 0;

}

[入力例]
4 2
5 4 -1 8

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

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

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

[入力例]
20 5
66 -110 31 68 -109 93 74 115 -63 37 -118 23 47 -99 31 44 -82 -39 6 -66

[出力例]
1000

[入力例]
50 7
16 30 -111 55 110 -121 0 67 -112 22 89 -90 20 102 -52 8 75 51 78 30 -48 100 3 29 -98 -67 77 60 65 -100 38 29 116 -57 67 1 15 -32 68 100 54 -123 24 -91 -91 118 6 -86 -55 77

[出力例]
1327

[入力例]

4 2

5 4 -1 8

[出力例]

※AtCoderテストケースより

[入力例]

10 4

-3 1 -4 1 -5 9 -2 6 -5 3

[出力例]

※AtCoderテストケースより

[入力例]

20 5

66 -110 31 68 -109 93 74 115 -63 37 -118 23 47 -99 31 44 -82 -39 6 -66

[出力例]

1000

[入力例]

50 7

16 30 -111 55 110 -121 0 67 -112 22 89 -90 20 102 -52 8 75 51 78 30 -48 100 3 29 -98 -67 77 60 65 -100 38 29 116 -57 67 1 15 -32 68 100 54 -123 24 -91 -91 118 6 -86 -55 77

[出力例]

1327

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 初期化(解説通り).
    rep(i, N + 1) repx(j, i + 1, N + 1) dp[i][j] = -INF;
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        repx(j, 1, i + 1){
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1] * (LL)j);
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[N][M]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc267/editorial/4728

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

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

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

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

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

const LL INF = 101010101010101010;

LL dp[2020][2020], a[2020];

int main(){

// 1. 入力情報.

int N, M;

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

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

// 2. 初期化(解説通り).

rep(i, N + 1) repx(j, i + 1, N + 1) dp[i][j] = -INF;

// 3. dp更新.

repx(i, 1, N + 1){

repx(j, 1, i + 1){

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + a[i - 1] * (LL)j);

}

// 4. 出力.

printf("%lld\n", dp[N][M]);

return 0;

}

[入力例]
4 2
5 4 -1 8

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

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

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

[入力例]
20 5
66 -110 31 68 -109 93 74 115 -63 37 -118 23 47 -99 31 44 -82 -39 6 -66

[出力例]
1352

[入力例]
50 7
16 30 -111 55 110 -121 0 67 -112 22 89 -90 20 102 -52 8 75 51 78 30 -48 100 3 29 -98 -67 77 60 65 -100 38 29 116 -57 67 1 15 -32 68 100 54 -123 24 -91 -91 118 6 -86 -55 77

[出力例]
3000

[入力例]

4 2

5 4 -1 8

[出力例]

※AtCoderテストケースより

[入力例]

10 4

-3 1 -4 1 -5 9 -2 6 -5 3

[出力例]

※AtCoderテストケースより

[入力例]

20 5

66 -110 31 68 -109 93 74 115 -63 37 -118 23 47 -99 31 44 -82 -39 6 -66

[出力例]

1352

[入力例]

50 7

16 30 -111 55 110 -121 0 67 -112 22 89 -90 20 102 -52 8 75 51 78 30 -48 100 3 29 -98 -67 77 60 65 -100 38 29 116 -57 67 1 15 -32 68 100 54 -123 24 -91 -91 118 6 -86 -55 77

[出力例]

3000

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

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

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) scanf("%lld", &a[i]);
    vvi G(N);
    rep(i, M){
        int u, v;
        scanf("%d %d", &u, &v);
        --u;
        --v;
        G[u].pb(v);
        G[v].pb(u);
    }
    
    // 2. 評価関数.
    auto f = [&](LL m) -> bool {
        // 2-1. 初期化.
        LL cost[N];
        int memo[N];
        rep(i, N) cost[i] = memo[i] = 0;
        rep(i, N) for(auto &u : G[i]) cost[i] += a[u];
        
        // 2-2. スタック に 追加.
        stack<int> st;
        rep(i, N) if(cost[i] <= m) st.push(i), ++memo[i];
        
        // 2-3. 操作.
        while(!st.empty()){
            // 頂点を取り出す.
            int u = st.top();
            st.pop();
            
            // 隣接頂点を確認.
            for(auto &v : G[u]){
                if(!memo[v]){
                    // コスト減算.
                    cost[v] -= a[u];
                    
                    // コストが, m以下ならば, 頂点 を スタック に 追加.
                    if(cost[v] <= m) st.push(v), ++memo[v];
                }
            }
        }
        
        // 2-4. 未削除の頂点が残っているか？
        bool ok = false;
        rep(i, N) if(!memo[i]) ok = true;
        
        // 2-5. 判定結果.
        return ok;
    };
    
    // 3. 二分探索で確認してみる.
    // test_10.txt ～ test_13.txt で, WA版だったため, l = 0 でなく, l = -1 に修正.
    // -> これらのテストケースは, M = 0 に, 該当すると予想.
    LL l = -1, h = 202020202020202020, m;
    while(l + 1 < h){
        LL m = (h + l) >> 1;
        if(f(m)) l = m;
        else     h = m;
    }
    
    // 4. 出力.
    printf("%lld\n", h);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc267/editorial/4729

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

LL a[202020];

int main(){

// 1. 入力情報.

int N, M;

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

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

vvi G(N);

rep(i, M){

int u, v;

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

--u;

--v;

G[u].pb(v);

G[v].pb(u);

}

// 2. 評価関数.

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

// 2-1. 初期化.

LL cost[N];

int memo[N];

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

rep(i, N) for(auto &u : G[i]) cost[i] += a[u];

// 2-2. スタックに追加.

stack<int> st;

rep(i, N) if(cost[i] <= m) st.push(i), ++memo[i];

// 2-3. 操作.

while(!st.empty()){

// 頂点を取り出す.

int u = st.top();

st.pop();

// 隣接頂点を確認.

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

if(!memo[v]){

// コスト減算.

cost[v] -= a[u];

// コストが, m以下ならば, 頂点をスタックに追加.

if(cost[v] <= m) st.push(v), ++memo[v];

}

// 2-4. 未削除の頂点が残っているか？

bool ok = false;

rep(i, N) if(!memo[i]) ok = true;

// 2-5. 判定結果.

return ok;

};

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

// test_10.txt ～ test_13.txt で, WA版だったため, l = 0 でなく, l = -1 に修正.

// -> これらのテストケースは, M = 0 に, 該当すると予想.

LL l = -1, h = 202020202020202020, m;

while(l + 1 < h){

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

if(f(m)) l = m;

else h = m;

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
7 13
464 661 847 514 74 200 188
5 1
7 1
5 7
4 1
4 5
2 4
5 2
1 3
1 6
3 5
1 2
4 6
2 7

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

[入力例]
3 0
7 5 3

[出力例]
0

[入力例]
5 6
222 106 77 51 333
1 2
2 3
3 1
3 4
1 4
4 5

[出力例]
234

[入力例]
15 20
97 35 65 88 53 49 65 37 101 29 65 68 55 49 75
1 4
1 5
2 1
7 1
6 4
6 2
3 2
13 2
13 11
13 3
11 3
5 8
5 15
15 14
14 8
8 7
8 9
9 7
9 12
9 10

[出力例]
123

[入力例]
22 28
463 888 999 1084 21 1220 1213 375 132 748 1188 61 612 1077 982 501 668 1042 533 273 1226 134
1 2
1 8
1 9
1 17
3 2
3 20
3 9
4 3
4 5
20 21
21 22
22 20
17 18
18 19
19 17
8 7
7 9
7 6
7 14
14 15
15 16
16 15
5 9
5 6
5 11
11 12
12 13
13 11

[出力例]
1234

100

101

102

103

104

105

106

107

108

109

110

111

112

113

[入力例]

4 3

3 1 4 2

1 2

1 3

4 1

[出力例]

※AtCoderテストケースより

[入力例]

7 13

464 661 847 514 74 200 188

5 1

7 1

5 7

4 1

4 5

2 4

5 2

1 3

1 6

3 5

1 2

4 6

2 7

[出力例]

1199

※AtCoderテストケースより

[入力例]

3 0

7 5 3

[出力例]

[入力例]

5 6

222 106 77 51 333

1 2

2 3

3 1

3 4

1 4

4 5

[出力例]

234

[入力例]

15 20

97 35 65 88 53 49 65 37 101 29 65 68 55 49 75

1 4

1 5

2 1

7 1

6 4

6 2

3 2

13 2

13 11

13 3

11 3

5 8

5 15

15 14

14 8

8 7

8 9

9 7

9 12

9 10

[出力例]

123

[入力例]

22 28

463 888 999 1084 21 1220 1213 375 132 748 1188 61 612 1077 982 501 668 1042 533 273 1226 134

1 2

1 8

1 9

1 17

3 2

3 20

3 9

4 3

4 5

20 21

21 22

22 20

17 18

18 19

19 17

8 7

7 9

7 6

7 14

14 15

15 16

16 15

5 9

5 6

5 11

11 12

12 13

13 11

[出力例]

1234

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

2022年9月2日2022年9月4日

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

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題G (Swap Many Times) を解いてみた.

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

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

■C++版プログラム(問題G／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 a[202020], ans[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    LL L, R;
    scanf("%d %lld %lld", &N, &L, &R);
    
    // 2. 事前準備.
    // 以下のように, 前半(L ～ X - 1), 中盤(X ～ Y), 後半(Y + 1 ～ R) に 分ける.
    // N = 8, L = 10, R = 24 の 場合.
    // (1, 2)
    // (1, 3)
    // (1, 4)
    // (1, 5)
    // (1, 6)
    // (1, 7)
    // (1, 8)
    // (2, 3)
    // (2, 4)
    // (2, 5) => L = 10
    // (2, 6)
    // (2, 7)
    // (2, 8)
    // (3, 4) => X = 14
    // (3, 5)
    // (3, 6)
    // (3, 7)
    // (3, 8)
    // (4, 5)
    // (4, 6)
    // (4, 7)
    // (4, 8) => Y = 22
    // (5, 6)
    // (5, 7) => R = 24
    // (5, 8)
    // (6, 7)
    // (6, 8)
    // (7, 8)
    // 2-1. 初期化.
    repx(i, 1, N + 1) a[i] = i;
    
    // 2-2. 情報整理(X, Y).
    LL X = 0, Y = 0;
    int x = 0, y = 0;
    repr(i, N - 1, 1){
        if(X < L){
            X += (LL)i;
            ++x;
            if(X >= L){
                ++X;
                ++x;
            }
        }
        if(Y < R){
            Y += (LL)i;
            ++y;
            if(Y > R){
                Y -= (LL)i;
                --y;
                break;
            }
        }
    }
    
    // 2-3. 情報整理(L).
    // L = (la, lb) と 置く.
    LL lSum = 0;
    int la = 0, lb = 0;
    repx(i, 1, N){
        lSum += (LL)(N - i);
        if(lSum >= L){
            la = i;
            lb = N - (int)(lSum - L);
            break;
        }
    }
    
    // 2-4. 情報整理(R).
    // R = (ra, rb) と 置く.
    LL rSum = 0;
    int ra = 0, rb = 0;
    repx(i, 1, N){
        rSum += (LL)(N - i);
        if(rSum >= R){
            ra = i;
            rb = N - (int)(rSum - R);
            break;
        }
    }
    
    // 3. 例外.
    if(la == ra){
        repx(i, lb, rb + 1) swap(a[la], a[i]);
        repx(i, 1, N + 1) printf("%d%s", a[i], (i < N) ? " " : "\n");
        return 0;
    }
    
    // 4. Swap操作.
    // 4-1. 前半(L ～ X - 1).
    repx(i, lb, N + 1) swap(a[la], a[i]);
    
    // 4-2. 中盤(X ～ Y).
    // 中盤(X ～ Y) では, 以下の性質を利用することを検討.
    // X = (x, x + 1), Y = (y, N) と 置いた場合.
    // 
    // [開始]
    // a[1], a[2], ..., a[x - 1], a[x], a[x + 1], ..., a[N - (y - x) - 1], a[N - (y - x)], ..., a[N - 1], a[N]
    // 
    // [終了]
    // a[1], a[2], ..., a[x - 1], a[N], a[N - 1], ..., a[N - (y - x)], a[x], a[x + 1]..., a[N - (y - x) - 1]
    repx(i, 1, x) ans[i] = a[i];
    rep(i, y - x + 1) ans[x + i] = a[N - i];
    rep(i, N - y) ans[y + 1 + i] = a[x + i];
    
    // 4-3. 後半(Y + 1 ～ R).
    if(Y < R) repx(i, y + 2, rb + 1) swap(ans[y + 1], ans[i]);
    
    // 5. 出力.
    repx(i, 1, N + 1) printf("%d%s", ans[i], (i < N) ? " " : "\n");
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

// 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 a[202020], ans[202020];

int main(){

// 1. 入力情報.

int N;

LL L, R;

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

// 2. 事前準備.

// 以下のように, 前半(L ～ X - 1), 中盤(X ～ Y), 後半(Y + 1 ～ R) に分ける.

// N = 8, L = 10, R = 24 の場合.

// (1, 2)

// (1, 3)

// (1, 4)

// (1, 5)

// (1, 6)

// (1, 7)

// (1, 8)

// (2, 3)

// (2, 4)

// (2, 5) => L = 10

// (2, 6)

// (2, 7)

// (2, 8)

// (3, 4) => X = 14

// (3, 5)

// (3, 6)

// (3, 7)

// (3, 8)

// (4, 5)

// (4, 6)

// (4, 7)

// (4, 8) => Y = 22

// (5, 6)

// (5, 7) => R = 24

// (5, 8)

// (6, 7)

// (6, 8)

// (7, 8)

// 2-1. 初期化.

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

// 2-2. 情報整理(X, Y).

LL X = 0, Y = 0;

int x = 0, y = 0;

repr(i, N - 1, 1){

if(X < L){

X += (LL)i;

++x;

if(X >= L){

++X;

++x;

}

if(Y < R){

Y += (LL)i;

++y;

if(Y > R){

Y -= (LL)i;

--y;

break;

}

// 2-3. 情報整理(L).

// L = (la, lb) と置く.

LL lSum = 0;

int la = 0, lb = 0;

repx(i, 1, N){

lSum += (LL)(N - i);

if(lSum >= L){

la = i;

lb = N - (int)(lSum - L);

break;

}

// 2-4. 情報整理(R).

// R = (ra, rb) と置く.

LL rSum = 0;

int ra = 0, rb = 0;

repx(i, 1, N){

rSum += (LL)(N - i);

if(rSum >= R){

ra = i;

rb = N - (int)(rSum - R);

break;

}

// 3. 例外.

if(la == ra){

repx(i, lb, rb + 1) swap(a[la], a[i]);

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

return 0;

}

// 4. Swap操作.

// 4-1. 前半(L ～ X - 1).

repx(i, lb, N + 1) swap(a[la], a[i]);

// 4-2. 中盤(X ～ Y).

// 中盤(X ～ Y) では, 以下の性質を利用することを検討.

// X = (x, x + 1), Y = (y, N) と置いた場合.

// [開始]

// a[1], a[2], ..., a[x - 1], a[x], a[x + 1], ..., a[N - (y - x) - 1], a[N - (y - x)], ..., a[N - 1], a[N]

// [終了]

// a[1], a[2], ..., a[x - 1], a[N], a[N - 1], ..., a[N - (y - x)], a[x], a[x + 1]..., a[N - (y - x) - 1]

repx(i, 1, x) ans[i] = a[i];

rep(i, y - x + 1) ans[x + i] = a[N - i];

rep(i, N - y) ans[y + 1 + i] = a[x + i];

// 4-3. 後半(Y + 1 ～ R).

if(Y < R) repx(i, y + 2, rb + 1) swap(ans[y + 1], ans[i]);

// 5. 出力.

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

return 0;

}

[入力例]
5 3 6

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

[入力例]
10 12 36

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

[入力例]
3 1 1

[出力例]
2 1 3

[入力例]
3 1 2

[出力例]
3 1 2

[入力例]
3 1 3

[出力例]
3 2 1

[入力例]
4 1 1

[出力例]
2 1 3 4

[入力例]
4 1 2

[出力例]
3 1 2 4

[入力例]
4 1 3

[出力例]
4 1 2 3

[入力例]
4 1 4

[出力例]
4 2 1 3

[入力例]
4 1 5

[出力例]
4 3 1 2

[入力例]
4 1 6

[出力例]
4 3 2 1

[入力例]
8 10 24

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

[入力例]
12 25 50

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

[入力例]
30 123 321

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

[入力例]
50 256 512

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

[入力例]
100 2020 3030

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

[入力例]
500 11111 111111

[出力例]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 421 420 419 418 417 416 415 414 413 412 411 410 409 408 407 406 405 404 403 402 401 400 399 398 397 396 395 394 393 392 391 390 389 388 387 23 386 385 384 383 382 381 380 379 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 305 304 303 302 301 300 299 298 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 80 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

100

101

102

103

[入力例]

5 3 6

[出力例]

5 1 2 3 4

※AtCoderテストケースより

[入力例]

10 12 36

[出力例]

1 10 9 8 7 4 3 2 5 6

※AtCoderテストケースより

[入力例]

3 1 1

[出力例]

2 1 3

[入力例]

3 1 2

[出力例]

3 1 2

[入力例]

3 1 3

[出力例]

3 2 1

[入力例]

4 1 1

[出力例]

2 1 3 4

[入力例]

4 1 2

[出力例]

3 1 2 4

[入力例]

4 1 3

[出力例]

4 1 2 3

[入力例]

4 1 4

[出力例]

4 2 1 3

[入力例]

4 1 5

[出力例]

4 3 1 2

[入力例]

4 1 6

[出力例]

4 3 2 1

[入力例]

8 10 24

[出力例]

1 8 7 6 2 3 4 5

[入力例]

12 25 50

[出力例]

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

[入力例]

30 123 321

[出力例]

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

[入力例]

50 256 512

[出力例]

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

[入力例]

100 2020 3030

[出力例]

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

[入力例]

500 11111 111111

[出力例]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 500 499 498 497 496 495 494 493 492 491 490 489 488 487 486 485 484 483 482 481 480 479 478 477 476 475 474 473 472 471 470 469 468 467 466 465 464 463 462 461 460 459 458 457 456 455 454 453 452 451 450 449 448 447 446 445 444 443 442 441 440 439 438 437 436 435 434 433 432 431 430 429 428 427 426 425 424 423 422 421 420 419 418 417 416 415 414 413 412 411 410 409 408 407 406 405 404 403 402 401 400 399 398 397 396 395 394 393 392 391 390 389 388 387 23 386 385 384 383 382 381 380 379 378 377 376 375 374 373 372 371 370 369 368 367 366 365 364 363 362 361 360 359 358 357 356 355 354 353 352 351 350 349 348 347 346 345 344 343 342 341 340 339 338 337 336 335 334 333 332 331 330 329 328 327 326 325 324 323 322 321 320 319 318 317 316 315 314 313 312 311 310 309 308 307 306 305 304 303 302 301 300 299 298 297 296 295 294 293 292 291 290 289 288 287 286 285 284 283 282 281 280 279 278 277 276 275 274 273 272 271 270 269 268 267 266 265 264 263 262 261 260 259 258 257 256 255 254 253 252 251 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 80 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

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

2022年9月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題F (Operations on a Matrix) を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考にして, AC版に到達できたと思う.
2. 実装に苦労したものの, Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.

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

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

// 解き直し.
// https://atcoder.jp/contests/abc253/editorial/4025
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define pb push_back
#define a first
#define b second
const int MAX = 202020;
LL rMatrix[MAX], qSub[MAX];
int qLatest[MAX];
int qf[MAX], ql[MAX], qr[MAX], qx[MAX], qi[MAX], qj[MAX];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    vvi q3(Q);
    rep(q, Q){
        // 1-1. クエリ入力情報.
        scanf("%d", &qf[q]);
        
        // 1-2. クエリ 1.
        if(qf[q] == 1) scanf("%d %d %d", &ql[q], &qr[q], &qx[q]);
        
        // 1-3. クエリ 2.
        if(qf[q] == 2){
            scanf("%d %d", &qi[q], &qx[q]);
            
            // 直近 の クエリ 2 番号 を 保存.
            qLatest[qi[q]] = q;
        }
        
        // 1-4. クエリ 3.
        if(qf[q] == 3){
            scanf("%d %d", &qi[q], &qj[q]);
            
            // 直近 の クエリ 2 番号 に対して, クエリ 3 番号 を 紐づける.
            q3[qLatest[qi[q]]].pb(q);
        }
    }
    
    // 2. 事前準備.
    BIT<LL> pre(M + 2);
    rep(q, Q){
        // 2-1. クエリ 1.
        if(qf[q] == 1){
            // 位置 l で, x を 加算.
            pre.add(ql[q], qx[q]);
            
            // 位置 r + 1 で, x を 減算.
            pre.add(qr[q] + 1, -qx[q]);
        }
        
        // 2-2. クエリ 2.
        if(qf[q] == 2){
            // クエリ 3 で 減算分 を 保存.
            for(auto &x : q3[q]) qSub[x] = pre.sum(1, qj[x] + 1);
        }
    }
    
    // 3. クエリ回答.
    BIT<LL> cur(M + 2);
    rep(q, Q){
        // 3-1. クエリ 1.
        if(qf[q] == 1){
            // 位置 l で, x を 加算.
            cur.add(ql[q], qx[q]);
            
            // 位置 r + 1 で, x を 減算.
            cur.add(qr[q] + 1, -qx[q]);
        }
        
        // 3-2. クエリ 2.
        if(qf[q] == 2) rMatrix[qi[q]] = qx[q];
        
        // 3-3. クエリ 3.
        if(qf[q] == 3) printf("%lld\n", cur.sum(1, qj[q] + 1) + rMatrix[qi[q]] - qSub[q]);
    }
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

// 解き直し.

// https://atcoder.jp/contests/abc253/editorial/4025

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using vi = vector<int>;

using vvi = vector<vi>;

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

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

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

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

#define pb push_back

#define a first

#define b second

const int MAX = 202020;

LL rMatrix[MAX], qSub[MAX];

int qLatest[MAX];

int qf[MAX], ql[MAX], qr[MAX], qx[MAX], qi[MAX], qj[MAX];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

int N, M, Q;

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

vvi q3(Q);

rep(q, Q){

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

scanf("%d", &qf[q]);

// 1-2. クエリ 1.

if(qf[q] == 1) scanf("%d %d %d", &ql[q], &qr[q], &qx[q]);

// 1-3. クエリ 2.

if(qf[q] == 2){

scanf("%d %d", &qi[q], &qx[q]);

// 直近のクエリ 2 番号を保存.

qLatest[qi[q]] = q;

}

// 1-4. クエリ 3.

if(qf[q] == 3){

scanf("%d %d", &qi[q], &qj[q]);

// 直近のクエリ 2 番号に対して, クエリ 3 番号を紐づける.

q3[qLatest[qi[q]]].pb(q);

}

// 2. 事前準備.

BIT<LL> pre(M + 2);

rep(q, Q){

// 2-1. クエリ 1.

if(qf[q] == 1){

// 位置 l で, x を加算.

pre.add(ql[q], qx[q]);

// 位置 r + 1 で, x を減算.

pre.add(qr[q] + 1, -qx[q]);

}

// 2-2. クエリ 2.

if(qf[q] == 2){

// クエリ 3 で減算分を保存.

for(auto &x : q3[q]) qSub[x] = pre.sum(1, qj[x] + 1);

}

// 3. クエリ回答.

BIT<LL> cur(M + 2);

rep(q, Q){

// 3-1. クエリ 1.

if(qf[q] == 1){

// 位置 l で, x を加算.

cur.add(ql[q], qx[q]);

// 位置 r + 1 で, x を減算.

cur.add(qr[q] + 1, -qx[q]);

}

// 3-2. クエリ 2.

if(qf[q] == 2) rMatrix[qi[q]] = qx[q];

// 3-3. クエリ 3.

if(qf[q] == 3) printf("%lld\n", cur.sum(1, qj[q] + 1) + rMatrix[qi[q]] - qSub[q]);

}

return 0;

}

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

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

[入力例]
1 1 10
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
1 1 1 1000000000
3 1 1

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

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

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

[入力例]
30 30 30
1 3 22 77
2 3 111
3 1 5
3 3 1
3 3 3
1 8 27 33
1 3 15 30
2 5 222
1 9 30 55
3 10 15
3 12 17
1 2 12 1
3 8 8
3 15 15
2 12 333
2 17 444
3 17 8
3 21 18
1 7 27 345
1 1 11 123
3 25 15
3 10 10
2 26 666
2 17 777
3 17 15
1 3 23 334
3 17 15
1 5 25 889
3 17 1
3 17 15

[出力例]
77
111
111
195
165
141
195
444
165
540
664
777
1111
777
2000

100

101

102

103

104

105

106

107

108

109

[入力例]

3 3 9

1 1 2 1

3 2 2

2 3 2

3 3 3

3 3 1

1 2 3 3

3 3 2

3 2 3

3 1 2

[出力例]

※AtCoderテストケースより

[入力例]

1 1 10

1 1 1 1000000000

3 1 1

[出力例]

9000000000

※AtCoderテストケースより

[入力例]

10 10 10

1 1 8 5

2 2 6

3 2 1

3 4 7

1 5 9 7

3 3 2

3 2 8

2 8 10

3 8 8

3 1 10

[出力例]

※AtCoderテストケースより

[入力例]

30 30 30

1 3 22 77

2 3 111

3 1 5

3 3 1

3 3 3

1 8 27 33

1 3 15 30

2 5 222

1 9 30 55

3 10 15

3 12 17

1 2 12 1

3 8 8

3 15 15

2 12 333

2 17 444

3 17 8

3 21 18

1 7 27 345

1 1 11 123

3 25 15

3 10 10

2 26 666

2 17 777

3 17 15

1 3 23 334

3 17 15

1 5 25 889

3 17 1

3 17 15

[出力例]

111

195

165

141

195

444

165

540

664

777

1111

777

2000

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

2022年8月28日

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

C++の練習を兼ねて, AtCoder Regular Contest 046 の問題D (うさぎとマス目) を解いてみた.

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

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc046
// 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;
LL FAC[2020202], INV[2020202];

// 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. 入力情報.
    LL H, W;
    scanf("%lld %lld", &H, &W);
    
    // 2. 事前計算.
    FAC[0] = INV[0] = 1;
    rep(i, 2020202){
        FAC[i + 1] = (LL)(i + 1) * FAC[i] % MOD;
        INV[i + 1] = mPow(FAC[i + 1], MOD - 2);
    }
    
    // 3. 全探索(解説通り).
    LL ans = 0, d = __gcd(H, W);
    repx(x, 1, (int)d){
        LL w = W / __gcd(W, (LL)x);
        LL h = H / __gcd(H, (LL)(d - x));
        LL g = __gcd(w, h);
        if(w / g * h == H / d * W) ans = (ans + combination(d, x)) % MOD;
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 解き直し.

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

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

LL FAC[2020202], INV[2020202];

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

LL H, W;

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

// 2. 事前計算.

FAC[0] = INV[0] = 1;

rep(i, 2020202){

FAC[i + 1] = (LL)(i + 1) * FAC[i] % MOD;

INV[i + 1] = mPow(FAC[i + 1], MOD - 2);

}

// 3. 全探索(解説通り).

LL ans = 0, d = __gcd(H, W);

repx(x, 1, (int)d){

LL w = W / __gcd(W, (LL)x);

LL h = H / __gcd(H, (LL)(d - x));

LL g = __gcd(w, h);

if(w / g * h == H / d * W) ans = (ans + combination(d, x)) % MOD;

}

// 4. 出力.

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

return 0;

}

[入力例]
2 2

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

[入力例]
6 3

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

[入力例]
3 4

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

[入力例]
10 10

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

[入力例]
200 300

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

[入力例]
7 7

[出力例]
126

[入力例]
77 121

[出力例]
1716

[入力例]
120 108

[出力例]
816

[入力例]
2022 828

[出力例]
12

[入力例]
72 96

[出力例]
5769552

[入力例]

2 2

[出力例]

※AtCoderのテストケースより

[入力例]

6 3

[出力例]

※AtCoderのテストケースより

[入力例]

3 4

[出力例]

※AtCoderのテストケースより

[入力例]

10 10

[出力例]

260

※AtCoderのテストケースより

[入力例]

200 300

[出力例]

551887980

※AtCoderのテストケースより

[入力例]

7 7

[出力例]

126

[入力例]

77 121

[出力例]

1716

[入力例]

120 108

[出力例]

816

[入力例]

2022 828

[出力例]

[入力例]

72 96

[出力例]

5769552

■参照サイト
AtCoder Regular Contest 046

C++の練習を兼ねて, AtCoder Beginner Contest 141 の 問題E (Who Says a Pun?) を解いてみた.

C++の練習を兼ねて, 第１０回 アルゴリズム実技検定 過去問 の 問題H (連結成分) を解いてみた.

C++の練習を兼ねて, 第１０回 アルゴリズム実技検定 過去問 の 問題G (方程式) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 023 の 問題C (Painting Machines) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 215 の 問題C (One More aab aba baa) ～ 問題D (Coprime 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 147 の 問題A (Max Mod Min) ～ 問題B (Swap to Sort) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 267 の 問題B (Split?) ～ 問題E (Erasing Vertices 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の 問題G (Swap Many Times) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の 問題F (Operations on a Matrix) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 046 の 問題D (うさぎとマス目) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 141 の問題E (Who Says a Pun?) を解いてみた.

C++の練習を兼ねて, 第１０回アルゴリズム実技検定過去問の問題H (連結成分) を解いてみた.

C++の練習を兼ねて, 第１０回アルゴリズム実技検定過去問の問題G (方程式) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 023 の問題C (Painting Machines) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 215 の問題C (One More aab aba baa) ～問題D (Coprime 2) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 147 の問題A (Max Mod Min) ～問題B (Swap to Sort) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 267 の問題B (Split?) ～問題E (Erasing Vertices 2) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題G (Swap Many Times) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 253 の問題F (Operations on a Matrix) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 046 の問題D (うさぎとマス目) を解いてみた.