11月, 2019 | 個人用メモ帳

2019年11月29日2019年11月29日

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

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

■感想.
1. 方針が見えなかったので, 解説を参考に実装した.
2. 前問に引き続き, 自力で解答出来なかったものの, どちらの問題も楽しく, 非常に勉強になったと思う.
3. また, これで解けてしまうことが摩訶不思議に思えた.

本家のサイトABC 146解説をご覧下さい.

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

// AC版.
// 解き直し.
// ABC 146解説.
// https://img.atcoder.jp/abc146/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define repx(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
const int INF = 2020202020;
const int MAX = 111111;
int d[MAX];

int main(){
    
    // 1. 入力情報.
    int N, M;
    char S[111111];
    scanf("%d %d %s", &N, &M, S);
    rep(i, MAX) d[i] = INF;
    
    // 2. 解説通り.
    // 連続する '1' が, M以上のものが存在したら, ゴールへの到達は不可能.
    int maxOne = 0, one = 0;
    rep(i, N + 1){
        if(S[i] == '1') one++;
        else            maxOne = max(maxOne, one), one = 0;
    }
    if(maxOne >= M){
        puts("-1");
        return 0;
    }
    
    // 3. 目的地点から, 各出発地点までの最短手数を求める.
    int bef = N, dx = 1, mIndex;
    d[N] = 0;
    repr(i, N - 1, 0){
        if(bef - i > M){
            bef = mIndex;
            dx++;
        }
        if(S[i] == '0' && bef - i <= M){
            d[i] = dx;
            mIndex = i;
        }
    }
    // rep(i, N + 1) printf("%d ", d[i]);
    // printf("\n");
    
    // 4. 最短経路の情報を保存.
    vector<int> v;
    int r = d[0];
    rep(i, N + 1) if(d[i] == r) v.pb(i), r--;
    
    // 5. 出力.
    int l = v.size();
    rep(i, l - 1){
        printf("%d", v[i + 1] - v[i]);
        if(i < l - 2) printf(" ");
    }
    printf("\n");
    return 0;
    
}

// AC版.

// 解き直し.

// ABC 146解説.

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

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

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

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

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

const int INF = 2020202020;

const int MAX = 111111;

int d[MAX];

