個人用メモ帳

2020年4月4日2020年4月4日

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

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

■感想.
1. 個人的には, 非常に面白い問題に感じた.
※ 但し, かなり重たい実装になってしまったので, 解説を, 勉強しようと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

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

// Lunlun数のリストを更新する.
// @param s:    (更新前)Lunlun数情報のリスト.
// @return ret: (更新後)Lunlun数情報のリスト.
set<LL> updateLunlun(set<LL> s){
    set<LL> ret;
    for(auto &o : s){
        LL r = o % 10; // 1の位を取得.
        for(LL d : {-1, 0, 1}){
            LL a = r + d; // 1の位に, -1, 0, 1 を 加算.
            if(a >= 0 && a <= 9) ret.insert(o), ret.insert(10 * o + a);
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. Lunlun数 を 保存.
    set<LL> s;
    rep(i, 9) s.insert(i + 1);
    rep(i, 10){
        set<LL> ls = updateLunlun(s);
        swap(s, ls);
    }
    
    // 3. K番目 を 取得.
    LL ans = 0;
    int count = 0;
    for(auto &p : s){
        if(++count == K){
            ans = p;
            break;
        }
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

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

// Lunlun数のリストを更新する.

// @param s: (更新前)Lunlun数情報のリスト.

// @return ret: (更新後)Lunlun数情報のリスト.

set<LL> updateLunlun(set<LL> s){

set<LL> ret;

for(auto &o : s){

LL r = o % 10; // 1の位を取得.

for(LL d : {-1, 0, 1}){

LL a = r + d; // 1の位に, -1, 0, 1 を加算.

if(a >= 0 && a <= 9) ret.insert(o), ret.insert(10 * o + a);

}

return ret;

}

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. Lunlun数を保存.

set<LL> s;

rep(i, 9) s.insert(i + 1);

rep(i, 10){

set<LL> ls = updateLunlun(s);

swap(s, ls);

}

// 3. K番目を取得.

LL ans = 0;

int count = 0;

for(auto &p : s){

if(++count == K){

ans = p;

break;

}

// 4. 出力.

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

return 0;

}

[入力例]
15

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

[入力例]
1

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

[入力例]
13

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

[入力例]
100000

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

[入力例]
123

[出力例]
1123

[入力例]
1234

[出力例]
222343

[入力例]
12345

[出力例]
33432123

[入力例]
123456

[出力例]
4455544433

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

100000

[出力例]

3234566667

※AtCoderテストケースより

[入力例]

123

[出力例]

1123

[入力例]

1234

[出力例]

222343

[入力例]

12345

[出力例]

33432123

[入力例]

123456

[出力例]

4455544433

■参照サイト
AtCoder Beginner Contest 161

2020年4月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 017 の問題A (A – 素数、コンテスト、素数) ～問題B (B – 解像度が低い。) を解いてみた.

■感想.
1. 素数, 累積和の復習が出来たので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#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 arc[1010101];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 素数を抽出.
    repx(i, 2, 1010101){
        if(arc[i] == 0) repex(j, i * 2, 1010101, i) if(!arc[j]) arc[j]++;;
    }
    
    // 3. 出力.
    printf("%s\n", arc[N] ? "NO" : "YES");
    return 0;
    
}

#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 arc[1010101];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 素数を抽出.

repx(i, 2, 1010101){

if(arc[i] == 0) repex(j, i * 2, 1010101, i) if(!arc[j]) arc[j]++;;

}

// 3. 出力.

printf("%s\n", arc[N] ? "NO" : "YES");

return 0;

}

[入力例]
17

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

[入力例]
18

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

[入力例]
999983

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

[入力例]
672263

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

[入力例]
314159

[出力例]
YES

[入力例]
954493

[出力例]
NO

[入力例]

[出力例]

YES

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

999983

[出力例]

YES

※AtCoderのテストケースより

[入力例]

672263

[出力例]

※AtCoderのテストケースより

[入力例]

314159

[出力例]

YES

[入力例]

954493

[出力例]

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

#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 a[303030], inc[303030], cum[303030];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N){
        scanf("%d", &a[i]);
        if(i && a[i - 1] < a[i]) inc[i]++;
    }
    
    // 2. 累積和.
    rep(i, N) cum[i + 1] = cum[i] + inc[i];
    
    // 3. K個の連続部分を確認.
    int ans = 0;
    repx(i, K, N + 1) if(cum[i] - cum[i - K + 1] == K - 1) ans++;
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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 a[303030], inc[303030], cum[303030];

int main(){

// 1. 入力情報.

int N, K;

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

rep(i, N){

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

if(i && a[i - 1] < a[i]) inc[i]++;

}

// 2. 累積和.

rep(i, N) cum[i + 1] = cum[i] + inc[i];

// 3. K個の連続部分を確認.

int ans = 0;

repx(i, K, N + 1) if(cum[i] - cum[i - K + 1] == K - 1) ans++;

// 4. 出力.

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

return 0;

}

[入力例]
10 4
100
300
600
700
800
400
500
800
900
900

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

[入力例]
10 3
10
40
50
80
90
30
20
40
90
95

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

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

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

[入力例]
8 2
100000
90000
50000
30000
10000
4000
200
1

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

[入力例]
3 1
5
4
3

[出力例]
3

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

[出力例]
3

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

[出力例]
7

100

101

102

103

104

[入力例]

10 4

100

300

600

700

800

400

500

800

900

[出力例]

※AtCoderのテストケースより

[入力例]

10 3

[出力例]

※AtCoderのテストケースより

[入力例]

8 4

[出力例]

※AtCoderのテストケースより

[入力例]

8 2

100000

90000

50000

30000

10000

4000

200

[出力例]

※AtCoderのテストケースより

[入力例]

3 1

[出力例]

[入力例]

5 2

[出力例]

[入力例]

15 5

[出力例]

■参照サイト
AtCoder Regular Contest 017

2020年4月2日2020年4月2日

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

C++の練習を兼ねて, AtCoder Regular Contest 012 の問題A (A – 週末) ～問題B (B – アキレスと亀) を解いてみた.

■感想.
1. 他の問題に比べて, すんなり実装できたので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 週末までの日数を出力.
// @param s: 曜日.
// @return : 週末までの日数.
int weekend(string s){
    if(s == "Sunday")    return 0;
    if(s == "Monday")    return 5;
    if(s == "Tuesday")   return 4;
    if(s == "Wednesday") return 3;
    if(s == "Thursday")  return 2;
    if(s == "Friday")    return 1;
    if(s == "Saturday")  return 0;
}

int main(){
    
    // 1. 入力情報.
    char c[22];
    scanf("%s", c);
    string s(c);
    
    // 2. 出力.
    printf("%d\n", weekend(s));
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

// 週末までの日数を出力.

// @param s: 曜日.

// @return : 週末までの日数.

int weekend(string s){

if(s == "Sunday") return 0;

if(s == "Monday") return 5;

if(s == "Tuesday") return 4;

if(s == "Wednesday") return 3;

if(s == "Thursday") return 2;

if(s == "Friday") return 1;

if(s == "Saturday") return 0;

}

int main(){

// 1. 入力情報.

char c[22];

scanf("%s", c);

string s(c);

// 2. 出力.

printf("%d\n", weekend(s));

return 0;

}

[入力例]
Monday

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

[入力例]
Saturday

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

[入力例]
Sunday

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

[入力例]
Wednesday

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

[入力例]

Monday

[出力例]

※AtCoderのテストケースより

[入力例]

Saturday

[出力例]

※AtCoderのテストケースより

[入力例]

Sunday

[出力例]

※AtCoderのテストケースより

[入力例]

Wednesday

[出力例]

※AtCoderのテストケースより

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

#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;
    double va, vb, L;
    scanf("%d %lf %lf %lf", &N, &va, &vb, &L);
    
    // 2. 高橋君とカメの距離は.
    double ans = L;
    rep(i, N) ans *= (vb / va);
    
    // 3. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

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

double va, vb, L;

scanf("%d %lf %lf %lf", &N, &va, &vb, &L);

// 2. 高橋君とカメの距離は.

double ans = L;

rep(i, N) ans *= (vb / va);

// 3. 出力.

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

return 0;

}

[入力例]
3 2 1 16

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

[入力例]
100 100 1 100

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

[入力例]
80 50 49 72

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

[入力例]
12 4 3 524288

[出力例]
16607.531250000000

[入力例]
10 100 99 999

[出力例]
903.477692933796

[入力例]

3 2 1 16

[出力例]

2.000000000000

※AtCoderのテストケースより

[入力例]

100 100 1 100

[出力例]

0.000000000000

※AtCoderのテストケースより

[入力例]

80 50 49 72

[出力例]

14.302717205907

※AtCoderのテストケースより

[入力例]

12 4 3 524288

[出力例]

16607.531250000000

[入力例]

10 100 99 999

[出力例]

903.477692933796

■参照サイト
AtCoder Regular Contest 012

2020年4月1日2020年4月1日

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

C++の練習を兼ねて, AtCoder Regular Contest 011 の問題A (A – 鉛筆リサイクルの新技術) ～問題B (B – ルイス・キャロルの記憶術) を解いてみた.

■感想.
1. 実装に苦労したものの, 個人的には, いずれも非常に面白い問題と感じた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

int main(){
    
    // 1. 入力情報.
    int m, n, N;
    scanf("%d %d %d", &m, &n, &N);
    
    // 2. 販売できる鉛筆の本数は？
    int sell = N, notRecycle = 0;
    while(N >= m){
        // リサイクル.
        int recycle = (N / m) * n;
        
        // 未リサイクル分.
        notRecycle += N % m;
        
        // 販売.
        sell += recycle;
        
        // 次回リサイクルの準備.
        N = recycle;
        // printf("recycle=%d N=%d notRecycle=%d sell=%d N=%d\n", recycle, N, notRecycle, sell, N);
        
        // 不足の場合.
        if(N < m){
            int d = min(m - N, notRecycle);
            N += d;
            notRecycle -= d;
        }
    }
    
    // 3. 出力.
    printf("%d\n", sell);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int m, n, N;

scanf("%d %d %d", &m, &n, &N);

// 2. 販売できる鉛筆の本数は？

int sell = N, notRecycle = 0;

while(N >= m){

// リサイクル.

int recycle = (N / m) * n;

// 未リサイクル分.

notRecycle += N % m;

// 販売.

sell += recycle;

// 次回リサイクルの準備.

N = recycle;

// printf("recycle=%d N=%d notRecycle=%d sell=%d N=%d\n", recycle, N, notRecycle, sell, N);

// 不足の場合.

if(N < m){

int d = min(m - N, notRecycle);

N += d;

notRecycle -= d;

}

// 3. 出力.

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

return 0;

}

[入力例]
2 1 8

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

[入力例]
7 4 30

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

[入力例]
100 99 1000

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

[入力例]
89 73 999

[出力例]
5160

[入力例]
7 3 987

[出力例]
1725

[入力例]

2 1 8

[出力例]

※AtCoderのテストケースより

[入力例]

7 4 30

[出力例]

※AtCoderのテストケースより

[入力例]

100 99 1000

[出力例]

90199

※AtCoderのテストケースより

[入力例]

89 73 999

[出力例]

5160

[入力例]

7 3 987

[出力例]

1725

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

// ロジック一部修正の上, 再提出.
#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 pb push_back
int alice[26];
vector<string> v;

// スキップするかどうかの判定.
// @param c: 対象文字.
// @return : スキップするかどうかの判定結果.
//     true: スキップする.
//    false: スキップしない.
bool isSkip(char c){
    // コンマ, ピリオドは, スキップ.
    if(c == ',' || c == '.') return true;
    
    // 母音(小文字)は, スキップ.
    if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y') return true;
    
    // 母音(大文字)は, スキップ.
    if(c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' || c == 'Y') return true;
    
    // それ以外は, スキップしない.
    return false;
}

// 変換テーブルを作成.
// @param : なし.
// @return : なし.
void update(){
    // 小文字.
    // ※ 大文字('B' - 'A' など)も, 同じ結果なので省略.
    alice['b' - 'a'] = 1;
    alice['c' - 'a'] = 1;
    alice['d' - 'a'] = 2;
    alice['w' - 'a'] = 2;
    alice['t' - 'a'] = 3;
    alice['j' - 'a'] = 3;
    alice['f' - 'a'] = 4;
    alice['q' - 'a'] = 4;
    alice['l' - 'a'] = 5;
    alice['v' - 'a'] = 5;
    alice['s' - 'a'] = 6;
    alice['x' - 'a'] = 6;
    alice['p' - 'a'] = 7;
    alice['m' - 'a'] = 7;
    alice['h' - 'a'] = 8;
    alice['k' - 'a'] = 8;
    alice['n' - 'a'] = 9;
    alice['g' - 'a'] = 9;
    alice['z' - 'a'] = 0;
    alice['r' - 'a'] = 0;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        char c[1010];
        scanf("%s", c);
        string s(c);
        v.pb(s);
    }
    
    // 2. 変換テーブル更新.
    update();
    
    // 3. 変換.
    string ans = "";
    int l = v.size();
    rep(i, l){
        string s = v[i];
        int count = 0;
        rep(j, s.size()){
            if(isSkip(s[j])){
                continue;
            }else{
                ans += (s[j] <= 'Z') ? to_string(alice[s[j] - 'A']) : to_string(alice[s[j] - 'a']);
                count++;
            }
        }
        if(count) ans += " ";
    }
    
    // 4. 出力.
    while(ans.back() == ' ') ans.pop_back();
    printf("%s\n", ans.c_str());
    return 0;
    
}

// ロジック一部修正の上, 再提出.

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

int alice[26];

vector<string> v;

// スキップするかどうかの判定.

// @param c: 対象文字.

// @return : スキップするかどうかの判定結果.

// true: スキップする.

// false: スキップしない.

bool isSkip(char c){

// コンマ, ピリオドは, スキップ.

if(c == ',' || c == '.') return true;

// 母音(小文字)は, スキップ.

if(c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'y') return true;

// 母音(大文字)は, スキップ.

if(c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U' || c == 'Y') return true;

// それ以外は, スキップしない.

return false;

}

// 変換テーブルを作成.

// @param : なし.

// @return : なし.

void update(){

// 小文字.

// ※ 大文字('B' - 'A' など)も, 同じ結果なので省略.

alice['b' - 'a'] = 1;

alice['c' - 'a'] = 1;

alice['d' - 'a'] = 2;

alice['w' - 'a'] = 2;

alice['t' - 'a'] = 3;

alice['j' - 'a'] = 3;

alice['f' - 'a'] = 4;

alice['q' - 'a'] = 4;

alice['l' - 'a'] = 5;

alice['v' - 'a'] = 5;

alice['s' - 'a'] = 6;

alice['x' - 'a'] = 6;

alice['p' - 'a'] = 7;

alice['m' - 'a'] = 7;

alice['h' - 'a'] = 8;

alice['k' - 'a'] = 8;

alice['n' - 'a'] = 9;

alice['g' - 'a'] = 9;

alice['z' - 'a'] = 0;

alice['r' - 'a'] = 0;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

char c[1010];

scanf("%s", c);

string s(c);

v.pb(s);

}

// 2. 変換テーブル更新.

update();

// 3. 変換.

string ans = "";

int l = v.size();

rep(i, l){

string s = v[i];

int count = 0;

rep(j, s.size()){

if(isSkip(s[j])){

continue;

}else{

ans += (s[j] <= 'Z') ? to_string(alice[s[j] - 'A']) : to_string(alice[s[j] - 'a']);

count++;

}

if(count) ans += " ";

}

// 4. 出力.

while(ans.back() == ' ') ans.pop_back();

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

return 0;

}

[入力例]
3
Mozart plays magic.

[出力例]
7003 756 791
※AtCoderのテストケースより

[入力例]
3
Columbus found USA.

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

[入力例]
7
I have a scissors for right hand.

[出力例]
85 616606 40 0983 892
※AtCoderのテストケースより

[入力例]
4
abc ab aa aiueo

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

[入力例]
4
aaa aa a aa

[出力例]

※AtCoderのテストケースより

[入力例]
20
Alice, a seven year old girl, is feeling bored and drowsy while sitting on the riverbank with her elder sister.

[出力例]
51 659 0 52 905 6 4599 102 92 2026 285 63399 9 38 050198 238 80 520 6630

[入力例]
34
Alice leaves the tea party and enters the garden where she comes upon three living playing cards painting the white roses on a rose tree red because The Queen of Hearts hates white roses.

[出力例]
51 556 38 3 703 92 9306 38 9029 280 68 176 79 380 5599 7599 1026 79399 38 283 066 9 06 30 02 116 38 49 4 8036 836 283 066

[入力例]

Mozart plays magic.

[出力例]

7003 756 791

※AtCoderのテストケースより

[入力例]

Columbus found USA.

[出力例]

15716 492 6

※AtCoderのテストケースより

[入力例]

I have a scissors for right hand.

[出力例]

85 616606 40 0983 892

※AtCoderのテストケースより

[入力例]

abc ab aa aiueo

[出力例]

11 1

※AtCoderのテストケースより

[入力例]

aaa aa a aa

[出力例]

※AtCoderのテストケースより

[入力例]

Alice, a seven year old girl, is feeling bored and drowsy while sitting on the riverbank with her elder sister.

[出力例]

51 659 0 52 905 6 4599 102 92 2026 285 63399 9 38 050198 238 80 520 6630

[入力例]

Alice leaves the tea party and enters the garden where she comes upon three living playing cards painting the white roses on a rose tree red because The Queen of Hearts hates white roses.

[出力例]

51 556 38 3 703 92 9306 38 9029 280 68 176 79 380 5599 7599 1026 79399 38 283 066 9 06 30 02 116 38 49 4 8036 836 283 066

■参照サイト
AtCoder Regular Contest 011
Alice’s Adventures in Wonderland

2020年3月31日2020年3月31日

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

C++の練習を兼ねて, AtCoder Beginner Contest 160 の問題E (E – Red and Green Apples) を解いてみた.

■感想.
1. 優先度付きキュー（priority_queue）を使う方針で, 何とかAC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using P = pair<LL, 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 a first
#define b second

int main(){
    
    // 1. 入力情報.
    int X, Y, A, B, C;
    scanf("%d %d %d %d %d", &X, &Y, &A, &B, &C);
    LL x;
    priority_queue<LL> pPQ, qPQ, r, apple;
    rep(i, A){
        scanf("%lld", &x);
        pPQ.push(x);
    }
    rep(i, B){
        scanf("%lld", &x);
        qPQ.push(x);
    }
    rep(i, C){
        scanf("%lld", &x);
        r.push(x);
    }
    
    // 2. X個 の 赤色リンゴ, Y個 の 緑色リンゴ を 保存.
    priority_queue<P, vector<P>, greater<P>> pq;
    int c1 = 0, c2 = 0;
    while(++c1 <= X){
        LL p = pPQ.top();
        pPQ.pop();
        pq.push({p, 1});
    }
    while(++c2 <= Y){
        LL q = qPQ.top();
        qPQ.pop();
        pq.push({q, 2});
    }
    
    // 3. 組み換え.
    // pq の 最小の美味しさのリンゴ と r の 最大の美味しさのリンゴ を 
    // 比較して, 組み換え.
    while(!pq.empty()){
        // pq から 取得.
        P a1 = pq.top();
        
        if(!r.empty()){
            // r から 取得.
            LL a2 = r.top();
            
            // リンゴ a1 が 赤色 の 場合, リンゴ a2 の 美味しさ が 大きい場合, 入れ替え.
            if(a1.b == 1 && X > 0 && a1.a < a2){
                pq.pop();
                pq.push({a2, 3});
                r.pop();
                X--;
                continue;
            }
            
            // リンゴ a1 が 緑色 の 場合, リンゴ a2 の 美味しさ が 大きい場合, 入れ替え.
            if(a1.b == 2 && Y > 0 && a1.a < a2){
                pq.pop();
                pq.push({a2, 3});
                r.pop();
                Y--;
                continue;
            }
        }
        
        // 組み替え出来なかった場合.
        pq.pop();
        apple.push(a1.a);
    }
    
    // 4. 美味しさの集計.
    LL ans = 0;
    while(!apple.empty()){
        LL a = apple.top();
        apple.pop();
        ans += a;
        // printf("%lld\n", a);
    }
    
    // 5. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using LL = long long;

using P = pair<LL, 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 a first

#define b second

int main(){

// 1. 入力情報.

int X, Y, A, B, C;

scanf("%d %d %d %d %d", &X, &Y, &A, &B, &C);

LL x;

priority_queue<LL> pPQ, qPQ, r, apple;

rep(i, A){

scanf("%lld", &x);

pPQ.push(x);

}

rep(i, B){

scanf("%lld", &x);

qPQ.push(x);

}

rep(i, C){

scanf("%lld", &x);

r.push(x);

}

// 2. X個の赤色リンゴ, Y個の緑色リンゴを保存.

priority_queue<P, vector<P>, greater<P>> pq;

int c1 = 0, c2 = 0;

while(++c1 <= X){

LL p = pPQ.top();

pPQ.pop();

pq.push({p, 1});

}

while(++c2 <= Y){

LL q = qPQ.top();

qPQ.pop();

pq.push({q, 2});

}

// 3. 組み換え.

// pq の最小の美味しさのリンゴと r の最大の美味しさのリンゴを

// 比較して, 組み換え.

while(!pq.empty()){

// pq から取得.

P a1 = pq.top();

if(!r.empty()){

// r から取得.

LL a2 = r.top();

// リンゴ a1 が赤色の場合, リンゴ a2 の美味しさが大きい場合, 入れ替え.

if(a1.b == 1 && X > 0 && a1.a < a2){

pq.pop();

pq.push({a2, 3});

r.pop();

X--;

continue;

}

// リンゴ a1 が緑色の場合, リンゴ a2 の美味しさが大きい場合, 入れ替え.

if(a1.b == 2 && Y > 0 && a1.a < a2){

pq.pop();

pq.push({a2, 3});

r.pop();

Y--;

continue;

}

// 組み替え出来なかった場合.

pq.pop();

apple.push(a1.a);

}

// 4. 美味しさの集計.

LL ans = 0;

while(!apple.empty()){

LL a = apple.top();

apple.pop();

ans += a;

// printf("%lld\n", a);

}

// 5. 出力.

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

return 0;

}

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

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

[入力例]
2 2 2 2 2
8 6
9 1
2 1

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

[入力例]
2 2 4 4 4
11 12 13 14
21 22 23 24
1 2 3 4

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

[入力例]
1 1 1 1 1
1
1
1

[出力例]
2

[入力例]
12 25 18 30 27
190 657 115 37 909 270 639 985 960 10 353 560 380 347 408 573 665 700
266 917 630 119 229 764 70 197 617 685 48 142 502 220 41 805 350 686 648 537 686 343 773 121 293 162 775 80 285 450
927 209 230 853 619 401 774 743 124 216 296 620 575 690 890 8 129 274 419 636 225 396 532 167 175 626 71

[出力例]
25435

[入力例]
5 7 10 13 11
691238539 839775129 423518584 201289886 582985771 538396815 443879402 161017534 58062635 755432143
825073727 921590855 430912918 297069423 791855375 938244497 692856590 357476221 986992383 228340270 893857249 56370970 868214757
238113853 321266905 137943723 899165731 612611308 830868780 74999267 423085548 878409626 769495093 357911685

[出力例]
10443543202

[入力例]

1 2 2 2 1

2 4

5 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2 2 2 2

8 6

9 1

2 1

[出力例]

※AtCoderテストケースより

[入力例]

2 2 4 4 4

11 12 13 14

21 22 23 24

1 2 3 4

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1 1

[出力例]

[入力例]

12 25 18 30 27

190 657 115 37 909 270 639 985 960 10 353 560 380 347 408 573 665 700

266 917 630 119 229 764 70 197 617 685 48 142 502 220 41 805 350 686 648 537 686 343 773 121 293 162 775 80 285 450

927 209 230 853 619 401 774 743 124 216 296 620 575 690 890 8 129 274 419 636 225 396 532 167 175 626 71

[出力例]

25435

[入力例]

5 7 10 13 11

691238539 839775129 423518584 201289886 582985771 538396815 443879402 161017534 58062635 755432143

825073727 921590855 430912918 297069423 791855375 938244497 692856590 357476221 986992383 228340270 893857249 56370970 868214757

238113853 321266905 137943723 899165731 612611308 830868780 74999267 423085548 878409626 769495093 357911685

[出力例]

10443543202

■参照サイト
AtCoder Beginner Contest 160

2020年3月30日2020年3月30日

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

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

■感想.
1. 解答見る前に, AC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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 g[2020][2020];
int ans[2020];

int main(){
    
    // 1. 入力情報.
    int N, X, Y;
    scanf("%d %d %d", &N, &X, &Y);
    
    // 2. 最短距離を保存(頂点 i -> 頂点 j).
    repx(i, 1, N + 1){
        repx(j, i + 1, N + 1){
            g[i][j] = min(j - i, abs(X - i) + abs(Y - j) + 1);
        }
    }
    
    // 3. 最短距離 k を 集計.
    repx(i, 1, N + 1) repx(j, i + 1, N + 1) ans[g[i][j]]++;
    
    // 4. 出力.
    repx(k, 1, N) printf("%d\n", ans[k]);
    return 0;
    
}

#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 g[2020][2020];

int ans[2020];

int main(){

// 1. 入力情報.

int N, X, Y;

scanf("%d %d %d", &N, &X, &Y);

// 2. 最短距離を保存(頂点 i -> 頂点 j).

repx(i, 1, N + 1){

repx(j, i + 1, N + 1){

g[i][j] = min(j - i, abs(X - i) + abs(Y - j) + 1);

}

// 3. 最短距離 k を集計.

repx(i, 1, N + 1) repx(j, i + 1, N + 1) ans[g[i][j]]++;

// 4. 出力.

repx(k, 1, N) printf("%d\n", ans[k]);

return 0;

}

[入力例]
5 2 4

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

[入力例]
3 1 3

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

[入力例]
7 3 7

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

[入力例]
10 4 8

[出力例]
10
12
10
8
4
1
0
0
0
※AtCoderテストケースより

[入力例]
25 6 11

[出力例]
25
27
27
25
24
23
21
18
16
15
14
13
12
11
10
8
5
3
2
1
0
0
0
0

[入力例]

5 2 4

[出力例]

※AtCoderテストケースより

[入力例]

3 1 3

[出力例]

※AtCoderテストケースより

[入力例]

7 3 7

[出力例]

※AtCoderテストケースより

[入力例]

10 4 8

[出力例]

※AtCoderテストケースより

[入力例]

25 6 11

[出力例]

■参照サイト
AtCoder Beginner Contest 160

2020年3月29日

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

C++の練習を兼ねて, AtCoder Beginner Contest 159 の問題E (E – Dividing Chocolate) を解いてみた.

■感想.
1. 解答を見る前にAC版となったものの, 実装に苦労した.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

#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 pb push_back
#define all(x) x.begin(), x.end()
string board[11];
int CUM[11][1010];

int main(){
    
    // 1. 入力情報.
    int H, W, K;
    scanf("%d %d %d", &H, &W, &K);
    rep(i, H){
        char c[1010];
        scanf("%s", c);
        string s(c);
        board[i] = s;
    }
    
    // 2. ホワイトチョコレートについて, 二次元累積和を保存.
    repx(i, 1, H + 1){
        repx(j, 1, W + 1){
            CUM[i][j] = (board[i - 1][j - 1] - '0') + CUM[i - 1][j] + CUM[i][j - 1] - CUM[i - 1][j - 1];
        }
    }
    
    // 3. 分割に必要な操作の回数をチェック.
    int ans = 2020;
    rep(i, 1 << (H - 1)){
        // チェック対象の行数を保存.
        vector<int> row, col;
        row.pb(0);
        row.pb(H);
        rep(j, H - 1) if((i >> j) & 1) row.pb(H - 1 - j);
        sort(all(row));
        // printf("--- row start i=%d ---\n", i);
        // for(auto &p : row) printf("%d ", p);
        // puts("\n--- row end ---");
        
        // 列方向にチェック.
        int s = 0, e = 0;
        priority_queue<int> pq;
        while(e < W){
            bool ok = true;
            int white = 0;
            while(ok && e < W){
                e++;
                rep(j, row.size() - 1){
                    // 各ブロックのホワイトチョコレートの個数を確認.
                    white = CUM[row[j + 1]][e] - CUM[row[j]][e] - CUM[row[j + 1]][s] + CUM[row[j]][s];
                    // printf("i=%d s=%d e=%d white=%d\n", i, s, e, white);
                    if(white > K){
                        ok = false;
                        break;
                    }
                }
            }
            
            // 各ブロックのホワイトチョコレートの個数を詰め直し.
            if(white > K){
                rep(j, row.size() - 1){
                    pq.push(CUM[row[j + 1]][e - 1] - CUM[row[j]][e - 1] - CUM[row[j + 1]][s] + CUM[row[j]][s]);
                }
                col.pb(e - 1), s = e - 1;
            }else{
                rep(j, row.size() - 1){
                    pq.push(CUM[row[j + 1]][e] - CUM[row[j]][e] - CUM[row[j + 1]][s] + CUM[row[j]][s]);
                }
                col.pb(e), s = e;
            }
            // printf("s=%d e=%d white=%d\n", s, e, white);
        }
        // printf("--- col i=%d ---\n", i);
        // for(auto &p : col) printf("%d ", p);
        // puts("\n--- col end ---");
        
        // 必要な操作数を更新.
        int rCount = row.size(), cCount = col.size();
        if(row.front() == 0) rCount--;
        if(row.back()  == H) rCount--;
        if(col.back()  == W) cCount--;
        if(pq.top() <= K) ans = min(ans, rCount + cCount);
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

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

string board[11];

int CUM[11][1010];

int main(){

// 1. 入力情報.

int H, W, K;

scanf("%d %d %d", &H, &W, &K);

rep(i, H){

char c[1010];

scanf("%s", c);

string s(c);

board[i] = s;

}

// 2. ホワイトチョコレートについて, 二次元累積和を保存.

repx(i, 1, H + 1){

repx(j, 1, W + 1){

CUM[i][j] = (board[i - 1][j - 1] - '0') + CUM[i - 1][j] + CUM[i][j - 1] - CUM[i - 1][j - 1];

}

// 3. 分割に必要な操作の回数をチェック.

int ans = 2020;

rep(i, 1 << (H - 1)){

// チェック対象の行数を保存.

vector<int> row, col;

row.pb(0);

row.pb(H);

rep(j, H - 1) if((i >> j) & 1) row.pb(H - 1 - j);

sort(all(row));

// printf("--- row start i=%d ---\n", i);

// for(auto &p : row) printf("%d ", p);

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

// 列方向にチェック.

int s = 0, e = 0;

priority_queue<int> pq;

while(e < W){

bool ok = true;

int white = 0;

while(ok && e < W){

e++;

rep(j, row.size() - 1){

// 各ブロックのホワイトチョコレートの個数を確認.

white = CUM[row[j + 1]][e] - CUM[row[j]][e] - CUM[row[j + 1]][s] + CUM[row[j]][s];

// printf("i=%d s=%d e=%d white=%d\n", i, s, e, white);

if(white > K){

ok = false;

break;

}

// 各ブロックのホワイトチョコレートの個数を詰め直し.

if(white > K){

rep(j, row.size() - 1){

pq.push(CUM[row[j + 1]][e - 1] - CUM[row[j]][e - 1] - CUM[row[j + 1]][s] + CUM[row[j]][s]);

}

col.pb(e - 1), s = e - 1;

}else{

rep(j, row.size() - 1){

pq.push(CUM[row[j + 1]][e] - CUM[row[j]][e] - CUM[row[j + 1]][s] + CUM[row[j]][s]);

}

col.pb(e), s = e;

}

// printf("s=%d e=%d white=%d\n", s, e, white);

}

// printf("--- col i=%d ---\n", i);

// for(auto &p : col) printf("%d ", p);

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

// 必要な操作数を更新.

int rCount = row.size(), cCount = col.size();

if(row.front() == 0) rCount--;

if(row.back() == H) rCount--;

if(col.back() == W) cCount--;

if(pq.top() <= K) ans = min(ans, rCount + cCount);

}

// 4. 出力.

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

return 0;

}

[入力例]
3 5 4
11100
10001
00111

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

[入力例]
3 5 8
11100
10001
00111

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

[入力例]
4 10 4
1110010010
1000101110
0011101001
1101000111

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

[入力例]
2 575 2
10100001001101111000100111111000010101011110011000010101010001001011000111100111111101000110000011110110100111000100101110110010110000101100111001110101111110101000101111001001100001000100100111010010011100001001101010110011000000101111011011001000100111100101100101011001000110010101100100001010101010110000101110110101110100001010110001100010101100001000101110010011010110110110001000111111110001010111101101001010111101101100001110011000110010010011100100011111000001100000101111110111110110011100111000001111001111100101010000000111100011011110001110001100100010010000010
10010101110000010011010100000100001100000101011111100110110010011010101001000001111101111101111100001111110101100000011100011100101001000000101010001000011001010101111001000011001010110111011011111011100111011101000110011110010000010110000101001110111011100010001111000010111011100111110010000000011101100100000110000100110110101101011001101110101101101011101001010000100001100101000001010010101011000101100000111100001010101100010000000000001010101100011100011000110110101110001100111100111001001000010110011110010100110111110111100101001101111111110011100001000010011111110

[出力例(random_01)]
175
※AtCoderテストケースより

[入力例]
3 5 1
11111
11111
11111

[出力例]
6

[入力例]
10 50 11
01010000010000010011111110100011001111010110000100
11001000000001111010001011110111111100011000110110
00001111001010000110100100101000100001110110011011
01010011111110100110001011000011111000110000000001
00000111000011101000110011100101110101000101010011
11101001101100010100001000010111111110001110011100
01111000111110100010001101011111110010111100001001
00101110100100100110110110100010011111010100111010
01100001101010110001000111000011110001000001001100
11111010111111110101101101011001001001010110110101

[出力例]
9

[入力例]

3 5 4

11100

10001

00111

[出力例]

※AtCoderテストケースより

[入力例]

3 5 8

11100

10001

00111

[出力例]

※AtCoderテストケースより

[入力例]

4 10 4

1110010010

1000101110

0011101001

1101000111

[出力例]

※AtCoderテストケースより

[入力例]

2 575 2

10100001001101111000100111111000010101011110011000010101010001001011000111100111111101000110000011110110100111000100101110110010110000101100111001110101111110101000101111001001100001000100100111010010011100001001101010110011000000101111011011001000100111100101100101011001000110010101100100001010101010110000101110110101110100001010110001100010101100001000101110010011010110110110001000111111110001010111101101001010111101101100001110011000110010010011100100011111000001100000101111110111110110011100111000001111001111100101010000000111100011011110001110001100100010010000010

10010101110000010011010100000100001100000101011111100110110010011010101001000001111101111101111100001111110101100000011100011100101001000000101010001000011001010101111001000011001010110111011011111011100111011101000110011110010000010110000101001110111011100010001111000010111011100111110010000000011101100100000110000100110110101101011001101110101101101011101001010000100001100101000001010010101011000101100000111100001010101100010000000000001010101100011100011000110110101110001100111100111001001000010110011110010100110111110111100101001101111111110011100001000010011111110

[出力例(random_01)]

175

※AtCoderテストケースより

[入力例]

3 5 1

11111

[出力例]

[入力例]

10 50 11

01010000010000010011111110100011001111010110000100

11001000000001111010001011110111111100011000110110

00001111001010000110100100101000100001110110011011

01010011111110100110001011000011111000110000000001

00000111000011101000110011100101110101000101010011

11101001101100010100001000010111111110001110011100

01111000111110100010001101011111110010111100001001

00101110100100100110110110100010011111010100111010

01100001101010110001000111000011110001000001001100

11111010111111110101101101011001001001010110110101

[出力例]

■参照サイト
AtCoder Beginner Contest 159
AtCoder Beginner Contest 159 (E)

2020年3月29日

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

C++の練習を兼ねて, AtCoder Regular Contest 007 の問題C (C – 節約生活) を解いてみた.

■感想.
1. 個人的には, 非常に面白い問題と感じた.
2. 但し, TLE版(2103[ms]) を AC版(1546[ms]) に持っていくための実装に, 非常に苦労した.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
int ox[11][111];

int main(){
    
    // 1. 入力情報.
    char c[22];
    scanf("%s", c);
    string s(c);
    
    // 2. 入寮情報を, 0, 1 に 変換.
    int l = s.size();
    rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;
    // rep(i, 111) printf("%d", ox[0][i]);
    // puts("");
    
    // 3. 'o' の 数が, l と 同じならば, 終了.
    // ex.
    // ooo
    // -> 1 が 正解のはず.
    // -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を 回避できた.
    int oCount = 0;
    rep(i, l) if(s[i] == 'o') oCount++;
    if(l == oCount){
        puts("1");
        return 0;
    }
    
    // 4. 'o' の 数が, 1個ならば, 終了.
    // ex.
    // xxxxxxxxxo
    // -> 10 が 正解のはず.
    // -> TLE防止のため(7563[ms]).
    if(1 == oCount){
        printf("%d\n", l);
        return 0;
    }
    
    // 5. 視聴パターンをチェック.
    // 02_maxrand_04.txt を AC にするには？
    // ex.
    // xxxxxxoxxo
    // -> 5 が 正解.
    // 
    // [配置例]
    // xxxxxxoxxoxxxxxxoxxo
    //   xxxxxxoxxoxxxxxxoxxo
    //     xxxxxxoxxoxxxxxxoxxo
    //       xxxxxxoxxoxxxxxxoxxo
    //         xxxxxxoxxoxxxxxxoxxo
    // -> 上記のような配置で, 5 を 実現できる.
    // 
    // ex.
    // xooxo
    // -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.
    // {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, 
    // {0, 2, 3}, {0, 2, 4}, 
    // {0, 3, 4}
    int ans = 1;
    repx(i, 1, l){
        // スタート地点を, (i + 1)箇所とする場合.
        vector<int> z(9);
        iota(all(z), 1);
        int mCount = 0;
        do{
            // for(auto &p : z) printf("%d ", p);
            // puts("");
            
            // 初期化.
            repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;
            
            // 視聴パターンを設定.
            repx(j, 1, i + 1) repx(k, z[j], 111) if(s[(k - z[j]) % l] == 'o') ox[j][k] = 1;
            
            // 視聴パターンチェック.
            // l ～ (2 * l - 1)番目 を チェック.
            int count = 0;
            repx(k, l, 2 * l){
                int a = 0;
                rep(i2, i + 1) a |= ox[i2][k];
                count += a;
            }
            
            // 最大値更新.
            if(mCount < count){
                mCount = count;
                ans = i + 1;
                // printf("----- start i=%d -----\n", i);
                // rep(x, i + 1){
                //     repx(y, l, 2 * l) printf("%d", ox[x][y]);
                //     puts("");
                // }
                // puts("----- end -----");
            }
        }while(next_permutation(all(z)));
        // mCount が l個以上ならば, 終了.
        if(mCount >= l) break;
    }
    
    // 6. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

int ox[11][111];

int main(){

// 1. 入力情報.

char c[22];

scanf("%s", c);

string s(c);

// 2. 入寮情報を, 0, 1 に変換.

int l = s.size();

rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;

// rep(i, 111) printf("%d", ox[0][i]);

// puts("");

// 3. 'o' の数が, l と同じならば, 終了.

// ex.

// ooo

// -> 1 が正解のはず.

// -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を回避できた.

int oCount = 0;

rep(i, l) if(s[i] == 'o') oCount++;

if(l == oCount){

puts("1");

return 0;

}

// 4. 'o' の数が, 1個ならば, 終了.

// ex.

// xxxxxxxxxo

// -> 10 が正解のはず.

// -> TLE防止のため(7563[ms]).

if(1 == oCount){

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

return 0;

}

// 5. 視聴パターンをチェック.

// 02_maxrand_04.txt を AC にするには？

// ex.

// xxxxxxoxxo

// -> 5 が正解.

// [配置例]

// xxxxxxoxxoxxxxxxoxxo

// -> 上記のような配置で, 5 を実現できる.

// ex.

// xooxo

// -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.

// {0, 1, 2}, {0, 1, 3}, {0, 1, 4},

// {0, 2, 3}, {0, 2, 4},

// {0, 3, 4}

int ans = 1;

repx(i, 1, l){

// スタート地点を, (i + 1)箇所とする場合.

vector<int> z(9);

iota(all(z), 1);

int mCount = 0;

do{

// for(auto &p : z) printf("%d ", p);

// puts("");

// 初期化.

repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;

// 視聴パターンを設定.

repx(j, 1, i + 1) repx(k, z[j], 111) if(s[(k - z[j]) % l] == 'o') ox[j][k] = 1;

// 視聴パターンチェック.

// l ～ (2 * l - 1)番目をチェック.

int count = 0;

repx(k, l, 2 * l){

int a = 0;

rep(i2, i + 1) a |= ox[i2][k];

count += a;

}

// 最大値更新.

if(mCount < count){

mCount = count;

ans = i + 1;

// printf("----- start i=%d -----\n", i);

// rep(x, i + 1){

// repx(y, l, 2 * l) printf("%d", ox[x][y]);

// puts("");

// }

// puts("----- end -----");

}

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

// mCount が l個以上ならば, 終了.

if(mCount >= l) break;

}

// 6. 出力.

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

return 0;

}

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

#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define all(x) x.begin(), x.end()
#define pb push_back
int ox[11][111];
set<set<int>> sSet[9];

int main(){
    
    // 1. 入力情報.
    char c[22];
    scanf("%s", c);
    string s(c);
    
    // 2. 入寮情報を, 0, 1 に 変換.
    int l = s.size();
    rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;
    // rep(i, 111) printf("%d", ox[0][i]);
    // puts("");
    
    // 3. 'o' の 数が, l と 同じならば, 終了.
    // ex.
    // ooo
    // -> 1 が 正解のはず.
    // -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を 回避できた.
    int oCount = 0;
    rep(i, l) if(s[i] == 'o') oCount++;
    if(l == oCount){
        puts("1");
        return 0;
    }
    
    // 4. 'o' の 数が, 1個ならば, 終了.
    // ex.
    // xxxxxxxxxo
    // -> 10 が 正解のはず.
    // -> TLE防止のため(7563[ms]).
    // if(1 == oCount){
    //     printf("%d\n", l);
    //     return 0;
    // }
    // -> 5. の 事前処理を追加したので, 廃止.
    
    // 5. 順列を保存.
    // 02_maxrand_16.txt で, TLE版(2103[ms]) と なったため, 事前計算してみる.
    vector<int> z(9);
    iota(all(z), 1);
    do{
        rep(i, 9){
            set<int> s;
            rep(j, i + 1) s.insert(z[j]);
            sSet[i].insert(s);
        }
    }while(next_permutation(all(z)));
    
    // rep(i, 9){
    //     for(auto &p : sSet[i]){
    //         for(auto &q : p) printf("%d ", q);
    //         puts("");
    //     }
    // }
    
    // 6. 視聴パターンをチェック.
    // 02_maxrand_04.txt を AC にするには？
    // ex.
    // xxxxxxoxxo
    // -> 5 が 正解.
    // 
    // [配置例]
    // xxxxxxoxxoxxxxxxoxxo
    //   xxxxxxoxxoxxxxxxoxxo
    //     xxxxxxoxxoxxxxxxoxxo
    //       xxxxxxoxxoxxxxxxoxxo
    //         xxxxxxoxxoxxxxxxoxxo
    // -> 上記のような配置で, 5 を 実現できる.
    // 
    // ex.
    // xooxo
    // -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.
    // {0, 1, 2}, {0, 1, 3}, {0, 1, 4}, 
    // {0, 2, 3}, {0, 2, 4}, 
    // {0, 3, 4}
    int ans = 1;
    repx(i, 1, l){
        // スタート地点を, (i + 1)箇所とする場合.
        int mCount = 0;
        for(auto &p : sSet[i - 1]){
            // 初期化.
            repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;
            
            // 視聴パターンを設定.
            int r = 0;
            for(auto &q : p){
                r++;
                repx(k, q, 111) if(s[(k - q) % l] == 'o') ox[r][k] = 1;
            }
            
            // 視聴パターンチェック.
            // l ～ (2 * l - 1)番目 を チェック.
            int count = 0;
            repx(k, l, 2 * l){
                int a = 0;
                rep(i2, i + 1) a |= ox[i2][k];
                count += a;
            }
            
            // 最大値更新.
            if(mCount < count){
                mCount = count;
                ans = i + 1;
                // printf("----- start i=%d -----\n", i);
                // rep(x, i + 1){
                //     repx(y, l, 2 * l) printf("%d", ox[x][y]);
                //     puts("");
                // }
                // puts("----- end -----");
            }
        }
        // mCount が l個以上ならば, 終了.
        if(mCount >= l) break;
    }
    
    // 7. 出力.
    printf("%d\n", ans);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

#include <bits/stdc++.h>

using namespace std;

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

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

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

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

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

#define pb push_back

int ox[11][111];

set<set<int>> sSet[9];

int main(){

// 1. 入力情報.

char c[22];

scanf("%s", c);

string s(c);

// 2. 入寮情報を, 0, 1 に変換.

int l = s.size();

rep(i, 111) if(s[i % l] == 'o') ox[0][i] = 1;

// rep(i, 111) printf("%d", ox[0][i]);

// puts("");

// 3. 'o' の数が, l と同じならば, 終了.

// ex.

// ooo

// -> 1 が正解のはず.

// -> このパターンを追加したことで, 01_rand_11.txt, 03_max.txt の WA を回避できた.

int oCount = 0;

rep(i, l) if(s[i] == 'o') oCount++;

if(l == oCount){

puts("1");

return 0;

}

// 4. 'o' の数が, 1個ならば, 終了.

// ex.

// xxxxxxxxxo

// -> 10 が正解のはず.

// -> TLE防止のため(7563[ms]).

// if(1 == oCount){

// printf("%d\n", l);

// return 0;

// }

// -> 5. の事前処理を追加したので, 廃止.

// 5. 順列を保存.

// 02_maxrand_16.txt で, TLE版(2103[ms]) となったため, 事前計算してみる.

vector<int> z(9);

iota(all(z), 1);

do{

rep(i, 9){

set<int> s;

rep(j, i + 1) s.insert(z[j]);

sSet[i].insert(s);

}

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

// rep(i, 9){

// for(auto &p : sSet[i]){

// for(auto &q : p) printf("%d ", q);

// puts("");

// }

// 6. 視聴パターンをチェック.

// 02_maxrand_04.txt を AC にするには？

// ex.

// xxxxxxoxxo

// -> 5 が正解.

// [配置例]

// xxxxxxoxxoxxxxxxoxxo

// -> 上記のような配置で, 5 を実現できる.

// ex.

// xooxo

// -> スタート地点を, 3箇所とする場合, 以下のパターンをチェック.

// {0, 1, 2}, {0, 1, 3}, {0, 1, 4},

// {0, 2, 3}, {0, 2, 4},

// {0, 3, 4}

int ans = 1;

repx(i, 1, l){

// スタート地点を, (i + 1)箇所とする場合.

int mCount = 0;

for(auto &p : sSet[i - 1]){

// 初期化.

repx(j, 1, i + 1) rep(k, 111) ox[j][k] = 0;

// 視聴パターンを設定.

int r = 0;

for(auto &q : p){

r++;

repx(k, q, 111) if(s[(k - q) % l] == 'o') ox[r][k] = 1;

}

// 視聴パターンチェック.

// l ～ (2 * l - 1)番目をチェック.

int count = 0;

repx(k, l, 2 * l){

int a = 0;

rep(i2, i + 1) a |= ox[i2][k];

count += a;

}

// 最大値更新.

if(mCount < count){

mCount = count;

ans = i + 1;

// printf("----- start i=%d -----\n", i);

// rep(x, i + 1){

// repx(y, l, 2 * l) printf("%d", ox[x][y]);

// puts("");

// }

// puts("----- end -----");

}

// mCount が l個以上ならば, 終了.

if(mCount >= l) break;

}

// 7. 出力.

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

return 0;

}

[入力例]
oxoxx

[出力例(debug版)]
----- start i=1 -----
10100
01010
----- end -----
----- start i=2 -----
10100
01010
00101
----- end -----
3
※AtCoderのテストケースより

[入力例]
oxxxxoooo

[出力例(debug版)]
----- start i=1 -----
100001111
110000111
----- end -----
----- start i=1 -----
100001111
111000011
----- end -----
----- start i=1 -----
100001111
111100001
----- end -----
----- start i=1 -----
100001111
111110000
----- end -----
2
※AtCoderのテストケースより

[入力例]
ox

[出力例(debug版)]
----- start i=1 -----
10
01
----- end -----
2
※AtCoderのテストケースより

[入力例]
o

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

[入力例]
xxxoxo

[出力例(debug版)]
----- start i=1 -----
000101
100010
----- end -----
----- start i=2 -----
000101
100010
010001
----- end -----
----- start i=3 -----
000101
100010
010001
101000
----- end -----
4
※AtCoderのテストケースより

[入力例]
oxoxxoooox

[出力例(debug版)]
----- start i=1 -----
1010011110
0101001111
----- end -----
----- start i=2 -----
1010011110
0101001111
1010100111
----- end -----
3

[入力例]
xxxxxxoxxo

[出力例(debug版)]
----- start i=1 -----
0000001001
1000000100
----- end -----
----- start i=2 -----
0000001001
1000000100
0100000010
----- end -----
----- start i=3 -----
0000001001
1000000100
0100000010
0010000001
----- end -----
----- start i=3 -----
0000001001
1000000100
0100000010
0010010000
----- end -----
----- start i=4 -----
0000001001
1000000100
0100000010
0010000001
1001000000
----- end -----
----- start i=4 -----
0000001001
1000000100
0100000010
1001000000
0010010000
----- end -----
----- start i=4 -----
0000001001
0100000010
1001000000
0010010000
0000100100
----- end -----
5

[入力例]
oxxxxxxxxx

[出力例(debug版)]
----- start i=1 -----
1000000000
0100000000
----- end -----
----- start i=2 -----
1000000000
0100000000
0010000000
----- end -----
----- start i=3 -----
1000000000
0100000000
0010000000
0001000000
----- end -----
----- start i=4 -----
1000000000
0100000000
0010000000
0001000000
0000100000
----- end -----
----- start i=5 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
----- end -----
----- start i=6 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
----- end -----
----- start i=7 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
----- end -----
----- start i=8 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
----- end -----
----- start i=9 -----
1000000000
0100000000
0010000000
0001000000
0000100000
0000010000
0000001000
0000000100
0000000010
0000000001
----- end -----
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

[入力例]

oxoxx

[出力例(debug版)]

----- start i=1 -----

10100

01010

----- end -----

----- start i=2 -----

10100

01010

00101

----- end -----

※AtCoderのテストケースより

[入力例]

oxxxxoooo

[出力例(debug版)]

----- start i=1 -----

100001111

110000111

----- end -----

----- start i=1 -----

100001111

111000011

----- end -----

----- start i=1 -----

100001111

111100001

----- end -----

----- start i=1 -----

100001111

111110000

----- end -----

※AtCoderのテストケースより

[入力例]

[出力例(debug版)]

----- start i=1 -----

----- end -----

※AtCoderのテストケースより

[入力例]

[出力例(debug版)]

※AtCoderのテストケースより

[入力例]

xxxoxo

[出力例(debug版)]

----- start i=1 -----

000101

100010

----- end -----

----- start i=2 -----

000101

100010

010001

----- end -----

----- start i=3 -----

000101

100010

010001

101000

----- end -----

※AtCoderのテストケースより

[入力例]

oxoxxoooox

[出力例(debug版)]

----- start i=1 -----

1010011110

0101001111

----- end -----

----- start i=2 -----

1010011110

0101001111

1010100111

----- end -----

[入力例]

xxxxxxoxxo

[出力例(debug版)]

----- start i=1 -----

0000001001

1000000100

----- end -----

----- start i=2 -----

0000001001

1000000100

0100000010

----- end -----

----- start i=3 -----

0000001001

1000000100

0100000010

0010000001

----- end -----

----- start i=3 -----

0000001001

1000000100

0100000010

0010010000

----- end -----

----- start i=4 -----

0000001001

1000000100

0100000010

0010000001

1001000000

----- end -----

----- start i=4 -----

0000001001

1000000100

0100000010

1001000000

0010010000

----- end -----

----- start i=4 -----

0000001001

0100000010

1001000000

0010010000

0000100100

----- end -----

[入力例]

oxxxxxxxxx

[出力例(debug版)]

----- start i=1 -----

1000000000

0100000000

----- end -----

----- start i=2 -----

1000000000

0100000000

0010000000

----- end -----

----- start i=3 -----

1000000000

0100000000

0010000000

0001000000

----- end -----

----- start i=4 -----

1000000000

0100000000

0010000000

0001000000

0000100000

----- end -----

----- start i=5 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

----- end -----

----- start i=6 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

----- end -----

----- start i=7 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

0000000100

----- end -----

----- start i=8 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

0000000100

0000000010

----- end -----

----- start i=9 -----

1000000000

0100000000

0010000000

0001000000

0000100000

0000010000

0000001000

0000000100

0000000010

0000000001

----- end -----

■参照サイト
AtCoder Regular Contest 007

2020年3月28日2020年3月28日

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

C++の練習を兼ねて, AtCoder Regular Contest 010 の問題A (A – 名刺交換) ～問題B (B – 超大型連休) を解いてみた.

■感想.
1. 問題A は, 名刺の残数が, 0 になる日が, 途中で, 何回有っても OK である点が面白いと感じた.
2. 問題B は, 12月31日時点で, 大型連休が継続中であるかを考える必要がある点が面白いと感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#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, M, A, B;
    scanf("%d %d %d %d", &N, &M, &A, &B);
    
    // 2. 名刺が足りなくなる場合があるか？
    int ans = 0, c;
    rep(i, M){
        scanf("%d", &c);
        if(N <= A) N += B;
        N -= c;
        if(N < 0){
            ans = i + 1;
            break;
        }
    }
    
    // 3. 出力.
    if(ans) printf("%d\n", ans);
    else    puts("complete");
    return 0;
    
}

#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, M, A, B;

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

// 2. 名刺が足りなくなる場合があるか？

int ans = 0, c;

rep(i, M){

scanf("%d", &c);

if(N <= A) N += B;

N -= c;

if(N < 0){

ans = i + 1;

break;

}

// 3. 出力.

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

else puts("complete");

return 0;

}

[入力例]
100 3 0 100
10
20
30

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

[入力例]
100 4 0 100
10
20
30
40

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

[入力例]
100 4 0 100
50
40
30
20

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

[入力例]
100 4 10 100
50
40
30
20

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

[入力例]
5 3 20 10
15
5
20

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

[入力例]
12 7 30 23
15
5
38
17
30
7
22

[出力例]
5

[入力例]
12 7 30 23
15
5
38
17
29
7
39

[出力例]
complete

[入力例]

100 3 0 100

[出力例]

complete

※AtCoderのテストケースより

[入力例]

100 4 0 100

[出力例]

complete

※AtCoderのテストケースより

[入力例]

100 4 0 100

[出力例]

※AtCoderのテストケースより

[入力例]

100 4 10 100

[出力例]

complete

※AtCoderのテストケースより

[入力例]

5 3 20 10

[出力例]

※AtCoderのテストケースより

[入力例]

12 7 30 23

[出力例]

[入力例]

12 7 30 23

[出力例]

complete

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

#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 days[999];
int past[] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};

// m/d の 情報を, 経過日数に変換.
// @param md: 月, 日.
// @return: 経過日数.
int toDay(string md){
    // '/' で 分割.
    int pos = md.find("/");
    string sm = md.substr(0, pos);
    string sd = md.substr(pos + 1);
    
    // 前月分までの経過日数.
    int im = stoi(sm), id = stoi(sd);
    int m = past[im - 1];
    
    // 今月分の経過日数を加算.
    int ret = m + id;
    
    // 返却.
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 土日を確定.
    repx(i, 1, 367){
        if(i % 7 == 0) days[i]++; // 土曜日.
        if(i % 7 == 1) days[i]++; // 日曜日.
    }
    
    // 3. 祝日 or 振替休日.
    rep(i, N){
        char c[111];
        scanf("%s", c);
        string sh(c);
        int ih = toDay(sh); // 祝日.
        // 祝日が土日ならば, 平日に移動.
        while(days[ih]) ih++;
        days[ih]++;
    }
    
    // 4. 連休の最大値.
    int ans = 0, s = 0, e = 0;
    repx(i, 1, 367){
        if(days[i]){
            if(s == 0) s = i, e = s + 1;
            else       e++;
        }else{
            ans = max(ans, e - s);
            s = 0, e = 0;
        }
    }
    ans = max(ans, e - s); // 12/31 時点で, 大型連休が継続中だった場合.
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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 days[999];

int past[] = {0, 31, 60, 91, 121, 152, 182, 213, 244, 274, 305, 335};

// m/d の情報を, 経過日数に変換.

// @param md: 月, 日.

// @return: 経過日数.

int toDay(string md){

// '/' で分割.

int pos = md.find("/");

string sm = md.substr(0, pos);

string sd = md.substr(pos + 1);

// 前月分までの経過日数.

int im = stoi(sm), id = stoi(sd);

int m = past[im - 1];

// 今月分の経過日数を加算.

int ret = m + id;

// 返却.

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 土日を確定.

repx(i, 1, 367){

if(i % 7 == 0) days[i]++; // 土曜日.

if(i % 7 == 1) days[i]++; // 日曜日.

}

// 3. 祝日 or 振替休日.

rep(i, N){

char c[111];

scanf("%s", c);

string sh(c);

int ih = toDay(sh); // 祝日.

// 祝日が土日ならば, 平日に移動.

while(days[ih]) ih++;

days[ih]++;

}

// 4. 連休の最大値.

int ans = 0, s = 0, e = 0;

repx(i, 1, 367){

if(days[i]){

if(s == 0) s = i, e = s + 1;

else e++;

}else{

ans = max(ans, e - s);

s = 0, e = 0;

}

ans = max(ans, e - s); // 12/31 時点で, 大型連休が継続中だった場合.

// 5. 出力.

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

return 0;

}

[入力例]
1
1/9

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

[入力例]
1
1/10

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

[入力例]
1
1/7

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

[入力例]
2
1/7
1/9

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

[入力例]
12
4/30
5/1
5/2
5/3
5/4
7/14
7/20
7/16
7/15
7/18
7/23
12/24

[出力例]
10

[入力例]
12
12/31
12/30
12/25
12/26
12/23
12/24
12/28
12/29
12/20
12/19
12/27
12/21

[出力例]
13

[入力例]

1/9

[出力例]

※AtCoderのテストケースより

[入力例]

1/10

[出力例]

※AtCoderのテストケースより

[入力例]

1/7

[出力例]

※AtCoderのテストケースより

[入力例]

1/7

1/9

[出力例]

※AtCoderのテストケースより

[入力例]

4/30

5/1

5/2

5/3

5/4

7/14

7/20

7/16

7/15

7/18

7/23

12/24

[出力例]

[入力例]

12/31

12/30

12/25

12/26

12/23

12/24

12/28

12/29

12/20

12/19

12/27

12/21

[出力例]

■参照サイト
AtCoder Regular Contest 010

2020年3月26日

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

C++の練習を兼ねて, AtCoder Regular Contest 009 の問題A (A – 元気にお使い！高橋君) ～問題B (B – おとぎの国の高橋君) を解いてみた.

■感想.
1. 問題B は, 数字の大小関係が変わる点が面白いと感じた.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

#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;
    scanf("%d", &N);
    
    // 2. おつかいに必要な金額を計算(消費税前).
    int ans = 0, a, b;
    rep(i, N){
        scanf("%d %d", &a, &b);
        ans += a * b;
    }
    
    // 3. 消費税加算.
    ans *= 105;
    ans /= 100;
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

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

scanf("%d", &N);

// 2. おつかいに必要な金額を計算(消費税前).

int ans = 0, a, b;

rep(i, N){

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

ans += a * b;

}

// 3. 消費税加算.

ans *= 105;

ans /= 100;

// 4. 出力.

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

return 0;

}

[入力例]
2
4 120
2 130

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

[入力例]
1
1 100

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

[入力例]
4
3 510
1 835
2 140
6 205

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

[入力例]
10
8 10
7 189
4 545
1 596
3 209
10 850
9 943
6 921
8 984
10 702

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

[入力例]

4 120

2 130

[出力例]

777

※AtCoderのテストケースより

[入力例]

1 100

[出力例]

105

※AtCoderのテストケースより

[入力例]

3 510

1 835

2 140

6 205

[出力例]

4068

※AtCoderのテストケースより

[入力例]

8 10

7 189

4 545

1 596

3 209

10 850

9 943

6 921

8 984

10 702

[出力例]

44321

※AtCoderのテストケースより

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

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, 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 all(x) x.begin(), x.end()
#define pb push_back
#define a first
#define b second

int main(){
    
    // 1. 入力情報.
    int N, b, rank[10];
    rep(i, 10){
        scanf("%d", &b);
        rank[b] = i;
    }
    vector<P> v;
    scanf("%d", &N);
    rep(i, N){
        char a[22];
        scanf("%s", a);
        string S(a), T(a);
        
        // AtCoder国の大小関係を満たす数字に変換.
        int sl = S.size();
        rep(j, sl) S[j] = rank[S[j] - '0'] + '0';
        
        // 二種類の数字を保管.
        v.pb({stoi(S), stoi(T)});
    }
    
    // 2. sort.
    sort(all(v));
    
    // 3. 出力.
    for(auto &p : v) printf("%d\n", p.b);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

using P = pair<int, 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 all(x) x.begin(), x.end()

#define pb push_back

#define a first

#define b second

int main(){

// 1. 入力情報.

int N, b, rank[10];

rep(i, 10){

scanf("%d", &b);

rank[b] = i;

}

vector<P> v;

scanf("%d", &N);

rep(i, N){

char a[22];

scanf("%s", a);

string S(a), T(a);

// AtCoder国の大小関係を満たす数字に変換.

int sl = S.size();

rep(j, sl) S[j] = rank[S[j] - '0'] + '0';

// 二種類の数字を保管.

v.pb({stoi(S), stoi(T)});

}

// 2. sort.

sort(all(v));

// 3. 出力.

for(auto &p : v) printf("%d\n", p.b);

return 0;

}

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

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

[入力例]
0 9 8 7 6 5 4 3 2 1
3
13467932
98738462
74392

[出力例]
74392
98738462
13467932
※AtCoderのテストケースより

[入力例]
0 1 2 3 4 5 6 7 8 9
4
643
1234
43
909

[出力例]
43
643
909
1234
※AtCoderのテストケースより

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

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

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

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

[入力例]
3 1 4 5 9 2 6 8 7 0
52
314159265
35897932
3846264
338327950
288419
71693
993751058
20974944
5923078
164062
86208
998
62
803
48253
421170
6
7
98
21480
8651
328230664
709384460
9550
582231
725359
408
128481117
45028410
2
701938
5211055
596446229
48954
930
381964428
810
9756659
33446128
475648
233786
783165
27120
1909145
648566923
460348610
45432
664821
3393607
260249
1412
737

[出力例]
2
6
7
98
62
408
930
998
810
803
737
1412
9550
8651
45432
48954
48253
3393607
21480
27120
86208
71693
164062
33446128
421170
475648
582231
233786
260249
288419
664821
3846264
725359
783165
701938
1909145
5923078
5211055
35897932
9756659
338327950
314159265
45028410
328230664
20974944
381964428
128481117
460348610
596446229
993751058
648566923
709384460

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

[入力例]

0 8 1 3 5 4 9 7 6 2

[出力例]

※AtCoderのテストケースより

[入力例]

0 9 8 7 6 5 4 3 2 1

13467932

98738462

74392

[出力例]

74392

98738462

13467932

※AtCoderのテストケースより

[入力例]

0 1 2 3 4 5 6 7 8 9

643

1234

909

[出力例]

643

909

1234

※AtCoderのテストケースより

[入力例]

0 7 4 3 9 5 6 2 1 8

333

[出力例]

333

※AtCoderのテストケースより

[入力例]

0 2 4 6 8 1 3 5 7 9

[出力例]

※AtCoderのテストケースより

[入力例]

3 1 4 5 9 2 6 8 7 0

314159265

35897932

3846264

338327950

288419

71693

993751058

20974944

5923078

164062

86208

998

803

48253

421170

21480

8651

328230664

709384460

9550

582231

725359

408

128481117

45028410

701938

5211055

596446229

48954

930

381964428

810

9756659

33446128

475648

233786

783165

27120

1909145

648566923

460348610

45432

664821

3393607

260249

1412

737

[出力例]

408

930

998

810

803

737

1412

9550

8651

45432

48954

48253

3393607

21480

27120

86208

71693

164062

33446128

421170

475648

582231

233786

260249

288419

664821

3846264

725359

783165

701938

1909145

5923078

5211055

35897932

9756659

338327950

314159265

45028410

328230664

20974944

381964428

128481117

460348610

596446229

993751058

648566923

709384460

■参照サイト
AtCoder Regular Contest 009

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

C++の練習を兼ねて, AtCoder Regular Contest 017 の 問題A (A – 素数、コンテスト、素数) ～ 問題B (B – 解像度が低い。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 012 の 問題A (A – 週末) ～ 問題B (B – アキレスと亀) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 011 の 問題A (A – 鉛筆リサイクルの新技術) ～ 問題B (B – ルイス・キャロルの記憶術) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 160 の 問題E (E – Red and Green Apples) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 159 の 問題E (E – Dividing Chocolate) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 007 の 問題C (C – 節約生活) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 010 の 問題A (A – 名刺交換) ～ 問題B (B – 超大型連休) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 009 の 問題A (A – 元気にお使い！高橋君) ～ 問題B (B – おとぎの国の高橋君) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 017 の問題A (A – 素数、コンテスト、素数) ～問題B (B – 解像度が低い。) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 012 の問題A (A – 週末) ～問題B (B – アキレスと亀) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 011 の問題A (A – 鉛筆リサイクルの新技術) ～問題B (B – ルイス・キャロルの記憶術) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 160 の問題E (E – Red and Green Apples) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 159 の問題E (E – Dividing Chocolate) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 007 の問題C (C – 節約生活) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 010 の問題A (A – 名刺交換) ～問題B (B – 超大型連休) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 009 の問題A (A – 元気にお使い！高橋君) ～問題B (B – おとぎの国の高橋君) を解いてみた.