個人用メモ帳

2021年2月9日2021年2月9日

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

C++の練習を兼ねて, AtCoder Regular Contest 084 の問題D (Small Multiple)を解いてみた.

■感想.
1. 問題Dは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 01-BFS の復習が出来たので良かったと思う.
3. 実装に苦労したものの, 個人的には, 非常に面白い問題に感じた.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc084/editorial.pdf
// 01-BFSのちょっと丁寧な解説
// https://betrue12.hateblo.jp/entry/2018/12/08/000020
// C++(GCC 9.2.1)
#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 pof pop_front
#define pob pop_back
#define pub push_back
#define puf push_front
const int INF = 2020202020;
int d[101010];

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. 01-BFS(解説通り).
    // https://ja.wikipedia.org/wiki/幅優先探索
    // -> 01-BFS版へ修正.
    auto bfs01 = [&](int s){
        // 2-1. 空のキュー.
        deque<int> dq;
        
        // 2-2. 探索開始地点 s の コスト設定.
        d[s] = 0;
        
        // 2-3. 探索開始地点 s をキュー に追加.
        dq.pub(s);
        while(!dq.empty()){
            // 2-4. キュー の 先頭要素を取り出す.
            int u = dq.front();
            dq.pof();
            
            // 2-5. コストを計算して, 小さい場合に, コストを更新.
            // コスト 0 における遷移(※コストの更新式で, +0 とする点に要注意).
            int u0 = u * 10 % K; // 10倍.
            if(d[u0] > d[u] + 0) d[u0] = d[u] + 0, dq.puf(u0);
            
            // コスト 1 における遷移.
            int u1 = (u + 1) % K; // 1加算.
            if(d[u1] > d[u] + 1) d[u1] = d[u] + 1, dq.pub(u1);
        }
        return;
    };
    rep(i, 101010) d[i] = INF;
    bfs01(1);
    
    // 3. 出力.
    printf("%d", d[0] + 1);
    return 0;
    
}

// 解き直し.

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

// 01-BFSのちょっと丁寧な解説

// https://betrue12.hateblo.jp/entry/2018/12/08/000020

// C++(GCC 9.2.1)

#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 pof pop_front

#define pob pop_back

#define pub push_back

#define puf push_front

const int INF = 2020202020;

int d[101010];

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. 01-BFS(解説通り).

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

// -> 01-BFS版へ修正.

auto bfs01 = [&](int s){

// 2-1. 空のキュー.

deque<int> dq;

// 2-2. 探索開始地点 s のコスト設定.

d[s] = 0;

// 2-3. 探索開始地点 s をキューに追加.

dq.pub(s);

while(!dq.empty()){

// 2-4. キューの先頭要素を取り出す.

int u = dq.front();

dq.pof();

// 2-5. コストを計算して, 小さい場合に, コストを更新.

// コスト 0 における遷移(※コストの更新式で, +0 とする点に要注意).

int u0 = u * 10 % K; // 10倍.

if(d[u0] > d[u] + 0) d[u0] = d[u] + 0, dq.puf(u0);

// コスト 1 における遷移.

int u1 = (u + 1) % K; // 1加算.

if(d[u1] > d[u] + 1) d[u1] = d[u] + 1, dq.pub(u1);

}

return;

};

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

bfs01(1);

// 3. 出力.

printf("%d", d[0] + 1);

return 0;

}

[入力例]
6

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

[入力例]
41

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

[入力例]
79992

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

[入力例]
2019

[出力例]
3

[入力例]
2020

[出力例]
2

[入力例]
2021

[出力例]
3

[入力例]
753

[出力例]
3

[入力例]
33333

[出力例]
15

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

79992

[出力例]

※AtCoderのテストケースより

[入力例]

2019

[出力例]

[入力例]

2020

[出力例]

[入力例]

2021

[出力例]

[入力例]

753

[出力例]

[入力例]

33333

[出力例]

■参照サイト
AtCoder Regular Contest 084
01-BFSのちょっと丁寧な解説

2021年2月9日

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

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

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 実装に苦労したものの, 個人的には, 非常に面白い問題に感じた.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/arc080/editorial.pdf
// 参考資料.
// https://atcoder.jp/contests/pakencamp-2020-day1/editorial/527
// C++(GCC 9.2.1)
#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
const int INF = 2020202020;
int p[202020], pos[202020];

struct section{
    int l, r, a; // 半開区間[l, r) と, 区間内 の 偶数番目の最小値 を 保存.
    bool operator < (const section& rhs) const{
        return a > rhs.a;
    }
};

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)
// -> 一部改変(2021/02/05).
template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{
public:
    SegmentTree() : SegmentTree(0){}
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}
    explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod(){
        return d[1];
    }
private:
    int _n, size, log;
    vector<S> d;
    void update(int k){
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};

static int RMiQ_nodef(int l, int r){
    return min(l, r);
}
static int RMiQ_ef(){
    return INF;
}
using RMiQ = SegmentTree<int, RMiQ_nodef, RMiQ_ef>;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        scanf("%d", &p[i]);
        pos[p[i]] = i; // p[i] の 出現位置.
    }
    
    // 2. 前処理.
    RMiQ eSeg(N + 2); // 偶数番目だけ保存.
    RMiQ oSeg(N + 2); // 奇数番目だけ保存.
    rep(i, N){
        if(i & 1) oSeg.set(i, p[i]);
        else      eSeg.set(i, p[i]);
    }
    
    // 3. 操作を繰り返す.
    vector<int> q;
    priority_queue<section> pq;
    
    // 3-1. 全区間を保存.
    int qe = 0, posQe = 0, qo = 0, posQo = 0;
    section s;
    s.l = 0, s.r = N, s.a = eSeg.prod(s.l, s.r);
    pq.push(s);
    while(!pq.empty() && q.size() < N){
        // 3-2. 区間を一つ取り出す.
        s = pq.top();
        pq.pop();
        
        // 偶数番目を見る.
        if(s.r > s.l){
            // 3-3. 最小の要素は？
            if(s.l & 1) qe = oSeg.prod(s.l, s.r);
            else        qe = eSeg.prod(s.l, s.r);
            
            // 3-4. 最小の要素の出現場所は？
            posQe = pos[qe];
            
            // 3-5. 数列 q に追加.
            q.pb(qe);
        }
        
        // 奇数番目を見る.
        if(s.r > posQe + 1){
            // 3-6. 最小の要素は？
            if(s.l & 1) qo = eSeg.prod(posQe + 1, s.r);
            else        qo = oSeg.prod(posQe + 1, s.r);
            
            // 3-7. 最小の要素の出現場所は？
            posQo = pos[qo];
            
            // 3-8. 数列 q に追加.
            q.pb(qo);
        }
        // printf("qe=%d posQe=%d qo=%d posQo=%d\n", qe, posQe, qo, posQo);
        
        // 3-9. 区間分割／保存.
        section sl, sm, sr;
        // 左.
        if(posQe > s.l + 1){
            sl.l = s.l;
            sl.r = posQe;
            if(sl.l & 1) sl.a = oSeg.prod(sl.l, sl.r);
            else         sl.a = eSeg.prod(sl.l, sl.r);
            pq.push(sl);
        }
        // 中央.
        if(posQo > posQe + 1){
            sm.l = posQe + 1;
            sm.r = posQo;
            if(sm.l & 1) sm.a = oSeg.prod(sm.l, sm.r);
            else         sm.a = eSeg.prod(sm.l, sm.r);
            pq.push(sm);
        }
        // 右.
        if(s.r > posQo + 1){
            sr.l = posQo + 1;
            sr.r = s.r;
            if(sr.l & 1) sr.a = oSeg.prod(sr.l, sr.r);
            else         sr.a = eSeg.prod(sr.l, sr.r);
            pq.push(sr);
        }
        // if(posQe > s.l + 1)   printf("sl.l=%d sl.r=%d sl.a=%d\n", sl.l, sl.r, sl.a);
        // if(posQo > posQe + 1) printf("sm.l=%d sm.r=%d sm.a=%d\n", sm.l, sm.r, sm.a);
        // if(s.r > posQo + 1)   printf("sr.l=%d sr.r=%d sr.a=%d\n", sr.l, sr.r, sr.a);
    }
    
    // 4. 出力.
    int ql = q.size();
    rep(i, ql){
        printf("%d", q[i]);
        printf("%s", (i < ql - 1) ? " " : "\n");
    }
    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

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

// 解き直し.

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

// 参考資料.

// https://atcoder.jp/contests/pakencamp-2020-day1/editorial/527

// C++(GCC 9.2.1)

#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

const int INF = 2020202020;

int p[202020], pos[202020];

struct section{

int l, r, a; // 半開区間[l, r) と, 区間内の偶数番目の最小値を保存.

bool operator < (const section& rhs) const{

return a > rhs.a;

}

};

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)

// -> 一部改変(2021/02/05).

template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{

public:

SegmentTree() : SegmentTree(0){}

explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}

explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

rep(i, _n) d[size + i] = v[i];

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

return d[p + size];

}

S prod(int l, int r){

assert(0 <= l && l <= r && r <= _n);

S sml = e(), smr = e();

l += size;

r += size;

while(l < r){

if(l & 1) sml = op(sml, d[l++]);

if(r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod(){

return d[1];

}

private:

int _n, size, log;

vector<S> d;

void update(int k){

d[k] = op(d[2 * k], d[2 * k + 1]);

}

};

static int RMiQ_nodef(int l, int r){

return min(l, r);

}

static int RMiQ_ef(){

return INF;

}

using RMiQ = SegmentTree<int, RMiQ_nodef, RMiQ_ef>;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

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

pos[p[i]] = i; // p[i] の出現位置.

}

// 2. 前処理.

RMiQ eSeg(N + 2); // 偶数番目だけ保存.

RMiQ oSeg(N + 2); // 奇数番目だけ保存.

rep(i, N){

if(i & 1) oSeg.set(i, p[i]);

else eSeg.set(i, p[i]);

}

// 3. 操作を繰り返す.

vector<int> q;

priority_queue<section> pq;

// 3-1. 全区間を保存.

int qe = 0, posQe = 0, qo = 0, posQo = 0;

section s;

s.l = 0, s.r = N, s.a = eSeg.prod(s.l, s.r);

pq.push(s);

while(!pq.empty() && q.size() < N){

// 3-2. 区間を一つ取り出す.

s = pq.top();

pq.pop();

// 偶数番目を見る.

if(s.r > s.l){

// 3-3. 最小の要素は？

if(s.l & 1) qe = oSeg.prod(s.l, s.r);

else qe = eSeg.prod(s.l, s.r);

// 3-4. 最小の要素の出現場所は？

posQe = pos[qe];

// 3-5. 数列 q に追加.

q.pb(qe);

}

// 奇数番目を見る.

if(s.r > posQe + 1){

// 3-6. 最小の要素は？

if(s.l & 1) qo = eSeg.prod(posQe + 1, s.r);

else qo = oSeg.prod(posQe + 1, s.r);

// 3-7. 最小の要素の出現場所は？

posQo = pos[qo];

// 3-8. 数列 q に追加.

q.pb(qo);

}

// printf("qe=%d posQe=%d qo=%d posQo=%d\n", qe, posQe, qo, posQo);

// 3-9. 区間分割／保存.

section sl, sm, sr;

// 左.

if(posQe > s.l + 1){

sl.l = s.l;

sl.r = posQe;

if(sl.l & 1) sl.a = oSeg.prod(sl.l, sl.r);

else sl.a = eSeg.prod(sl.l, sl.r);

pq.push(sl);

}

// 中央.

if(posQo > posQe + 1){

sm.l = posQe + 1;

sm.r = posQo;

if(sm.l & 1) sm.a = oSeg.prod(sm.l, sm.r);

else sm.a = eSeg.prod(sm.l, sm.r);

pq.push(sm);

}

// 右.

if(s.r > posQo + 1){

sr.l = posQo + 1;

sr.r = s.r;

if(sr.l & 1) sr.a = oSeg.prod(sr.l, sr.r);

else sr.a = eSeg.prod(sr.l, sr.r);

pq.push(sr);

}

// if(posQe > s.l + 1) printf("sl.l=%d sl.r=%d sl.a=%d\n", sl.l, sl.r, sl.a);

// if(posQo > posQe + 1) printf("sm.l=%d sm.r=%d sm.a=%d\n", sm.l, sm.r, sm.a);

// if(s.r > posQo + 1) printf("sr.l=%d sr.r=%d sr.a=%d\n", sr.l, sr.r, sr.a);

}

// 4. 出力.

int ql = q.size();

rep(i, ql){

printf("%d", q[i]);

printf("%s", (i < ql - 1) ? " " : "\n");

}

return 0;

}

