緑以下Ratedのdiv4
全完出来たけど前半割と難しくない?後半はdiv3より流石に簡単だったけど(というかdiv3の後ろ難しすぎる)
div4 pretest全完〜 pic.twitter.com/WCQ7opiD7W
— ボンド@競プロ (@bond_cmprog) 2020年5月9日
A. Sum of Round Numbers
問題文
正の整数nが与えられる
nを先頭桁以外が0の整数の和で表現する
そのような整数の最小の数とそのそれぞれの整数を出力せよ
解法
下の桁から見ていき、その桁が0以外なら桁数分掛けたものを答えに加える
提出コード
void solve(){ int n; cin >> n; vector<int> ans; int cur = 1; while(n > 0){ int d = n % 10; if(d > 0) ans.emplace_back(d * cur); cur *= 10; n /= 10; } cout << ans.size() << endl; for(auto x : ans) cout << x << " "; cout << endl; }
B. Same Parity Summands
問題文
正の整数nとkが与えられる
k個の0以上の整数からなる数列aの和がnとなるようなものを見つけたい
ただし、数列の要素の偶奇は全て一致していなければならない
このような数列が存在する時、その一つを出力せよ
解法
頭壊れた
nが奇数、kが偶数のときは絶対作れない
nが奇数、kが奇数のときはなら必ず作れる
nが偶数、kが偶数のときはなら必ず作れる
nが偶数、kが奇数のときはなら必ず作れる
作れるときは一番小さい要素を出力して、最後の一つで帳尻を合わせればいい
提出コード
void solve(){ int n, k; cin >> n >> k; if(n == k){ cout << "YES" << endl; REP(i,k) cout << 1 << " "; cout << endl; return; } if(n < k){ cout << "NO" << endl; return; } if(n & 1){ if(k & 1){ if(n >= k){ cout << "YES" << endl; REP(i,k-1) cout << 1 << " "; cout << n - (k - 1) << endl; } else cout << "NO" << endl; } else cout << "NO" << endl; } else{ if(k & 1){ if(n >= 2 * k){ cout << "YES" << endl; REP(i,k-1) cout << 2 << " "; cout << n - 2 * (k - 1) << endl; } else cout << "NO" << endl; } else{ if(n >= k){ cout << "YES" << endl; REP(i,k-1) cout << 1 << " "; cout << n - (k - 1) << endl; } else cout << "NO" << endl; } } }
C. K-th Not Divisible by n
問題文
正の整数nとkが与えられる
nの倍数でないもののうち、k番目の整数を出力せよ
解法
にぶたんでもできそうだけど算数したほうが早そうなので算数をした
まず、番目のnの倍数以下の整数は全て使うことになる
この時、nの倍数でないものの個数は個となる
そのため、残っている個数は個以下なので、からその分を足していく
ただし、残りが0個のときはその分引いて上げる必要がある
提出コード
void solve(){ ll n, k; cin >> n >> k; ll cur = k / (n - 1) * n; k -= k / (n - 1) * (n - 1); REP(i,k) cur++; if(k % (n-1) == 0) cur--; cout << cur << endl; }
D. Alice, Bob and Candies
問題文
n個のキャンディがありそのサイズはである
Aliceはこのキャンディーを左から、Bobは右から食べていく
この時、1ターンで食べるキャンディのサイズの合計は、その前のターンより心に大きくなるまで食べなければならず、大きくなった瞬間食べるのをやめる
Aliceから最初のターンを始める時、終わるまでにかかるターン数、Aliceが食べたキャンディのサイズの合計、Bobが食べたキャンディのサイズの合計を出力せよ
解法
実際にシミュレートしていけばいい
void solve(){ int n; cin >> n; vector<int> a(n); REP(i,n) cin >> a[i]; int cur = 0; int l = 0, r = n - 1; int turn = 0; int Alice = 0, Bob = 0; while(l <= r){ int tmp = 0; if(turn & 1){ while(tmp <= cur && l <= r){ tmp += a[r]; r--; } Bob += tmp; } else{ while(tmp <= cur && l <= r){ tmp += a[l]; l++; } Alice += tmp; } cur = tmp; turn++; } cout << turn << " " << Alice << " " << Bob << endl; }
E. Special Elements
問題文
n個の正の整数からなる数列aが与えられる
を満たすペア(l, r)が存在する時、をspecialと呼ぶ
与えられた数列aのうち、specialなものの個数を出力せよ
解法
全探索しても十分に間に合うので区間の和を全探索する
メモリの制約が小さいのでしゃくとりっぽくやった
提出コード
void solve(){ int n; cin >> n; vector<int> a(n); map<int, int> mp; REP(i,n){ cin >> a[i]; mp[a[i]]++; } int ans = 0; for(int i=2;i<n;i++){ int sum = 0; REP(j,i) sum += a[j]; if(mp.count(sum)){ ans += mp[sum]; mp.erase(sum); } for(int j=i;j<n;j++){ sum -= a[j-i]; sum += a[j]; if(mp.count(sum)){ ans += mp[sum]; mp.erase(sum); } } } cout << ans << endl; }
F. Binary String Reconstruction
問題文
'0'と'1'からなる"binary string" sがある
sのうち、長さが2の連続部分文字列を考える
この連続部分文字列のうち、'1'が出現する個数が0、1、2個のものの個数をそれぞれn0、n1、n2とする
n0、n1、n2が与えられるのでこれを満たすような文字列 sを出力せよ
これを満たす文字列は必ず存在することが保証される
解法
初めにn0の分だけ"00...0"を作る
今作ったものに"1010..."のように作ったものをくっつける
この時偶数分だけ後ろにつけて、奇数分があれば先頭に1個くっつけると楽
後は先頭か後ろが'1'になっているのでn2分だけ"111..."をくっつける
提出コード
void solve(){ int n0, n1, n2; cin >> n0 >> n1 >> n2; string ans = ""; if(n0 > 0) ans = string(n0+1, '0'); if(n1 > 0){ if(ans == "") ans = '0'; if(n1 % 2 == 0){ REP(i,n1-1){ if(i & 1) ans += '0'; else ans += '1'; } ans = "1" + ans; } else{ REP(i,n1){ if(i & 1) ans += '0'; else ans += '1'; } } } if(ans == "") ans = string(n2+1, '1'); else if(ans[0] == '1') ans = string(n2, '1') + ans; else if(ans.back() == '1') ans += string(n2, '1'); cout << ans << endl; }
G. Special Permutation
問題文
正の整数nが与えられる
1 からnまでの順列pを考える
この時、に対して、を満たすような順列pを求めたい
このような順列が存在する時、そのような順列を一つ出力せよ
解法
実は、のとき ... 7, 5, 3, 1, 4, 2, 4, 6, 8, ... のように[3, 1, 4, 2]の左側に奇数、右側に偶数を並べていくことでそのような順列を作ることが出来る
残り時間が少なかったのもあってコンテスト中は全探索通りそうだなーって思ったので全探索を書いて投げた
間に合いそうだなーって思ったけどちゃんと見積もれてたわけじゃないので、こどふぉだとあんまりやらないほうがいいね
提出コード
void solve(){ int n; cin >> n; if(n <= 2){ cout << -1 << endl; return; } vector<vector<int>> G(n+10); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(i == j) continue; if(2 <= abs(i - j) && abs(i - j) <= 4) G[i].emplace_back(j); } } vector<int> ans; vector<bool> used(n + 10); auto dfs = [&](auto && self, int cur, int par, int cnt) -> bool{ used[cur] = true; if(cnt == n){ ans.push_back(cur); return true; } for(auto nv : G[cur]){ if(nv == par) continue; if(used[nv]) continue; if(self(self, nv, cur, cnt + 1)){ ans.push_back(cur); return true; } } used[cur] = false; return false; }; dfs(dfs, 2, -1, 1); if(ans.size() < n){ cout << -1 << endl; return; } for(auto x : ans) cout << x << " "; cout << endl; }
おわりに
div4楽しい
序盤結構辛く感じたけどrated帯の人どうなんだろうね