9月, 2019 | 個人用メモ帳

2019年9月28日2019年9月28日

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

C++の練習を兼ねて, AtCoder Beginner Contest 142 の問題D (D – Disjoint Set of Common Divisors) を解いてみた.

■感想.
1. 解説見る前に, AC版となったので良かったと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

// 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<LL, int> div(LL X){
    
    // 1. X を 2で割り切れなくなるまで割っていく.
    map<LL, int> ret;
    while(X % 2 == 0) ret[2]++, X >>= 1;
    
    // 2. X を 3以上の奇数で, 割り切れなくなるまで順次割っていく.
    for(LL i = 3; i <= sqrt(X); i += 2){
        while(X % i == 0){
            ret[i]++;
            X /= i;
        }
    }
    
    // 3. X が 2 より 大きな素数であれば, 追加.
    if(X > 2) ret[X]++;
    
    // 4. 本問では, 1 も 追加.
    ret[1]++;
    
    // 5. 出力.
    return ret;
}

int main(){
    
    // 1. 入力情報取得.
    LL a, b;
    scanf("%lld %lld", &a, &b);
    
    // 2. a, b の 最大公約数.
    LL g = __gcd(a, b);
    // printf("g=%lld\n", g);
    
    // 3. g を 素因数分解.
    map<LL, int> m = div(g);
    // for(auto &p : m) printf("%lld ", p.first);
    // printf("\n");
    
    // 4. 出力 ～ 後処理.
    printf("%d\n", m.size());
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

// 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<LL, int> div(LL X){

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

map<LL, int> ret;

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

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

for(LL i = 3; i <= sqrt(X); i += 2){

while(X % i == 0){

ret[i]++;

X /= i;

}

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

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

// 4. 本問では, 1 も追加.

ret[1]++;

// 5. 出力.

return ret;

}

int main(){

// 1. 入力情報取得.

LL a, b;

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

// 2. a, b の最大公約数.

LL g = __gcd(a, b);

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

// 3. g を素因数分解.

map<LL, int> m = div(g);

// for(auto &p : m) printf("%lld ", p.first);

// printf("\n");

// 4. 出力～後処理.

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

return 0;

}

[入力例]
12 18

[出力例(debug版)]
g=6
1 2 3 
3
※AtCoderテストケースより

[入力例]
420 660

[出力例(debug版)]
g=60
1 2 3 5 
4
※AtCoderテストケースより

[入力例]
1 2019

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

[入力例]
200560490130 7420738134810

[出力例(debug版)]
g=200560490130
1 2 3 5 7 11 13 17 19 23 29 31 
12

[入力例]
7420738134810 304250263527210

[出力例(debug版)]
g=7420738134810
1 2 3 5 7 11 13 17 19 23 29 31 37 
13

[入力例]
13201409035815 171618317465595

[出力例(debug版)]
g=13201409035815
1 3 5 7 11 13 17 19 23 29 53 
11

[入力例]

12 18

[出力例(debug版)]

g=6

1 2 3

※AtCoderテストケースより

[入力例]

420 660

[出力例(debug版)]

g=60

1 2 3 5

※AtCoderテストケースより

[入力例]

1 2019

[出力例(debug版)]

g=1

※AtCoderテストケースより

[入力例]

200560490130 7420738134810

[出力例(debug版)]

g=200560490130

1 2 3 5 7 11 13 17 19 23 29 31

[入力例]

7420738134810 304250263527210

[出力例(debug版)]

g=7420738134810

1 2 3 5 7 11 13 17 19 23 29 31 37

[入力例]

13201409035815 171618317465595

[出力例(debug版)]

g=13201409035815

1 3 5 7 11 13 17 19 23 29 53

■参照サイト
AtCoder Beginner Contest 142

2019年9月22日2019年9月22日

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

C++の練習を兼ねて, AtCoder Grand Contest 008 の問題D (D – K-th K) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を見て, 実装した.
2. ややこしい実装となったが, 何とかAC版になった.

本家のサイトAGC 008 Editorialをご覧下さい.

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

// 解き直し.
// AGC 008 Editorial
// https://img.atcoder.jp/agc008/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
const int MAX = 555;
int IX[MAX], OX[MAX * MAX + 1], ANS[MAX * MAX + 1];
deque<int> lDq, rDq;

int main(){
    // 1. 入力情報取得.
    int N;
    scanf("%d", &N);
    for(int i = 1; i <= N; i++){
        scanf("%d", &IX[i]);
        OX[IX[i]] = i;
        ANS[IX[i]] = i;
    }
    
    // 2. 解説通り.
    // 2-1. 左側から配置していく.
    for(int i = 0; i <= MAX * MAX; i++){
        int index = OX[i];
        // index - 1 個 を 配置.
        if(index > 0) for(int j = 1; j < index; j++) lDq.pb(index);
    }
    
    // 2-2. 右側から配置していく.
    for(int i = MAX * MAX; i >= 0; i--){
        int index = OX[i];
        // N - index 個 を 配置.
        if(index > 0) for(int j = 1; j <= N - index; j++) rDq.pf(index);
    }
    
    // 3. 数列作成.
    int index = 1;
    while(!lDq.empty()){
        int d = lDq.front();
        while(ANS[index] > 0) index++;
        lDq.pop_front();
        ANS[index] = d;
        index++;
    }
    while(!rDq.empty()){
        int d = rDq.front();
        while(ANS[index] > 0) index++;
        rDq.pop_front();
        ANS[index] = d;
        index++;
    }
    
    // 4. 整合性チェック.
    bool ok = true;
    for(int i = 1; i <= N; i++){
        int count = 0;
        for(int j = 1; j <= N * N; j++){
            if(ANS[j] == i) count++;
            if(count == i){
                if(j != IX[i]) ok = false;
                break;
            }
        }
        if(!ok) break;
    }
    
    // 5. 出力.
    if(!ok){
        printf("%s\n", "No");
        return 0;
    }
    printf("%s\n", "Yes");
    for(int i = 1; i <= MAX * MAX; i++) if(ANS[i] != 0) printf("%d ", ANS[i]);
    return 0;
}

// 解き直し.

// AGC 008 Editorial

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

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define pf push_front

const int MAX = 555;

int IX[MAX], OX[MAX * MAX + 1], ANS[MAX * MAX + 1];

deque<int> lDq, rDq;

int main(){

// 1. 入力情報取得.

int N;

scanf("%d", &N);

for(int i = 1; i <= N; i++){

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

OX[IX[i]] = i;

ANS[IX[i]] = i;

}

// 2. 解説通り.

// 2-1. 左側から配置していく.

for(int i = 0; i <= MAX * MAX; i++){

int index = OX[i];

// index - 1 個を配置.

if(index > 0) for(int j = 1; j < index; j++) lDq.pb(index);

}

// 2-2. 右側から配置していく.

for(int i = MAX * MAX; i >= 0; i--){

int index = OX[i];

// N - index 個を配置.

if(index > 0) for(int j = 1; j <= N - index; j++) rDq.pf(index);

}

// 3. 数列作成.

int index = 1;

while(!lDq.empty()){

int d = lDq.front();

while(ANS[index] > 0) index++;

lDq.pop_front();

ANS[index] = d;

index++;

}

while(!rDq.empty()){

int d = rDq.front();

while(ANS[index] > 0) index++;

rDq.pop_front();

ANS[index] = d;

index++;

}

// 4. 整合性チェック.

bool ok = true;

for(int i = 1; i <= N; i++){

int count = 0;

for(int j = 1; j <= N * N; j++){

if(ANS[j] == i) count++;

if(count == i){

if(j != IX[i]) ok = false;

break;

}

if(!ok) break;

}

// 5. 出力.

if(!ok){

printf("%s\n", "No");

return 0;

}

printf("%s\n", "Yes");

for(int i = 1; i <= MAX * MAX; i++) if(ANS[i] != 0) printf("%d ", ANS[i]);

return 0;

}

[入力例]
3
1 5 9

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

[入力例]
2
4 1

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

[入力例]
5
1 5 9 11 15

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

[入力例]

1 5 9

[出力例]

Yes

1 2 3 3 2 1 1 2 3

※AtCoderテストケースより

[入力例]

4 1

[出力例]

※AtCoderテストケースより

[入力例]

1 5 9 11 15

[出力例]

Yes

1 2 3 3 2 4 4 4 3 5 4 5 5 5 5 1 1 1 1 2 2 2 3 3 4

■参照サイト
AtCoder Grand Contest 008

2019年9月22日

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

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

■感想.
1. 方針が見えなかったので, 解説を見て, 実装した.
2. 個人的には, 非常に面白い問題と感じた.

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

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

// 解き直し.
// AGC038解説.
// https://img.atcoder.jp/agc038/editorial.pdf
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報取得.
    int H, W, A, B;
    scanf("%d %d %d %d", &H, &W, &A, &B);
    
    // 2. 解説通り.
    // 0, 1 の 書き込み.
    int Matrix[H][W];
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            if(i < B && j < A)   Matrix[i][j] = 0;
            if(i < B && j >= A)  Matrix[i][j] = 1;
            if(i >= B && j < A)  Matrix[i][j] = 1;
            if(i >= B && j >= A) Matrix[i][j] = 0;
        }
    }
    
    // 3. 出力 ～ 後処理.
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++) printf("%d", Matrix[i][j]);
        printf("\n");
    }
    return 0;

}