[入力例]
4
3 2 4 1

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

[入力例]
2
1 2

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

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

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

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

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

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

[出力例]
2 3 6 4 8 7 10 13 12 20 14 1 11 15 16 5 9 19 18 17

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

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

[入力例]

3 2 4 1

[出力例]

3 1 2 4

※AtCoderのテストケースより

[入力例]

1 2

[出力例]

1 2

※AtCoderのテストケースより

[入力例]

4 6 3 2 8 5 7 1

[出力例]

3 1 2 7 4 6 8 5

※AtCoderのテストケースより

[入力例]

11 5 4 3 1 2 6 7 9 8 10 12

[出力例]

1 2 4 3 6 7 9 8 10 12 11 5

[入力例]

14 11 15 1 12 20 2 6 4 16 9 19 5 3 8 10 13 7 18 17

[出力例]

2 3 6 4 8 7 10 13 12 20 14 1 11 15 16 5 9 19 18 17

[入力例]

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

[出力例]

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

■参照サイト
AtCoder Regular Contest 080
パ研合宿2020 第1日「SpeedRun」／N – 背の順解説／セグメント木（Range Minimum Query）の使い方を参考にしました

2021年2月7日

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の問題C (Digital Graffiti), 問題E (Come Back Quickly) ～問題F (GCD or MIN) を解いてみた.

