1月, 2019 | 個人用メモ帳

2019年1月27日2019年1月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 084 の問題C（Special Trains) ～問題D (2017-like Number) を解いてみた.

■感想.
1. 問題C は, いったん解いてみたが, ロジックのバグを直すことが出来なかったため, 解答を参照して, 復習した.
2. 問題D は, いったん解いて, TLE版まで持ってこれたので, 2017に似た数のテーブルを持たせたりして, 計算量を減らすように修正したところ, AC版に到達出来た.

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

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

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

struct train {
    int c;  // 駅間にかかる列車時間(秒).
    int s;  // 開通式開始後(秒).
    int f;  // 列車の発車頻度(秒).
};

// 駅(start + 1) ～ 駅N までの 開通式開始秒後を計算.
// @param start: 駅番号 - 1.
// @param N: 駅情報のサイズ.
// @param v: 駅情報.
// @return : 計算結果.
int getTrainTime(int start, int N, vector<train> v){

    int buf[N] = {};
    FOR(i, start, N - 1){
        if(i == start) {
            buf[i + 1] = v[i].s + v[i].c;
            continue;
        }
        buf[i + 1] += buf[i];
        buf[i + 1] += v[i].c;
        int dt = buf[i] - v[i].s;
        cout << dt << endl;
        if(dt >= 0) buf[i + 1] += (dt % v[i].f);
        else        buf[i + 1] += (-dt);
    }
    return buf[N - 1];

}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<train> v;
    FOR(i, 0, N - 1) {
        train t;
        cin >> t.c >> t.s >> t.f;
        v.push_back(t);
    }

    // 2. 各駅 ～ 駅N の 開通式開始秒後を計算.
    int ans[N] = {};
    FOR(i, 0, N - 1) ans[i] = getTrainTime(i, N, v);
    
    // 3. 出力 ～ 後処理.
    FOR(i, 0, N) cout << ans[i] << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

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

struct train {

int c; // 駅間にかかる列車時間(秒).

int s; // 開通式開始後(秒).

int f; // 列車の発車頻度(秒).

};

// 駅(start + 1) ～駅N までの開通式開始秒後を計算.

// @param start: 駅番号 - 1.

// @param N: 駅情報のサイズ.

// @param v: 駅情報.

// @return : 計算結果.

int getTrainTime(int start, int N, vector<train> v){

int buf[N] = {};

FOR(i, start, N - 1){

if(i == start) {

buf[i + 1] = v[i].s + v[i].c;

continue;

}

buf[i + 1] += buf[i];

buf[i + 1] += v[i].c;

int dt = buf[i] - v[i].s;

cout << dt << endl;

if(dt >= 0) buf[i + 1] += (dt % v[i].f);

else buf[i + 1] += (-dt);

}

return buf[N - 1];

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<train> v;

FOR(i, 0, N - 1) {

train t;

cin >> t.c >> t.s >> t.f;

v.push_back(t);

}

// 2. 各駅～駅N の開通式開始秒後を計算.

int ans[N] = {};

FOR(i, 0, N - 1) ans[i] = getTrainTime(i, N, v);

// 3. 出力～後処理.

FOR(i, 0, N) cout << ans[i] << endl;

return 0;

}

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

// 解き直し.
// ABC 084 解説.
// https://img.atcoder.jp/abc084/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

struct train {
    int c;  // 駅間にかかる列車時間(秒).
    int s;  // 開通式開始後(秒).
    int f;  // 列車の発車頻度(秒).
};

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<train> v;
    FOR(i, 0, N - 1) {
        train t;
        cin >> t.c >> t.s >> t.f;
        v.push_back(t);
    }

    // 2. 解説通り.
    int ans[N] = {};
    FOR(i, 0, N) {
        int t = 0;
        FOR(j, i, N - 1){
            train vj = v[j];
            if(t < vj.s) t = vj.s;
            else if(t % vj.f == 0);
            else t = t + vj.f - t % vj.f;
            t += vj.c;
        }
        cout << t << endl;
    }
    
    return 0;
    
}

// 解き直し.

// ABC 084 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

struct train {

int c; // 駅間にかかる列車時間(秒).

int s; // 開通式開始後(秒).

int f; // 列車の発車頻度(秒).

};

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<train> v;

FOR(i, 0, N - 1) {

train t;

cin >> t.c >> t.s >> t.f;

v.push_back(t);

}

// 2. 解説通り.

int ans[N] = {};

FOR(i, 0, N) {

int t = 0;

FOR(j, i, N - 1){

train vj = v[j];

if(t < vj.s) t = vj.s;

else if(t % vj.f == 0);

else t = t + vj.f - t % vj.f;

t += vj.c;

}

cout << t << endl;

}

return 0;

}

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

// TLE版(01.txt - 07.txt).
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORN(i, a, b, n) for(int i = (a); i < (b); i += n)

// 2017に似た数であるかの判定.
// @param m: 素数マップ.
// @param n: 与えられた奇数.
// @return: 2017に似た数 … true, そうでない場合 … false.
bool is2017Like(map<int, int> m, int n){
    int x = (n + 1) / 2;
    // cout << "n=" << n << " x=" << x << endl;
    if(m[n] == 1 && m[x] == 1) return true;
    else                       return false;
}

int main() {
    
    // 1. 入力情報取得.
    int Q;
    cin >> Q;
    int left[Q], right[Q];
    FOR(i, 0, Q) cin >> left[i] >> right[i];

    // 2. 素数を用意する.
    map<int, int> m;
    vector<int> v;
    m[2]++;
    v.push_back(2);
    FORN(i, 3, 100002, 2) {
        bool isPrime = true;
        FORN(j, 3, sqrt(i) + 1, 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) m[i]++, v.push_back(i);
    }
    
    // 3. 2017に似た数の個数を計算.
    FOR(i, 0, Q){
        // 3-1. 各変数初期化.
        int l = left[i];
        int r = right[i];
        int like2017 = 0;
        
        // 3-2. l ～ r で, 2017に似た数の個数をカウント.
        FORN(j, l, r + 1, 2) if(j % 2 == 1 && j >= l && j <= r && is2017Like(m, j)) like2017++;
        
        // 3-3. 出力.
        cout << like2017 << endl;
    }
    
    return 0;

}

// TLE版(01.txt - 07.txt).

#include <bits/stdc++.h>

using namespace std;

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

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

// 2017に似た数であるかの判定.

// @param m: 素数マップ.

// @param n: 与えられた奇数.

// @return: 2017に似た数 … true, そうでない場合 … false.

bool is2017Like(map<int, int> m, int n){

int x = (n + 1) / 2;

// cout << "n=" << n << " x=" << x << endl;

if(m[n] == 1 && m[x] == 1) return true;

else return false;

}