// 解き直し.

// AGC038解説.

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

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報取得.

int H, W, A, B;

scanf("%d %d %d %d", &H, &W, &A, &B);

// 2. 解説通り.

// 0, 1 の書き込み.

int Matrix[H][W];

for(int i = 0; i < H; i++){

for(int j = 0; j < W; j++){

if(i < B && j < A) Matrix[i][j] = 0;

if(i < B && j >= A) Matrix[i][j] = 1;

if(i >= B && j < A) Matrix[i][j] = 1;

if(i >= B && j >= A) Matrix[i][j] = 0;

}

// 3. 出力～後処理.

for(int i = 0; i < H; i++){

for(int j = 0; j < W; j++) printf("%d", Matrix[i][j]);

printf("\n");

}

return 0;

}

[入力例]
3 3 1 1

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

[入力例]
1 5 2 0

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

[入力例]
10 10 3 7

[出力例]
0001111111
0001111111
0001111111
0001111111
0001111111
0001111111
0001111111
1110000000
1110000000
1110000000


[入力例]
21 20 19 18

[出力例]
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
00000000000000000001
11111111111111111110
11111111111111111110
11111111111111111110

[入力例]

3 3 1 1

[出力例]

011

100

※AtCoderテストケースより

[入力例]

1 5 2 0

