monkukui のページ

競技プログラミングや北海道のおいしいご飯について書きます

RUPC2019 day3 の writer 解まとめ

RUPC 2019 お疲れさまでした
day3 北大セットの writer 解(A B C D F) を掲載します
詳しい解説などは解説スライドを参照ください

[問題リンク]
Aizu Online Judge Arena

A問題: 情報検索

尺取り解を掲載します

#include<iostream>
#include<vector>
using namespace std;

int main(){

    int n, m; cin >> n >> m;
    vector<int> a(n);
    vector<int> b(m);
    for(int i = 0; i < n; i++) cin >> a[i];
    for(int i = 0; i < m; i++) cin >> b[i];

    vector<int> and_result;
    vector<int> or_result;

    int j = 0;
    for(int i = 0; i < n; i++){
        while(j < m && b[j] <= a[i]){

	    if(a[i] == b[j]){ 
		and_result.push_back(a[i]);
	    }else{ 
		or_result.push_back(b[j]);
	    }
    
            j++;
	}
		
	or_result.push_back(a[i]);
    }

    for(;j < m; j++) or_result.push_back(b[j]);

    cout << and_result.size() << " " << or_result.size() << endl;
    for(int i = 0; i < and_result.size(); i++) cout << and_result[i] << endl;
    for(int i = 0; i < or_result.size(); i++) cout << or_result[i] << endl;
    return 0;
}

B 問題: 括弧を語る数

本質は同じですが、僕は stack を使いませんでした

#include<iostream>
#include<vector>
using namespace std;

int main(){

    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++){
        //i 番目の閉じ括弧が in 番目の開き括弧に対応
        int in; cin >> in;
        in--;
        a[in] = i;
    }

    vector<int> vec(n, 0);
    
    int cnt = 0;
    for(int i = 0; i < n; i++){

        //i := 消費している開き括弧
        //cnt := 消費している閉き括弧
        int idx = i + a[i] - cnt;
        if(idx < 0 || n - 1 < idx){
            cout << ":(" << endl;
            return 0;
        }
        vec[idx]++;
        cnt += vec[i];
    }

    for(int i = 0; i < n; i++){
        cout << "(";
        for(int j = 0; j < vec[i]; j++) cout << ")";
    }

    cout << endl;

    return 0;
}

C 問題: 約数ゲーム

実装自体は素因数分解と約数列挙です

#include<iostream>
#include<vector>
#include<map>
using namespace std;

#define int long long

vector<int> ans_max(int n){
    vector<int> res;
    for(int i = 1; i * i <= n; ++i){
        if(n % i != 0) continue;
        res.push_back(i);
        if(n/i == i) continue;
        res.push_back(n/i);
    }
    return res;
}

map<int, int> ans_min(int n){
    map<int, int> res;
    if(n == 1){
        res[n] = 1;
        return res;
    }
    for(int i = 2, _n = n; i*i <= _n; i++){
        while(n % i == 0) {
            ++res[i];
            n /= i;
        }
    }

    if(n != 1) res[n] = 1;
    return res;
}

signed main(){
    
    int n; cin >> n;
    cout << ans_min(n).size() << " " << ans_max(n).size() - 1 <<  endl;
    return 0;
}

D問題 矢

矢の長さにかかわらず、m[0] - 1 の損失はおこります。
また x = n + 1 の位置に送風機があることとします。
こうすることで、座標の両端に送風機があることとして問題を解くことができます。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){

    //入力
    int N, M; cin >> N >> M;
    vector<int> m(M);
    for(int i = 0; i < M; i++) cin >> m[i];
    m.push_back(N + 1);
    vector<int> a(N, 0);

    // 前処理
    for(int i = 1; i <= M; i++){
        a[m[i] - m[i - 1] - 1]++;
    }

    vector<int> dp(N + 1);
    dp[N] = m[0] - 1;
    int sum = 0;
    for(int i = N - 1; i >= 0; i--){
        sum += a[i];
        dp[i] = dp[i + 1] + sum;
    }

    //二分探索
    int q; cin >> q;
    for(int i = 0; i < q; i++){
        int x; cin >> x;
        int l = 0;
        int r = N + 1;
        while(r - l > 1){
            int d = (r + l) / 2;
            if(dp[d] > x) l = d;
            else r = d;
        }

        if(r == N + 1) cout << -1 << endl;
        else cout << r << endl;
    }

    return 0;
}

問題F: 赤黒そーるじぇむ

包除原理です。
包除原理を知ってる人は解説スライドを参考にしてください。
知らない人は以下のスライドを参考にしてください。
http://compro.tsutajiro.com/archive/181015_incexc.pdf

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2020;
int comb[MAXN][MAXN];
int N, M;

void init(){
    for(int i = 0; i < MAXN; i++){
        comb[i][0] = 1;
        for(int j = 1; j <= i; j++){
            comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M;
        }
    }
}

int mod_pow(int x, int n){
    int res = 1;
    while(n > 0){
        if(n & 1) res = res * x % M;

        x = (x * x) % M;
        n = n >> 1;
    }
    return res;
}


signed main(){

    cin >> N >> M;
    init();
    int ans = 0;

    // r := 赤の個数
    // b := 黒の個数
    for(int r = 1; r < N; r++){
        int b = N - r;
        int sum = 0;
        
        // x := 絶対無視する黒の個数
        for(int x = 0; x <= b; x++){
            int canUse = (b - x);
            int val = (mod_pow(2, canUse) - 1 + M) % M;
            val = mod_pow(val, r) % M;
            val = val * comb[b][x];
            val %= M;
            if(x % 2 == 0) sum = (sum + val    ) % M;
            else           sum = (sum - val + M) % M;
            sum %= M;
        }

        ans += ( ( ( sum % M * comb[N][r] ) % M * mod_pow(2, r * (r - 1) / 2) ) % M * mod_pow(2, b * (b - 1) / 2) ) % M;
        ans %= M;
    }

    cout << ans << endl;
    return 0;
}