■感想.
1. 問題C, 問題E, 問題Fは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
※ 問題D は, よくわからなかったので, スキップ(汗)
2. ダイクストラ法の復習が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 191 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc191/editorial/612
// C++(GCC 9.2.1)
#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 board[22][22];

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    rep(i, H){
        char c[22];
        scanf("%s", c);
        rep(j, W) if(c[j] == '#') board[i][j] = 1;
    }
    
    // 2. 頂点を探索(周囲四マスを調べる).
    int ans = 0;
    rep(i, H - 1){
        rep(j, W - 1){
            int count = 0;
            count += board[i][j];
            count += board[i + 1][j];
            count += board[i][j + 1];
            count += board[i + 1][j + 1];
            if(count == 1 || count == 3) ans++;
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc191/editorial/612

// C++(GCC 9.2.1)

#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 board[22][22];

int main(){

// 1. 入力情報.

int H, W;

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

rep(i, H){

char c[22];

scanf("%s", c);

rep(j, W) if(c[j] == '#') board[i][j] = 1;

}

// 2. 頂点を探索(周囲四マスを調べる).

int ans = 0;

rep(i, H - 1){

rep(j, W - 1){

int count = 0;

count += board[i][j];

count += board[i + 1][j];

count += board[i][j + 1];

count += board[i + 1][j + 1];

if(count == 1 || count == 3) ans++;

}

// 3. 出力.

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

return 0;

}

[入力例]
5 5
.....
.###.
.###.
.###.
.....

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

[入力例]
7 7
.......
..###..
.#####.
.#####.
.#####.
..###..
.......

[出力例]
12

[入力例]

5 5

.....

.###.

.....

[出力例]

※AtCoderテストケースより

[入力例]

7 7

.......

..###..

.#####.

..###..

.......

[出力例]

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

// 解き直し.
// https://atcoder.jp/contests/abc191/editorial/610
// C++(GCC 9.2.1)
#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
const LL INF = 202020202020202020;

struct edge{
    int n; // 次の頂点.
    LL c;  // 移動時間.
    bool operator < (const edge &E) const{ return c > E.c; }
};

LL d[2020][2020]; // i -> j の 移動時間.
LL ds[2020];      // i -> i の 移動時間.
LL ans[2020];     // 出力用.
vector<edge> G[2020];

int main(){
    
    // 1. 入力情報.
    int N, M;
    scanf("%d %d", &N, &M);
    rep(i, N) rep(j, N) d[i][j] = INF;
    rep(i, N) ds[i] = INF;
    rep(i, M){
        int a, b;
        LL c;
        scanf("%d %d %lld", &a, &b, &c);
        a--, b--;
        edge e;
        e.n = b;
        e.c = c;
        G[a].pb(e);                       // a -> b.
        if(a == b) ds[a] = min(ds[a], c); // a -> a.  (random_10.txt の WA回避？)
    }
    
    // 2. ダイクストラ法.
    // https://ja.wikipedia.org/wiki/ダイクストラ法
    auto dijkstra = [&](int s){
        // 1. 初期化.
        priority_queue<edge> pq;
        
        // 2. 始点設定.
        d[s][s] = 0;
        pq.push({s, 0LL});
        
        // 3. キュー pq が 空になるまで, 探索.
        while(!pq.empty()){
            // 4. 探索を継続するために, 頂点を取得.
            edge e = pq.top();
            pq.pop();
            int cn = e.n;
            LL cc = e.c;
            
            // 4. 各隣接する頂点について, 距離を確認し, 移動時間を更新.
            for(auto &g : G[cn]){
                int nn = g.n;
                LL nc = cc + g.c;
                
                // 5. 移動時間更新.
                if(d[s][nn] > nc) d[s][nn] = nc, pq.push({nn, nc});
            }
        }
        return;
    };
    
    // 3. 各頂点に対して, 最短経路を求める.
    rep(i, N) dijkstra(i);
    
    // 4. 出力用の情報を作成.
    rep(i, N){
        ans[i] = ds[i];
        rep(j, N) if(i != j) ans[i] = min(ans[i], d[i][j] + d[j][i]);
    }
    rep(i, N) if(ans[i] >= INF) ans[i] = -1;
    
    // 5. 出力.
    rep(i, N) printf("%lld\n", ans[i]);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc191/editorial/610

// C++(GCC 9.2.1)

#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

const LL INF = 202020202020202020;

struct edge{

int n; // 次の頂点.

LL c; // 移動時間.

bool operator < (const edge &E) const{ return c > E.c; }

};

LL d[2020][2020]; // i -> j の移動時間.

LL ds[2020]; // i -> i の移動時間.

LL ans[2020]; // 出力用.

vector<edge> G[2020];

int main(){

// 1. 入力情報.

int N, M;

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

rep(i, N) rep(j, N) d[i][j] = INF;

rep(i, N) ds[i] = INF;

rep(i, M){

int a, b;

LL c;

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

a--, b--;

edge e;

e.n = b;

e.c = c;

G[a].pb(e); // a -> b.

if(a == b) ds[a] = min(ds[a], c); // a -> a. (random_10.txt の WA回避？)

}

// 2. ダイクストラ法.

// https://ja.wikipedia.org/wiki/ダイクストラ法

auto dijkstra = [&](int s){

// 1. 初期化.

priority_queue<edge> pq;

// 2. 始点設定.

d[s][s] = 0;

pq.push({s, 0LL});

// 3. キュー pq が空になるまで, 探索.

while(!pq.empty()){

// 4. 探索を継続するために, 頂点を取得.

edge e = pq.top();

pq.pop();

int cn = e.n;

LL cc = e.c;

// 4. 各隣接する頂点について, 距離を確認し, 移動時間を更新.

for(auto &g : G[cn]){

int nn = g.n;

LL nc = cc + g.c;

// 5. 移動時間更新.

if(d[s][nn] > nc) d[s][nn] = nc, pq.push({nn, nc});

}

return;

};

// 3. 各頂点に対して, 最短経路を求める.

rep(i, N) dijkstra(i);

// 4. 出力用の情報を作成.

rep(i, N){

ans[i] = ds[i];

rep(j, N) if(i != j) ans[i] = min(ans[i], d[i][j] + d[j][i]);

}

rep(i, N) if(ans[i] >= INF) ans[i] = -1;

// 5. 出力.

rep(i, N) printf("%lld\n", ans[i]);

return 0;

}

[入力例]
4 4
1 2 5
2 3 10
3 1 15
4 3 20

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

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

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

[入力例]
4 7
1 2 10
2 3 30
1 4 15
3 4 25
3 4 20
4 3 20
4 3 30

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

[入力例]
10 20
4 4 530
1 6 537
3 1 2004
6 3 420
7 8 1766
7 6 1114
2 10 751
1 10 466
2 2 358
3 6 1263
4 2 584
9 7 1252
8 1 1122
7 7 210
5 2 1285
3 10 536
8 8 18
8 5 405
4 8 1078
7 5 695

[出力例]
2961
358
1683
530
-1
1683
210
18
-1
-1

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

[出力例]
7
32
11
16
22
26
42
16
42
-1
11
38
47
22
16

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

[入力例]

4 4

1 2 5

2 3 10

3 1 15

4 3 20

[出力例]

-1

※AtCoderテストケースより

[入力例]

4 6

1 2 5

1 3 10

2 4 5

3 4 10

4 1 10

1 1 10

[出力例]

※AtCoderテストケースより

[入力例]

4 7

1 2 10

2 3 30

1 4 15

3 4 25

3 4 20

4 3 20

4 3 30

[出力例]

-1

※AtCoderテストケースより

[入力例]

10 20

4 4 530

1 6 537

3 1 2004

6 3 420

7 8 1766

7 6 1114

2 10 751

1 10 466

2 2 358

3 6 1263

4 2 584

9 7 1252

8 1 1122

7 7 210

5 2 1285

3 10 536

8 8 18

8 5 405

4 8 1078

7 5 695

[出力例]

2961

358

1683

530

-1

1683

210

-1

[入力例]

15 35

4 11 15

15 6 19

12 4 9

14 5 6

4 7 7

1 1 11

8 9 20

7 3 20

15 4 4

15 4 20

1 5 12

14 3 12

1 1 7

6 15 7

4 8 7

11 14 10

2 8 3

5 10 5

11 12 14

15 6 20

8 13 12

5 11 6

2 10 19

8 15 5

2 8 16

13 1 10

9 3 16

5 2 10

11 3 10

6 11 2

6 5 20

8 1 7

3 11 1

3 8 6

2 4 10

[出力例]

-1

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

// 解き直し.
// https://atcoder.jp/contests/abc191/editorial/586
// C++(GCC 9.2.1)
#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 a first
#define b second
LL a[2020];

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数(※1以上).
set<LL> div(LL X){
    set<LL> ret;
    for(LL d = 1; d * d <= X; d++){
        if(!(X % d)){
            ret.insert(d);
            if(d * d != X) ret.insert(X / d);
        }
    }
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // ※解説通り.
    // 2. 最小値計算.
    LL minA = 202020202020202020;
    rep(i, N) minA = min(minA, a[i]);
    
    // 3. 連想配列に計算結果を保存.
    map<LL, LL> m;
    rep(i, N){
        set<LL> divisors = div(a[i]);
        for(auto &p : divisors){
            if(!m.count(p)) m[p] = a[i];
            else            m[p] = __gcd(m[p], a[i]);
        }
    }
    
    // 4. 条件を満たすものをカウント.
    int ans = 0;
    for(auto &p : m) if(p.a == p.b && p.a <= minA) ans++;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc191/editorial/586

// C++(GCC 9.2.1)

#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 a first

#define b second

LL a[2020];

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数(※1以上).

set<LL> div(LL X){

set<LL> ret;

for(LL d = 1; d * d <= X; d++){

if(!(X % d)){

ret.insert(d);

if(d * d != X) ret.insert(X / d);

}

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &a[i]);

// ※解説通り.

// 2. 最小値計算.

LL minA = 202020202020202020;

rep(i, N) minA = min(minA, a[i]);

// 3. 連想配列に計算結果を保存.

map<LL, LL> m;

rep(i, N){

set<LL> divisors = div(a[i]);

for(auto &p : divisors){

if(!m.count(p)) m[p] = a[i];

else m[p] = __gcd(m[p], a[i]);

}

// 4. 条件を満たすものをカウント.

int ans = 0;

for(auto &p : m) if(p.a == p.b && p.a <= minA) ans++;

// 5. 出力.

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

return 0;

}

[入力例]
3
6 9 12

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

[入力例]
4
8 2 12 6

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

[入力例]
7
30 28 33 49 27 37 48

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

[入力例]
20
109 27 40 25 61 44 18 65 11 119 122 68 14 112 118 72 26 81 71 60

[出力例]
10

[入力例]
30
10424 3725 8181 11925 2195 11525 1741 4066 9820 5680 4488 7590 395 1692 7813 2406 4939 4923 11179 1595 2809 1520 6561 4327 11551 9252 8222 8454 4639 10903

[出力例]
22

[入力例]

6 9 12

[出力例]

※AtCoderテストケースより

[入力例]

8 2 12 6

[出力例]

※AtCoderテストケースより

[入力例]

30 28 33 49 27 37 48

[出力例]

※AtCoderテストケースより

[入力例]

109 27 40 25 61 44 18 65 11 119 122 68 14 112 118 72 26 81 71 60

[出力例]

[入力例]

10424 3725 8181 11925 2195 11525 1741 4066 9820 5680 4488 7590 395 1692 7813 2406 4939 4923 11179 1595 2809 1520 6561 4327 11551 9252 8222 8454 4639 10903

[出力例]

■参照サイト
AtCoder Beginner Contest 191

2021年2月5日2021年2月5日

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. ただし, セグメント木（Range Minimum Query）を, 二本使うことに気付くのに, 非常に時間がかかってしまったと思う.
3. 個人的には, 非常に面白い問題と感じたとともに, Grundy数という新しい知識が増えたので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
4. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc038
// 参考資料.
// https://atcoder.jp/contests/pakencamp-2020-day1/editorial/527
// C++(GCC 9.2.1)
#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--)
const int INF = 2020202020;
int a[101010], c[101010], k[101010], grundy[101010];

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)
// -> 一部改変(2021/02/05).
template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{
public:
    SegmentTree() : SegmentTree(0){}
    explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}
    explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){
        log = 0;
        while((1 << log) < _n) log++;
        size = 1 << log;
        d = vector<S>(2 * size, e());
        rep(i, _n) d[size + i] = v[i];
        repr(i, size - 1, 1) update(i);
    }
    void set(int p, S x){
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        repx(i, 1, log + 1) update(p >> i);
    }
    S get(int p){
        assert(0 <= p && p < _n);
        return d[p + size];
    }
    S prod(int l, int r){
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;
        while(l < r){
            if(l & 1) sml = op(sml, d[l++]);
            if(r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }
    S all_prod(){
        return d[1];
    }
private:
    int _n, size, log;
    vector<S> d;
    void update(int k){
        d[k] = op(d[2 * k], d[2 * k + 1]);
    }
};

static int RMiQ_nodef(int l, int r){
    return min(l, r);
}
static int RMiQ_ef(){
    return INF;
}
using RMiQ = SegmentTree<int, RMiQ_nodef, RMiQ_ef>;

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N - 1) scanf("%d %d", &c[i], &a[i]);
    
    // 2. Grundy数 を 計算.
    // ex.
    // 18
    // 1 1
    // 1 0
    // 2 2
    // 3 5
    // 1 17
    // 2 3
    // 1 12
    // 5 13
    // 4 5
    // 1 7
    // 6 11
    // 3 9
    // 7 0
    // 2 15
    // 5 8
    // 8 7
    // 5 6
    // 
    // index          | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
    // c[i]           | 0 1 1 2 3 1 2 1 5 4  1  6  3  7  2  5  8  5
    // grundy[i]      | 0 1 0 2 3 0 1 0 4 2  0  3  1  5  0  2  6  3 
    // k[i]           | 0 0 1 1 1 1 3 3 3 4  4  6  8  8  8  8  8  8 
    // l(= 0)         | 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0  0  0  0
    // r(= maxGrundy) | 0 0 1 2 3 3 3 3 4 4  4  4  4  5  5  5  6  6
    // -> 例えば, index = 12 に対する grundy[12] を 計算する場合, 
    //    区間[i - C[i], i - 1] = [12 - 3, 12 - 1] = [9, 11] に 出現している Grundy数{2, 0, 3}
    //    からは, 選択できない.
    //    区間[k[i - 1], i - C[i] - 1] = [6, 12 - 3 - 1] = [6, 8] に着目して,
    //    この中のGrundy数{1, 4} から 最小のものを選択して, grundy[12] に 設定すれば良いはず.
    // -> 区間[6, 8] に Grundy数{0} を 含まない理由は, 区間[9, 11]側 に 含まれているからである.
    // -> 前行のデータ管理をするため, 二本目のセグメント木(pgSeg)が, 必要となると理解する.
    // -> 補足として, 一本目のセグメント木(gpSeg)は, 過去に出現した各Grundy数の一番直近に出現した
    //    位置を保存しているので, 解説上 の k を 算出するために必要.
    RMiQ gpSeg(N + 2); // 各Grundy数に対し, 一番直近に出現した位置(position)だけ保存.
    RMiQ pgSeg(N + 2); // 各位置(position)に対し, 一番直近に出現したGrundy数だけ保存.
    int maxGrundy = 0;
    gpSeg.set(0, 0);
    pgSeg.set(0, 0);
    repx(i, 1, N){
        // 2-1. 区間[i - C[i], i - 1] の 左端 が 前回 の k 以下の場合.
        int befPos = 0, curPos = i, l = i - c[i - 1];
        if(l <= k[i - 1]){
            // Grundy数 を 最大値 に 設定.
            grundy[i] = maxGrundy + 1;
            
            // Grundy数 の 最大値 を 更新.
            maxGrundy = max(maxGrundy, grundy[i]);
            
            // 今回確定した Grundy数 の 前回出現位置 を 取得.
            befPos = gpSeg.get(grundy[i]);
            
            // 今回確定した Grundy数 の 今回出現位置 を 更新.
            gpSeg.set(grundy[i], i);
        }
        
        // 2-2. 区間[i - C[i], i - 1] の 左端 が 前回 の k より大きい場合.
        if(l > k[i - 1]){
            // 区間[前回 の k, i - C[i] - 1] の Grundy数 の 最小値 を 取得.
            int minGrundy = pgSeg.prod(k[i - 1], l);
            
            // Grundy数を更新.
            grundy[i] = minGrundy;
            
            // Grundy数 の 最大値 を 更新.
            maxGrundy = max(maxGrundy, grundy[i]);
            
            // 今回確定した Grundy数 の 前回出現位置 を 取得.
            befPos = gpSeg.get(grundy[i]);
            
            // 今回確定した Grundy数 の 今回出現位置 を 更新.
            gpSeg.set(grundy[i], i);
        }
        
        // 2-3. セグメント木更新(※今回確定した Grundy数 の 前回出現位置).
        if(befPos != INF) pgSeg.set(befPos, INF);
        
        // 2-4. セグメント木更新(※今回確定した Grundy数 の 今回出現位置).
        pgSeg.set(curPos, grundy[i]);
        
        // 2-5. 区間[0, maxGrundy] を 参照して, 今回 の k を 更新.
        k[i] = gpSeg.prod(0, maxGrundy + 1);
    }
    // puts("--- k ---");
    // rep(i, N) printf("%d ", k[i]);
    // puts("\n--- grundy ---");
    // rep(i, N) printf("%d ", grundy[i]);
    // puts("");
    
    // 3. Grundy数 の XOR を 計算.
    int ans = 0;
    repx(i, 1, N) if(a[i - 1] & 1) ans ^= grundy[i];
    
    // 4. 出力.
    printf("%s\n", (ans == 0) ? "Second" : "First");
    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

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

// 解き直し.

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

// 参考資料.

// https://atcoder.jp/contests/pakencamp-2020-day1/editorial/527

// C++(GCC 9.2.1)

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

const int INF = 2020202020;

int a[101010], c[101010], k[101010], grundy[101010];

// AtCoder Library(https://github.com/atcoder/ac-library/blob/master/atcoder/segtree.hpp)

// -> 一部改変(2021/02/05).

template<class S, S (*op)(S, S), S (*e)()> struct SegmentTree{

public:

SegmentTree() : SegmentTree(0){}

explicit SegmentTree(int n) : SegmentTree(vector<S>(n, e())){}

explicit SegmentTree(const vector<S>& v) : _n(int(v.size())){

log = 0;

while((1 << log) < _n) log++;

size = 1 << log;

d = vector<S>(2 * size, e());

rep(i, _n) d[size + i] = v[i];

repr(i, size - 1, 1) update(i);

}

void set(int p, S x){

assert(0 <= p && p < _n);

p += size;

d[p] = x;

repx(i, 1, log + 1) update(p >> i);

}

S get(int p){

assert(0 <= p && p < _n);

return d[p + size];

}

S prod(int l, int r){

assert(0 <= l && l <= r && r <= _n);

S sml = e(), smr = e();

l += size;

r += size;

while(l < r){

if(l & 1) sml = op(sml, d[l++]);

if(r & 1) smr = op(d[--r], smr);

l >>= 1;

r >>= 1;

}

return op(sml, smr);

}

S all_prod(){

return d[1];

}

private:

int _n, size, log;

vector<S> d;

void update(int k){

d[k] = op(d[2 * k], d[2 * k + 1]);

}

};

static int RMiQ_nodef(int l, int r){

return min(l, r);

}

static int RMiQ_ef(){

return INF;

}

using RMiQ = SegmentTree<int, RMiQ_nodef, RMiQ_ef>;

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N - 1) scanf("%d %d", &c[i], &a[i]);

// 2. Grundy数を計算.

// ex.

// 18

// 1 1

// 1 0

// 2 2

// 3 5

// 1 17

// 2 3

// 1 12

// 5 13

// 4 5

// 1 7

// 6 11

// 3 9

// 7 0

// 2 15

// 5 8

// 8 7

// 5 6

// index | 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

// c[i] | 0 1 1 2 3 1 2 1 5 4 1 6 3 7 2 5 8 5

// grundy[i] | 0 1 0 2 3 0 1 0 4 2 0 3 1 5 0 2 6 3

// k[i] | 0 0 1 1 1 1 3 3 3 4 4 6 8 8 8 8 8 8

// l(= 0) | 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

// r(= maxGrundy) | 0 0 1 2 3 3 3 3 4 4 4 4 4 5 5 5 6 6

// -> 例えば, index = 12 に対する grundy[12] を計算する場合,

// 区間[i - C[i], i - 1] = [12 - 3, 12 - 1] = [9, 11] に出現している Grundy数{2, 0, 3}

// からは, 選択できない.

// 区間[k[i - 1], i - C[i] - 1] = [6, 12 - 3 - 1] = [6, 8] に着目して,

// この中のGrundy数{1, 4} から最小のものを選択して, grundy[12] に設定すれば良いはず.

// -> 区間[6, 8] に Grundy数{0} を含まない理由は, 区間[9, 11]側に含まれているからである.

// -> 前行のデータ管理をするため, 二本目のセグメント木(pgSeg)が, 必要となると理解する.

// -> 補足として, 一本目のセグメント木(gpSeg)は, 過去に出現した各Grundy数の一番直近に出現した

// 位置を保存しているので, 解説上の k を算出するために必要.

RMiQ gpSeg(N + 2); // 各Grundy数に対し, 一番直近に出現した位置(position)だけ保存.

RMiQ pgSeg(N + 2); // 各位置(position)に対し, 一番直近に出現したGrundy数だけ保存.

int maxGrundy = 0;

gpSeg.set(0, 0);

pgSeg.set(0, 0);

repx(i, 1, N){

// 2-1. 区間[i - C[i], i - 1] の左端が前回の k 以下の場合.

int befPos = 0, curPos = i, l = i - c[i - 1];

if(l <= k[i - 1]){

// Grundy数を最大値に設定.

grundy[i] = maxGrundy + 1;

// Grundy数の最大値を更新.

maxGrundy = max(maxGrundy, grundy[i]);

// 今回確定した Grundy数の前回出現位置を取得.

befPos = gpSeg.get(grundy[i]);

// 今回確定した Grundy数の今回出現位置を更新.

gpSeg.set(grundy[i], i);

}

// 2-2. 区間[i - C[i], i - 1] の左端が前回の k より大きい場合.

if(l > k[i - 1]){

// 区間[前回の k, i - C[i] - 1] の Grundy数の最小値を取得.

int minGrundy = pgSeg.prod(k[i - 1], l);

// Grundy数を更新.

grundy[i] = minGrundy;

// Grundy数の最大値を更新.

maxGrundy = max(maxGrundy, grundy[i]);

// 今回確定した Grundy数の前回出現位置を取得.

befPos = gpSeg.get(grundy[i]);

// 今回確定した Grundy数の今回出現位置を更新.

gpSeg.set(grundy[i], i);

}

// 2-3. セグメント木更新(※今回確定した Grundy数の前回出現位置).

if(befPos != INF) pgSeg.set(befPos, INF);

// 2-4. セグメント木更新(※今回確定した Grundy数の今回出現位置).

pgSeg.set(curPos, grundy[i]);

// 2-5. 区間[0, maxGrundy] を参照して, 今回の k を更新.

k[i] = gpSeg.prod(0, maxGrundy + 1);

}

// puts("--- k ---");

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

// puts("\n--- grundy ---");

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

// puts("");

// 3. Grundy数の XOR を計算.

int ans = 0;

repx(i, 1, N) if(a[i - 1] & 1) ans ^= grundy[i];

// 4. 出力.

printf("%s\n", (ans == 0) ? "Second" : "First");

return 0;

}

[入力例]
3
1 0
1 1

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

[入力例]
7
1 1
2 0
1 0
2 0
4 1
3 0

[出力例(debug版)]
--- k ---
0 0 0 1 2 2 3 
--- grundy ---
0 1 2 0 1 3 2 
First
※AtCoderのテストケースより

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

[出力例(debug版)]
--- k ---
0 0 0 1 2 2 3 
--- grundy ---
0 1 2 0 1 3 2 
Second
※AtCoderのテストケースより

[入力例]
18
1 1
1 0
2 2
3 5
1 17
2 3
1 12
5 13
4 5
1 7
6 11
3 9
7 0
2 15
5 8
8 7
5 6

[出力例(debug版)]
--- k ---
0 0 1 1 1 1 3 3 3 4 4 6 8 8 8 8 8 8 
--- grundy ---
0 1 0 2 3 0 1 0 4 2 0 3 1 5 0 2 6 3 
First

[入力例]
30
1 1
1 0
2 2
3 5
1 17
2 3
3 6
1 12
5 13
2 7
1 7
6 6
3 11
7 9
1 0
2 15
5 8
8 7
3 6
2 11
9 18
3 10
5 4
3 19
7 17
10 9
5 8
7 15
3 23

[出力例(debug版)]
--- k ---
0 0 1 1 1 1 3 4 4 4 4 4 7 9 9 9 9 12 12 12 12 12 12 14 14 14 18 18 21 21 
--- grundy ---
0 1 0 2 3 0 1 2 0 4 1 0 3 2 5 0 1 4 6 0 1 7 2 3 0 4 5 1 6 0 
Second

[入力例]
50
5 69379463
14 121410993
5 65591092
5 45598468
13 13351854
7 11461527
6 26186966
10 71634680
11 66189154
1 53830114
3 15427275
12 6929923
12 18649567
12 88587971
1 82196776
10 39901772
3 61263173
3 79275060
3 86684502
14 37382396
15 62256931
12 86356755
16 22474298
8 101539891
2 30730994
10 69045198
14 75729438
15 112107055
7 112056635
8 1428515
2 45261247
3 121601466
17 94295137
9 68729985
17 12705325
1 32519109
11 5437491
5 78777121
6 36839199
13 44773739
15 80027184
1 72941422
17 12218068
15 21893608
10 47917352
14 73871275
17 119485015
14 109054715
7 24072763

[出力例(debug版)]
--- k ---
0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6 8 8 9 9 12 13 13 13 13 13 13 14 14 21 21 22 22 22 23 23 23 26 27 27 28 33 34 34 
--- grundy ---
0 1 2 3 4 5 6 0 7 8 0 1 9 10 11 0 2 1 3 0 4 5 6 12 7 0 8 9 13 1 2 0 3 10 4 11 0 5 1 2 6 7 0 12 8 3 9 13 10 1 
First

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

[入力例]

1 0

1 1

[出力例(debug版)]

--- k ---

0 0 1

--- grundy ---

0 1 0

Second

※AtCoderのテストケースより

[入力例]

1 1

2 0

1 0

2 0

4 1

3 0

[出力例(debug版)]

--- k ---

0 0 0 1 2 2 3

--- grundy ---

0 1 2 0 1 3 2

First

※AtCoderのテストケースより

[入力例]

1 1

2 0

1 9

2 10

4 3

3 5

[出力例(debug版)]

--- k ---

0 0 0 1 2 2 3

--- grundy ---

0 1 2 0 1 3 2

Second

※AtCoderのテストケースより

[入力例]

1 1

1 0

2 2

3 5

1 17

2 3

1 12

5 13

4 5

1 7

6 11

3 9

7 0

2 15

5 8

8 7

5 6

[出力例(debug版)]

--- k ---

0 0 1 1 1 1 3 3 3 4 4 6 8 8 8 8 8 8

--- grundy ---

0 1 0 2 3 0 1 0 4 2 0 3 1 5 0 2 6 3

First

[入力例]

1 1

1 0

2 2

3 5

1 17

2 3

3 6

1 12

5 13

2 7

1 7

6 6

3 11

7 9

1 0

2 15

5 8

8 7

3 6

2 11

9 18

3 10

5 4

3 19

7 17

10 9

5 8

7 15

3 23

[出力例(debug版)]

--- k ---

0 0 1 1 1 1 3 4 4 4 4 4 7 9 9 9 9 12 12 12 12 12 12 14 14 14 18 18 21 21

--- grundy ---

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

Second

[入力例]

5 69379463

14 121410993

5 65591092

5 45598468

13 13351854

7 11461527

6 26186966

10 71634680

11 66189154

1 53830114

3 15427275

12 6929923

12 18649567

12 88587971

1 82196776

10 39901772

3 61263173

3 79275060

3 86684502

14 37382396

15 62256931

12 86356755

16 22474298

8 101539891

2 30730994

10 69045198

14 75729438

15 112107055

7 112056635

8 1428515

2 45261247

3 121601466

17 94295137

9 68729985

17 12705325

1 32519109

11 5437491

5 78777121

6 36839199

13 44773739

15 80027184

1 72941422

17 12218068

15 21893608

10 47917352

14 73871275

17 119485015

14 109054715

7 24072763

[出力例(debug版)]

--- k ---

0 0 0 0 0 0 0 1 1 1 1 2 2 2 2 2 3 3 4 4 5 6 8 8 9 9 12 13 13 13 13 13 13 14 14 21 21 22 22 22 23 23 23 26 27 27 28 33 34 34

--- grundy ---

0 1 2 3 4 5 6 0 7 8 0 1 9 10 11 0 2 1 3 0 4 5 6 12 7 0 8 9 13 1 2 0 3 10 4 11 0 5 1 2 6 7 0 12 8 3 9 13 10 1

First

■参照サイト
AtCoder Regular Contest 038
パ研合宿2020 第1日「SpeedRun」／N – 背の順解説／セグメント木（Range Minimum Query）の使い方を参考にしました

2021年2月4日

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

C++の練習を兼ねて, AtCoder Regular Contest 040 の問題C (Z塗り)を解いてみた.

■感想.
1. 問題Cは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://www.slideshare.net/chokudai/arc040
// C++(GCC 9.2.1)
#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 board[111][111];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N){
        char c[111];
        scanf("%s", c);
        rep(j, N) if(c[j] == 'o') board[i][j] = 1;
    }
    
    // 2. 装置を使って, マスを塗る(※前回以前に塗った場所も, 塗り直し可と解釈).
    int ans = 0;
    auto zPaint = [&](int curR, int curC){
        // 2-1. スタート地点の行で, 列方向で, 左向きに塗っていく.
        int paint = 0;
        repr(j, curC, 0) if(!board[curR][j]) board[curR][j] = 1, paint++;
        
        // 2-2. スタート地点の次の行で, 列方向で, 右向きに塗っていく.
        if(curR < N - 1){
            int nexR = curR + 1;
            repx(j, curC, N) if(!board[nexR][j]) board[nexR][j] = 1, paint++;
        }
        
        // 2-3. マスを, 1マス以上塗ったか否かを返却.
        return (paint > 0) ? 1 : 0;
    };
    rep(i, N) repr(j, N - 1, 0) if(!board[i][j]) ans += zPaint(i, j);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

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

// C++(GCC 9.2.1)

#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 board[111][111];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N){

char c[111];

scanf("%s", c);

rep(j, N) if(c[j] == 'o') board[i][j] = 1;

}

// 2. 装置を使って, マスを塗る(※前回以前に塗った場所も, 塗り直し可と解釈).

int ans = 0;

auto zPaint = [&](int curR, int curC){

// 2-1. スタート地点の行で, 列方向で, 左向きに塗っていく.

int paint = 0;

repr(j, curC, 0) if(!board[curR][j]) board[curR][j] = 1, paint++;

// 2-2. スタート地点の次の行で, 列方向で, 右向きに塗っていく.

if(curR < N - 1){

int nexR = curR + 1;

repx(j, curC, N) if(!board[nexR][j]) board[nexR][j] = 1, paint++;

}

// 2-3. マスを, 1マス以上塗ったか否かを返却.

return (paint > 0) ? 1 : 0;

};

rep(i, N) repr(j, N - 1, 0) if(!board[i][j]) ans += zPaint(i, j);

// 3. 出力.

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

return 0;

}