[出力例]

11000

※AtCoderテストケースより

[入力例]

10 10 3 7

[出力例]

0001111111

1110000000

[入力例]

21 20 19 18

[出力例]

00000000000000000001

11111111111111111110

■参照サイト
AtCoder Grand Contest 038

2019年9月15日

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

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

■感想.
1. 解説を見る前に解けたので, とりあえず良かったと思う.
2. 一番大きな値段の品物に, 常に割引券を適用すると良さそうに見えたので, その方針で実装して, AC版となった.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報取得.
    int N, M;
    scanf("%d %d", &N, &M);
    priority_queue<LL> pq;
    for(int i = 0; i < N; i++){
        LL a;
        scanf("%lld", &a);
        pq.push(a);
    }
    
    // 2. priority_queue の 先頭要素 に, 常に 割引券 を 使用.
    while(M > 0){
        LL a = pq.top();
        pq.pop();
        a /= 2;     // 先頭要素に割引券使用.
        pq.push(a); // 割引券適用後の金額を追加.
        M--;
    }
    
    // 3. すべての品物を買うために必要なお金の最小値は？
    LL ans = 0;
    while(!pq.empty()){
        LL a = pq.top();
        pq.pop();
        ans += a;
    }
    
    // 4. 出力 ～ 後処理.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報取得.

int N, M;

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

priority_queue<LL> pq;

for(int i = 0; i < N; i++){

LL a;

scanf("%lld", &a);

pq.push(a);

}

// 2. priority_queue の先頭要素に, 常に割引券を使用.

while(M > 0){

LL a = pq.top();

pq.pop();

a /= 2; // 先頭要素に割引券使用.

pq.push(a); // 割引券適用後の金額を追加.

M--;

}

// 3. すべての品物を買うために必要なお金の最小値は？

LL ans = 0;

while(!pq.empty()){

LL a = pq.top();

pq.pop();

ans += a;

}

// 4. 出力～後処理.

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

return 0;

}

[入力例]
3 3
2 13 8

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

[入力例]
4 4
1 9 3 5

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

[入力例]
1 100000
1000000000

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

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

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

[入力例]
30 17
111 3333 66666 11111 77777 2222 888 555 333 4444 22222 88888 777 444 33333 5555 666 55555 1111 6666 7777 666 222 9999 44444 1215 8888 1353 99999 999

[出力例]
172109

[入力例]

3 3

2 13 8

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 9 3 5

[出力例]

※AtCoderテストケースより

[入力例]

1 100000

1000000000

[出力例]

※AtCoderテストケースより

[入力例]

10 1

1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

[出力例]

9500000000

※AtCoderテストケースより

[入力例]

30 17

111 3333 66666 11111 77777 2222 888 555 333 4444 22222 88888 777 444 33333 5555 666 55555 1111 6666 7777 666 222 9999 44444 1215 8888 1353 99999 999

[出力例]

172109

■参照サイト
AtCoder Beginner Contest 141

2019年9月14日2019年9月14日

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

C++の練習を兼ねて, AtCoder Grand Contest 008 の問題B (B – Contiguous Repainting) を解いてみた.

■感想.
1. 解説を見る前に解けたので, とりあえず良かったと思う.
2. 一番最後に塗った, 連続K個のマス以外のマスは, マスの色を自由に決定可能に見えたので, その方針で実装して, AC版となった.
3. 引き続き, 大量に残っている未着手の問題を, 時間見つけて復習していきたいと思う.

本家のサイトAGC 008 Editorialをご覧下さい.

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL A[123456], kPlus[123456], kTotal[123456];