int main() {

// 1. 入力情報取得.

int Q;

cin >> Q;

int left[Q], right[Q];

FOR(i, 0, Q) cin >> left[i] >> right[i];

// 2. 素数を用意する.

map<int, int> m;

vector<int> v;

m[2]++;

v.push_back(2);

FORN(i, 3, 100002, 2) {

bool isPrime = true;

FORN(j, 3, sqrt(i) + 1, 2) {

if(i % j == 0){

isPrime = false;

break;

}

if(isPrime) m[i]++, v.push_back(i);

}

// 3. 2017に似た数の個数を計算.

FOR(i, 0, Q){

// 3-1. 各変数初期化.

int l = left[i];

int r = right[i];

int like2017 = 0;

// 3-2. l ～ r で, 2017に似た数の個数をカウント.

FORN(j, l, r + 1, 2) if(j % 2 == 1 && j >= l && j <= r && is2017Like(m, j)) like2017++;

// 3-3. 出力.

cout << like2017 << endl;

}

return 0;

}

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

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORN(i, a, b, n) for(int i = (a); i < (b); i += n)

int main() {
    
    // 1. 入力情報取得.
    int Q;
    cin >> Q;
    int left[Q], right[Q];
    FOR(i, 0, Q) cin >> left[i] >> right[i];

    // 2. 素数を用意する.
    map<int, int> m;
    vector<int> v;
    m[2]++;
    v.push_back(2);
    FORN(i, 3, 100002, 2) {
        bool isPrime = true;
        FORN(j, 3, sqrt(i) + 1, 2) {
            if(i % j == 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) m[i]++, v.push_back(i);
    }
    
    // 3. 2017に似た数を用意する.
    // ex. 3, 5, 13, 37, 61, 73, 157, 193, 277, 313
    vector<int> v2017;
    for(auto &p : v) {
        int x = (p + 1) / 2;
        if(m[x] == 1) v2017.push_back(p);
    }
    // FOR(i, 0, 10) cout << v2017[i] << endl;
    
    // 4. 2017に似た数の個数を計算.
    FOR(i, 0, Q){
        // 4-1. 各変数初期化.
        int l = left[i];
        int r = right[i];
        int like2017 = 0;
        
        // 4-2. l ～ r で, 2017に似た数の個数をカウント.
        vector<int>::iterator lItr, rItr;
        lItr = lower_bound(v2017.begin(), v2017.end(), l);
        rItr = upper_bound(v2017.begin(), v2017.end(), r);
        int lIndex = distance(v2017.begin(), lItr);
        int rIndex = distance(v2017.begin(), rItr);
        // cout << "l=" << l << " r=" << r << " lIndex=" << lIndex << " rIndex=" << rIndex << endl;
        int diff = rIndex - lIndex;
        like2017 += diff;
        
        // 4-3. 出力.
        cout << like2017 << endl;
    }
    
    return 0;

}

#include <bits/stdc++.h>

using namespace std;

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

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

int main() {

// 1. 入力情報取得.

int Q;

cin >> Q;

int left[Q], right[Q];

FOR(i, 0, Q) cin >> left[i] >> right[i];

// 2. 素数を用意する.

map<int, int> m;

vector<int> v;

m[2]++;

v.push_back(2);

FORN(i, 3, 100002, 2) {

bool isPrime = true;

FORN(j, 3, sqrt(i) + 1, 2) {

if(i % j == 0){

isPrime = false;

break;

}

if(isPrime) m[i]++, v.push_back(i);

}

// 3. 2017に似た数を用意する.

// ex. 3, 5, 13, 37, 61, 73, 157, 193, 277, 313

vector<int> v2017;

for(auto &p : v) {

int x = (p + 1) / 2;

if(m[x] == 1) v2017.push_back(p);

}

// FOR(i, 0, 10) cout << v2017[i] << endl;

// 4. 2017に似た数の個数を計算.

FOR(i, 0, Q){

// 4-1. 各変数初期化.

int l = left[i];

int r = right[i];

int like2017 = 0;

// 4-2. l ～ r で, 2017に似た数の個数をカウント.

vector<int>::iterator lItr, rItr;

lItr = lower_bound(v2017.begin(), v2017.end(), l);

rItr = upper_bound(v2017.begin(), v2017.end(), r);

int lIndex = distance(v2017.begin(), lItr);

int rIndex = distance(v2017.begin(), rItr);

// cout << "l=" << l << " r=" << r << " lIndex=" << lIndex << " rIndex=" << rIndex << endl;

int diff = rIndex - lIndex;

like2017 += diff;

// 4-3. 出力.

cout << like2017 << endl;

}

return 0;

}

[入力例]
1
3 7

[出力例(debug版)]
l=3 r=7 lIndex=0 rIndex=2
2
※AtCoderのテストケースより

[入力例]
4
13 13
7 11
7 11
2017 2017

[出力例(debug版)]
l=13 r=13 lIndex=2 rIndex=3
1
l=7 r=11 lIndex=2 rIndex=2
0
l=7 r=11 lIndex=2 rIndex=2
0
l=2017 r=2017 lIndex=35 rIndex=36
1
※AtCoderのテストケースより

[入力例]
6
1 53
13 91
37 55
19 51
73 91
13 49

[出力例(debug版)]
l=1 r=53 lIndex=0 rIndex=4
4
l=13 r=91 lIndex=2 rIndex=6
4
l=37 r=55 lIndex=3 rIndex=4
1
l=19 r=51 lIndex=3 rIndex=4
1
l=73 r=91 lIndex=5 rIndex=6
1
l=13 r=49 lIndex=2 rIndex=4
2
※AtCoderのテストケースより

[入力例]

3 7

[出力例(debug版)]

l=3 r=7 lIndex=0 rIndex=2

※AtCoderのテストケースより

[入力例]

13 13

7 11

2017 2017

[出力例(debug版)]

l=13 r=13 lIndex=2 rIndex=3

l=7 r=11 lIndex=2 rIndex=2

l=2017 r=2017 lIndex=35 rIndex=36

※AtCoderのテストケースより

[入力例]

1 53

13 91

37 55

19 51

73 91

13 49

[出力例(debug版)]

l=1 r=53 lIndex=0 rIndex=4

l=13 r=91 lIndex=2 rIndex=6

l=37 r=55 lIndex=3 rIndex=4

l=19 r=51 lIndex=3 rIndex=4

l=73 r=91 lIndex=5 rIndex=6

l=13 r=49 lIndex=2 rIndex=4

※AtCoderのテストケースより

■参照サイト
AtCoder Beginner Contest 084

2019年1月27日2019年1月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 083 の問題C（Multiple Gift) ～問題D (Wide Flip) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.

本家のサイトARC 088/ABC 083 解説をご覧下さい.

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

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

int main() {
    
    // 1. 入力情報取得.
    LL X, Y;
    cin >> X >> Y;
    
    // 2. 条件を満たす数列を計算.
    LL curA = X;    // 今回の計算結果保存用.
    LL befA = curA; // 前回の計算結果保存用.
    LL ans = 1;     // 数列の長さ.
    while(true) {
       curA = 2 * befA;
       befA = curA;
       ans++;
       if(curA > Y) {
           ans--;
           break;
       }
    }
    
    // 3. 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {

// 1. 入力情報取得.

LL X, Y;

cin >> X >> Y;

// 2. 条件を満たす数列を計算.

LL curA = X; // 今回の計算結果保存用.

LL befA = curA; // 前回の計算結果保存用.

LL ans = 1; // 数列の長さ.

while(true) {

curA = 2 * befA;

befA = curA;

ans++;

if(curA > Y) {

ans--;

break;

}

// 3. 後処理.

cout << ans << endl;

return 0;

}

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

// 解き直し.
// ARC 088/ABC 083 解説.
// https://img.atcoder.jp/arc088/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

int main() {
    
    // 1. 入力情報取得.
    string S;
    cin >> S;
    
    // 2. 解説通り.
    // S の k文字目 と k + 1文字目が, 異なる箇所で, max(k, n - k) の最小値をT(S).
    int L    = S.size();  // 文字列長.
    int ans  = S.size();  // T(S).
    char cur = S[0];      // 今回出現する文字.
    char bef = S[0];      // 前回出現した文字.
    FOR(k, 1, L + 1) {
        // 今回出現する文字を設定.
        cur = S[k - 1];
        
        // k文字目 と k + 1 文字目を比較.
        if(cur != bef) ans = min(ans, max(k - 1, L - k + 1));
        
        // 前回出現文字を更新.
        bef = cur;
    }
    
    // 3. 後処理.
    cout << ans << endl;
    return 0;

}

// 解き直し.

// ARC 088/ABC 083 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

int main() {

// 1. 入力情報取得.

string S;

cin >> S;

// 2. 解説通り.

// S の k文字目と k + 1文字目が, 異なる箇所で, max(k, n - k) の最小値をT(S).

int L = S.size(); // 文字列長.

int ans = S.size(); // T(S).

char cur = S[0]; // 今回出現する文字.

char bef = S[0]; // 前回出現した文字.

FOR(k, 1, L + 1) {

// 今回出現する文字を設定.

cur = S[k - 1];

// k文字目と k + 1 文字目を比較.

if(cur != bef) ans = min(ans, max(k - 1, L - k + 1));

// 前回出現文字を更新.

bef = cur;

}

// 3. 後処理.

cout << ans << endl;

return 0;

}

[入力例]
010

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

[入力例]
100000000

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

[入力例]
100010001

[出力例]
5
※例えば, 以下のような変換が考えられる.
(10001)0001 -> (01110)0001  (1文字目 ～ 5文字目までの5文字を変換)
0111(00001) -> 0111(11110)  (5文字目 ～ 9文字目までの5文字を変換)
0(1111111)0 -> 0(0000000)0  (2文字目 ～ 8文字目までの7文字を変換)
-> K = 5 と分かる.

[入力例]
100010001100010001

[出力例]
10
※例えば, 以下のような変換が考えられる.
(1000100011)00010001 -> (0111011100)00010001  (1文字目 ～ 10文字目までの10文字を変換)
0(111011100000)10001 -> 0(000100011111)10001  (2文字目 ～ 13文字目までの12文字を変換)
0000(10001111110001) -> 0000(01110000001110)  (5文字目 ～ 18文字目までの14文字を変換)
00000(111000000111)0 -> 00000(000111111000)0  (6文字目 ～ 17文字目までの12文字を変換)
00000000(1111110000) -> 00000000(0000001111)  (9文字目 ～ 18文字目までの10文字を変換)
(00000000000000)1111 -> (11111111111111)1111  (1文字目 ～ 14文字目までの14文字を変換)
(111111111111111111) -> (000000000000000000)  (1文字目 ～ 18文字目までの18文字を変換)
-> K = 10 と分かる.

[入力例]

010

[出力例]

※AtCoderテストケースより

[入力例]

100000000

[出力例]

※AtCoderテストケースより

[入力例]

100010001

[出力例]

※例えば, 以下のような変換が考えられる.

(10001)0001 -> (01110)0001 (1文字目～ 5文字目までの5文字を変換)

0111(00001) -> 0111(11110) (5文字目～ 9文字目までの5文字を変換)

0(1111111)0 -> 0(0000000)0 (2文字目～ 8文字目までの7文字を変換)

-> K = 5 と分かる.

[入力例]

100010001100010001

[出力例]

※例えば, 以下のような変換が考えられる.

(1000100011)00010001 -> (0111011100)00010001 (1文字目～ 10文字目までの10文字を変換)

0(111011100000)10001 -> 0(000100011111)10001 (2文字目～ 13文字目までの12文字を変換)

0000(10001111110001) -> 0000(01110000001110) (5文字目～ 18文字目までの14文字を変換)

00000(111000000111)0 -> 00000(000111111000)0 (6文字目～ 17文字目までの12文字を変換)

00000000(1111110000) -> 00000000(0000001111) (9文字目～ 18文字目までの10文字を変換)

(00000000000000)1111 -> (11111111111111)1111 (1文字目～ 14文字目までの14文字を変換)

(111111111111111111) -> (000000000000000000) (1文字目～ 18文字目までの18文字を変換)

-> K = 10 と分かる.

■参照サイト
AtCoder Beginner Contest 083

2019年1月26日2019年1月27日

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

C++の練習を兼ねて, AtCoder Beginner Contest 081 の問題C（Not so Diverse) ～問題D (Non-decreasing) を解いてみた.

■感想.
1. 問題D は, 解答方針が見えなかったので, 解説を参照して確認した.

本家のサイトAtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説をご覧下さい.

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

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define max(x, y) ((x > y) ? x : y)

int main() {
    
    // 1. 入力情報取得.
    int N, K;
    cin >> N >> K;
    map<int, int> m;
    FOR(i, 0, N) {
        int ai;
        cin >> ai;
        m[ai]++;
    }
    
    // 2. map の 値 で, 昇順ソート.
    // [入力値]
    // 10 3
    // 5 1 3 2 4 1 1 2 3 4
    // (整数, 出現回数) = (5, 1), (2, 2), (3, 2), (4, 2), (1, 3) なので, 
    // 5 … 1回, 2 … 2回 の 合計3回書き換えれば 3種類以下となる.
    int size = m.size();
    int A[size] = {};
    int index = 0;
    for(auto i = m.begin(); i != m.end() ; ++i) A[index++] = i->second;
    sort(A, A + size);
    
    // 3. 書き換え回数をカウント.
    int rewrites = 0;
    FOR(i, 0, size) if(size - i > K) rewrites += A[i];

    // 4 . 出力 ～ 後処理.
    cout << rewrites << endl;
    return 0;
    
}

#include <iostream>

#include <map>

#include <algorithm>

using namespace std;

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

#define max(x, y) ((x > y) ? x : y)

int main() {

// 1. 入力情報取得.

int N, K;

cin >> N >> K;

map<int, int> m;

FOR(i, 0, N) {

int ai;

cin >> ai;

m[ai]++;

}

// 2. map の値で, 昇順ソート.

// [入力値]

// 10 3

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

// (整数, 出現回数) = (5, 1), (2, 2), (3, 2), (4, 2), (1, 3) なので,

// 5 … 1回, 2 … 2回の合計3回書き換えれば 3種類以下となる.

int size = m.size();

int A[size] = {};

int index = 0;

for(auto i = m.begin(); i != m.end() ; ++i) A[index++] = i->second;

sort(A, A + size);

// 3. 書き換え回数をカウント.

int rewrites = 0;

FOR(i, 0, size) if(size - i > K) rewrites += A[i];

// 4 . 出力～後処理.

cout << rewrites << endl;

return 0;

}

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

// 解き直し.
// AtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説.
// https://img.atcoder.jp/arc086/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b)  for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {

    // 1. 入力情報取得.
    int N;
    cin >> N;
    int A[N + 1];
    // pair の 第一成分: インデックス(1 ～ N), 第二成分: 値.
    pair<int, int> aMax = {-1, -1e6};
    pair<int, int> aMin = {-1,  1e6};
    FOR(i, 1, N + 1) {
        int a;
        cin >> a;
        if(aMax.second < a) aMax.first = i, aMax.second = a;
        if(aMin.second > a) aMin.first = i, aMin.second = a;
        A[i] = a;
    }
    
    // 2. 解説通り.
    int iMax = aMax.first;
    int vMax = aMax.second;
    int iMin = aMin.first;
    int vMin = aMin.second;
    
    // 2-1. 配列A が, 非負整数の場合.
    // a(2) += a(1), a(3) += a(2), ..., a(N) += a(N - 1) の操作で実現できる.
    if(vMin >= 0) {
        cout << N - 1 << endl;
        FOR(i, 1, N) cout << i << " " << i + 1 << endl;
    }

    // 2-2. 配列A に, 負整数が混在する(abs(vMin) <= abs(vMax))場合.
    // すべての配列A の要素に, vMax を 加算後, 2-1. と同じ操作を追加すれば実現できる.
    if(vMin < 0 && abs(vMin) <= abs(vMax)) {
        cout << N * 2 - 1 << endl;
        FOR(i, 1, N + 1) cout << iMax << " " << i << endl;
        FOR(i, 1, N) cout << i << " " << i + 1 << endl;
    }
    
    // 2-3. 配列A に, 負整数が混在する(abs(vMin) > abs(vMax))場合.
    // すべての配列A の要素に, vMin を 加算後, 2-1. と類似の操作を追加すれば実現できる.
    if(vMin < 0 && abs(vMin) > abs(vMax)) {
        cout << N * 2 - 1 << endl;
        FOR(i, 1, N + 1) cout << iMin << " " << i << endl;
        FORR(i, N, 1)    cout << i << " " << i - 1 << endl;
    }
    
    return 0;

}

// 解き直し.

// AtCoder Beginner Contest 081 / AtCoder Regular Contest 086 解説.

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

#include <bits/stdc++.h>

using namespace std;

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

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

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

int A[N + 1];

// pair の第一成分: インデックス(1 ～ N), 第二成分: 値.

pair<int, int> aMax = {-1, -1e6};

pair<int, int> aMin = {-1, 1e6};

FOR(i, 1, N + 1) {

int a;

cin >> a;

if(aMax.second < a) aMax.first = i, aMax.second = a;

if(aMin.second > a) aMin.first = i, aMin.second = a;

A[i] = a;

}

// 2. 解説通り.

int iMax = aMax.first;

int vMax = aMax.second;

int iMin = aMin.first;

int vMin = aMin.second;

// 2-1. 配列A が, 非負整数の場合.

// a(2) += a(1), a(3) += a(2), ..., a(N) += a(N - 1) の操作で実現できる.

if(vMin >= 0) {

cout << N - 1 << endl;

FOR(i, 1, N) cout << i << " " << i + 1 << endl;

}

// 2-2. 配列A に, 負整数が混在する(abs(vMin) <= abs(vMax))場合.

// すべての配列A の要素に, vMax を加算後, 2-1. と同じ操作を追加すれば実現できる.

if(vMin < 0 && abs(vMin) <= abs(vMax)) {

cout << N * 2 - 1 << endl;

FOR(i, 1, N + 1) cout << iMax << " " << i << endl;

FOR(i, 1, N) cout << i << " " << i + 1 << endl;

}

// 2-3. 配列A に, 負整数が混在する(abs(vMin) > abs(vMax))場合.

// すべての配列A の要素に, vMin を加算後, 2-1. と類似の操作を追加すれば実現できる.

if(vMin < 0 && abs(vMin) > abs(vMax)) {

cout << N * 2 - 1 << endl;

FOR(i, 1, N + 1) cout << iMin << " " << i << endl;

FORR(i, N, 1) cout << i << " " << i - 1 << endl;

}

return 0;

}

