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

C++の練習を兼ねて, AtCoder Regular Contest 069 の問題E (Frequency) を解いてみた.

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

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

■C++版プログラム(問題E／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--)
#define pb push_back
#define a first
#define b second
LL ans[101010];

struct Mt{
    int c; // 石の個数.
    int i; // 山の番号.
    bool operator < (const Mt &rhs) const {
        return (c < rhs.c) || ((c == rhs.c) && (i > rhs.i));
    }
};

int main(){
    
    // 1. 入力情報.
    int N, a;
    scanf("%d", &N);
    priority_queue<Mt> pq;
    Mt mt;
    map<LL, LL> m;
    rep(i, N){
        scanf("%d", &a);
        mt.c = a;
        mt.i = i + 1;
        pq.push(mt); // {石の個数, 山の番号}
        m[mt.c]++;
    }
    
    // 2. 番兵.
    mt.c = 0;
    mt.i = 0;
    pq.push(mt);
    m[0] = 0;
    
    // 3. 累積和.
    LL t = 0;
    map<LL, LL> sCum;
    map<LL, LL>::reverse_iterator it;
    for(it=m.rbegin(); it!=m.rend(); ++it){
        t += it->b;      // 山の個数.
        sCum[it->a] = t; // 累積和を保存.
    }
    sCum[0] = 0; // 番兵分は, 除外.
    // for(auto &p : sCum) printf("key=%lld val=%lld\n", p.a, p.b);
    
    // 4. 集計.
    // 石の個数が変化したら, 山の番号を確認し, 減少していたら更新.
    LL cur = 0, bef = 0, idx = 101010;
    while(!pq.empty()){
        // 4-1. 要素を一つ取得.
        Mt m = pq.top();
        pq.pop();
        
        // 4-2. 現在の石の個数を取得.
        cur = (LL)m.c;
        
        // 4-3. 初回設定.
        if(idx == 101010) idx = m.i;
        
        // 4-4. 前回と変わっていたら, 更新.
        if(cur != bef){
            // 石の個数をカウント.
            ans[idx] += (bef - cur) * sCum[bef];
            
            // 山の番号を更新.
            if(idx > m.i) idx = m.i;
        }
        
        // 4-5. 前回分更新.
        bef = cur;
        // printf("c=%d i=%d\n", m.c, m.i);
    }
    
    // 5. 出力.
    repx(i, 1, N + 1) printf("%lld\n", ans[i]);
    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--)

#define pb push_back

#define a first

#define b second

LL ans[101010];

struct Mt{

int c; // 石の個数.

int i; // 山の番号.

bool operator < (const Mt &rhs) const {

return (c < rhs.c) || ((c == rhs.c) && (i > rhs.i));

}

};

int main(){

// 1. 入力情報.

int N, a;

scanf("%d", &N);

priority_queue<Mt> pq;

Mt mt;

map<LL, LL> m;

rep(i, N){

scanf("%d", &a);

mt.c = a;

mt.i = i + 1;

pq.push(mt); // {石の個数, 山の番号}

m[mt.c]++;

}

// 2. 番兵.

mt.c = 0;

mt.i = 0;

pq.push(mt);

m[0] = 0;

// 3. 累積和.

LL t = 0;

map<LL, LL> sCum;

map<LL, LL>::reverse_iterator it;

for(it=m.rbegin(); it!=m.rend(); ++it){

t += it->b; // 山の個数.

sCum[it->a] = t; // 累積和を保存.

}

sCum[0] = 0; // 番兵分は, 除外.

// for(auto &p : sCum) printf("key=%lld val=%lld\n", p.a, p.b);

// 4. 集計.

// 石の個数が変化したら, 山の番号を確認し, 減少していたら更新.

LL cur = 0, bef = 0, idx = 101010;

while(!pq.empty()){

// 4-1. 要素を一つ取得.

Mt m = pq.top();

pq.pop();

// 4-2. 現在の石の個数を取得.

cur = (LL)m.c;

// 4-3. 初回設定.

if(idx == 101010) idx = m.i;

// 4-4. 前回と変わっていたら, 更新.

if(cur != bef){

// 石の個数をカウント.

ans[idx] += (bef - cur) * sCum[bef];

// 山の番号を更新.

if(idx > m.i) idx = m.i;

}

// 4-5. 前回分更新.

bef = cur;

// printf("c=%d i=%d\n", m.c, m.i);

}

// 5. 出力.

repx(i, 1, N + 1) printf("%lld\n", ans[i]);

return 0;

}

[入力例]
2
1 2

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

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

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

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

[出力例]
22
0
8
0
16
0
0
0
0
0
0
0

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

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

[入力例]
20
3 3 5 5 7 7 5 5 3 3 11 11 15 15 55 11 33 33 55 11

[出力例]
60
0
32
0
24
0
0
0
0
0
40
0
24
0
116
0
0
0
0
0

[入力例]

1 2

[出力例]

※AtCoderのテストケースより

[入力例]

1 2 1 3 2 4 2 5 8 1

[出力例]

※AtCoderのテストケースより

[入力例]

2 1 3 3 7 7 7 5 5 2 3 1

[出力例]

[入力例]

1 2 3 4 5 6 7

[出力例]

[入力例]

3 3 5 5 7 7 5 5 3 3 11 11 15 15 55 11 33 33 55 11

[出力例]

116

■参照サイト
AtCoder Regular Contest 069

C++の練習を兼ねて, AtCoder Regular Contest 069 の 問題E (Frequency) を解いてみた.

コメントを残す コメントをキャンセル

C++の練習を兼ねて, AtCoder Regular Contest 069 の問題E (Frequency) を解いてみた.

コメントを残すコメントをキャンセル