int main(){
    
    // 1. 入力情報取得.
    int N, K;
    scanf("%d %d", &N, &K);
    LL pTotal = 0;
    for(int i = 0; i < N; i++){
        scanf("%lld", &A[i]);
        if(A[i] > 0) pTotal += A[i];
    }
    
    // 2. プラスのみの累積和, 符号に依らない累積和 を 保存.
    // ex.
    // kPlus[4]  は, A[0] ～ A[4] で, プラスのものだけを合計.
    // kTotal[4] は, A[0] ～ A[4] を合計.
    kPlus[0] = (A[0] > 0) ? A[0] : 0;
    kTotal[0] = A[0];
    for(int i = 1; i < N; i++){
        // kPlus更新.
        if(A[i] > 0) kPlus[i] += kPlus[i - 1] + A[i];
        else         kPlus[i] =  kPlus[i - 1];
        // kTotal更新.
        kTotal[i] += kTotal[i - 1] + A[i];
    }
    // for(int i = 0; i < N; i++) printf("%lld ", kPlus[i]);
    // printf("\n");
    // for(int i = 0; i < N; i++) printf("%lld ", kTotal[i]);
    // printf("\n");
    
    // 3. スコアの最大値を計算.
    LL ans = 0;
    for(int i = K - 1; i < N; i++){
        LL kp = (i > K - 1) ? kPlus[i]  - kPlus[i - K]  : kPlus[i];
        LL kt = (i > K - 1) ? kTotal[i] - kTotal[i - K] : kTotal[i];
        // K個連続で, 黒色にする場合.
        ans = max(ans, pTotal - kp + kt);
        // K個連続で, 白色にする場合.
        ans = max(ans, pTotal - kp + 0);
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

LL A[123456], kPlus[123456], kTotal[123456];

int main(){

// 1. 入力情報取得.

int N, K;

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

LL pTotal = 0;

for(int i = 0; i < N; i++){

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

if(A[i] > 0) pTotal += A[i];

}

// 2. プラスのみの累積和, 符号に依らない累積和を保存.

// ex.

// kPlus[4] は, A[0] ～ A[4] で, プラスのものだけを合計.

// kTotal[4] は, A[0] ～ A[4] を合計.

kPlus[0] = (A[0] > 0) ? A[0] : 0;

kTotal[0] = A[0];

for(int i = 1; i < N; i++){

// kPlus更新.

if(A[i] > 0) kPlus[i] += kPlus[i - 1] + A[i];

else kPlus[i] = kPlus[i - 1];

// kTotal更新.

kTotal[i] += kTotal[i - 1] + A[i];

}

// for(int i = 0; i < N; i++) printf("%lld ", kPlus[i]);

// printf("\n");

// for(int i = 0; i < N; i++) printf("%lld ", kTotal[i]);

// printf("\n");

// 3. スコアの最大値を計算.

LL ans = 0;

for(int i = K - 1; i < N; i++){

LL kp = (i > K - 1) ? kPlus[i] - kPlus[i - K] : kPlus[i];

LL kt = (i > K - 1) ? kTotal[i] - kTotal[i - K] : kTotal[i];

// K個連続で, 黒色にする場合.

ans = max(ans, pTotal - kp + kt);

// K個連続で, 白色にする場合.

ans = max(ans, pTotal - kp + 0);

}

// 4. 出力.

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

return 0;

}

[入力例]
5 3
-10 10 -10 10 -10

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

[入力例]
4 2
10 -10 -10 10

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

[入力例]
1 1
-10

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

[入力例]
10 5
5 -4 -5 -8 -4 7 2 -4 0 7

[出力例(debug版)]
5 5 5 5 5 12 14 14 14 21 
5 1 -4 -12 -16 -9 -7 -11 -11 -4 
17
※AtCoderテストケースより

[入力例]
32 8
1 -4 1 -4 2 -1 3 -5 6 -2 3 -7 3 0 9 -5 0 -4 8 -8 0 -1 6 -8 8 -7 2 -4 2 0 9 -7

[出力例(debug版)]
1 1 2 2 4 4 7 7 13 13 16 16 19 19 28 28 28 28 36 36 36 36 42 42 50 50 52 52 54 54 63 63 
1 -3 -2 -6 -4 -5 -2 -7 -1 -3 0 -7 -4 -4 5 0 0 -4 4 -4 -4 -5 1 -7 1 -6 -4 -8 -6 -6 3 -4 
56

[入力例]

5 3

-10 10 -10 10 -10

[出力例(debug版)]

0 10 10 20 20

-10 0 -10 0 -10

※AtCoderテストケースより

[入力例]

4 2

10 -10 -10 10

[出力例(debug版)]

10 10 10 20

10 0 -10 0

※AtCoderテストケースより

[入力例]

1 1

-10

[出力例(debug版)]

-10

※AtCoderテストケースより

[入力例]

10 5

5 -4 -5 -8 -4 7 2 -4 0 7

[出力例(debug版)]

5 5 5 5 5 12 14 14 14 21

5 1 -4 -12 -16 -9 -7 -11 -11 -4

※AtCoderテストケースより

[入力例]

32 8

1 -4 1 -4 2 -1 3 -5 6 -2 3 -7 3 0 9 -5 0 -4 8 -8 0 -1 6 -8 8 -7 2 -4 2 0 9 -7

[出力例(debug版)]

1 1 2 2 4 4 7 7 13 13 16 16 19 19 28 28 28 28 36 36 36 36 42 42 50 50 52 52 54 54 63 63

1 -3 -2 -6 -4 -5 -2 -7 -1 -3 0 -7 -4 -4 5 0 0 -4 4 -4 -4 -5 1 -7 1 -6 -4 -8 -6 -6 3 -4

■参照サイト
AtCoder Grand Contest 008

2019年9月8日2019年9月8日

■感想.
1. 方針が見えなかったので, 解説を参照して, 実装した.
2. 最初, testcase_01等で, TLE となったが, while文の終了条件が不足していたので, 追加した.
3. 幸福の最大人数は, (N – 1)人のはずなので, やや強引だと思われるが, min(ans, N – 1) の制約条件を追加した.
※while文で, 幸福の最大人数の制約条件を追加する方法が分からなかったため.

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

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

// 解き直し.
// ABC 140解説.
// https://img.atcoder.jp/abc140/editorial.pdf
#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報取得.
    int N, K;
    scanf("%d %d", &N, &K);
    char c[111111];
    scanf("%s", c);
    
    // 2. 解説通り.
    // 赤印: r0, r, rn
    int r0 = (c[0] == 'L') ? 1 : 0;     // c[0]     が 'L' の 場合は, r0 = 1 を 設定.
    int rn = (c[N - 1] == 'R') ? 1 : 0; // c[N - 1] が 'R' の 場合は, rn = 1 を 設定.
    int r = 0, ans = 0;
    for(int i = 1; i < N; i++){
        if(c[i - 1] == 'R' && c[i] == 'L') r++;   // 赤印加算.
        if(c[i - 1] == c[i])               ans++; // 'LL' or 'RR' の 場合.
    }
    // printf("r0=%d r=%d rn=%d ans=%d\n", r0, r, rn, ans);
    
    // 3. 幸福の最大人数を計算.
    // 操作K回で, 幸福である人を増加.
    while(1){
        if(K > 0 && r > 0)            ans += 2,  r--, K--;
        if(K > 0 && r == 0 && r0 > 0) ans++,    r0--, K--;
        if(K > 0 && r == 0 && rn > 0) ans++,    rn--, K--;
        // testcase_01等 の TLE対応.
        if(K == 0)                       break;
        if(r == 0 && r0 == 0 && rn == 0) break;
        if(ans >= N - 1)                 break;
    }
    
    // 4. 出力 ～ 後処理.
    // 幸福の最大人数は, N - 1人 の はず.
    ans = min(ans, N - 1);
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// ABC 140解説.

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

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報取得.

int N, K;

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

char c[111111];

scanf("%s", c);

// 2. 解説通り.

// 赤印: r0, r, rn

int r0 = (c[0] == 'L') ? 1 : 0; // c[0] が 'L' の場合は, r0 = 1 を設定.

int rn = (c[N - 1] == 'R') ? 1 : 0; // c[N - 1] が 'R' の場合は, rn = 1 を設定.

int r = 0, ans = 0;

for(int i = 1; i < N; i++){

if(c[i - 1] == 'R' && c[i] == 'L') r++; // 赤印加算.

if(c[i - 1] == c[i]) ans++; // 'LL' or 'RR' の場合.

}

// printf("r0=%d r=%d rn=%d ans=%d\n", r0, r, rn, ans);

// 3. 幸福の最大人数を計算.

// 操作K回で, 幸福である人を増加.

while(1){

if(K > 0 && r > 0) ans += 2, r--, K--;

if(K > 0 && r == 0 && r0 > 0) ans++, r0--, K--;

if(K > 0 && r == 0 && rn > 0) ans++, rn--, K--;

// testcase_01等の TLE対応.

if(K == 0) break;

if(r == 0 && r0 == 0 && rn == 0) break;

if(ans >= N - 1) break;

}

// 4. 出力～後処理.

// 幸福の最大人数は, N - 1人のはず.

ans = min(ans, N - 1);

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

return 0;

}

[入力例]
6 1
LRLRRL

[出力例(debug版)]
r0=1 r=2 rn=0 ans=1
3
※AtCoderテストケースより

[入力例]
13 3
LRRLRLRRLRLLR

[出力例(debug版)]
r0=1 r=4 rn=1 ans=3
9
※AtCoderテストケースより

[入力例]
10 1
LLLLLRRRRR

[出力例(debug版)]
r0=1 r=0 rn=1 ans=8
9
※AtCoderテストケースより

[入力例]
9 2
RRRLRLRLL

[出力例(debug版)]
r0=0 r=3 rn=0 ans=3
7
※AtCoderテストケースより

[入力例]
6 2
LRLRRL

[出力例(debug版)]
r0=1 r=2 rn=0 ans=1
5
※実際, LRLRRL = L "RLRR" L -> L "LRLL" L = LL "R" LLL -> LL "L" LLL = LLLLLL
となり, 幸福の最大人数 5人 に到達することが分かる.

[入力例]
30 5
LRLRRLRLLRLRLLRRLRLRRRRLRLLRLR

[出力例(debug版)]
r0=1 r=10 rn=1 ans=8
18
※実際, 
① L "RL" RRLRLLRLRLLRRLRLRRRRLRLLRLR -> L "LR" RRLRLLRLRLLRRLRLRRRRLRLLRLR
② LLRRR "LRLL" RLRLLRRLRLRRRRLRLLRLR -> LLRRR "RRLR" RLRLLRRLRLRRRRLRLLRLR
③ LLRRRRR "LRRL" RLLRRLRLRRRRLRLLRLR -> LLRRRRR "RLLR" RLLRRLRLRRRRLRLLRLR
④ LLRRRRRRLLRRLLRRL "RLRRRR" LRLLRLR -> LLRRRRRRLLRRLLRRL "LLLLRL" LRLLRLR
⑤ LLRRRRRRLLRRLLRRLLLLL "RLLR" LLRLR -> LLRRRRRRLLRRLLRRLLLLL "LRRL" LLRLR
上記から, LLRRRRRRLLRRLLRRLLLLLLRRLLLRLR であり,
1 + 5 + 1 + 1 + 1 + 1 + 5 + 1 + 2 = 18 と集計出来るので, 幸福である人 18人 に到達することが分かる.

[入力例]

6 1

LRLRRL

[出力例(debug版)]

r0=1 r=2 rn=0 ans=1

※AtCoderテストケースより

[入力例]

13 3

LRRLRLRRLRLLR

[出力例(debug版)]

r0=1 r=4 rn=1 ans=3

※AtCoderテストケースより

[入力例]

10 1

LLLLLRRRRR

[出力例(debug版)]

r0=1 r=0 rn=1 ans=8

※AtCoderテストケースより

[入力例]

9 2

RRRLRLRLL

[出力例(debug版)]

r0=0 r=3 rn=0 ans=3

※AtCoderテストケースより

[入力例]

6 2

LRLRRL

[出力例(debug版)]

r0=1 r=2 rn=0 ans=1

※実際, LRLRRL = L "RLRR" L -> L "LRLL" L = LL "R" LLL -> LL "L" LLL = LLLLLL

となり, 幸福の最大人数 5人に到達することが分かる.

[入力例]

30 5

LRLRRLRLLRLRLLRRLRLRRRRLRLLRLR

[出力例(debug版)]

r0=1 r=10 rn=1 ans=8

※実際,

① L "RL" RRLRLLRLRLLRRLRLRRRRLRLLRLR -> L "LR" RRLRLLRLRLLRRLRLRRRRLRLLRLR

② LLRRR "LRLL" RLRLLRRLRLRRRRLRLLRLR -> LLRRR "RRLR" RLRLLRRLRLRRRRLRLLRLR

③ LLRRRRR "LRRL" RLLRRLRLRRRRLRLLRLR -> LLRRRRR "RLLR" RLLRRLRLRRRRLRLLRLR

④ LLRRRRRRLLRRLLRRL "RLRRRR" LRLLRLR -> LLRRRRRRLLRRLLRRL "LLLLRL" LRLLRLR

⑤ LLRRRRRRLLRRLLRRLLLLL "RLLR" LLRLR -> LLRRRRRRLLRRLLRRLLLLL "LRRL" LLRLR

上記から, LLRRRRRRLLRRLLRRLLLLLLRRLLLRLR であり,

1 + 5 + 1 + 1 + 1 + 1 + 5 + 1 + 2 = 18 と集計出来るので, 幸福である人 18人に到達することが分かる.

■参照サイト
AtCoder Beginner Contest 140

2019年9月7日

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

C++の練習を兼ねて, AtCoder Regular Contest 102 の問題D (D – All Your Paths are Different Lengths) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を参照して, 実装した.
2. ほぼ, 解説通りに実装できたと思う.
3. 1年以上前に, AtCoder Beginner Contest 108 の問題D（All Your Paths are Different Lengths）として, 復習していたが, 記憶から, ほとんど消えていたようである.
今回, 改めて復習して良かったと思う.

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

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

// 解き直し.
// ARC 102解説.
// https://img.atcoder.jp/arc102/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define p1 first
#define p2 second
const int MAX_N = 21;
typedef pair<int, int> pii;

vector<vector<pii>> graph(MAX_N);
int pow2[MAX_N];

int main(){
    
    // 1. 入力情報取得.
    int L;
    scanf("%d", &L);
    
    // 2. 解説通り.
    // 2-1. 頂点 i から 頂点 i + 1 へ, 長さ 0, pow2[i - 1] の 辺を, 1本ずつ張る.
    int r = 0, M = 0;
    pow2[0] = 1;
    for(int i = 1; i < MAX_N; i++){
        pow2[i] = pow2[i - 1] * 2;
        if(pow2[i] <= L) r++;
    }
    int N = r + 1;
    for(int i = 1; i < N; i++){
        graph[i].pb({i + 1, 0});
        graph[i].pb({i + 1, pow2[i - 1]});
        M += 2;
    }
    
    // 2-2. 条件を確認しながら, 頂点 t から 頂点 N に, 長さ L - pow2[t - 1] の 辺を, 1本ずつ張る.
    for(int t = N - 1; t >= 1; t--){
        if(L - pow2[t - 1] >= pow2[r]){
            graph[t].pb({N, L - pow2[t - 1]});
            L -= pow2[t - 1];
            M++;
        }
    }
    
    // 3. 出力.
    printf("%d %d\n", N, M);
    for(int i = 1; i <= N; i++){
        for(auto &o : graph[i]) printf("%d %d %d\n", i, o.p1, o.p2);
    }
    return 0;
}

// 解き直し.

// ARC 102解説.

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

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

#define p1 first

#define p2 second

const int MAX_N = 21;

typedef pair<int, int> pii;

vector<vector<pii>> graph(MAX_N);

int pow2[MAX_N];

int main(){

// 1. 入力情報取得.

int L;

scanf("%d", &L);

// 2. 解説通り.

// 2-1. 頂点 i から頂点 i + 1 へ, 長さ 0, pow2[i - 1] の辺を, 1本ずつ張る.

int r = 0, M = 0;

pow2[0] = 1;

for(int i = 1; i < MAX_N; i++){

pow2[i] = pow2[i - 1] * 2;

if(pow2[i] <= L) r++;

}

int N = r + 1;

for(int i = 1; i < N; i++){

graph[i].pb({i + 1, 0});

graph[i].pb({i + 1, pow2[i - 1]});

M += 2;

}

// 2-2. 条件を確認しながら, 頂点 t から頂点 N に, 長さ L - pow2[t - 1] の辺を, 1本ずつ張る.

for(int t = N - 1; t >= 1; t--){

if(L - pow2[t - 1] >= pow2[r]){

graph[t].pb({N, L - pow2[t - 1]});

L -= pow2[t - 1];

M++;

}

// 3. 出力.

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

for(int i = 1; i <= N; i++){

for(auto &o : graph[i]) printf("%d %d %d\n", i, o.p1, o.p2);

}

return 0;

}

[入力例]
2

[出力例]
2 2
1 2 0
1 2 1

[入力例]
3

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

[入力例]
4

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

[入力例]
5

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

[入力例]
6

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

[入力例]
123456

[出力例]
17 37
1 2 0
1 2 1
2 3 0
2 3 2
3 4 0
3 4 4
4 5 0
4 5 8
5 6 0
5 6 16
6 7 0
6 7 32
7 8 0
7 8 64
7 17 65536
8 9 0
8 9 128
9 10 0
9 10 256
10 11 0
10 11 512
10 17 65600
11 12 0
11 12 1024
12 13 0
12 13 2048
13 14 0
13 14 4096
14 15 0
14 15 8192
14 17 66112
15 16 0
15 16 16384
15 17 74304
16 17 0
16 17 32768
16 17 90688

[入力例]
654321

[出力例]
20 51
1 2 0
1 2 1
1 20 524288
2 3 0
2 3 2
3 4 0
3 4 4
4 5 0
4 5 8
5 6 0
5 6 16
5 20 524289
6 7 0
6 7 32
6 20 524305
7 8 0
7 8 64
7 20 524337
8 9 0
8 9 128
8 20 524401
9 10 0
9 10 256
9 20 524529
10 11 0
10 11 512
10 20 524785
11 12 0
11 12 1024
12 13 0
12 13 2048
12 20 525297
13 14 0
13 14 4096
13 20 527345
14 15 0
14 15 8192
14 20 531441
15 16 0
15 16 16384
15 20 539633
16 17 0
16 17 32768
16 20 556017
17 18 0
17 18 65536
17 20 588785
18 19 0
18 19 131072
19 20 0
19 20 262144

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

[入力例]

[出力例]

2 2

1 2 0

1 2 1

[入力例]

[出力例]

2 3

1 2 0

1 2 1

1 2 2

[入力例]

[出力例]

3 4

1 2 0

1 2 1

2 3 0

2 3 2

※AtCoderテストケースより

[入力例]

[出力例]

3 5

1 2 0

1 2 1

1 3 4

2 3 0

2 3 2

※AtCoderテストケースより

[入力例]

[出力例]

3 5

1 2 0

1 2 1

2 3 0

2 3 2

2 3 4

[入力例]

123456

[出力例]

17 37

1 2 0

1 2 1

2 3 0

2 3 2

3 4 0

3 4 4

4 5 0

4 5 8

5 6 0

5 6 16

6 7 0

6 7 32

7 8 0

7 8 64

7 17 65536

8 9 0

8 9 128

9 10 0

9 10 256

10 11 0

10 11 512

10 17 65600

11 12 0

11 12 1024

12 13 0

12 13 2048

13 14 0

13 14 4096

14 15 0

14 15 8192

14 17 66112

15 16 0

15 16 16384

15 17 74304

16 17 0

16 17 32768

16 17 90688

[入力例]

654321

[出力例]

20 51

1 2 0

1 2 1

1 20 524288

2 3 0

2 3 2

3 4 0

3 4 4

4 5 0

4 5 8

5 6 0

5 6 16

5 20 524289

6 7 0

6 7 32

6 20 524305

7 8 0

7 8 64

7 20 524337

8 9 0

8 9 128

8 20 524401

9 10 0

9 10 256

9 20 524529

10 11 0

10 11 512

10 20 524785

11 12 0

11 12 1024

12 13 0

12 13 2048

12 20 525297

13 14 0

13 14 4096

13 20 527345

14 15 0

14 15 8192

14 20 531441

15 16 0

15 16 16384

15 20 539633

16 17 0

16 17 32768

16 20 556017

17 18 0

17 18 65536

17 20 588785

18 19 0

18 19 131072

19 20 0

19 20 262144

■参照サイト
AtCoder Regular Contest 102

2019年9月1日

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

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

■感想.
1. とりあえず, 推測した内容で, AC版となったので, 良かったと思う.
2. 引き続き, 時間を見つけて, 過去問の復習を進めたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(){
    
    // 1. 入力情報取得.
    LL N;
    scanf("%lld", &N);
    
    // 2. M1 + ... + MN の 最大値 を 計算.
    // -> 最大値になると思われるパターン.
    // 1 を 2 で 割った余り     … 1
    // 2 を 3 で 割った余り     … 2
    // ...
    // N - 1 を N で 割った余り … N - 1
    // N     を 1 で 割った余り … 0
    LL ans = (N - 1) * N / 2;
    
    // 3. 出力 ～ 後処理.
    printf("%lld", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

int main(){

// 1. 入力情報取得.

LL N;

scanf("%lld", &N);

// 2. M1 + ... + MN の最大値を計算.

// -> 最大値になると思われるパターン.

// 1 を 2 で割った余り … 1

// 2 を 3 で割った余り … 2

// ...

// N - 1 を N で割った余り … N - 1

// N を 1 で割った余り … 0

LL ans = (N - 1) * N / 2;

// 3. 出力～後処理.

printf("%lld", ans);

return 0;

}

[入力例]
2

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

[入力例]
13

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

[入力例]
1

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

[入力例]
123454321

[出力例]
7620484625058360

[入力例]
1000000000

[出力例]
499999999500000000

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

123454321

[出力例]

7620484625058360

[入力例]

1000000000

[出力例]

499999999500000000

■参照サイト
AtCoder Beginner Contest 139

月: 2019年9月

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

C++の練習を兼ねて, AtCoder Beginner Contest 142 の問題D (D – Disjoint Set of Common Divisors) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 008 の問題D (D – K-th K) を解いてみた.

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

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

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

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

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

C++の練習を兼ねて, AtCoder Grand Contest 008 の問題B (B – Contiguous Repainting) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Regular Contest 102 の問題D (D – All Your Paths are Different Lengths) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 142 の 問題D (D – Disjoint Set of Common Divisors) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 008 の 問題D (D – K-th K) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Grand Contest 008 の 問題B (B – Contiguous Repainting) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 102 の 問題D (D – All Your Paths are Different Lengths) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 142 の問題D (D – Disjoint Set of Common Divisors) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 008 の問題D (D – K-th K) を解いてみた.

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

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

C++の練習を兼ねて, AtCoder Grand Contest 008 の問題B (B – Contiguous Repainting) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 102 の問題D (D – All Your Paths are Different Lengths) を解いてみた.

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