■参照サイト
AtCoder Beginner Contest 081

2019年1月20日2019年1月20日

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

■感想.
1. いったん実装してみた(下記, WA版)が, ロジックの修正方法が分からなかったので, 解説を見て, 再度やり直ししたものである.
解説を見て, 本問についても, なるほどと感心させられた.

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

■C++版プログラム(問題C／WA版).
※テストケース(1_04.txt, 1_08.txt, 1_10.txt, 1_18.txt, 1_21.txt, 1_22.txt, 1_24.txt, 1_26.txt, 1_27.txt, 1_29.txt)で,
WA判定となった.

// WA版.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<string, int> P;

bool comp1(const P& f, const P& s) { return f.second < s.second; }
bool comp2(const P& f, const P& s) { return (f.first < s.first && f.second > s.second); }

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    vector<P> knots;
    
    // 結び目情報(前回, 今回).
    LL bef, cur;
    int ok = 0;
    cin >> bef;
    FOR(i, 1, N) {
        string s;
        cin >> cur;
        if(cur + bef >= L)  s = "OK", ok++;
        else                s = "NG";
        knots.push_back(make_pair(s, i));
        // 前回結び目情報を更新.
        bef = cur;
    }
    // for(auto &p : knots) cout << "status: " << p.first << "  knot index:" << p.second << endl;
    
    // 2. OK が 一つもない場合は, 終了.
    string ans = "Impossible";
    if(ok == 0) {
        cout << ans << endl;
        return 0;
    }
    
    // 3. 各区間に, "OK" が, 一つずつ含まれるように分割.
    vector<vector<P>> setOfKnots;
    priority_queue<P> q;
    ok = 0;
    for(auto &p : knots) {
        
        string status = p.first;
        int knotIndex = p.second;
        // 3-1. status が "OK" なら, ok を increment.
        if(status == "OK") ok++;
        // cout << "status: " << status << "  knot index:" << knotIndex << " q.size()=" << q.size() << " ok=" << ok << endl;
        // 3-2. ok == 1 の 場合は, setOfKnots に 登録.
        if(ok == 1) {
            // priority queue を 空にする.
            vector<P> v;
            while(!q.empty()) {
                v.push_back(q.top());
                q.pop();
            }
            setOfKnots.push_back(v);
            ok = 0;
        }
        q.push(make_pair(status, knotIndex));
    }
    // 3-3. 残りを setOfKnots に 登録.
    vector<P> v;
    while(!q.empty()) {
        v.push_back(q.top());
        q.pop();
    }
    setOfKnots.push_back(v);
    
    // 4. 各区間について, 出力.
    // setOfKnots の 各区間の先頭が, status: OK になっているはず.
    // -> 最初の区間は, status: OK が含まれてないはずなので,2番目の区間に合わせて出力.
    ans = "Possible";
    cout << ans << endl;
    int nKnot = 1;
    for(auto &knots : setOfKnots) {
        // cout << "--- start this set ---" << endl;
        if(nKnot == 1) sort(knots.begin(), knots.end(), comp1);
        else           sort(knots.begin(), knots.end(), comp2);
        for(auto &p : knots) {
            // cout << "status: " << p.first << "  knot index:" << p.second << endl;
            cout << p.second << endl;
        }
        // cout << "---- end this set ----" << endl;
        nKnot++;
    }
    return 0;
    
}

// WA版.

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef pair<string, int> P;

bool comp1(const P& f, const P& s) { return f.second < s.second; }

bool comp2(const P& f, const P& s) { return (f.first < s.first && f.second > s.second); }

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

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

vector knots;

// 結び目情報(前回, 今回).

LL bef, cur;

int ok = 0;

cin >> bef;

FOR(i, 1, N) {

string s;

cin >> cur;

if(cur + bef >= L) s = "OK", ok++;

else s = "NG";

knots.push_back(make_pair(s, i));

// 前回結び目情報を更新.

bef = cur;

}

// for(auto &p : knots) cout << "status: " << p.first << " knot index:" << p.second << endl;

// 2. OK が一つもない場合は, 終了.

string ans = "Impossible";

if(ok == 0) {

cout << ans << endl;

return 0;

}

// 3. 各区間に, "OK" が, 一つずつ含まれるように分割.

vector<vector> setOfKnots;

priority_queue q;

ok = 0;

for(auto &p : knots) {

string status = p.first;

int knotIndex = p.second;

// 3-1. status が "OK" なら, ok を increment.

if(status == "OK") ok++;

// cout << "status: " << status << " knot index:" << knotIndex << " q.size()=" << q.size() << " ok=" << ok << endl;

// 3-2. ok == 1 の場合は, setOfKnots に登録.

if(ok == 1) {

// priority queue を空にする.

vector v;

while(!q.empty()) {

v.push_back(q.top());

q.pop();

}

setOfKnots.push_back(v);

ok = 0;

}

q.push(make_pair(status, knotIndex));

}

// 3-3. 残りを setOfKnots に登録.

vector v;

while(!q.empty()) {

v.push_back(q.top());

q.pop();

}

setOfKnots.push_back(v);

// 4. 各区間について, 出力.

// setOfKnots の各区間の先頭が, status: OK になっているはず.

// -> 最初の区間は, status: OK が含まれてないはずなので,2番目の区間に合わせて出力.

ans = "Possible";

cout << ans << endl;

int nKnot = 1;

for(auto &knots : setOfKnots) {

// cout << "--- start this set ---" << endl;

if(nKnot == 1) sort(knots.begin(), knots.end(), comp1);

else sort(knots.begin(), knots.end(), comp2);

for(auto &p : knots) {

// cout << "status: " << p.first << " knot index:" << p.second << endl;

cout << p.second << endl;

}

// cout << "---- end this set ----" << endl;

nKnot++;

}

return 0;

}

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

// 解き直し.
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i, a, b)  for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    vector<LL> a;
    FOR(i, 0, N) {
        LL k;
        cin >> k;
        a.push_back(k);
    }
    
    // 2. 解説通り.
    // a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.
    LL knotInfo[N - 1] = {};
    int lastKnotIndex = -1;
    FOR(i, 0, N - 1) {
        LL x = a[i] + a[i + 1];
        knotInfo[i] = x;
        if(x >= L) {
            lastKnotIndex = i + 1;
            break;
        }
    }
    
    // 3. 解説通り.
    // 最後にほどく結び目が, 一つもない場合は, 終了.
    if(lastKnotIndex == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 4. 解説通り.
    cout << "Possible" << endl;
    // 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.
    FOR(l, 1, lastKnotIndex)      cout << l << endl;
    // 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.
    FORR(r, N - 1, lastKnotIndex) cout << r << endl;
    // 4-3. 最後に，結び目 i をほどく.
    cout << lastKnotIndex << endl;

    return 0;
    
}

// 解き直し.

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

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

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

vector<LL> a;

FOR(i, 0, N) {

LL k;

cin >> k;

a.push_back(k);

}

// 2. 解説通り.

// a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.

LL knotInfo[N - 1] = {};

int lastKnotIndex = -1;

FOR(i, 0, N - 1) {

LL x = a[i] + a[i + 1];

knotInfo[i] = x;

if(x >= L) {

lastKnotIndex = i + 1;

break;

}

// 3. 解説通り.

// 最後にほどく結び目が, 一つもない場合は, 終了.

if(lastKnotIndex == -1) {

cout << "Impossible" << endl;

return 0;

}

// 4. 解説通り.

cout << "Possible" << endl;

// 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.

FOR(l, 1, lastKnotIndex) cout << l << endl;

// 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.

FORR(r, N - 1, lastKnotIndex) cout << r << endl;

// 4-3. 最後に，結び目 i をほどく.

cout << lastKnotIndex << endl;

return 0;

}

■C++版プログラム(問題C／AC版).
上記のプログラムが, 冗長に感じたので, 修正.