[入力例]
7
...oooo
oo.....
ooooooo
ooooooo
.....oo
oooo...
ooooooo

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

[入力例]
4
.oo.
..oo
o..o
oo..

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

[入力例]
1
o

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

[入力例]
10
.o..oooooo
ooo..o.ooo
o.o.....oo
...oooo...
oo..oo.o.o
....oooooo
.oooooo.o.
...o..o.o.
ooo...oo.o
o...oo.oo.

[出力例]
7

[入力例]
20
..o.....oooooo..oo..
ooooooooooo.oooooooo
ooooooooooo.ooo.o.o.
oo..ooo.o....ooo.o.o
o.o..ooo....ooo.ooo.
o....oooo..o...oo.o.
....o...o.o.oooo.o..
ooooooooooo.ooo.o.o.
.oo.ooo...ooo.oooo..
oo...oo..o.oo.oo.oo.
..ooo.o..ooo.oo.oooo
ooooooooooo.ooo.o.o.
o....ooooo..ooo.o.o.
oo.o..o.ooo.o...o...
o.ooo..o..ooo...o...
oooo.oo..ooo..o..o.o
ooooooooooo.ooo.o.o.
.ooo.....o..o...o.oo
.oooo.ooooo.oo...o.o
oo..oo.ooooo..o.....

