1691->1714(+23). 413位.
A, B, C, D1, D2, E まで出して C 以外は通った.
C は unordered_map killer っぽいもので落ちた.
A. Holidays
問題概要
1 年が 7 日であり, 平日 5 日と休日 2 日が交互にくる.
任意の年を選択するとき, 休日の最大数と最小数を求めよ.
解法
まず, 休日を最大にするとき, 休休平平平平平.
また, 休日を最小にするとき, 平平平平平休休.
基本は だが, 休日の位置と の値によって, 休日を微妙に含んだりするのでそこら辺を場合分けする.
ソース
#include <bits/stdc++.h> using namespace std; int main() { int N; cin >> N; cout << N / 7 * 2 + (N % 7 >= 6) << " " << N / 7 * 2 + min(N % 7, 2) << endl; }
B. Game of Robots
問題概要
ロボットが 体いる.
まず 1 番目のロボットから順に, 番目のロボットは自分の前のロボットが言った番号 をすべて順に復唱したあと, 自分の番号を言う.
番目に言った番号を求めよ.
解法
番目のロボットが発言をする回数は明らかに 回.
よって 1 番目の人から順に見ていき, 回足した結果が最初に 回を上回った人が発言するので, 頑張って計算する.
ソース
から引いてく実装のほうが楽だったかな...
#include <bits/stdc++.h> using namespace std; typedef long long int64; int main() { int64 N, K, id[100001]; cin >> N >> K; int64 pos = 0; for(int i = 1; i <= N; i++) { cin >> id[i]; pos += i; if(pos >= K) { cout << id[i - (pos - K)] << endl; break; } } }
C. Cinema
問題概要
人の科学者が それぞれ使える言語は 1 つである.
また, 映画が 個あり, 音声と字幕は違う言語で, それぞれ である.
1 つの映画を全員で見るとき, もっとも満足できる言語はどれか. 満足とは, 使える言語と音声の言語が一致する人数の多さで, もしそれが等しければ, 使える言語と字幕の言語の一致する人数の多さのことである.
解法
それぞれの映画ごとに, 音声言語を使える人数, 字幕言語を使える人数が分かればそのままなので, map で数える.
ソース
unordered_map 使ったら TLE で落ちた悲しい. 下はそれを map にしただけのやつ.
#include <bits/stdc++.h> using namespace std; typedef long long int64; int64 N, A[200000], M, B[200000], C[200000]; map< int, int > people; int main() { cin >> N; for(int i = 0; i < N; i++) { cin >> A[i]; people[A[i]]++; } cin >> M; for(int i = 0; i < M; i++) { cin >> B[i]; } for(int i = 0; i < M; i++) { cin >> C[i]; } pair< pair< int, int >, int > ret = {{0, 0}, 1}; for(int i = 0; i < M; i++) { ret = max(ret, {{people[B[i]], people[C[i]]}, i + 1}); } cout << ret.second << endl; }
D. Magic Powder
問題概要
1 枚のクッキーを作るには, 種類の材料がそれぞれ 必要である.
いま材料がそれぞれ ある. また魔法のパウダーが あって, これは任意の材料に代用できる.
クッキーは最大で何個作れるか求めよ.
解法
どうみても二分探索.
個作れるかどうかを判定することを考える.
個作るにはそれぞれ材料が 必要である.
すると材料 を作るのに足りない分は であり, この和が 以下であれば作れることが明らかである.
ソース
オーバーフローに注意
#include <bits/stdc++.h> using namespace std; typedef long long int64; int64 N, K, A[100000], B[100000]; bool calc(int64 mid) { int64 dec = K; for(int i = 0; i < N; i++) { if(mid * A[i] > B[i]) { dec -= mid * A[i] - B[i]; if(dec < 0) return(false); } } return(true); } int main() { scanf("%I64d %I64d", &N, &K); for(int i = 0; i < N; i++) { scanf("%I64d", &A[i]); } for(int i = 0; i < N; i++) { scanf("%I64d", &B[i]); } int64 low = 0, high = 1LL << 31; while(high - low > 0) { int64 mid = (low + high + 1) / 2; if(calc(mid)) low = mid; else high = mid - 1; } printf("%I64d\n", low); }
E. Correct Bracket Sequence Editor
問題概要
CBS を以下のように定める.
長さ の CBS に対して, ある初期位置 から次のような文字で操作をする.
- 'L': を左に 1 移動する
- 'R': を右に 1 移動する
- 'D': 番目の括弧とそれに対応する括弧, 及びその間にある括弧をすべて取り除く. その後 の右側に括弧かあれば, を1個右にずらし, なければ1個左にずらす.
長さ の操作履歴が与えられるので, 最終的にできる CBS を求めよ.
解法
すべての対応する括弧はスタックを使ってえいってやれば, 簡単に で求まる. 番目の文字に対応する括弧の位置をそれぞれ とする.
'L'と'R' は簡単そうなので, 'D' の操作について考える.
'D' はすなわち, 区間 を削除するクエリそのものである.
segtree やらなんとか木やら怖いデータ構造を使っても出来そうだけど, の移動の実装が闇になるので, もうちょっと簡単なものを考えようとすると, 双方向リストが使えそうなことが分かる.
双方向リストは, 隣接要素への移動と任意位置への挿入削除が O(1) でできるデータ構造として一般的に知られている.(類題:
バトンリレーゲーム | Aizu Online Judge )
これを配列で実装する. 番目の要素の左隣( とする)と右隣(とする)を持たせておく. 区間 の削除は,の右隣との左隣が変化することと同値なので, と を行えばよい.
ソース
#include <bits/stdc++.h> using namespace std; int N, M, P; string S, T; int prv[600000], nxt[600000], build[600000]; int main() { cin >> N >> M >> P; cin >> S; cin >> T; S = "*" + S; for(int i = 0; i < S.size(); i++) prv[i] = i - 1; for(int i = 0; i < S.size(); i++) nxt[i] = i + 1; stack< int > ss; ss.push(0); for(int i = 1; i < S.size(); i++) { int now = ss.top(); if(S[i] == '(') { ss.push(i); } else { build[i] = now; build[now] = i; ss.pop(); } } for(char query : T) { if(query == 'L') { P = prv[P]; } else if(query == 'R') { P = nxt[P]; } else { int s = min(P, build[P]); int t = max(P, build[P]); nxt[prv[s]] = nxt[t]; prv[nxt[t]] = prv[s]; if(nxt[t] == S.size()) P = prv[s]; else P = nxt[t]; } } string ret = ""; int ptr = 0; while(ptr != S.size()) { if(ptr != 0) ret += S[ptr]; ptr = nxt[ptr]; } cout << ret << endl; }
Fはね、眠くてまともな考察ができなかった.(そもそも追加される番号が固定なことすら考察できなかった)