// 解き直し(その②).
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i, a, b)  for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = (a); i > (b); --i)

int main() {
    
    // 1. 入力情報取得.
    int N;
    LL L;
    cin >> N >> L;
    
    // 2. 解説通り.
    // a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.
    int lastKnotIndex = -1;  // 最後にほどく結び目.
    LL bef;                  // 前回ロープ長.
    cin >> bef;
    FOR(i, 1, N) {
        LL cur;    // 今回ロープ長.
        cin >> cur;
        if(bef + cur >= L) {
            lastKnotIndex = i;
            break;
        }
        // 前回ロープ長を更新.
        bef = cur;
    }
    
    // 3. 解説通り.
    // 最後にほどく結び目が, 一つもない場合は, 終了.
    if(lastKnotIndex == -1) {
        cout << "Impossible" << endl;
        return 0;
    }
    
    // 4. 解説通り.
    cout << "Possible" << endl;
    // 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.
    FOR(l, 1, lastKnotIndex)      cout << l << endl;
    // 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.
    FORR(r, N - 1, lastKnotIndex) cout << r << endl;
    // 4-3. 最後に，結び目 i をほどく.
    cout << lastKnotIndex << endl;

    return 0;
    
}

// 解き直し(その②).

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

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

int main() {

// 1. 入力情報取得.

int N;

LL L;

cin >> N >> L;

// 2. 解説通り.

// a(i) + a(i + 1) >= L となる最後にほどく結び目を探索.

int lastKnotIndex = -1; // 最後にほどく結び目.

LL bef; // 前回ロープ長.

cin >> bef;

FOR(i, 1, N) {

LL cur; // 今回ロープ長.

cin >> cur;

if(bef + cur >= L) {

lastKnotIndex = i;

break;

}

// 前回ロープ長を更新.

bef = cur;

}

// 3. 解説通り.

// 最後にほどく結び目が, 一つもない場合は, 終了.

if(lastKnotIndex == -1) {

cout << "Impossible" << endl;

return 0;

}

// 4. 解説通り.

cout << "Possible" << endl;

// 4-1. 結び目 1, 2, ... , i - 1 の順でほどく.

FOR(l, 1, lastKnotIndex) cout << l << endl;

// 4-2. 結び目 N - 1, N - 2, ... , i + 1 の順でほどく.

FORR(r, N - 1, lastKnotIndex) cout << r << endl;

// 4-3. 最後に，結び目 i をほどく.

cout << lastKnotIndex << endl;

return 0;

}

■参照サイト
AtCoder Grand Contest 002

2019年1月20日

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題B（Box and Ball) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解答を確認したところ, なるほどと感心させられた.

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

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

// 解き直し.
// AtCoder Grand Contest 002 解説.
// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)

struct Box {
    int x;    // 移動元(箱).
    int y;    // 移動先(箱).
};