[出力例]
17

[入力例]
30
...o..oooo..o.o.oo....o.o.o..o
o..ooo..oo.o.o.oo...oooo.oo.oo
o..o.oo..o...oo...o.....oooooo
ooooooooooooooooo.............
ooo....ooo.oo..oo..o.o...o....
oooooooooooooooooooooooooooooo
o..ooo...oooo.oo.o..o.....oooo
ooooooo.ooooooooooooooooo.o.oo
ooooooo.oooooooo.ooooooooooooo
o.oooooo..oo..ooooo....o.o.o..
....oo..o.o.oooo...o.o.....o..
o.ooo...oo.oo.oo.oo.o.o..oo...
o...o.o..oo.o.oo..o...o...ooo.
o...ooo...o...o...o.oo.......o
..ooo..o.ooo.oo.o.oo.o...o.ooo
oooooooooooo.oooo.oooo.oo.oooo
...o.o..o..ooooooo.o.o.o.oo.o.
...oo..o.oo...o..o.ooo..o..o.o
ooo.o.oo..oooo...o.o..o..oo..o
oooooooooooooooooooooo.ooooooo
oo.oooo...o.oo...oo....ooooooo
oooo.o....o.o.o..ooooo..o....o
..o.......ooooo....o.o.oo...oo
.ooooooo.oo..o.....o....oo....
oo....o.o.oo........oooo...oo.
....oo..o.oooo.o.o.o..oooo.oo.
ooo.ooo...oo..ooo...o.o....o..
oo...ooooo...o..o.oo..ooo.o...
....oo...oo.o..oo.o..oo...o...
.oooooo.ooooooo.oooooooooooooo

[出力例]
27

100

101

102

103

104

105

106

107

108

109

110

[入力例]

...oooo

oo.....

ooooooo

.....oo

oooo...

ooooooo

[出力例]

※AtCoderのテストケースより

[入力例]

.oo.

..oo

o..o

oo..

[出力例]

※AtCoderのテストケースより

[入力例]

[出力例]

※AtCoderのテストケースより

[入力例]

.o..oooooo

ooo..o.ooo

o.o.....oo

...oooo...

oo..oo.o.o

....oooooo

.oooooo.o.

...o..o.o.

ooo...oo.o

o...oo.oo.

[出力例]

[入力例]

..o.....oooooo..oo..

ooooooooooo.oooooooo

ooooooooooo.ooo.o.o.

oo..ooo.o....ooo.o.o

o.o..ooo....ooo.ooo.

o....oooo..o...oo.o.

....o...o.o.oooo.o..

ooooooooooo.ooo.o.o.

.oo.ooo...ooo.oooo..

oo...oo..o.oo.oo.oo.

..ooo.o..ooo.oo.oooo

ooooooooooo.ooo.o.o.

o....ooooo..ooo.o.o.

oo.o..o.ooo.o...o...

o.ooo..o..ooo...o...

oooo.oo..ooo..o..o.o

ooooooooooo.ooo.o.o.

.ooo.....o..o...o.oo

.oooo.ooooo.oo...o.o

oo..oo.ooooo..o.....

[出力例]

[入力例]

...o..oooo..o.o.oo....o.o.o..o

o..ooo..oo.o.o.oo...oooo.oo.oo

o..o.oo..o...oo...o.....oooooo

ooooooooooooooooo.............

ooo....ooo.oo..oo..o.o...o....

oooooooooooooooooooooooooooooo

o..ooo...oooo.oo.o..o.....oooo

ooooooo.ooooooooooooooooo.o.oo

ooooooo.oooooooo.ooooooooooooo

o.oooooo..oo..ooooo....o.o.o..

....oo..o.o.oooo...o.o.....o..

o.ooo...oo.oo.oo.oo.o.o..oo...

o...o.o..oo.o.oo..o...o...ooo.

o...ooo...o...o...o.oo.......o

..ooo..o.ooo.oo.o.oo.o...o.ooo

oooooooooooo.oooo.oooo.oo.oooo

...o.o..o..ooooooo.o.o.o.oo.o.

...oo..o.oo...o..o.ooo..o..o.o

ooo.o.oo..oooo...o.o..o..oo..o

oooooooooooooooooooooo.ooooooo

oo.oooo...o.oo...oo....ooooooo

oooo.o....o.o.o..ooooo..o....o

..o.......ooooo....o.o.oo...oo

.ooooooo.oo..o.....o....oo....

oo....o.o.oo........oooo...oo.

....oo..o.oooo.o.o.o..oooo.oo.

ooo.ooo...oo..ooo...o.o....o..

oo...ooooo...o..o.oo..ooo.o...

....oo...oo.o..oo.o..oo...o...

.oooooo.ooooooo.oooooooooooooo

[出力例]

■参照サイト
AtCoder Regular Contest 040

2021年2月3日

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

C++の練習を兼ねて, AtCoder Beginner Contest 190 の問題F (Shift and Inversions)を解いてみた.

■感想.
1. 問題Fは, 方針が見えなかったので, 解説を見て提出したところ, AC版に到達できたので, 良かったと思う.
2. Binary Indexed Tree の復習が出来たので, 非常に良かったと思う.
※ 公式のライブラリを拝借させて頂いてます.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 190 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc190/editorial/631
// C++(GCC 9.2.1)
#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--)
LL a[303030];

// Binary Indexed Tree (Fenwick Tree)
// https://youtu.be/lyHk98daDJo?t=7960
template<typename T>
struct BIT{
    int n;
    vector<T> d;
    BIT(int n = 0) : n(n), d(n + 1) {}
    void add(int i, T x = 1){
        for(i++; i <= n; i += i & -i) d[i] += x;
    }
    T sum(int i){
        T x = 0;
        for(i++; i; i -= i & -i) x += d[i];
        return x;
    }
    T sum(int l, int r){
        return sum(r - 1) - sum(l - 1);
    }
};

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &a[i]);
    
    // 2. 転倒数(数列 A) を 計算.
    BIT<LL> ft(N + 1);
    LL per = 0;
    rep(i, N){
        // 2-1. 位置 a[i] に, 1 を 加算.
        ft.add(a[i], 1LL);
        
        // 2-2. 区間[a[i] + 1, N] の 合計は？
        LL t = ft.sum(a[i] + 1, N + 1);
        
        // 2-3. 集計.
        per += t;
    }
    
    // 3. 転倒数(数列 B) を 計算しながら出力.
    LL ans = per;
    rep(i, N){
        // 3-1. 出力.
        printf("%lld\n", ans);
        
        // 3-2. 差分更新(※解説通り).
        ans += (LL)(N - 1 - 2 * a[i]);
    }
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc190/editorial/631

// C++(GCC 9.2.1)

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

LL a[303030];

// Binary Indexed Tree (Fenwick Tree)

// https://youtu.be/lyHk98daDJo?t=7960

template<typename T>

struct BIT{

int n;

vector<T> d;

BIT(int n = 0) : n(n), d(n + 1) {}

void add(int i, T x = 1){

for(i++; i <= n; i += i & -i) d[i] += x;

}

T sum(int i){

T x = 0;

for(i++; i; i -= i & -i) x += d[i];

return x;

}

T sum(int l, int r){

return sum(r - 1) - sum(l - 1);

}

};

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &a[i]);

// 2. 転倒数(数列 A) を計算.

BIT<LL> ft(N + 1);

LL per = 0;

rep(i, N){

// 2-1. 位置 a[i] に, 1 を加算.

ft.add(a[i], 1LL);

// 2-2. 区間[a[i] + 1, N] の合計は？

LL t = ft.sum(a[i] + 1, N + 1);

// 2-3. 集計.

per += t;

}

// 3. 転倒数(数列 B) を計算しながら出力.

LL ans = per;

rep(i, N){

// 3-1. 出力.

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

// 3-2. 差分更新(※解説通り).

ans += (LL)(N - 1 - 2 * a[i]);

}

return 0;

}

[入力例]
4
0 1 2 3

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

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

[出力例]
9
18
21
28
27
28
33
24
21
14
※AtCoderテストケースより

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

[出力例]
100
87
92
103
96
97
96
105
112
97
94
75
88
103
106
123
106
95
86
105

[入力例]
50
31 17 46 41 23 13 6 3 38 24 37 20 39 48 30 7 29 1 12 10 11 22 21 47 8 45 16 32 34 43 27 19 33 15 9 44 4 14 18 25 28 42 2 5 36 40 49 26 35 0

[出力例]
621
608
623
580
547
550
573
610
653
626
627
602
611
582
535
524
559
550
597
622
651
678
683
690
645
678
637
654
639
620
583
578
589
572
591
622
583
624
645
658
657
650
615
660
699
676
645
596
593
572

100

101

102

103

104

105

106

107

108

109

[入力例]

0 1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

0 3 1 5 4 2 9 6 8 7

[出力例]

※AtCoderテストケースより

[入力例]

16 7 4 13 9 10 5 6 17 11 19 3 2 8 1 18 15 14 0 12

[出力例]

100

103

105

112

103

106

123

106

105

[入力例]

31 17 46 41 23 13 6 3 38 24 37 20 39 48 30 7 29 1 12 10 11 22 21 47 8 45 16 32 34 43 27 19 33 15 9 44 4 14 18 25 28 42 2 5 36 40 49 26 35 0

[出力例]

621

608

623

580

547

550

573

610

653

626

627

602

611

582

535

524

559

550

597

622

651

678

683

690

645

678

637

654

639

620

583

578

589

572

591

622

583

624

645

658

657

650

615

660

699

676

645

596

593

572

■参照サイト
AtCoder Beginner Contest 190
Binary Indexed Tree (Fenwick Tree)

2021年2月1日

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

C++の練習を兼ねて, AtCoder Beginner Contest 190 の問題C (Bowls and Dishes) ～問題D (Staircase Sequences) を解いてみた.

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

本家のサイト AtCoder Beginner Contest 190 解説の各リンクをご覧下さい.

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

