結果
5完 [A(100), B(200), C(300), D(400), E(500)] 46:53 ペナルティ: 1 (-> 51:53)
・順位: 329位 (Rated内260位)
・パフォーマンス: 1776 (青)
・Rating変化: 1466 -> 1501 (+35) [Rating最高値]
お知らせ
ABC139,140の解説はお休みとなります。要望があれば,各問題についての解説を書きます。
各問題の解法
A問題 “Weather Prediction” (100点)
天気が Sunny, Cloudy, Rainy, Sunny… と周期的に変化します。
今日の天気が与えられるので,明日の天気を答える問題です。
つまり,今日が Sunny なら Cloudy, Cloudy なら Rainy, Rainy なら Sunny を出力すれば良いです。
これは,if 文を使うことなどで実装できます。
計算量 \(O(1)\)
実装例
#include <string> #include <iostream> using namespace std; int main() { string S; cin >> S; string ans; if (S == "Sunny") ans = "Cloudy"; else if (S == "Cloudy") ans = "Rainy"; else ans = "Sunny"; cout << ans << endl; }
B問題 “Tap Dance” (200点)
文字列 \(S\) が与えられるので,その文字が “踏みやすい文字列” かどうかを判定する問題です。
C++ などの言語では,長さ \(N\) の文字列や配列 \(X\) に対して,添字は \(0\) から \(N-1\) となります。(つまり,\(3\) 番目の要素にアクセスするなら,X[2] と書きます)
そのため,問題内で「奇数文字目」とされているものは,プログラム内では「偶数文字目」となります。
また,奇数文字目で条件を満たさないのは ‘L’,偶数文字目で条件を満たさないのは ‘R’ のみなので,これに一致しないかどうかを判定すれば良いです。
計算量 \(O(|S|)\)
実装例
#include <string> #include <iostream> using namespace std; int main() { string S; cin >> S; const int length = int(S.size()); bool ok = true; for (int i = 0; i < length; i++) { // i % 2 == 0 なら i は 偶数 // 1 なら奇数 if (i % 2 == 1) { //偶数文字目 if (S[i] == 'R') { ok = false; } } else { if (S[i] == 'L') { ok = false; } } } cout << (ok ? "Yes" : "No") << endl; }
C問題 “Attack Survival” (300点)
各ラウンドごとに書かれた通りの操作をすると, \(O(NQ)\) となるので間に合いません。
あるラウンドで 参加者 \(i\ (1 \leq i \leq N)\) が正解すると,正解者以外の全員の点数が1ポイント減るということは,「全員の点数が1ポイント減り,正解者の点数が1ポイント増える」と言い換えられます。
また,途中で点数が加算されることはないので,途中で点数が非正数になったのに,その後に正数になるということはありません。
よって,最初に全員の点数を \(K – Q\) 点にしておいて,各参加者が正解した点数だけ最後に加算すればよいです。
計算量 \(O(N + Q)\)
実装例
#include <iostream> #include <vector> using namespace std; int main() { int N, K, Q; cin >> N >> K >> Q; // あらかじめ全要素を K - Q に初期化しておく vector<int> v(N, K - Q); for (int i = 0; i < Q; i++) { int a; cin >> a; ++v[--a]; } for (int i = 0; i < N; i++) { cout << (v[i] > 0 ? "Yes" : "No") << endl; } }
D問題 “Powerful Discount Tickets” (400点)
\(Y\) 枚の割引券を使うと,品物の値段は \(\frac{1}{2^Y}\) (の小数点以下切り捨て) になります。
これは,割引券を \(1\) 枚使うごとに,品物の値段が \(\lfloor\frac{1}{2}\rfloor\) になるということができます。
割引券を \(1\) 枚使うとき,もっとも割引される値段が大きくなるのは,その時の値段が一番高いものに対して使う場合です。
毎回ソートしていると \(O (NM log N)\) となって間に合いませんが, Priority Queue などのデータ構造を使うと, 一番値段の高いものを取り出す → その値段を半分にする → Queue に戻す という操作を \(M\) 回行うことで,題意を達成することができます。
計算量 \(O(M log N)\)
実装例
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int N, M, a; cin >> N >> M; priority_queue<int> pque; for (int i = 0; i < N; i++) { cin >> a; pque.push(a); } for (int i = 0; i < M; i++) { int now = pque.top(); pque.pop(); now /= 2; pque.push(now); } long long ans = 0; while (!pque.empty()) { ans += pque.top(); pque.pop(); } cout << ans << endl; }
E問題 “Who Says a Pun?” (500点)
まず,2つの部分文字列が重ならないという条件がない場合は,\(S\) と \(S\) の最長共通連続部分列問題を解けばいいことになります。
これは,
\[
dp_{i,j} (0 \leq i, j < N) = \left\{ \begin{array}{ll}
0 & (S_i \neq S_j) \\
1 & (i = 0 \vee j = 0) \\
dp_{i-1,j-1} + 1 & (otherwise)
\end{array} \right.
\]
としたときに,\(max(dp_{i,j})\)を求めることで解くことができます。
また, \(dp_{i,j}\) が \(x\) であるというのは,
\[ S_a (i-x < a \leq i) = S_b (j-x < b \leq j) \]
であるということを表します。
この \(i-x < a \leq i\) と \(j-x < b \leq j\) の区間が重複していなければ,2つの部分文字列も重複していないことになります。
よって,\(dp_{i,j}\) の中で,この条件を満たすものの最大値,つまり
\[max(dp_{i,j}\ (0 \leq i, j < N, i < j - dp_{i,j} + 1 \vee j < i - dp_{i,j} + 1))\]
を求めればよいです。
計算量 \(O(N^2)\)
実装例
#include <iostream> #include <vector> using namespace std; int main() { int N; string S; cin >> N >> S; vector<vector<int>> dp(N, vector<int>(N)); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (S[i] != S[j]) continue; if (i > 0 && j > 0) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = 1; } } int ans = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (dp[i][j] > ans && (j < i - dp[i][j] + 1 || i < j - dp[i][j] + 1)) ans = dp[i][j]; } } cout << ans << endl; }
全体の感想
今回からは解説にもさらに力を入れています。
コンテストの成績については,過去2番目のパフォーマンスで,黄色パフォを取った大成功回からのレート上昇としては最大でした。
この調子で青を目指したいです。