int main() {
    
    // 1. 入力情報取得.
    int N, M;
    cin >> N >> M;
    vector<Box> v;
    FOR(i, 0, M) {
        Box b;
        cin >> b.x >> b.y;
        b.x--;
        b.y--;
        v.push_back(b);
    }
    
    // 2. 各箱について, ボールの個数を設定(解説通り.).
    int balls[N] = {};
    FOR(i, 0, N) balls[i]++;
    bool red[N] = {};
    red[0] = true;
    
    // 3. 赤いボールの移動を確認(解説通り).
    FOR(i, 0, M) {
        Box b = v[i];
        if(red[b.x]) red[b.y] = true;
        balls[b.x]--;
        balls[b.y]++;
        if(balls[b.x] == 0) red[b.x] = false;
    }
    
    // 4. 出力.
    int ans = 0;
    FOR(i, 0, N) if(red[i]) ans++;
    cout << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Grand Contest 002 解説.

// http://agc002.contest.atcoder.jp/data/agc/002/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

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

struct Box {

int x; // 移動元(箱).

int y; // 移動先(箱).

};

int main() {

// 1. 入力情報取得.

int N, M;

cin >> N >> M;

vector<Box> v;

FOR(i, 0, M) {

Box b;

cin >> b.x >> b.y;

b.x--;

b.y--;

v.push_back(b);

}

// 2. 各箱について, ボールの個数を設定(解説通り.).

int balls[N] = {};

FOR(i, 0, N) balls[i]++;

bool red[N] = {};

red[0] = true;

// 3. 赤いボールの移動を確認(解説通り).

FOR(i, 0, M) {

Box b = v[i];

if(red[b.x]) red[b.y] = true;

balls[b.x]--;

balls[b.y]++;

if(balls[b.x] == 0) red[b.x] = false;

}

// 4. 出力.

int ans = 0;

FOR(i, 0, N) if(red[i]) ans++;

cout << ans << endl;

return 0;

}

■参照サイト
AtCoder Grand Contest 002

2019年1月14日

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

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

■感想.
1. 問題C は, かなりゴリゴリ実装せざるを得なかった.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.

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

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    LL N, M;
    cin >> N >> M;
    
    // Map of int and vector<int> in c++
    // https://stackoverflow.com/questions/15192534/map-of-int-and-vectorint-in-c
    // map の key:   県番号(Pi).
    // map の value: vector<pair<LL, LL>>: 誕生年(Yi), 市の番号.
    map<LL, vector<pair<LL, LL>>> m;
    FOR(i, 0, M) {
        LL p, y;
        cin >> p >> y;
        m[p].push_back(make_pair(y, i));
    }
    
    // ex.
    // [input]
    // 2 3
    // 1 32
    // 2 63
    // 1 12
    // 
    // [output]
    // city: 0 -> year: 32 belongs to Prefecture: 1
    // city: 2 -> year: 12 belongs to Prefecture: 1
    // city: 1 -> year: 63 belongs to Prefecture: 2
    // for(auto &p : m) for(auto &i : p.second) cout << "city: " << i.second << " -> year: " << i.first << " belongs to " << "Prefecture: " << p.first << endl;

    // 2. ID生成 ～ 出力.
    map<LL, string> ans;    // 市の番号, 市の認識番号 を 保存.
    for(auto &p : m) {
        
        // 2-1. 誕生年 で 昇順sort.
        vector<pair<LL, LL>> v = p.second;
        sort(v.begin(), v.end());
        
        // 2-2. 市の認識番号を作成.
        for(auto i = v.begin(); i != v.end(); ++i) {
            LL x = i - v.begin() + 1;
            ostringstream ss;
            // 上6桁: 県(Pi)
            ss << std::setw(6) << std::setfill('0') << p.first;
            // 下6桁: 市が, 県(Pi) で, x番目に誕生した
            ss << std::setw(6) << std::setfill('0') << x;
            string id(ss.str());
            // map に 保管して, 市の番号順に, 自動で昇順sort.
            ans[i->second] = id;
        }
    }
    
    // 3. 後処理.
    for(auto &a : ans) cout << a.second << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

LL N, M;

cin >> N >> M;

// Map of int and vector<int> in c++

// https://stackoverflow.com/questions/15192534/map-of-int-and-vectorint-in-c

// map の key: 県番号(Pi).

// map の value: vector<pair<LL, LL>>: 誕生年(Yi), 市の番号.

map<LL, vector<pair<LL, LL>>> m;

FOR(i, 0, M) {

LL p, y;

cin >> p >> y;

m[p].push_back(make_pair(y, i));

}

// ex.

// [input]

// 2 3

// 1 32

// 2 63

// 1 12

// [output]

// city: 0 -> year: 32 belongs to Prefecture: 1

// city: 2 -> year: 12 belongs to Prefecture: 1

// city: 1 -> year: 63 belongs to Prefecture: 2

// for(auto &p : m) for(auto &i : p.second) cout << "city: " << i.second << " -> year: " << i.first << " belongs to " << "Prefecture: " << p.first << endl;

// 2. ID生成～出力.

map<LL, string> ans; // 市の番号, 市の認識番号を保存.

for(auto &p : m) {

// 2-1. 誕生年で昇順sort.

vector<pair<LL, LL>> v = p.second;

sort(v.begin(), v.end());

// 2-2. 市の認識番号を作成.

for(auto i = v.begin(); i != v.end(); ++i) {

LL x = i - v.begin() + 1;

ostringstream ss;

// 上6桁: 県(Pi)

ss << std::setw(6) << std::setfill('0') << p.first;

// 下6桁: 市が, 県(Pi) で, x番目に誕生した

ss << std::setw(6) << std::setfill('0') << x;

string id(ss.str());

// map に保管して, 市の番号順に, 自動で昇順sort.

ans[i->second] = id;

}

// 3. 後処理.

for(auto &a : ans) cout << a.second << endl;

return 0;

}

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

// 解き直し.
// ABC 113 解説.
// https://img.atcoder.jp/abc113/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

int main() {
    
    // 1. 入力情報取得.
    LL H, W, K;
    cin >> H >> W >> K;
    
    // 2. 解説通り.
    // DP を 使うとのこと.
    // DP(h, x): 縦から h 列目を通過した(横棒を通った場合も含む)直後に, 左から x本目の縦棒にいる場合の数.
    // DP(h, x) の 遷移先は, DP(h + 1, x - 1), DP(h + 1, x), DP(h + 1, x + 1) の 3種類.
    LL DP[H + 1][W + 1] = {};
    DP[0][1] = 1;
    
    // 2-1. (h + 1)列目の横棒の全配置は, 何通り？
    // W本の縦棒から, 正しいあみだくじの条件を満たすように横棒を配置することに注意.
    // ex.
    // 
    // W = 0 -> 1通り.
    // W = 1 -> 1通り.
    // W = 2 -> 2通り.
    // W = 3 -> 3通り.
    // W = 4 -> 5通り(※横棒:"_", 横棒無し: "." とすると, ... _.. ._. .._ _._ の5通り).
    // ...
    // -> 解説通り, フィボナッチ数列と同じになっていることが分かる.
    LL BAR[W + 1] = {};
    BAR[0] = 1;
    BAR[1] = 1;
    FOR(i, 2, W + 1) BAR[i] = BAR[i - 1] + BAR[i - 2];
    
    // 2-2. DP更新.
    FOR(h, 1, H + 1) {
        FOR(x, 1, W + 1) {
            // 2-2-1. DP(h, x) -> DP(h + 1, x - 1)
            // 左から, x本目 -> (x - 1)本目に遷移するには, 
            // x > 1 の場合で, 
            // ① (x - 1)本目 と x本目       との間に, 横棒が必要.
            // ② (x - 2)本目 と (x - 1)本目 との間は, 横棒が無い状態.
            // ③ (x + 1)本目 と x本目       との間は, 横棒が無い状態.
            // -> 場合の数としては, 左から(x - 2)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数 なので,
            // X = BAR[x - 2] × BAR[W - (x + 1) + 1] と分かる.
            if(x > 1) {
                LL X = BAR[x - 2] * BAR[W - x];
                DP[h][x - 1] += X * DP[h - 1][x];
                DP[h][x - 1] %= MOD;
            }
            
            // 2-2-2. DP(h, x) -> DP(h + 1, x)
            // 左から, x本目 -> x本目のように留まるためには, 
            // (x - 1)本目 と x本目, x本目 と (x + 1)本目 との間に, それぞれ横棒が無い状態.
            // x == 1 または x == W の場合.
            // -> 場合の数としては, (W - 1)本についての横棒配置数 なので, Y = BAR[W - 1] と分かる.
            if(x == 1 || x == W) {
                LL Y = BAR[W - 1];
                DP[h][x] += Y * DP[h - 1][x];
                DP[h][x] %= MOD;
            }
            // x > 1 かつ x < W の場合.
            // -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数 なので,
            // Y = BAR[x - 1] × BAR[W - (x + 1) + 1] と分かる.
            if(x > 1 && x < W) {
                LL Y = BAR[x - 1] * BAR[W - x];
                DP[h][x] += Y * DP[h - 1][x];
                DP[h][x] %= MOD;
            }

            // 2-2-3. DP(h, x) -> DP(h + 1, x + 1)
            // 左から, x本目 -> (x + 1)本目に遷移するには, 
            // x < W の場合で, 
            // ① (x + 1)本目 と x本目       との間に, 横棒が必要.
            // ② (x + 2)本目 と (x + 1)本目 との間は, 横棒が無い状態.
            // ③ (x - 1)本目 と x本目       との間に, 横棒が無い状態.
            // -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 2)本目以降の横棒配置数 なので,
            // Z = BAR[x - 1] × BAR[W - (x + 2) + 1] と分かる.
            if(x < W) {
                LL Z = BAR[x - 1] * BAR[W - x - 1];
                DP[h][x + 1] += Z * DP[h - 1][x];
                DP[h][x + 1] %= MOD;
            }
        }
    }
    
    // 3. 出力 ～ 後処理.
    // FOR(h, 0, H + 1) {
    //     FOR(x, 0, W + 1) {
    //         cout << DP[h][x] << " ";
    //     }
    //     cout << endl;
    // }
    LL ans = 0LL;
    FOR(i, 0, W + 1) {
        LL val = DP[H][i];
        if(i == K) {
            ans = val;
            break;
        }
    }
    cout << ans << endl;
    return 0;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

// 解き直し.

// ABC 113 解説.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const LL MOD = 1e9 + 7;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

int main() {

// 1. 入力情報取得.

LL H, W, K;

cin >> H >> W >> K;

// 2. 解説通り.

// DP を使うとのこと.

// DP(h, x): 縦から h 列目を通過した(横棒を通った場合も含む)直後に, 左から x本目の縦棒にいる場合の数.

// DP(h, x) の遷移先は, DP(h + 1, x - 1), DP(h + 1, x), DP(h + 1, x + 1) の 3種類.

LL DP[H + 1][W + 1] = {};

DP[0][1] = 1;

// 2-1. (h + 1)列目の横棒の全配置は, 何通り？

// W本の縦棒から, 正しいあみだくじの条件を満たすように横棒を配置することに注意.

// ex.

// W = 0 -> 1通り.

// W = 1 -> 1通り.

// W = 2 -> 2通り.

// W = 3 -> 3通り.

// W = 4 -> 5通り(※横棒:"_", 横棒無し: "." とすると, ... _.. ._. .._ _._ の5通り).

// ...

// -> 解説通り, フィボナッチ数列と同じになっていることが分かる.

LL BAR[W + 1] = {};

BAR[0] = 1;

BAR[1] = 1;

FOR(i, 2, W + 1) BAR[i] = BAR[i - 1] + BAR[i - 2];

// 2-2. DP更新.

FOR(h, 1, H + 1) {

FOR(x, 1, W + 1) {

// 2-2-1. DP(h, x) -> DP(h + 1, x - 1)

// 左から, x本目 -> (x - 1)本目に遷移するには,

// x > 1 の場合で,

// ① (x - 1)本目と x本目との間に, 横棒が必要.

// ② (x - 2)本目と (x - 1)本目との間は, 横棒が無い状態.

// ③ (x + 1)本目と x本目との間は, 横棒が無い状態.

// -> 場合の数としては, 左から(x - 2)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数なので,

// X = BAR[x - 2] × BAR[W - (x + 1) + 1] と分かる.

if(x > 1) {

LL X = BAR[x - 2] * BAR[W - x];

DP[h][x - 1] += X * DP[h - 1][x];

DP[h][x - 1] %= MOD;

}

// 2-2-2. DP(h, x) -> DP(h + 1, x)

// 左から, x本目 -> x本目のように留まるためには,

// (x - 1)本目と x本目, x本目と (x + 1)本目との間に, それぞれ横棒が無い状態.

// x == 1 または x == W の場合.

// -> 場合の数としては, (W - 1)本についての横棒配置数なので, Y = BAR[W - 1] と分かる.

if(x == 1 || x == W) {

LL Y = BAR[W - 1];

DP[h][x] += Y * DP[h - 1][x];

DP[h][x] %= MOD;

}

// x > 1 かつ x < W の場合.

// -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 1)本目以降の横棒配置数なので,

// Y = BAR[x - 1] × BAR[W - (x + 1) + 1] と分かる.

if(x > 1 && x < W) {

LL Y = BAR[x - 1] * BAR[W - x];

DP[h][x] += Y * DP[h - 1][x];

DP[h][x] %= MOD;

}

// 2-2-3. DP(h, x) -> DP(h + 1, x + 1)

// 左から, x本目 -> (x + 1)本目に遷移するには,

// x < W の場合で,

// ① (x + 1)本目と x本目との間に, 横棒が必要.

// ② (x + 2)本目と (x + 1)本目との間は, 横棒が無い状態.

// ③ (x - 1)本目と x本目との間に, 横棒が無い状態.

// -> 場合の数としては, 左から(x - 1)本目までの横棒配置数 × 左から(x + 2)本目以降の横棒配置数なので,

// Z = BAR[x - 1] × BAR[W - (x + 2) + 1] と分かる.

if(x < W) {

LL Z = BAR[x - 1] * BAR[W - x - 1];

DP[h][x + 1] += Z * DP[h - 1][x];

DP[h][x + 1] %= MOD;

}

// 3. 出力～後処理.

// FOR(h, 0, H + 1) {

// FOR(x, 0, W + 1) {

// cout << DP[h][x] << " ";

// }

// cout << endl;

// }

LL ans = 0LL;

FOR(i, 0, W + 1) {

LL val = DP[H][i];

if(i == K) {

ans = val;

break;

}

cout << ans << endl;

return 0;

}

[入力例]
1 3 2

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

[入力例]
1 3 1

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

[入力例]
2 3 3

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

[入力例]
2 3 1

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

[入力例]
7 1 1

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

[入力例]
2 5 1

[出力例(debug版)]
0 1 0 0 0 0 
0 5 3 0 0 0 
0 34 24 6 0 0 
34

[入力例]
2 5 2

[出力例(debug版)]
0 1 0 0 0 0 
0 5 3 0 0 0 
0 34 24 6 0 0 
24

[入力例]
15 8 5

[出力例(debug版)]
0 1 0 0 0 0 0 0 0 
0 21 13 0 0 0 0 0 0 
0 610 442 104 0 0 0 0 0 
0 18556 14508 5200 1040 0 0 0 0 
0 578280 471432 209664 67600 9360 0 0 0 
0 18272496 15323568 7802080 3194880 748800 93600 0 0 
0 582928800 499165472 279370624 132683200 40921920 8985600 748800 0 
0 730655810 302190416 790085697 152251485 897833593 558979200 81619200 9734400 
0 272247285 747686381 581409218 265131456 427559120 574956604 659430365 265471993 
0 437115833 910411283 935352977 639096009 549135846 750339658 623383374 147506500 
0 14779025 676149 639897790 882192358 492298204 483859826 24285514 201620285 
0 319149462 320099547 65697279 62546938 162802402 859023284 807653953 549737639 
0 863432743 835815293 237422192 60398457 595191235 833628041 518276800 43991654 
0 997686216 989601843 89261909 636919834 807734929 436175245 978514139 661423085 
0 816234264 548839857 714203523 716030842 210054737 884266168 808585704 610568410 
0 275837517 459591596 978283490 772990360 437760187 717491536 523132651 333550601 
437760187
※AtCoderテストケースより

[入力例]

1 3 2

[出力例(debug版)]

0 1 0 0

0 2 1 0

※AtCoderテストケースより

[入力例]

1 3 1

[出力例(debug版)]

0 1 0 0

0 2 1 0

※AtCoderテストケースより

[入力例]

2 3 3

[出力例(debug版)]

0 1 0 0

0 2 1 0

0 5 3 1

※AtCoderテストケースより

[入力例]

2 3 1

[出力例(debug版)]

0 1 0 0

0 2 1 0

0 5 3 1

※AtCoderテストケースより

[入力例]

7 1 1

[出力例(debug版)]

0 1

※AtCoderテストケースより

[入力例]

2 5 1

[出力例(debug版)]

0 1 0 0 0 0

0 5 3 0 0 0

0 34 24 6 0 0

[入力例]

2 5 2

[出力例(debug版)]

0 1 0 0 0 0

0 5 3 0 0 0

0 34 24 6 0 0

[入力例]

15 8 5

[出力例(debug版)]

0 1 0 0 0 0 0 0 0

0 21 13 0 0 0 0 0 0

0 610 442 104 0 0 0 0 0

0 18556 14508 5200 1040 0 0 0 0

0 578280 471432 209664 67600 9360 0 0 0

0 18272496 15323568 7802080 3194880 748800 93600 0 0

0 582928800 499165472 279370624 132683200 40921920 8985600 748800 0

0 730655810 302190416 790085697 152251485 897833593 558979200 81619200 9734400

0 272247285 747686381 581409218 265131456 427559120 574956604 659430365 265471993

0 437115833 910411283 935352977 639096009 549135846 750339658 623383374 147506500

0 14779025 676149 639897790 882192358 492298204 483859826 24285514 201620285

0 319149462 320099547 65697279 62546938 162802402 859023284 807653953 549737639

0 863432743 835815293 237422192 60398457 595191235 833628041 518276800 43991654

0 997686216 989601843 89261909 636919834 807734929 436175245 978514139 661423085

0 816234264 548839857 714203523 716030842 210054737 884266168 808585704 610568410

0 275837517 459591596 978283490 772990360 437760187 717491536 523132651 333550601

437760187

※AtCoderテストケースより

■参照サイト
AtCoder Beginner Contest 113

2019年1月14日

Python の動作確認をしてみた（１）

Python 3 の練習を兼ねて, AtCoder Regular Contest 002 の問題B（割り切れる日付) ～問題C (コマンド入力) を解いてみた.

■感想.
1. C++で実装しようとしたところ, 実装方法で迷宮入りしたため, Python 3 で, 書き換えたものである(汗).

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

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

# -*- coding: utf-8 -*-
import datetime

# 1. 入力情報取得.
I = input()

# 2. 1000/01/01 ～ 2999/12/31 で調査.
# 日付の加算・減算.
# https://python.civic-apps.com/timedelta/
iDate = datetime.datetime.strptime(I, '%Y/%m/%d')

passage = 0
ans = ""
while True:
    # passage日加算して調査.
    nDate = iDate + datetime.timedelta(days = passage)
    y = nDate.year
    m = nDate.month
    d = nDate.day
    
    # 割り切れる日付かどうか.
    quoYM,  modYM  = divmod(int(y), int(m))
    quoYMD, modYMD = divmod(quoYM,  int(d))
    
    # 割り切れる日付が来たら, 終了.
    if modYM == 0 and modYMD == 0:
        ans = datetime.datetime(y, m, d, 0, 0, 0, 0)
        ans = ans.strftime('%Y/%m/%d')
        break
    
    # passage を インクリメント.
    passage = passage + 1
    
# 3. 出力.
print(ans)

# -*- coding: utf-8 -*-

import datetime

# 1. 入力情報取得.

I = input()

# 2. 1000/01/01 ～ 2999/12/31 で調査.

# 日付の加算・減算.

# https://python.civic-apps.com/timedelta/

iDate = datetime.datetime.strptime(I, '%Y/%m/%d')

passage = 0

ans = ""

while True:

# passage日加算して調査.

nDate = iDate + datetime.timedelta(days = passage)

y = nDate.year

m = nDate.month

d = nDate.day

# 割り切れる日付かどうか.

quoYM, modYM = divmod(int(y), int(m))

quoYMD, modYMD = divmod(quoYM, int(d))

# 割り切れる日付が来たら, 終了.

if modYM == 0 and modYMD == 0:

ans = datetime.datetime(y, m, d, 0, 0, 0, 0)

ans = ans.strftime('%Y/%m/%d')

break

# passage をインクリメント.

passage = passage + 1

# 3. 出力.

print(ans)

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

# -*- coding: utf-8 -*-
# 1. 入力情報取得.
N = int(input())
C = str(input())

# 2. ボタンの入力回数を計算.
c = "ABXY"
ans = N
for la in range(4):
    for lb in range(4):
        # Lボタン作成.
        L = c[la:la+1] + c[lb:lb+1]
        for ra in range(4):
            for rb in range(4):
                # Rボタン作成.
                R = c[ra:ra+1] + c[rb:rb+1]
                # print(L + " " + R)
                if L != R:
                    lc = C.replace(L, "L")
                    rc = lc.replace(R, "R")
                    # ボタン入力回数更新.
                    ans = min(ans, len(rc))

# 3. 出力.
print(ans)

# -*- coding: utf-8 -*-

# 1. 入力情報取得.

N = int(input())

C = str(input())

# 2. ボタンの入力回数を計算.

c = "ABXY"

ans = N

for la in range(4):

for lb in range(4):

# Lボタン作成.

L = c[la:la+1] + c[lb:lb+1]

for ra in range(4):

for rb in range(4):

# Rボタン作成.

R = c[ra:ra+1] + c[rb:rb+1]

# print(L + " " + R)

if L != R:

lc = C.replace(L, "L")

rc = lc.replace(R, "R")

# ボタン入力回数更新.

ans = min(ans, len(rc))

# 3. 出力.

print(ans)

■参照サイト
AtCoder Regular Contest 002

2019年1月3日2022年1月24日

■感想.
1. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
2. Binary Indexed Tree について, そもそも知らなかったので, 後述の参照サイトを元に, サンプルプログラム(binary_indexed_sample.cpp) で, いったん動作確認してみた.
3. 組み立てた解答が, テストケースをほとんど通過しなかったので, 正解者のコーディングを参照したところ, update関数で, tree[idx] の更新処理が誤っていることが分かったので, 以下のように修正した.
[修正前]
値 k で更新.

[修正後]
値 k と tree[idx] のうち, 大きい方で更新.

本家のサイトAtCoder Beginnar Contest 038 解説をご覧下さい.
※感想として, 私見ではあるが, 以下の読み替えが必要となるように思われる.
解説(P.20): “列で1番目からk番目の最小値を求める操作” -> “列で1番目からk番目の最大値を求める操作”
解説(P.21): “update(i,a)を列のi番目をaで更新” -> “update(i,a)を列のi番目を a, BIT[i] の大きい方で更新”

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

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    
    // 2. 単調増加を調べる.
    LL ans = 1;
    LL inc = 0;  // 単調増加の連続項数.
    LL bef;      // 前回の数.
    cin >> bef;
    FOR(i, 1, N) {
        LL a;
        cin >> a;
        if(bef < a) {
            inc = inc + 1;
            ans += inc;
        } else {
            inc = 0;
        }
        bef = a;
        ans++;
    }
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

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

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

// 2. 単調増加を調べる.

LL ans = 1;

LL inc = 0; // 単調増加の連続項数.

LL bef; // 前回の数.

cin >> bef;

FOR(i, 1, N) {

LL a;

cin >> a;

if(bef < a) {

inc = inc + 1;

ans += inc;

} else {

inc = 0;

}

bef = a;

ans++;

}

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

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

// 解き直し.
// AtCoder Beginnar Contest 038解説
// http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf
#include <bits/stdc++.h>

using namespace std;

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

struct box {
    int h; // 高さ.
    int w; // 幅.
};

// How do i sort a pair increasing based on first element then decreasing based on second element?
// https://stackoverflow.com/questions/35776189/how-do-i-sort-a-pair-increasing-based-on-first-element-then-decreasing-based-on
struct boxCompareHeight {
    bool operator()(const box &a, const box &b) {
        if (a.h == b.h) return a.w > b.w;
        else            return a.h < b.h;
    }
};

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the maximum from index 1 to idx
// @param idx: 指定された範囲におけるインデックスの最大値.
// @param tree: binary indexed tree の 構造を持った配列.
// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.
// -> @return ret: binary indexed tree の 構造を持った配列上で, インデックス 1 ～ idx までの最大値を計算.
int query(int idx, int tree[]) {
    int ret = 0;
    // Returns the sum from index 1 to idx
    // while(idx > 0) ret += tree[idx], idx -= LSB(idx);
    // -> 以下のように修正.
    while(idx > 0) ret = max(ret, tree[idx]), idx -= LSB(idx);
    return ret;
}

// Update each tree[idx] on the larger of k and tree[idx].
// @param idx: 通常の配列における更新対象要素のインデックス.
// @param k: 加算する値.
// @param tree: binary indexed tree の 構造を持った配列.
// @param size: 通常の配列についての配列サイズ.
// @return: none.
void update(int idx, int k, int tree[], int size) {
    // Adds k to element with index idx
    // while(idx < size) tree[idx] += k, idx += LSB(idx);
    // -> 以下のように修正.
    // Update k to element with index idx
    // while(idx < size) tree[idx] = k, idx += LSB(idx);
    // -> sample0.txt, sample1.txt, subtask0_10.txt, subtask0_11.txt, subtask1_10.txt, subtask1_11.txt 以外全てWA.
    // -> 正解者の方々のソースを参照して, 以下のように修正.
    while(idx < size) tree[idx] = max(k, tree[idx]), idx += LSB(idx);
}

int main() {
    
    // 1. 入力情報取得.
    int N;
    cin >> N;
    vector<box> v;
    FOR(i, 0, N) {
        box b;
        cin >> b.w >> b.h;
        v.push_back(b);
    }
    
    // 2. 解説通り.
    // プレゼントの入れ子の最大数を確認.
    // -> Binary Indexed Tree を使うとのこと.
    
    // 2-1. 高さで昇順sort.
    // -> 高さが同じ場合は, 幅の降順sortとする(※解説通り).
    boxCompareHeight bch;
    sort(v.begin(), v.end(), bch);
    // for(auto &p : v) cout << p.w << " " << p.h << endl;
    // cout << endl;

    // 2-2. dp, bit を 計算.
    // dp(i) == i番目の箱を, 最も外側とするとき, 最大何重の入れ子に出来るか.
    // int LIMIT = 10;  // Debug用.
    int LIMIT = 100000;
    int dp[LIMIT + 1] = {};
    // bit(i) == 最も外側の箱の横の長さが, iとなる入れ子の数の最大値.
    int bit[LIMIT + 1] = {};
    dp[0] = 0;
    bit[0] = 0;
    FOR(i, 1, N + 1) {
        dp[i] = query(v[i - 1].w - 1, bit) + 1;
        update(v[i - 1].w, dp[i], bit, LIMIT + 1);
    }
    // FOR(i, 0, LIMIT + 1) cout << "dp=" << dp[i] << " bit=" << bit[i] << endl;
    
    // 3. 出力 ～ 後処理.
    int ans = 0;
    FOR(i, 1, LIMIT + 1) ans = max(ans, dp[i]);
    cout << ans << endl;
    return 0;
    
}

100

101

102

103

// 解き直し.

// AtCoder Beginnar Contest 038解説

// http://abc038.contest.atcoder.jp/data/abc/038/editorial.pdf

#include <bits/stdc++.h>

using namespace std;

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

struct box {

int h; // 高さ.

int w; // 幅.

};

// How do i sort a pair increasing based on first element then decreasing based on second element?

// https://stackoverflow.com/questions/35776189/how-do-i-sort-a-pair-increasing-based-on-first-element-then-decreasing-based-on

struct boxCompareHeight {

bool operator()(const box &a, const box &b) {

if (a.h == b.h) return a.w > b.w;

else return a.h < b.h;

}

};

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the maximum from index 1 to idx

// @param idx: 指定された範囲におけるインデックスの最大値.

// @param tree: binary indexed tree の構造を持った配列.

// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.

// -> @return ret: binary indexed tree の構造を持った配列上で, インデックス 1 ～ idx までの最大値を計算.

int query(int idx, int tree[]) {

int ret = 0;

// Returns the sum from index 1 to idx

// while(idx > 0) ret += tree[idx], idx -= LSB(idx);

// -> 以下のように修正.

while(idx > 0) ret = max(ret, tree[idx]), idx -= LSB(idx);

return ret;

}

// Update each tree[idx] on the larger of k and tree[idx].

// @param idx: 通常の配列における更新対象要素のインデックス.

// @param k: 加算する値.

// @param tree: binary indexed tree の構造を持った配列.

// @param size: 通常の配列についての配列サイズ.

// @return: none.

void update(int idx, int k, int tree[], int size) {

// Adds k to element with index idx

// while(idx < size) tree[idx] += k, idx += LSB(idx);

// -> 以下のように修正.

// Update k to element with index idx

// while(idx < size) tree[idx] = k, idx += LSB(idx);

// -> sample0.txt, sample1.txt, subtask0_10.txt, subtask0_11.txt, subtask1_10.txt, subtask1_11.txt 以外全てWA.

// -> 正解者の方々のソースを参照して, 以下のように修正.

while(idx < size) tree[idx] = max(k, tree[idx]), idx += LSB(idx);

}

int main() {

// 1. 入力情報取得.

int N;

cin >> N;

vector<box> v;

FOR(i, 0, N) {

box b;

cin >> b.w >> b.h;

v.push_back(b);

}

// 2. 解説通り.

// プレゼントの入れ子の最大数を確認.

// -> Binary Indexed Tree を使うとのこと.

// 2-1. 高さで昇順sort.

// -> 高さが同じ場合は, 幅の降順sortとする(※解説通り).

boxCompareHeight bch;

sort(v.begin(), v.end(), bch);

// for(auto &p : v) cout << p.w << " " << p.h << endl;

// cout << endl;

// 2-2. dp, bit を計算.

// dp(i) == i番目の箱を, 最も外側とするとき, 最大何重の入れ子に出来るか.

// int LIMIT = 10; // Debug用.

int LIMIT = 100000;

int dp[LIMIT + 1] = {};

// bit(i) == 最も外側の箱の横の長さが, iとなる入れ子の数の最大値.

int bit[LIMIT + 1] = {};

dp[0] = 0;

bit[0] = 0;

FOR(i, 1, N + 1) {

dp[i] = query(v[i - 1].w - 1, bit) + 1;

update(v[i - 1].w, dp[i], bit, LIMIT + 1);

}

// FOR(i, 0, LIMIT + 1) cout << "dp=" << dp[i] << " bit=" << bit[i] << endl;

// 3. 出力～後処理.

int ans = 0;

FOR(i, 1, LIMIT + 1) ans = max(ans, dp[i]);

cout << ans << endl;

return 0;

}

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

[出力例]
4

[入力例]
8
3 1000
2 3
3 4
2 999
4 7
5 4
1 998
1 2

[出力例]
4

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

[出力例]
7
※(1, 2) -> (2, 3) -> (3, 4) -> (5, 6) -> (7, 8) -> (8, 9) -> (10, 12) で, 7重と分かる.

[入力例]

8 8

5 3

2 2

4 2

2 1

※AtCoderテストケースより

[出力例]

[入力例]

3 1000

2 3

3 4

2 999

4 7

5 4

1 998

1 2

[出力例]

[入力例]

1 2

2 3

5 6

3 4

4 3

4 7

8 9

10 12

7 8

4 4

[出力例]

※(1, 2) -> (2, 3) -> (3, 4) -> (5, 6) -> (7, 8) -> (8, 9) -> (10, 12) で, 7重と分かる.

■Binary Indexed Tree とは？

// Fenwick tree.
// https://en.wikipedia.org/wiki/Fenwick_tree
// Fenwick (Binary Indexed) Trees.
// https://www.hackerearth.com/ja/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/
// Binary Indexed Tree のはなし.
// http://hos.ac/slides/20140319_bit.pdf
#include <bits/stdc++.h>

using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the sum from index 1 to idx
// @param idx: 指定された範囲におけるインデックスの最大値.
// @param tree: binary indexed tree の 構造を持った配列.
// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.
int query(int idx, int tree[]) {
    int ret = 0;
    while(idx > 0) ret += tree[idx], idx -= LSB(idx);
    return ret;
}

// Adds k to element with index idx
// @param idx: 通常の配列における更新対象要素のインデックス.
// @param k: 加算する値.
// @param tree: binary indexed tree の 構造を持った配列.
// @param size: 通常の配列についての配列サイズ.
// @return: none.
void update(int idx, int k, int tree[], int size) {
    while(idx < size) tree[idx] += k, idx += LSB(idx);
}

int main() {
    
    // 1. 変数初期化など.
    int N = 10;
    int tree[N + 1] = {};
    
    // 2. 配列 tree を, 通常の配列として初期化.
    // ex.
    // 1, 2, 4, 8, 16, 32, 64, 128, 256, 512
    FOR(i, 1, N + 1) tree[i] = (1 << (i - 1));
    cout << "---------- initialize as an array -----------------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    
    // 3. 配列 tree を, binary indexed tree の 構造を持った配列として初期化.
    // ex.
    // 1, 3(= 1 + 2), 4, 15(= 1 + 2 + 4 + 8), 16, 48(= 16 + 32), 64, 
    // 255(= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128), 256, 768(= 256 + 512)
    FOR(i, 1, N + 1) tree[i + LSB(i)] += tree[i];
    cout << "---------- initialize as a binary indexed tree ----------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    
    // 4. 累積和確認.
    int a = query(3, tree);
    int b = query(7, tree);
    int c = query(9, tree);
    cout << "---------- check sum as a binary indexed tree -----------" << endl;
    cout << "a=" << a << " b=" << b << " c=" << c << endl;
    
    // 5. 更新確認.
    update(1, 5, tree, 10);
    cout << "---------- updated as a binary indexed tree -------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;
    update(3, 2, tree, 10);
    cout << "---------- updated as a binary indexed tree -------------" << endl;
    FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

    return 0;

}

// Fenwick tree.

// https://en.wikipedia.org/wiki/Fenwick_tree

// Fenwick (Binary Indexed) Trees.

// https://www.hackerearth.com/ja/practice/data-structures/advanced-data-structures/fenwick-binary-indexed-trees/tutorial/

// Binary Indexed Tree のはなし.

// http://hos.ac/slides/20140319_bit.pdf

#include <bits/stdc++.h>

using namespace std;

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the least significant one

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

// Returns the sum from index 1 to idx

// @param idx: 指定された範囲におけるインデックスの最大値.

// @param tree: binary indexed tree の構造を持った配列.

// @return ret: 通常の配列として, インデックス 1 ～ idx までの要素の合計値.

int query(int idx, int tree[]) {

int ret = 0;

while(idx > 0) ret += tree[idx], idx -= LSB(idx);

return ret;

}

// Adds k to element with index idx

// @param idx: 通常の配列における更新対象要素のインデックス.

// @param k: 加算する値.

// @param tree: binary indexed tree の構造を持った配列.

// @param size: 通常の配列についての配列サイズ.

// @return: none.

void update(int idx, int k, int tree[], int size) {

while(idx < size) tree[idx] += k, idx += LSB(idx);

}

int main() {

// 1. 変数初期化など.

int N = 10;

int tree[N + 1] = {};

// 2. 配列 tree を, 通常の配列として初期化.

// ex.

// 1, 2, 4, 8, 16, 32, 64, 128, 256, 512

FOR(i, 1, N + 1) tree[i] = (1 << (i - 1));

cout << "---------- initialize as an array -----------------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

// 3. 配列 tree を, binary indexed tree の構造を持った配列として初期化.

// ex.

// 1, 3(= 1 + 2), 4, 15(= 1 + 2 + 4 + 8), 16, 48(= 16 + 32), 64,

// 255(= 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128), 256, 768(= 256 + 512)

FOR(i, 1, N + 1) tree[i + LSB(i)] += tree[i];

cout << "---------- initialize as a binary indexed tree ----------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

// 4. 累積和確認.

int a = query(3, tree);

int b = query(7, tree);

int c = query(9, tree);

cout << "---------- check sum as a binary indexed tree -----------" << endl;

cout << "a=" << a << " b=" << b << " c=" << c << endl;

// 5. 更新確認.

update(1, 5, tree, 10);

cout << "---------- updated as a binary indexed tree -------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

update(3, 2, tree, 10);

cout << "---------- updated as a binary indexed tree -------------" << endl;

FOR(i, 1, N + 1) cout << "i=" << i << " tree[" << i << "]=" << tree[i] << endl;

return 0;

}

※値の変化が目立つように, 出力結果に, コメント(<--- +5, <--- +2) を追加している.
---------- initialize as an array -----------------------
i=1 tree[1]=1
i=2 tree[2]=2
i=3 tree[3]=4
i=4 tree[4]=8
i=5 tree[5]=16
i=6 tree[6]=32
i=7 tree[7]=64
i=8 tree[8]=128
i=9 tree[9]=256
i=10 tree[10]=512
---------- initialize as a binary indexed tree ----------
i=1 tree[1]=1
i=2 tree[2]=3
i=3 tree[3]=4
i=4 tree[4]=15
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=255
i=9 tree[9]=256
i=10 tree[10]=768
---------- check sum as a binary indexed tree -----------
a=7 b=127 c=511
---------- updated as a binary indexed tree -------------
i=1 tree[1]=6    <--- +5
i=2 tree[2]=8    <--- +5
i=3 tree[3]=4
i=4 tree[4]=20   <--- +5
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=260  <--- +5
i=9 tree[9]=256
i=10 tree[10]=768
---------- updated as a binary indexed tree -------------
i=1 tree[1]=6
i=2 tree[2]=8
i=3 tree[3]=6    <--- +2
i=4 tree[4]=22   <--- +2
i=5 tree[5]=16
i=6 tree[6]=48
i=7 tree[7]=64
i=8 tree[8]=262  <--- +2
i=9 tree[9]=256
i=10 tree[10]=768

※値の変化が目立つように, 出力結果に, コメント(<--- +5, <--- +2) を追加している.

---------- initialize as an array -----------------------

i=1 tree[1]=1

i=2 tree[2]=2

i=3 tree[3]=4

i=4 tree[4]=8

i=5 tree[5]=16

i=6 tree[6]=32

i=7 tree[7]=64

i=8 tree[8]=128

i=9 tree[9]=256

i=10 tree[10]=512

---------- initialize as a binary indexed tree ----------

i=1 tree[1]=1

i=2 tree[2]=3

i=3 tree[3]=4

i=4 tree[4]=15

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=255

i=9 tree[9]=256

i=10 tree[10]=768

---------- check sum as a binary indexed tree -----------

a=7 b=127 c=511

---------- updated as a binary indexed tree -------------

i=1 tree[1]=6 <--- +5

i=2 tree[2]=8 <--- +5

i=3 tree[3]=4

i=4 tree[4]=20 <--- +5

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=260 <--- +5

i=9 tree[9]=256

i=10 tree[10]=768

---------- updated as a binary indexed tree -------------

i=1 tree[1]=6

i=2 tree[2]=8

i=3 tree[3]=6 <--- +2

i=4 tree[4]=22 <--- +2

i=5 tree[5]=16

i=6 tree[6]=48

i=7 tree[7]=64

i=8 tree[8]=262 <--- +2

i=9 tree[9]=256

i=10 tree[10]=768

■参照サイト
AtCoder Beginner Contest 038
Fenwick tree.
Fenwick (Binary Indexed) Trees.
Binary Indexed Tree のはなし.

2019年1月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 034 の問題C（経路) ～問題D (食塩水) を解いてみた.

■感想.
1. 問題C は, AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid) と類似しているように見えたので, この問題の解答をベースに, 対応した.
2. 問題D は, 解答方針が, 全く見えなかったので, 解答を参照して, 解答を組み立てた.
但し, おおよそ, このような内容を解答で説明されているだろう, との推測が多分に含まれていると思われる.
※例えば, テストケース s1.txt の WA回避対応で, 小数第10桁までを出力するように修正している.

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

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

// AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid)
// -> 上記問題をベースに対応.
#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

const LL MOD = 1e9 + 7;

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

int main() {
    
    // 1. 入力情報取得.
    LL W, H;
    cin >> W >> H;
    
    // 2. 経路数 (H + W - 2)! ÷ (H - 1)! ÷ (W - 1)! を 計算.
    // 2-1. 0 ≦ x ≦ H + W - 2 の x!(MOD版) を 計算.
    LL LIMIT = H + W - 2;
    LL FAC[LIMIT + 1] = {};
    FAC[0] = 1;
    FOR(i, 1, LIMIT + 1) FAC[i] = i * FAC[i - 1] % MOD;
    
    // 2-2. 0 ≦ x ≦ H + W - 2 の x!(MOD版)の逆元 を 計算.
    LL INV[LIMIT + 1] = {};
    FOR(i, 0, LIMIT + 1) INV[i] = inverse(FAC[i], MOD - 2) % MOD;
    
    // 2-3. 経路数を計算.
    LL ans = 0LL;
    ans = FAC[H + W - 2];
    ans *= INV[H - 1];
    ans %= MOD;
    ans *= INV[W - 1];
    ans %= MOD;
    
    // 3. 出力 ～ 後処理.
    cout << ans << endl;
    return 0;
    
}

// AtCoder Beginner Contest 042 問題D (いろはちゃんとマス目 / Iroha and a Grid)

// -> 上記問題をベースに対応.

#include <bits/stdc++.h>

using namespace std;

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

typedef long long LL;

const LL MOD = 1e9 + 7;

// Fermat's little theorem を適用するため, 大きな冪乗の計算ができるようにする.

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

// @param b: 指数.

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

LL inverse(LL a, LL b){

LL t = 1;

while(b) {

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

a *= a;

a %= MOD;

b >>= 1;

}

return t % MOD;

}

int main() {

// 1. 入力情報取得.

LL W, H;

cin >> W >> H;

// 2. 経路数 (H + W - 2)! ÷ (H - 1)! ÷ (W - 1)! を計算.

// 2-1. 0 ≦ x ≦ H + W - 2 の x!(MOD版) を計算.

LL LIMIT = H + W - 2;

LL FAC[LIMIT + 1] = {};

FAC[0] = 1;

FOR(i, 1, LIMIT + 1) FAC[i] = i * FAC[i - 1] % MOD;

// 2-2. 0 ≦ x ≦ H + W - 2 の x!(MOD版)の逆元を計算.

LL INV[LIMIT + 1] = {};

FOR(i, 0, LIMIT + 1) INV[i] = inverse(FAC[i], MOD - 2) % MOD;

// 2-3. 経路数を計算.

LL ans = 0LL;

ans = FAC[H + W - 2];

ans *= INV[H - 1];

ans %= MOD;

ans *= INV[W - 1];

ans %= MOD;

// 3. 出力～後処理.

cout << ans << endl;

return 0;

}

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

// 解き直し.
// AtCoder Beginner Contest 034 解説.
// https://www.slideshare.net/chokudai/abc034
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

typedef long long LL;

struct solution {
    LL w;  // 食塩水(グラム).
    LL p;  // 濃度(パーセント).
    double c;  // 計算上の濃度から過不足する食塩量(グラム).
};

// 指定した濃度の食塩水が作成可能であるかを確認.
// @param v: 食塩水の入った容器.
// @param x: 指定した濃度.
// @param K: 選択する容器数.
// @return: 
//    true:  指定した濃度の食塩水を作ることが可能である.
//    false: 指定した濃度の食塩水を作ることが不可能である.
bool check(vector<solution> v, double x, LL K) {
    
    // 食塩の過不足を確認,
    FOR(i, 0, v.size()) v[i].c = v[i].w * (v[i].p - x) / 100;
    
    // 過不足する食塩量で, 降順sort.
    sort(v.begin(), v.end(), [](const solution& x, const solution& y) {return x.c > y.c;});
    
    // 容器を, K個選択して, 食塩水を作ってみる.
    double wTotal = 0.0; // 食塩水の総量.
    double sTotal = 0.0; // 食塩の総量.
    FOR(i, 0, K) wTotal += v[i].w, sTotal += v[i].w * v[i].p;
    double ret = sTotal * 1.0 / wTotal;
    // cout << ret << endl;
    
    // 指定した濃度の食塩水を作ることが 可能 か 不可能か？
    if(ret >= x) return true;
    else         return false;

}

int main() {
    
    // 1. 入力情報取得.
    LL N, K;
    cin >> N >> K;
    vector<solution> v; // 食塩水に関する情報.
    FOR(i, 0, N) {
        LL w, p;
        cin >> w >> p;
        solution s;
        s.w = w;
        s.p = p;
        s.c = 0.0;
        v.push_back(s);
    }
    
    // 2. 解説通り.
    // -> 2分法使う.
    int counter = 0;
    double lower = 0.0;   // 食塩水濃度の下限.
    double upper = 100.0; // 食塩水濃度の上限.
    double ans = 0.0;     // 最終的に求めたい食塩水の濃度.
    while(counter < 50) {
        ans = (lower + upper) / 2;
        if(check(v, ans, K)) lower = ans;
        else                 upper = ans;
        counter++;
    }
    
    
    // 4. 出力 ～ 後処理.
    // s1.txt の WA回避対応.
    // -> AtCoderテストケース(25.000000000)より, 小数第10桁までで出力するように修正.
    cout << fixed;
    cout << setprecision(10) << ans << endl;
    return 0;
    
}

// 解き直し.

// AtCoder Beginner Contest 034 解説.

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

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(LL i = (a); i < (b); ++i)

typedef long long LL;

struct solution {

LL w; // 食塩水(グラム).

LL p; // 濃度(パーセント).

double c; // 計算上の濃度から過不足する食塩量(グラム).

};

// 指定した濃度の食塩水が作成可能であるかを確認.

// @param v: 食塩水の入った容器.

// @param x: 指定した濃度.

// @param K: 選択する容器数.

// @return:

// true: 指定した濃度の食塩水を作ることが可能である.

// false: 指定した濃度の食塩水を作ることが不可能である.

bool check(vector<solution> v, double x, LL K) {

// 食塩の過不足を確認,

FOR(i, 0, v.size()) v[i].c = v[i].w * (v[i].p - x) / 100;

// 過不足する食塩量で, 降順sort.

sort(v.begin(), v.end(), [](const solution& x, const solution& y) {return x.c > y.c;});

// 容器を, K個選択して, 食塩水を作ってみる.

double wTotal = 0.0; // 食塩水の総量.

double sTotal = 0.0; // 食塩の総量.

FOR(i, 0, K) wTotal += v[i].w, sTotal += v[i].w * v[i].p;

double ret = sTotal * 1.0 / wTotal;

// cout << ret << endl;

// 指定した濃度の食塩水を作ることが可能か不可能か？

if(ret >= x) return true;

else return false;

}

int main() {

// 1. 入力情報取得.

LL N, K;

cin >> N >> K;

vector<solution> v; // 食塩水に関する情報.

FOR(i, 0, N) {

LL w, p;

cin >> w >> p;

solution s;

s.w = w;

s.p = p;

s.c = 0.0;

v.push_back(s);

}

// 2. 解説通り.

// -> 2分法使う.

int counter = 0;

double lower = 0.0; // 食塩水濃度の下限.

double upper = 100.0; // 食塩水濃度の上限.

double ans = 0.0; // 最終的に求めたい食塩水の濃度.

while(counter < 50) {

ans = (lower + upper) / 2;

if(check(v, ans, K)) lower = ans;

else upper = ans;

counter++;

}

// 4. 出力～後処理.

// s1.txt の WA回避対応.

// -> AtCoderテストケース(25.000000000)より, 小数第10桁までで出力するように修正.

cout << fixed;

cout << setprecision(10) << ans << endl;

return 0;

}

[入力例]
3 2
100 15
300 20
200 30

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

[入力例]
3 2
100 60
300 25
200 30

[出力例]
40.0000000000

[入力例]
6 3
100 30
200 20
300 50
400 40
500 15
600 25

[出力例]
42.5000000000
※(300, 5), (400, 40), (100, 30) を 選択すると, 42.5000000000% を実現できる.

[入力例]
10 4
100 60
200 30
300 40
400 45
500 40
600 50
700 30
800 25
900 20
1000 35

[出力例]
47.1428571429
※(100, 60), (300, 40), (400, 45), (600, 50) を 選択すると, 47.1428571429% を実現できる.

[入力例]
1 1
1 0

[出力例]
0.0000000000
-> 仮に, 小数点以下10桁指定しないと, 7.88861e-29 のように出力される.
-> このように, 0 と出力されないので, s1.txt で, WA判定されたと推測した.

[入力例]

3 2

100 15

300 20

200 30

[出力例]

25.0000000000

※AtCoderテストケースより

[入力例]

3 2

100 60

300 25

200 30

[出力例]

40.0000000000

[入力例]

6 3

100 30

200 20

300 50

400 40

500 15

600 25

[出力例]

42.5000000000

※(300, 5), (400, 40), (100, 30) を選択すると, 42.5000000000% を実現できる.

[入力例]

10 4

100 60

200 30

300 40

400 45

500 40

600 50

700 30

800 25

900 20

1000 35

[出力例]

47.1428571429

※(100, 60), (300, 40), (400, 45), (600, 50) を選択すると, 47.1428571429% を実現できる.

[入力例]

1 1

1 0

[出力例]

0.0000000000

-> 仮に, 小数点以下10桁指定しないと, 7.88861e-29 のように出力される.

-> このように, 0 と出力されないので, s1.txt で, WA判定されたと推測した.

■参照サイト
AtCoder Beginner Contest 034

月: 2019年1月

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

C++の練習を兼ねて, AtCoder Beginner Contest 084 の問題C（Special Trains) ～問題D (2017-like Number) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 083 の問題C（Multiple Gift) ～問題D (Wide Flip) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 081 の問題C（Not so Diverse) ～問題D (Non-decreasing) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題B（Box and Ball) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