int main(){

// 1. 入力情報.

int N, M;

char S[111111];

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

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

// 2. 解説通り.

// 連続する '1' が, M以上のものが存在したら, ゴールへの到達は不可能.

int maxOne = 0, one = 0;

rep(i, N + 1){

if(S[i] == '1') one++;

else maxOne = max(maxOne, one), one = 0;

}

if(maxOne >= M){

puts("-1");

return 0;

}

// 3. 目的地点から, 各出発地点までの最短手数を求める.

int bef = N, dx = 1, mIndex;

d[N] = 0;

repr(i, N - 1, 0){

if(bef - i > M){

bef = mIndex;

dx++;

}

if(S[i] == '0' && bef - i <= M){

d[i] = dx;

mIndex = i;

}

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

// printf("\n");

// 4. 最短経路の情報を保存.

vector<int> v;

int r = d[0];

rep(i, N + 1) if(d[i] == r) v.pb(i), r--;

// 5. 出力.

int l = v.size();

rep(i, l - 1){

printf("%d", v[i + 1] - v[i]);

if(i < l - 2) printf(" ");

}

printf("\n");

return 0;

}

[入力例]
9 3
0001000100

[出力例(debug版)]
4 3 3 2020202020 2 2 1 2020202020 1 0 
1 3 2 3
※AtCoderテストケースより

[入力例]
5 4
011110

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

[入力例]
6 6
0101010

[出力例(debug版)]
1 2020202020 1 2020202020 1 2020202020 0 
6
※AtCoderテストケースより

[入力例]
100 10
01110011110001111100001111110000011100111100011111000011111100000111001111000111110000111111010011100

[出力例]
10 8 10 4 10 8 10 4 10 8 10 8

[入力例]
300 8
0110110000011110000111011010111001100011011011001101000011010111101101011001011010010101011011011011101110111101000001010000110101011100110011011111010000000101010000101000110111110010111110000101000011100000110111100011011001110000110011110011110101001100100100010001011110110111010101101000000110000

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

[入力例]

9 3

0001000100

[出力例(debug版)]

4 3 3 2020202020 2 2 1 2020202020 1 0

1 3 2 3

※AtCoderテストケースより

[入力例]

5 4

011110

[出力例(debug版)]

-1

※AtCoderテストケースより

[入力例]

6 6

0101010

[出力例(debug版)]

1 2020202020 1 2020202020 1 2020202020 0

※AtCoderテストケースより

[入力例]

100 10

01110011110001111100001111110000011100111100011111000011111100000111001111000111110000111111010011100

[出力例]

10 8 10 4 10 8 10 4 10 8 10 8

[入力例]

300 8

0110110000011110000111011010111001100011011011001101000011010111101101011001011010010101011011011011101110111101000001010000110101011100110011011111010000000101010000101000110111110010111110000101000011100000110111100011011001110000110011110011110101001100100100010001011110110111010101101000000110000

[出力例]

3 6 8 8 7 8 6 6 8 8 8 8 7 6 8 5 8 8 8 8 6 4 8 7 7 6 3 8 8 8 8 5 8 6 6 6 8 6 8 8 8 8 8

■参照サイト
AtCoder Beginner Contest 146

2019年11月28日2019年11月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 146 の問題E (E – Rem of Sum is Num) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を参考に実装した.
2. 解説上では, 読み取れなかったが, おそらく, 1 ＜＝ j ＜＝ N でなく, 0 ＜＝ j ＜＝ N にする必要があると推測した.

本家のサイトABC 146解説をご覧下さい.

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

// 解き直し.
// ABC 146解説.
// https://img.atcoder.jp/abc146/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define repex(i, a, b, c) for(LL 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 a first
#define b second
const int MAX = 202020;
LL A[MAX], CUM[MAX];

int main(){
    
    // 1. 入力情報.
    LL N, K;
    scanf("%lld %lld", &N, &K);
    rep(i, N) scanf("%lld", A + i), CUM[i + 1] = CUM[i] + A[i];
    
    // 2. 条件を満たす連続部分列をカウント(TLE版).
    // (N + 1) * N / 2 の 計算量があるはず.
    LL ans = 0;
    // rep(i, N){
    //     repx(j, i, N){
    //         if((CUM[j + 1] - CUM[i]) % K == j - i + 1) ans++, printf("i=%d j=%d\n", i, j);
    //     }
    // }
    
    // 3. 解説通り.
    // (CUM[j] - j) % K == (CUM[i] - i) % K かつ j - i < K となるものを集計.
    // -> 1 <= j <= N で, (CUM[j] - j) % K == (CUM[i] - i) % K を 満たす
    // j - K < i < j となる iの個数を調べるとのこと.
    // ex. 
    // [入力例]
    // 10 7
    // 14 15 92 65 35 89 79 32 38 46
    // index     0   1   2   3   4   5   6   7   8   9  10
    // S[i]      0  14  29 121 186 221 310 389 421 459 505
    // S[i] - i  0  13  27 118 182 216 304 382 413 450 495
    // mod K     0   6   6   6   0   6   3   4   0   2   5
    // 
    // [計算メモ]
    //  j  j - K < i < j  S[j] - j  個数   マップ
    //  0    -7 < i <  0      0      0    {0:1}
    //  1    -6 < i <  1      6      0    {0:1}, {6:1}
    //  2    -5 < i <  2      6      1    {0:1}, {6:2}
    //  3    -4 < i <  3      6      2    {0:1}, {6:3}
    //  4    -3 < i <  4      0      1    {0:2}, {6:3}
    //  5    -2 < i <  5      6      3    {0:2}, {6:4}
    //  6    -1 < i <  6      3      0    {0:2}, {3:1}, {6:4}
    //  7     0 < i <  7      4      0    {0:1}, {3:1}, {4:1}, {6:4}
    //  8     1 < i <  8      0      1    {0:2}, {3:1}, {4:1}, {6:3}
    //  9     2 < i <  9      2      0    {0:2}, {2:1}, {3:1}, {4:1}, {6:2}
    // 10     3 < i < 10      5      0    {0:2}, {2:1}, {3:1}, {4:1}, {5:1}, {6:1}
    // -----------------------------------------------------------------------------
    // 合計                          8
    map<LL, LL> m;
    LL cur = 0, bef = 0;
    rep(i, N + 1){
        cur = (CUM[i] - i) % K;
        m[cur]++;
        if(i - K >= 0){
            bef = (CUM[i - K] - (i - K)) % K;
            m[bef]--;
        }
        ans += m[cur] - 1;
        // printf("cur=%lld bef=%lld\n", cur, bef);
        // for(auto &p : m) printf("{%lld:%lld}, ", p.a, p.b);
        // printf("\n");
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;

}

// 解き直し.

// ABC 146解説.

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

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

#define repex(i, a, b, c) for(LL 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 a first

#define b second

const int MAX = 202020;

LL A[MAX], CUM[MAX];

int main(){

// 1. 入力情報.

LL N, K;

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

rep(i, N) scanf("%lld", A + i), CUM[i + 1] = CUM[i] + A[i];

// 2. 条件を満たす連続部分列をカウント(TLE版).

// (N + 1) * N / 2 の計算量があるはず.

LL ans = 0;

// rep(i, N){

// repx(j, i, N){

// if((CUM[j + 1] - CUM[i]) % K == j - i + 1) ans++, printf("i=%d j=%d\n", i, j);

// }

// 3. 解説通り.

// (CUM[j] - j) % K == (CUM[i] - i) % K かつ j - i < K となるものを集計.

// -> 1 <= j <= N で, (CUM[j] - j) % K == (CUM[i] - i) % K を満たす

// j - K < i < j となる iの個数を調べるとのこと.

// ex.

// [入力例]

// 10 7

// 14 15 92 65 35 89 79 32 38 46

// index 0 1 2 3 4 5 6 7 8 9 10

// S[i] 0 14 29 121 186 221 310 389 421 459 505

// S[i] - i 0 13 27 118 182 216 304 382 413 450 495

// mod K 0 6 6 6 0 6 3 4 0 2 5

// [計算メモ]

// j j - K < i < j S[j] - j 個数マップ

// 0 -7 < i < 0 0 0 {0:1}

// 1 -6 < i < 1 6 0 {0:1}, {6:1}

// 2 -5 < i < 2 6 1 {0:1}, {6:2}

// 3 -4 < i < 3 6 2 {0:1}, {6:3}

// 4 -3 < i < 4 0 1 {0:2}, {6:3}

// 5 -2 < i < 5 6 3 {0:2}, {6:4}

// 6 -1 < i < 6 3 0 {0:2}, {3:1}, {6:4}

// 7 0 < i < 7 4 0 {0:1}, {3:1}, {4:1}, {6:4}

// 8 1 < i < 8 0 1 {0:2}, {3:1}, {4:1}, {6:3}

// 9 2 < i < 9 2 0 {0:2}, {2:1}, {3:1}, {4:1}, {6:2}

// 10 3 < i < 10 5 0 {0:2}, {2:1}, {3:1}, {4:1}, {5:1}, {6:1}

// -----------------------------------------------------------------------------

// 合計 8

map<LL, LL> m;

LL cur = 0, bef = 0;

rep(i, N + 1){

cur = (CUM[i] - i) % K;

m[cur]++;

if(i - K >= 0){

bef = (CUM[i - K] - (i - K)) % K;

m[bef]--;

}

ans += m[cur] - 1;

// printf("cur=%lld bef=%lld\n", cur, bef);

// for(auto &p : m) printf("{%lld:%lld}, ", p.a, p.b);

// printf("\n");

}

// 4. 出力.

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

return 0;

}

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

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

[入力例]
8 4
4 2 4 2 4 2 4 2

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

[入力例]
10 7
14 15 92 65 35 89 79 32 38 46

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

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

[出力例]
15

[入力例]
9 7
123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678

[出力例]
7

[入力例]
100 123
111111111 111111112 111111113 111111114 111111115 111111116 111111117 111111118 111111119 111111120 111111121 111111122 111111123 111111124 111111125 111111126 111111127 111111128 111111129 111111130 111111131 111111132 111111133 111111134 111111135 111111136 111111137 111111138 111111139 111111140 111111141 111111142 111111143 111111144 111111145 111111146 111111147 111111148 111111149 111111150 111111151 111111152 111111153 111111154 111111155 111111156 111111157 111111158 111111159 111111160 111111161 111111162 111111163 111111164 111111165 111111166 111111167 111111168 111111169 111111170 111111171 111111172 111111173 111111174 111111175 111111176 111111177 111111178 111111179 111111180 111111181 111111182 111111183 111111184 111111185 111111186 111111187 111111188 111111189 111111190 111111191 111111192 111111193 111111194 111111195 111111196 111111197 111111198 111111199 111111200 111111201 111111202 111111203 111111204 111111205 111111206 111111207 111111208 111111209 111111210

[出力例]
90

[入力例]

5 4

1 4 2 3 5

[出力例]

※AtCoderテストケースより

[入力例]

8 4

4 2 4 2 4 2 4 2

[出力例]

※AtCoderテストケースより

[入力例]

10 7

14 15 92 65 35 89 79 32 38 46

[出力例]

※AtCoderテストケースより

[入力例]

5 10

1 1 1 1 1

[出力例]

[入力例]

9 7

123456789 234567891 345678912 456789123 567891234 678912345 789123456 891234567 912345678

[出力例]

[入力例]

100 123

111111111 111111112 111111113 111111114 111111115 111111116 111111117 111111118 111111119 111111120 111111121 111111122 111111123 111111124 111111125 111111126 111111127 111111128 111111129 111111130 111111131 111111132 111111133 111111134 111111135 111111136 111111137 111111138 111111139 111111140 111111141 111111142 111111143 111111144 111111145 111111146 111111147 111111148 111111149 111111150 111111151 111111152 111111153 111111154 111111155 111111156 111111157 111111158 111111159 111111160 111111161 111111162 111111163 111111164 111111165 111111166 111111167 111111168 111111169 111111170 111111171 111111172 111111173 111111174 111111175 111111176 111111177 111111178 111111179 111111180 111111181 111111182 111111183 111111184 111111185 111111186 111111187 111111188 111111189 111111190 111111191 111111192 111111193 111111194 111111195 111111196 111111197 111111198 111111199 111111200 111111201 111111202 111111203 111111204 111111205 111111206 111111207 111111208 111111209 111111210

[出力例]

■参照サイト
AtCoder Beginner Contest 146

2019年11月26日2019年11月26日

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

C++の練習を兼ねて, AtCoder Beginner Contest 146 の問題D (D – Coloring Edges on Tree) を解いてみた.

■感想.
1. 非常に苦労したものの, 解説見る前に, AC版となったので良かったと思う.
2. 但し, スリムな実装方法が思いつかなかったので, 上級者の方々のソースを見て, 勉強する必要があると感じた.

本家のサイトABC 146解説をご覧下さい.

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

// TODO: 計算量が非常に多い気がする.
#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 pb push_back
#define a first
#define b second
const int MAX = 101010;
int memo[MAX];
vector<int> graph[MAX];
map<pair<int, int>, int> m; // 着色時の頂点ペア, 色を保存.
vector<pair<int, int>> o;   // 入力時の頂点ペアを保存.
set<int> color[MAX];
int maxColor;

// グラフを幅優先探索する.
// https://ja.wikipedia.org/wiki/幅優先探索
// ※bfsの動作確認用.
// @param s: 探索開始の頂点番号.
// @return: 特に無し.
void bfs(int s){
    
    // 1. 空のキュー.
    queue<int> q;
    
    // 2. 訪問済みフラグ設定.
    // ※スタート地点は, 距離ゼロを指定.
    memo[s] = 0;
    
    // 3. 探索地点 s をキュー q に追加.
    q.push(s);
    
    // 4. キュー q が 空になるまで, 探索.
    while(!q.empty()){
        
        // 5. 頂点 u を キュー q から取り出す.
        int u = q.front();
        q.pop();
        
        // 6. 取り出した要素を処理.
        int c = 1;
        for(auto &e : graph[u]){
            // 6-1. 頂点u の 隣接する頂点e が, 未訪問だったら, キュー q に追加.
            if(memo[e] == 0 && e != s){
                // 頂点e を キュー q に追加.
                q.push(e);
                // 頂点e に 距離memo[u] プラス 1 を 加算.
                memo[e] += (memo[u] + 1);
                // 色を着色.
                // すでに使用している色があれば, Skip.
                while(color[u].count(c) != 0) c++;
                color[u].insert(c);
                color[e].insert(c);
                m[{u, e}] = c;
                m[{e, u}] = c;
                // 必要とする色の最大数を更新.
                maxColor = max(maxColor, c);
            }
        }
    }
}

int main(){
    
    // 1. 入力情報.
    int N, a, b;
    scanf("%d", &N);
    
    // 2. グラフ作成.
    rep(i, N - 1){
        scanf("%d %d", &a, &b);
        a--, b--;
        graph[a].pb(b);
        graph[b].pb(a);
        o.pb({a, b}); // オリジナルの入力情報.
    }
    
    // 3. 頂点 0 から 探索.
    bfs(0);
    // rep(i, N) printf("%d ", memo[i]);
    // printf("\n");
    // printf("maxColor=%d\n", maxColor);
    // for(auto &p : m) printf("a=%d b=%d c=%d\n", p.a.a, p.a.b, p.b);
    
    // 4. 出力.
    printf("%d\n", maxColor);
    for(auto &p : o) printf("%d\n", m[p]);
    return 0;

}

// TODO: 計算量が非常に多い気がする.

#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 pb push_back

#define a first

#define b second

const int MAX = 101010;

int memo[MAX];

vector<int> graph[MAX];

map<pair<int, int>, int> m; // 着色時の頂点ペア, 色を保存.

vector<pair<int, int>> o; // 入力時の頂点ペアを保存.

set<int> color[MAX];

int maxColor;

// グラフを幅優先探索する.

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

// ※bfsの動作確認用.

// @param s: 探索開始の頂点番号.

// @return: 特に無し.

void bfs(int s){

// 1. 空のキュー.

queue<int> q;

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

// ※スタート地点は, 距離ゼロを指定.

memo[s] = 0;

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

q.push(s);

// 4. キュー q が空になるまで, 探索.

while(!q.empty()){

// 5. 頂点 u をキュー q から取り出す.

int u = q.front();

q.pop();

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

int c = 1;

for(auto &e : graph[u]){

// 6-1. 頂点u の隣接する頂点e が, 未訪問だったら, キュー q に追加.

if(memo[e] == 0 && e != s){

// 頂点e をキュー q に追加.

q.push(e);

// 頂点e に距離memo[u] プラス 1 を加算.

memo[e] += (memo[u] + 1);

// 色を着色.

// すでに使用している色があれば, Skip.

while(color[u].count(c) != 0) c++;

color[u].insert(c);

color[e].insert(c);

m[{u, e}] = c;

m[{e, u}] = c;

// 必要とする色の最大数を更新.

maxColor = max(maxColor, c);

}

int main(){

// 1. 入力情報.

int N, a, b;

scanf("%d", &N);

// 2. グラフ作成.

rep(i, N - 1){

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

a--, b--;

graph[a].pb(b);

graph[b].pb(a);

o.pb({a, b}); // オリジナルの入力情報.

}

// 3. 頂点 0 から探索.

bfs(0);

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

// printf("\n");

// printf("maxColor=%d\n", maxColor);

// for(auto &p : m) printf("a=%d b=%d c=%d\n", p.a.a, p.a.b, p.b);

// 4. 出力.

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

for(auto &p : o) printf("%d\n", m[p]);

return 0;

}

[入力例]
3
1 2
2 3

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

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

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

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

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

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

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

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

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

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

[入力例]

1 2

2 3

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

2 4

2 5

4 7

5 6

6 8

[出力例]

※AtCoderテストケースより

[入力例]

1 2

1 3

1 4

1 5

1 6

[出力例]

※AtCoderテストケースより

[入力例]

1 2

2 3

3 4

4 5

5 6

6 7

7 8

8 9

9 10

2 11

2 12

11 13

3 14

3 15

4 16

[出力例]

[入力例]

1 18

1 19

1 20

2 4

10 28

10 29

3 8

3 9

4 10

4 27

5 11

5 12

2 5

2 6

3 7

5 13

7 17

8 14

8 15

10 23

10 24

1 2

1 3

10 25

10 26

6 30

7 16

19 21

19 22

[出力例]

■参照サイト
AtCoder Beginner Contest 146

2019年11月16日

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

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題D (D – Knight) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 解説と同様の方針で解答出来たので, 及第点は取れたと思う.

本家のサイトABC 145解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define repx(i, a, b) for(int i = a; i < b; i++)
using LL = long long;
const LL MOD = 1e9 + 7;
const int LIMIT = 1e6 + 1;
LL FAC[LIMIT + 1];
LL INV[LIMIT + 1];

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

// 組み合わせ(nCk)計算用(mod版).
// ※配列FAC, INV は, 事前に計算済のものを使う.
// @param n: 対象となる要素の個数.
// @param k: 選択する要素の個数.
// @return: 組み合わせ(nCk)の計算結果.
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. 入力情報.
    LL X, Y;
    scanf("%lld %lld", &X, &Y);
    FAC[0] = 1;
    repx(i, 1, LIMIT) FAC[i] = (LL)i * FAC[i - 1] % MOD;
    rep(i, LIMIT)     INV[i] = inverse(FAC[i], MOD - 2) % MOD;
    
    // 2. ナイトの駒を移動.
    // 移動方法は, (1, 2) または (2, 1) を 選択できるので, それぞれの操作回数を計算.
    // X = 1 * op12 + 2 * op21, Y = 2 * op12 + 1 * op21
    // -> 
    // 1 * op12 = X - 2 * op21
    // 2 * op12 = Y - 1 * op21
    // -> 
    // op12 = (2 * Y - X) / 3
    // op21 = (2 * X - Y) / 3
    LL op12 = (2 * Y - X) / 3, op21 = (2 * X - Y) / 3;
    
    // 3. 移動できない場合.
    if(X != op12 + 2 * op21 || Y != 2 * op12 + op21){
        printf("%d\n", 0);
        return 0;
    }
    
    // 4. 移動させる方法が何通りあるか？
    LL ans = combination(op12 + op21, op12);
    
    // 5. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

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

using LL = long long;

const LL MOD = 1e9 + 7;

const int LIMIT = 1e6 + 1;

LL FAC[LIMIT + 1];

LL INV[LIMIT + 1];

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

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

// @param b: 指数.

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

LL inverse(LL a, LL b){

LL t = 1;

while(b){

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

a *= a;

a %= MOD;

b >>= 1;

}

return t % MOD;

}

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

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

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

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

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

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

LL X, Y;

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

FAC[0] = 1;

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

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

// 2. ナイトの駒を移動.

// 移動方法は, (1, 2) または (2, 1) を選択できるので, それぞれの操作回数を計算.

// X = 1 * op12 + 2 * op21, Y = 2 * op12 + 1 * op21

// ->

// 1 * op12 = X - 2 * op21

// 2 * op12 = Y - 1 * op21

// ->

// op12 = (2 * Y - X) / 3

// op21 = (2 * X - Y) / 3

LL op12 = (2 * Y - X) / 3, op21 = (2 * X - Y) / 3;

// 3. 移動できない場合.

if(X != op12 + 2 * op21 || Y != 2 * op12 + op21){

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

return 0;

}

// 4. 移動させる方法が何通りあるか？

LL ans = combination(op12 + op21, op12);

// 5. 出力～後処理.

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

return 0;

}

[入力例]
3 3

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

[入力例]
2 2

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

[入力例]
999999 999999

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

[入力例]
1000000 1000000

[出力例]
0

[入力例]
332211 223311

[出力例]
170944920

[入力例]
987654 876543

[出力例]
76408594

[入力例]

3 3

[出力例]

※AtCoderテストケースより

[入力例]

2 2

[出力例]

※AtCoderテストケースより

[入力例]

999999 999999

[出力例]

151840682

※AtCoderテストケースより

[入力例]

1000000 1000000

[出力例]

[入力例]

332211 223311

[出力例]

170944920

[入力例]

987654 876543

[出力例]

76408594

■参照サイト
AtCoder Beginner Contest 145

2019年11月5日

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

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題A (A – ><) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.
2. 解説と同様の方針で解答出来たので, 時間かかったが, 及第点は取れたと思う.

本家のサイトAGC040解説をご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL increase[543210], decrease[543210], ans;

int main(){
    
    // 1. 入力情報.
    char c[543210];
    scanf("%s", c);
    int l = strlen(c);
    
    // 2. 数列の増加時, 減少時を分けて集計.
    // 2-1. 増加時(※ i が 大きくなる方向で確認).
    for(int i = 0; i < l; i++) if(c[i] == '<') increase[i + 1] = increase[i] + 1;
    
    // 2-2. 減少時(※ i が 小さくなる方向で確認).
    for(int i = l - 1; i >= 0; i--) if(c[i] == '>') decrease[i] = decrease[i + 1] + 1;
    
    // 3. 良い非負整数列の要素の総和の最小値を計算.
    for(int i = 0; i <= l; i++) ans += max(increase[i], decrease[i]);
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL increase[543210], decrease[543210], ans;

int main(){

// 1. 入力情報.

char c[543210];

scanf("%s", c);

int l = strlen(c);

// 2. 数列の増加時, 減少時を分けて集計.

// 2-1. 増加時(※ i が大きくなる方向で確認).

for(int i = 0; i < l; i++) if(c[i] == '<') increase[i + 1] = increase[i] + 1;

// 2-2. 減少時(※ i が小さくなる方向で確認).

for(int i = l - 1; i >= 0; i--) if(c[i] == '>') decrease[i] = decrease[i + 1] + 1;

// 3. 良い非負整数列の要素の総和の最小値を計算.

for(int i = 0; i <= l; i++) ans += max(increase[i], decrease[i]);

// 4. 出力.

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

return 0;

}

[入力例]
<>>

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

[入力例]
<>>><<><<<<<>>><

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

[入力例]
>>>>>>>>><<<<<<<<>>>>>>><<<<<<>>>>><<<<>>><<>

[出力例]
149

[入力例]
<<<><<<<><<<<<>>>>>>>>><<>>>>>><<<<<>>>

[出力例]
111

[入力例]
<<<>>><<<><<<<<<<>><<>>>>>>><<><<><<<<<<<>>>>>><><<<<<><<<<<<<>><<>><<<<<<>>><<>><

[入力例]
200

[入力例]

<>>

[出力例]

※AtCoderテストケースより

[入力例]

<>>><<><<<<<>>><

[出力例]

※AtCoderテストケースより

[入力例]

>>>>>>>>><<<<<<<<>>>>>>><<<<<<>>>>><<<<>>><<>

[出力例]

149

[入力例]

<<<><<<<><<<<<>>>>>>>>><<>>>>>><<<<<>>>

[出力例]

111

[入力例]

<<<>>><<<><<<<<<<>><<>>>>>>><<><<><<<<<<<>>>>>><><<<<<><<<<<<<>><<>><<<<<<>>><<>><

[入力例]

200

■参照サイト
AtCoder Grand Contest 040

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

C++の練習を兼ねて, AtCoder Beginner Contest 146 の 問題E (E – Rem of Sum is Num) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 146 の 問題D (D – Coloring Edges on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 145 の 問題D (D – Knight) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 040 の 問題A (A – ><) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 146 の問題E (E – Rem of Sum is Num) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 146 の問題D (D – Coloring Edges on Tree) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 145 の問題D (D – Knight) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 040 の問題A (A – ><) を解いてみた.