// C++(GCC 9.2.1)
#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[101], b[101], x[101][2];

int main(){
    
    // 1. 入力情報.
    int N, M, K;
    scanf("%d %d", &N, &M);
    rep(i, M) scanf("%d %d", &a[i], &b[i]);
    scanf("%d", &K);
    rep(i, K) scanf("%d %d", &x[i][0], &x[i][1]);
    
    // 2. 全探索.
    int ans = 0;
    rep(i, 1 << K){
        // 2-1. 皿C, D の置き方.
        // ex.
        // K = 5 で, i = 25 であれば, 11001 と見て, 
        // 皿C には, 人1, 2, 5 が, 皿D には, 人3, 4 が ボールを置くと見る.
        int d[101];
        rep(j, 101) d[j] = 0;
        rep(j, K){
            int f = i & (1 << (K - 1 - j));
            d[x[j][(f > 0)]]++;
        }
        
        // 2-2. 皿A, B の両方にボールが置かれているか を チェック.
        int t = 0;
        rep(j, M) if(d[a[j]] && d[b[j]]) t++;
        
        // 2-3. 最大値更新.
        ans = max(ans, t);
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// C++(GCC 9.2.1)

#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[101], b[101], x[101][2];

int main(){

// 1. 入力情報.

int N, M, K;

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

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

scanf("%d", &K);

rep(i, K) scanf("%d %d", &x[i][0], &x[i][1]);

// 2. 全探索.

int ans = 0;

rep(i, 1 << K){

// 2-1. 皿C, D の置き方.

// ex.

// K = 5 で, i = 25 であれば, 11001 と見て,

// 皿C には, 人1, 2, 5 が, 皿D には, 人3, 4 がボールを置くと見る.

int d[101];

rep(j, 101) d[j] = 0;

rep(j, K){

int f = i & (1 << (K - 1 - j));

d[x[j][(f > 0)]]++;

}

// 2-2. 皿A, B の両方にボールが置かれているかをチェック.

int t = 0;

rep(j, M) if(d[a[j]] && d[b[j]]) t++;

// 2-3. 最大値更新.

ans = max(ans, t);

}

// 3. 出力.

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

return 0;

}

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

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

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

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

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

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

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

[出力例]
7

[入力例]

4 4

1 2

1 3

2 4

3 4

1 2

1 3

2 3

[出力例]

※AtCoderテストケースより

[入力例]

4 4

1 2

1 3

2 4

3 4

1 2

2 4

[出力例]

※AtCoderテストケースより

[入力例]

6 12

2 3

4 6

1 2

4 5

2 6

1 5

4 5

1 3

1 2

2 6

2 3

2 5

3 5

1 4

2 6

4 6

5 6

[出力例]

※AtCoderテストケースより

[入力例]

11 15

1 3

2 3

3 5

3 10

2 10

7 8

1 10

2 8

5 11

5 7

4 11

5 6

2 9

7 10

3 11

1 6

2 8

3 9

4 11

5 11

3 5

2 7

[出力例]

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

// C++(GCC 9.2.1)
#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--)

// 与えられた正の整数のすべての約数を抽出.
// @param X: 約数を抽出したい正の整数.
// @return ret: すべての約数(※1以上).
set<LL> div(LL X){
    set<LL> ret;
    ret.insert(1);
    for(LL d = 2; d * d <= X; d++){
        if(X % d == 0){
            ret.insert(d);
            if(d * d != X) ret.insert(X / d);
        }
    }
    ret.insert(X);
    return ret;
}

int main(){
    
    // 1. 入力情報.
    LL N;
    scanf("%lld", &N);
    
    // 2. すべての約数を抽出.
    set<LL> divisors = div(N);
    
    // 3. 約数が, 奇数のものの個数をカウント.
    int ans = 0;
    for(auto &d : divisors) if(d & 1) ans++;
    
    // 4. 出力.
    printf("%d\n", ans * 2);
    return 0;
    
}

// C++(GCC 9.2.1)

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

// 与えられた正の整数のすべての約数を抽出.

// @param X: 約数を抽出したい正の整数.

// @return ret: すべての約数(※1以上).

set<LL> div(LL X){

set<LL> ret;

ret.insert(1);

for(LL d = 2; d * d <= X; d++){

if(X % d == 0){

ret.insert(d);

if(d * d != X) ret.insert(X / d);

}

ret.insert(X);

return ret;

}

int main(){

// 1. 入力情報.

LL N;

scanf("%lld", &N);

// 2. すべての約数を抽出.

set<LL> divisors = div(N);

// 3. 約数が, 奇数のものの個数をカウント.

int ans = 0;

for(auto &d : divisors) if(d & 1) ans++;

// 4. 出力.

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

return 0;

}

[入力例]
12

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

[入力例]
1

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

[入力例]
963761198400

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

[入力例]
202020212022

[出力例]
32

[入力例]
3736247840325

[出力例]
5184

[入力例]
12345678987654321

[出力例]
90

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

963761198400

[出力例]

1920

※AtCoderテストケースより

[入力例]

202020212022

[出力例]

[入力例]

3736247840325

[出力例]

5184

[入力例]

12345678987654321

[出力例]

■参照サイト
AtCoder Beginner Contest 190

2021年1月30日2021年1月30日

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

C++の練習を兼ねて, AtCoder Grand Contest 038 の問題B (Sorting a Segment) を解いてみた.

■感想.
1. 問題Bは, 方針が見えなかったので, 解説を参考に, AC版に到達できたので, 良かったと思う.
2. 但し, AC版となるまでに, 実装に非常に苦労したように思う.
3. なお, equivalent となる区間どうしが, 共通部分を持たないパターンについては,
最初に見つかった区間を基準とし, その先頭要素から, K個以上離れたものを, 順次見ていくと仮定して, 実装している.
4. 個人的には, 数列の並び替えが, グラフに置き換えて考える部分について, 非常に面白いと感じた.
5. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

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

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

// 解き直し.
// https://img.atcoder.jp/agc038/editorial.pdf
// C++(GCC 9.2.1)
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vs = vector<set<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 pb push_back
int P[202020];

int main(){
    
    // 1. 入力情報.
    int N, K;
    scanf("%d %d", &N, &K);
    rep(i, N) scanf("%d", &P[i]);
    
    // 2. もともと昇順で並んでいる場合の頂点を抽出.
    // -> 解説にある通り, equivalentとなる区間について, 共通部分を持たないようにチェックする必要があるとのこと.
    vi v;
    rep(i, N - K + 1){
        // 2-1. 区間[i, i + K - 1] の要素が, 昇順であれば OK とする.
        int bef = P[i], cur;
        bool ok = true;
        repx(j, i + 1, i + K){
            // 今回頂点更新.
            cur = P[j];
            
            // 昇順チェック.
            if(cur < bef){
                ok = false;
                // index更新(※注意: for文のインクリメント(+1) が 混ざるので, j - 1).
                i = j - 1;
                break;
            }
            
            // 前回頂点更新.
            bef = cur;
        }
        
        // 2-2. 頂点を保存.
        // index更新(※注意: for文のインクリメント(+1) が 混ざるので, K - 1).
        if(ok) v.pb(i), i += (K - 1);
    }
    
    // 3. グラフ作成(もともと昇順で並んでいる場合).
    vs G(N - K + 1); // 頂点 0 ～ (N - K) の グラフ.
    int vl = v.size();
    if(vl > 1) repx(i, 1, vl) G[v[0]].insert(v[i]), G[v[i]].insert(v[0]);
    
    // 4. グラフ作成(もともと昇順で並んでいない場合).
    set<int> st;
    rep(i, K) st.insert(P[i]);
    rep(i, N - K){
        // 4-1. 最終要素追加.
        st.insert(P[i + K]);
        
        // 4-2. 区間[i, i + K + 1) の 最小値.
        int minP = *st.begin();
        
        // 4-3. 区間[i, i + K + 1) の 最大値.
        int maxP = *(--(st.end()));
        
        // 4-4. 頂点 i, (i + 1) が, equivalentであるか？
        if(P[i] == minP && P[i + K] == maxP){
            G[i].insert(i + 1);
            G[i + 1].insert(i);
        }
        
        // 4-5. 先頭要素削除.
        st.erase(P[i]);
    }
    
    // 5. 探索を行い, 連結成分に分割.
    // https://ja.wikipedia.org/wiki/幅優先探索
    auto bfs = [&](vs &G, int s, int* d, int l){
        // 5-1. 空のキュー.
        queue<int> q;
        
        // 5-2. 連結成分番号を設定.
        d[s] = l;
        
        // 5-3. 探索地点 s をキュー q に追加.
        q.push(s);
        while(!q.empty()){
            // 5-4. キューから取り出す.
            int u = q.front();
            q.pop();
            
            // 5-5. 取り出した要素を処理.
            for(auto &e : G[u]){
                // 5-6. 訪問済であれば, 処理をスキップ.
                if(d[e])            continue;
                if(!d[e] && e != s) d[e] = l, q.push(e);
            }
        }
        return;
    };
    int d[N], idx = 0;
    rep(i, N) d[i] = 0;
    rep(i, N - K + 1) if(!d[i]) bfs(G, i, d, ++idx);
    
    // 6. 出力.
    printf("%d\n", idx);
    return 0;
    
}

100

101

102

103

104

105

106

107

108

109

110

111

// 解き直し.

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

// C++(GCC 9.2.1)

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

using vs = vector<set<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 pb push_back

int P[202020];

int main(){

// 1. 入力情報.

int N, K;

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

rep(i, N) scanf("%d", &P[i]);

// 2. もともと昇順で並んでいる場合の頂点を抽出.

// -> 解説にある通り, equivalentとなる区間について, 共通部分を持たないようにチェックする必要があるとのこと.

vi v;

rep(i, N - K + 1){

// 2-1. 区間[i, i + K - 1] の要素が, 昇順であれば OK とする.

int bef = P[i], cur;

bool ok = true;

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

// 今回頂点更新.

cur = P[j];

// 昇順チェック.

if(cur < bef){

ok = false;

// index更新(※注意: for文のインクリメント(+1) が混ざるので, j - 1).

i = j - 1;

break;

}

// 前回頂点更新.

bef = cur;

}

// 2-2. 頂点を保存.

// index更新(※注意: for文のインクリメント(+1) が混ざるので, K - 1).

if(ok) v.pb(i), i += (K - 1);

}

// 3. グラフ作成(もともと昇順で並んでいる場合).

vs G(N - K + 1); // 頂点 0 ～ (N - K) のグラフ.

int vl = v.size();

if(vl > 1) repx(i, 1, vl) G[v[0]].insert(v[i]), G[v[i]].insert(v[0]);

// 4. グラフ作成(もともと昇順で並んでいない場合).

set<int> st;

rep(i, K) st.insert(P[i]);

rep(i, N - K){

// 4-1. 最終要素追加.

st.insert(P[i + K]);

// 4-2. 区間[i, i + K + 1) の最小値.

int minP = *st.begin();

// 4-3. 区間[i, i + K + 1) の最大値.

int maxP = *(--(st.end()));

// 4-4. 頂点 i, (i + 1) が, equivalentであるか？

if(P[i] == minP && P[i + K] == maxP){

G[i].insert(i + 1);

G[i + 1].insert(i);

}

// 4-5. 先頭要素削除.

st.erase(P[i]);

}

// 5. 探索を行い, 連結成分に分割.

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

auto bfs = [&](vs &G, int s, int* d, int l){

// 5-1. 空のキュー.

queue<int> q;

// 5-2. 連結成分番号を設定.

d[s] = l;

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

q.push(s);

while(!q.empty()){

// 5-4. キューから取り出す.

int u = q.front();

q.pop();

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

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

// 5-6. 訪問済であれば, 処理をスキップ.

if(d[e]) continue;

if(!d[e] && e != s) d[e] = l, q.push(e);

}

return;

};

int d[N], idx = 0;

rep(i, N) d[i] = 0;

rep(i, N - K + 1) if(!d[i]) bfs(G, i, d, ++idx);

// 6. 出力.

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

return 0;

}

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

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

[入力例]
4 4
0 1 2 3

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

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

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

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

[出力例]
3

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

[出力例]
7

[入力例]

5 3

0 2 1 4 3

[出力例]

※AtCoderテストケースより

[入力例]

4 4

0 1 2 3

[出力例]

※AtCoderテストケースより

[入力例]

10 4

2 0 1 3 7 5 4 6 8 9

[出力例]

※AtCoderテストケースより

[入力例]

10 3

1 0 2 3 5 4 6 7 8 9

[出力例]

[入力例]

18 5

10 11 12 13 14 1 0 2 3 5 4 6 7 8 9 15 16 17

[出力例]

■参照サイト
AtCoder Grand Contest 038

2021年1月25日

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

C++の練習を兼ねて, AtCoder Beginner Contest 189 の問題E (Rotate and Flip) を解いてみた.

■感想.
1. 問題Eは, 方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 189 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc189/editorial/539
// C++(GCC 9.2.1)
#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--)
LL matrix[202020][3][3], x[202020], y[202020];

// 各操作のアフィン変換を行う.
// -> 各操作に対応する変換行列を, 左側から順次乗じてみる.
// @param M: 更新対称の行列.
// @param i: 更新対称の行列(index).
// @param o: 回転, 対称移動などの操作.
// @param a: 対称移動の中心軸.
// @return: アフィン変換を適用した行列.
void affineTransformation(LL (&M)[202020][3][3], int i, int o, LL a){
    // 1. 時計回り(90度回転).
    // (x, y, 1) -> (y, -x, 1)
    if(o == 1){
        // (1, 1)成分.
        M[i][0][0] = M[i - 1][1][0];
        
        // (1, 2)成分.
        M[i][0][1] = M[i - 1][1][1];
        
        // (1, 3)成分.
        M[i][0][2] = M[i - 1][1][2];
        
        // (2, 1)成分.
        M[i][1][0] = -M[i - 1][0][0];
        
        // (2, 2)成分.
        M[i][1][1] = -M[i - 1][0][1];
        
        // (2, 3)成分.
        M[i][1][2] = -M[i - 1][0][2];
        
        // (3, 1)成分.
        M[i][2][0] = M[i - 1][2][0];
        
        // (3, 2)成分.
        M[i][2][1] = M[i - 1][2][1];
        
        // (3, 3)成分.
        M[i][2][2] = M[i - 1][2][2];
    }
    
    // 2. 反時計回り(90度回転).
    // (x, y, 1) -> (-y, x, 1)
    if(o == 2){
        // (1, 1)成分.
        M[i][0][0] = -M[i - 1][1][0];
        
        // (1, 2)成分.
        M[i][0][1] = -M[i - 1][1][1];
        
        // (1, 3)成分.
        M[i][0][2] = -M[i - 1][1][2];
        
        // (2, 1)成分.
        M[i][1][0] = M[i - 1][0][0];
        
        // (2, 2)成分.
        M[i][1][1] = M[i - 1][0][1];
        
        // (2, 3)成分.
        M[i][1][2] = M[i - 1][0][2];
        
        // (3, 1)成分.
        M[i][2][0] = M[i - 1][2][0];
        
        // (3, 2)成分.
        M[i][2][1] = M[i - 1][2][1];
        
        // (3, 3)成分.
        M[i][2][2] = M[i - 1][2][2];
    }
    
    // 3. 直線 x = p で対称移動.
    // (x, y, 1) -> (2 * p - x, y, 1)
    if(o == 3){
        // (1, 1)成分.
        M[i][0][0] = -M[i - 1][0][0] + 2 * a * M[i - 1][2][0];
        
        // (1, 2)成分.
        M[i][0][1] = -M[i - 1][0][1] + 2 * a * M[i - 1][2][1];
        
        // (1, 3)成分.
        M[i][0][2] = -M[i - 1][0][2] + 2 * a * M[i - 1][2][2];
        
        // (2, 1)成分.
        M[i][1][0] = M[i - 1][1][0];
        
        // (2, 2)成分.
        M[i][1][1] = M[i - 1][1][1];
        
        // (2, 3)成分.
        M[i][1][2] = M[i - 1][1][2];
        
        // (3, 1)成分.
        M[i][2][0] = M[i - 1][2][0];
        
        // (3, 2)成分.
        M[i][2][1] = M[i - 1][2][1];
        
        // (3, 3)成分.
        M[i][2][2] = M[i - 1][2][2];
    }
    
    // 4. 直線 y = q で対称移動.
    // (x, y, 1) -> (x, 2 * q - y, 1)
    if(o == 4){
        // (1, 1)成分.
        M[i][0][0] = M[i - 1][0][0];
        
        // (1, 2)成分.
        M[i][0][1] = M[i - 1][0][1];
        
        // (1, 3)成分.
        M[i][0][2] = M[i - 1][0][2];
        
        // (2, 1)成分.
        M[i][1][0] = -M[i - 1][1][0] + 2 * a * M[i - 1][2][0];
        
        // (2, 2)成分.
        M[i][1][1] = -M[i - 1][1][1] + 2 * a * M[i - 1][2][1];
        
        // (2, 3)成分.
        M[i][1][2] = -M[i - 1][1][2] + 2 * a * M[i - 1][2][2];
        
        // (3, 1)成分.
        M[i][2][0] = M[i - 1][2][0];
        
        // (3, 2)成分.
        M[i][2][1] = M[i - 1][2][1];
        
        // (3, 3)成分.
        M[i][2][2] = M[i - 1][2][2];
    }
    return;
}

// X座標, Y座標について, アフィン変換を行う.
// @param M: アフィン変換に対応する行列.
// @param i: アフィン変換に対応する行列(index).
// @param X: アフィン変換前のX座標.
// @param Y: アフィン変換前のY座標.
// @return: アフィン変換後のX座標, Y座標.
LL* affine(LL (&M)[202020][3][3], int i, LL X, LL Y){
    static LL ret[2];
    ret[0] = M[i][0][0] * X + M[i][0][1] * Y + M[i][0][2] * 1;
    ret[1] = M[i][1][0] * X + M[i][1][1] * Y + M[i][1][2] * 1;
    return ret;
}

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld %lld", &x[i], &y[i]);
    
    // 2. 行列の初期化.
    matrix[0][0][0] = matrix[0][1][1] = matrix[0][2][2] = 1;
    
    // 3. アフィン変換の事前計算.
    int M;
    scanf("%d", &M);
    rep(i, M){
        // 3-1. 操作情報.
        int o, a = 0;
        scanf("%d", &o);
        if(o == 3 || o == 4) scanf("%d", &a);
        
        // 3-2. 行列更新.
        affineTransformation(matrix, i + 1, o, a);
    }
    
    // 4. クエリ回答.
    int Q;
    scanf("%d", &Q);
    rep(i, Q){
        // 4-1. クエリ情報.
        int a, b;
        scanf("%d %d", &a, &b);
        b--;
        
        // 4-2. 座標計算.
        LL* ans = affine(matrix, a, x[b], y[b]);
        
        // 4-3. 出力.
        printf("%lld %lld\n", ans[0], ans[1]);
    }
    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

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

// 解き直し.

// https://atcoder.jp/contests/abc189/editorial/539

// C++(GCC 9.2.1)

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

LL matrix[202020][3][3], x[202020], y[202020];

// 各操作のアフィン変換を行う.

// -> 各操作に対応する変換行列を, 左側から順次乗じてみる.

// @param M: 更新対称の行列.

// @param i: 更新対称の行列(index).

// @param o: 回転, 対称移動などの操作.

// @param a: 対称移動の中心軸.

// @return: アフィン変換を適用した行列.

void affineTransformation(LL (&M)[202020][3][3], int i, int o, LL a){

// 1. 時計回り(90度回転).

// (x, y, 1) -> (y, -x, 1)

if(o == 1){

// (1, 1)成分.

M[i][0][0] = M[i - 1][1][0];

// (1, 2)成分.

M[i][0][1] = M[i - 1][1][1];

// (1, 3)成分.

M[i][0][2] = M[i - 1][1][2];

// (2, 1)成分.

M[i][1][0] = -M[i - 1][0][0];

// (2, 2)成分.

M[i][1][1] = -M[i - 1][0][1];

// (2, 3)成分.

M[i][1][2] = -M[i - 1][0][2];

// (3, 1)成分.

M[i][2][0] = M[i - 1][2][0];

// (3, 2)成分.

M[i][2][1] = M[i - 1][2][1];

// (3, 3)成分.

M[i][2][2] = M[i - 1][2][2];

}

// 2. 反時計回り(90度回転).

// (x, y, 1) -> (-y, x, 1)

if(o == 2){

// (1, 1)成分.

M[i][0][0] = -M[i - 1][1][0];

// (1, 2)成分.

M[i][0][1] = -M[i - 1][1][1];

// (1, 3)成分.

M[i][0][2] = -M[i - 1][1][2];

// (2, 1)成分.

M[i][1][0] = M[i - 1][0][0];

// (2, 2)成分.

M[i][1][1] = M[i - 1][0][1];

// (2, 3)成分.

M[i][1][2] = M[i - 1][0][2];

// (3, 1)成分.

M[i][2][0] = M[i - 1][2][0];

// (3, 2)成分.

M[i][2][1] = M[i - 1][2][1];

// (3, 3)成分.

M[i][2][2] = M[i - 1][2][2];

}

// 3. 直線 x = p で対称移動.

// (x, y, 1) -> (2 * p - x, y, 1)

if(o == 3){

// (1, 1)成分.

M[i][0][0] = -M[i - 1][0][0] + 2 * a * M[i - 1][2][0];

// (1, 2)成分.

M[i][0][1] = -M[i - 1][0][1] + 2 * a * M[i - 1][2][1];

// (1, 3)成分.

M[i][0][2] = -M[i - 1][0][2] + 2 * a * M[i - 1][2][2];

// (2, 1)成分.

M[i][1][0] = M[i - 1][1][0];

// (2, 2)成分.

M[i][1][1] = M[i - 1][1][1];

// (2, 3)成分.

M[i][1][2] = M[i - 1][1][2];

// (3, 1)成分.

M[i][2][0] = M[i - 1][2][0];

// (3, 2)成分.

M[i][2][1] = M[i - 1][2][1];

// (3, 3)成分.

M[i][2][2] = M[i - 1][2][2];

}

// 4. 直線 y = q で対称移動.

// (x, y, 1) -> (x, 2 * q - y, 1)

if(o == 4){

// (1, 1)成分.

M[i][0][0] = M[i - 1][0][0];

// (1, 2)成分.

M[i][0][1] = M[i - 1][0][1];

// (1, 3)成分.

M[i][0][2] = M[i - 1][0][2];

// (2, 1)成分.

M[i][1][0] = -M[i - 1][1][0] + 2 * a * M[i - 1][2][0];

// (2, 2)成分.

M[i][1][1] = -M[i - 1][1][1] + 2 * a * M[i - 1][2][1];

// (2, 3)成分.

M[i][1][2] = -M[i - 1][1][2] + 2 * a * M[i - 1][2][2];

// (3, 1)成分.

M[i][2][0] = M[i - 1][2][0];

// (3, 2)成分.

M[i][2][1] = M[i - 1][2][1];

// (3, 3)成分.

M[i][2][2] = M[i - 1][2][2];

}

return;

}

// X座標, Y座標について, アフィン変換を行う.

// @param M: アフィン変換に対応する行列.

// @param i: アフィン変換に対応する行列(index).

// @param X: アフィン変換前のX座標.

// @param Y: アフィン変換前のY座標.

// @return: アフィン変換後のX座標, Y座標.

LL* affine(LL (&M)[202020][3][3], int i, LL X, LL Y){

static LL ret[2];

ret[0] = M[i][0][0] * X + M[i][0][1] * Y + M[i][0][2] * 1;

ret[1] = M[i][1][0] * X + M[i][1][1] * Y + M[i][1][2] * 1;

return ret;

}

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld %lld", &x[i], &y[i]);

// 2. 行列の初期化.

matrix[0][0][0] = matrix[0][1][1] = matrix[0][2][2] = 1;

// 3. アフィン変換の事前計算.

int M;

scanf("%d", &M);

rep(i, M){

// 3-1. 操作情報.

int o, a = 0;

scanf("%d", &o);

if(o == 3 || o == 4) scanf("%d", &a);

// 3-2. 行列更新.

affineTransformation(matrix, i + 1, o, a);

}

// 4. クエリ回答.

int Q;

scanf("%d", &Q);

rep(i, Q){

// 4-1. クエリ情報.

int a, b;

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

b--;

// 4-2. 座標計算.

LL* ans = affine(matrix, a, x[b], y[b]);

// 4-3. 出力.

printf("%lld %lld\n", ans[0], ans[1]);

}

return 0;

}

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

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

[入力例]
2
1000000000 0
0 1000000000
4
3 -1000000000
4 -1000000000
3 1000000000
4 1000000000
2
4 1
4 2

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

[入力例]
10
-774 10125
1227 6704
10975 5670
-2768 -7746
5036 -5052
2216 -7065
3586 -1589
4670 11782
-6248 -10410
9051 3889
20
2
4 -6247
1
3 4364
2
3 2382
2
1
4 -8441
3 -2451
2
3 -10758
3 4128
4 -5352
1
3 3017
3 -3497
3 7103
2
1
15
13 5
15 1
7 7
17 10
11 9
10 2
14 5
17 4
12 6
8 1
14 4
1 9
20 5
18 6
3 4

[出力例]
72912 -4614
9087 -67102
-24808 3175
-10177 -76927
31856 744
-16370 -39331
72912 -6090
-21812 -65108
-61836 -2601
14889 20448
65108 -8784
10410 -6248
33324 -72912
35337 -70092
-9726 -7746

100

101

102

103

104

105

106

107

[入力例]

1 2

3 3

4 2

0 1

1 1

2 1

3 1

4 1

[出力例]

1 2

2 -1

4 -1

1 4

1 0

※AtCoderテストケースより

[入力例]

1000000000 0

0 1000000000

3 -1000000000

4 -1000000000

3 1000000000

4 1000000000

4 1

4 2

[出力例]

5000000000 4000000000

4000000000 5000000000

※AtCoderテストケースより

[入力例]

-774 10125

1227 6704

10975 5670

-2768 -7746

5036 -5052

2216 -7065

3586 -1589

4670 11782

-6248 -10410

9051 3889

4 -6247

3 4364

3 2382

4 -8441

3 -2451

3 -10758

3 4128

4 -5352

3 3017

3 -3497

3 7103

13 5

15 1

7 7

17 10

11 9

10 2

14 5

17 4

12 6

8 1

14 4

1 9

20 5

18 6

3 4

[出力例]

72912 -4614

9087 -67102

-24808 3175

-10177 -76927

31856 744

-16370 -39331

72912 -6090

-21812 -65108

-61836 -2601

14889 20448

65108 -8784

10410 -6248

33324 -72912

35337 -70092

-9726 -7746

■参照サイト
AtCoder Beginner Contest 189

2021年1月24日2021年1月24日

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

C++の練習を兼ねて, AtCoder Beginner Contest 189 の問題C (Mandarin Orange) ～問題D (Logical Expression) を解いてみた.

■感想.
1. 問題Cは, 計算量を削減する方針が見えなかったので, 解説を参考に実装して, AC版に到達できたので, 良かったと思う.
2. 問題Dは, dp更新式が抽出できたので, AC版に到達できたと思う, 苦手な dp の訓練が積めたので良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイト AtCoder Beginner Contest 189 解説の各リンクをご覧下さい.

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

// 解き直し.
// https://atcoder.jp/contests/abc189/editorial/533
// C++(GCC 9.2.1)
#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[10101];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &a[i]);
    
    // 2. 全探索.
    int ans = 0;
    rep(l, N){
        int x = a[l];
        repx(r, l, N){
            // [l, r] の 最小値.
            x = min(x, a[r]);
            
            // ans更新.
            ans = max(ans, x * (r - l + 1));
        }
    }
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

// 解き直し.

// https://atcoder.jp/contests/abc189/editorial/533

// C++(GCC 9.2.1)

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

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

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

// 2. 全探索.

int ans = 0;

rep(l, N){

int x = a[l];

repx(r, l, N){

// [l, r] の最小値.

x = min(x, a[r]);

// ans更新.

ans = max(ans, x * (r - l + 1));

}

// 3. 出力.

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

return 0;

}

[入力例]
6
2 4 4 9 4 9

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

[入力例]
6
200 4 4 9 4 9

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

[入力例]
15
3 7 5 6 12 3 2 17 23 15 22 27 10 19 18

[出力例]
80

[入力例]
27
31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58

[出力例]
345

[入力例]

2 4 4 9 4 9

[出力例]

※AtCoderテストケースより

[入力例]

200 4 4 9 4 9

[出力例]

200

※AtCoderテストケースより

[入力例]

3 7 5 6 12 3 2 17 23 15 22 27 10 19 18

[出力例]

[入力例]

31 41 59 26 53 58 97 93 23 84 62 64 33 83 27 9 50 28 84 19 71 69 39 93 75 10 58

[出力例]

345

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

// C++(GCC 9.2.1)
#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--)
LL dp[66][2];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    
    // 2. 初期値設定.
    dp[0][0] = 1; // y[0] が True.
    dp[0][1] = 1; // y[0] が False.
    
    // 3. dp更新.
    repx(i, 1, N + 1){
        // 3-1. AND／OR情報取得.
        char c[11];
        scanf("%s", c);
        string s(c);
        
        // 3-2. AND の 場合.
        if(s == "AND"){
            // y[i] が True.
            dp[i][0] += dp[i - 1][0]; // x[i] が True.
            
            // y[i] が False.
            dp[i][1] += dp[i - 1][0];     // x[i] が False.
            dp[i][1] += dp[i - 1][1] * 2; // x[i] が True／False.
        }
        
        // 3-3. OR の 場合.
        if(s == "OR"){
            // y[i] が True.
            dp[i][0] += dp[i - 1][0] * 2; // x[i] が True／False.
            dp[i][0] += dp[i - 1][1];     // x[i] が True.
            
            // y[i] が False.
            dp[i][1] += dp[i - 1][1]; // x[i] が False.
        }
    }
    
    // 4. 出力.
    printf("%lld\n", dp[N][0]);
    return 0;
    
}

