RUPC2019 day3 の writer 解まとめ
RUPC 2019 お疲れさまでした
day3 北大セットの writer 解(A B C D F) を掲載します
詳しい解説などは解説スライドを参照ください
RUPC Day3 の解説が生えたマジ?
— tsutaj (@_TTJR_) March 7, 2019
※download または full screen しないと見れないものが一部あり
A: https://t.co/B9W5qJAu1O
B: https://t.co/FHgjp89tUp
C: https://t.co/kYLnbyiHCu
D: https://t.co/MkOa5IcXf1
E: https://t.co/bQA621ssXS
F: https://t.co/7u2EYYzcwO
G: https://t.co/9FB0spIaoE
[問題リンク]
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; }