Python の動作確認をしてみた（１）

Python 3 の練習を兼ねて, AtCoder Regular Contest 002 の問題B（割り切れる日付) ～問題C (コマンド入力) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題C（単調増加) ～問題D (プレゼント) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 034 の問題C（経路) ～問題D (食塩水) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 084 の 問題C（Special Trains) ～ 問題D (2017-like Number) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 083 の 問題C（Multiple Gift) ～ 問題D (Wide Flip) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 081 の 問題C（Not so Diverse) ～ 問題D (Non-decreasing) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題C（C – Knot Puzzle) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の 問題B（Box and Ball) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 113 の 問題C（ID) ～ 問題D (Number of Amidakuji) を解いてみた.

Python 3 の練習を兼ねて, AtCoder Regular Contest 002 の 問題B（割り切れる日付) ～ 問題C (コマンド入力) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の 問題C（単調増加) ～ 問題D (プレゼント) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 034 の 問題C（経路) ～ 問題D (食塩水) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 084 の問題C（Special Trains) ～問題D (2017-like Number) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 083 の問題C（Multiple Gift) ～問題D (Wide Flip) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 081 の問題C（Not so Diverse) ～問題D (Non-decreasing) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題C（C – Knot Puzzle) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 002 の問題B（Box and Ball) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 113 の問題C（ID) ～問題D (Number of Amidakuji) を解いてみた.

Python 3 の練習を兼ねて, AtCoder Regular Contest 002 の問題B（割り切れる日付) ～問題C (コマンド入力) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 038 の問題C（単調増加) ～問題D (プレゼント) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 034 の問題C（経路) ～問題D (食塩水) を解いてみた.