// C++(GCC 9.2.1)

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

LL dp[66][2];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

// 2. 初期値設定.

dp[0][0] = 1; // y[0] が True.

dp[0][1] = 1; // y[0] が False.

// 3. dp更新.

repx(i, 1, N + 1){

// 3-1. AND／OR情報取得.

char c[11];

scanf("%s", c);

string s(c);

// 3-2. AND の場合.

if(s == "AND"){

// y[i] が True.

dp[i][0] += dp[i - 1][0]; // x[i] が True.

// y[i] が False.

dp[i][1] += dp[i - 1][0]; // x[i] が False.

dp[i][1] += dp[i - 1][1] * 2; // x[i] が True／False.

}

// 3-3. OR の場合.

if(s == "OR"){

// y[i] が True.

dp[i][0] += dp[i - 1][0] * 2; // x[i] が True／False.

dp[i][0] += dp[i - 1][1]; // x[i] が True.

// y[i] が False.

dp[i][1] += dp[i - 1][1]; // x[i] が False.

}

// 4. 出力.

printf("%lld\n", dp[N][0]);

return 0;

}

[入力例]
2
AND
OR

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

[入力例]
5
OR
OR
OR
OR
OR

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

[入力例]
10
AND
OR
AND
OR
OR
AND
AND
OR
AND
OR

