結果
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番目のパフォーマンスで，黄色パフォを取った大成功回からのレート上昇としては最大でした。
この調子で青を目指したいです。