[出力例]
1333

[入力例]
30
AND
OR
OR
AND
AND
AND
AND
OR
AND
OR
AND
AND
OR
OR
OR
OR
AND
OR
AND
AND
OR
AND
OR
OR
AND
AND
AND
OR
AND
AND

[出力例]
296084749

[入力例]

AND

[出力例]

※AtCoderテストケースより

[入力例]

[出力例]

※AtCoderテストケースより

[入力例]

AND

[出力例]

1333

[入力例]

AND

[出力例]

296084749

■参照サイト
AtCoder Beginner Contest 189

個人用メモ帳

投稿

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

C++の練習を兼ねて, AtCoder Regular Contest 084 の問題D (Small Multiple)を解いてみた.

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

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

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の問題C (Digital Graffiti), 問題E (Come Back Quickly) ～問題F (GCD or MIN) を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 038 の問題C (茶碗と豆)を解いてみた.

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

C++の練習を兼ねて, AtCoder Regular Contest 040 の問題C (Z塗り)を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 190 の問題F (Shift and Inversions)を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 190 の問題C (Bowls and Dishes) ～問題D (Staircase Sequences) を解いてみた.

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

C++の練習を兼ねて, AtCoder Grand Contest 038 の問題B (Sorting a Segment) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 189 の問題E (Rotate and Flip) を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 189 の問題C (Mandarin Orange) ～問題D (Logical Expression) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 084 の 問題D (Small Multiple)を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の 問題C (Digital Graffiti), 問題E (Come Back Quickly) ～ 問題F (GCD or MIN) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 038 の 問題C (茶碗と豆)を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 040 の 問題C (Z塗り)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 190 の 問題F (Shift and Inversions)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 190 の 問題C (Bowls and Dishes) ～ 問題D (Staircase Sequences) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 038 の 問題B (Sorting a Segment) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 189 の 問題E (Rotate and Flip) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 189 の 問題C (Mandarin Orange) ～ 問題D (Logical Expression) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 084 の問題D (Small Multiple)を解いてみた.

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

C++の練習を兼ねて, AtCoder Beginner Contest 191 の問題C (Digital Graffiti), 問題E (Come Back Quickly) ～問題F (GCD or MIN) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 038 の問題C (茶碗と豆)を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 040 の問題C (Z塗り)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 190 の問題F (Shift and Inversions)を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 190 の問題C (Bowls and Dishes) ～問題D (Staircase Sequences) を解いてみた.

C++の練習を兼ねて, AtCoder Grand Contest 038 の問題B (Sorting a Segment) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 189 の問題E (Rotate and Flip) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 189 の問題C (Mandarin Orange) ～問題D (Logical Expression) を解いてみた.