kichi2004's BLOG

競技プログラミングの参加記とか日常とか。(※Google Analyticsを使用しています)

競プロ

「AtCoder Beginner Contest 141」に参加しました

投稿日:

コンテストページはこちら

結果

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点)

コンテスト中の提出
C++ での提出

天気が 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点)

コンテスト中の提出
C++ での提出

文字列 \(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点)

コンテスト中の提出
C++ での提出

各ラウンドごとに書かれた通りの操作をすると, \(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点)

コンテスト中の提出
C++ での提出

\(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点)

コンテスト中の提出
C++ での提出

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

-競プロ

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


関連記事

no image

「AtCoder Grand Contest 031」に参加しました

コンテストページはこちら 結果 0完 ・順位: 1565位 ・パフォーマンス: 358 ・Rating変化: 1046 -> 992 (-54) 各問題の考察 感想 全くわからなかった。出なかったら良 …

no image

「AtCoder Grand Contest 033」に参加しました

コンテストページはこちら 結果 2完 [A(300), B(600)] 139:48 ペナルティ: 7 (139:48 -> 174:48) ・順位: 817位 (Rated) ・パフォーマンス: 1 …

no image

「AtCoder Beginner Contest 124」に参加しました

コンテストページはこちら 結果 全完 [A(100), B(200), C(300), D(400)] 39:46 ペナルティ: 1 (+5:00 -> 44:46) ・順位: 313位 ・パフォーマ …

no image

「第3回 RCO日本橋ハーフマラソン 予選」に参加しました

コンテストページはこちら 結果:133位(A: 147位、B: 108位) A: 286,823点、B: 493,349点 予選突破はできませんでした。(ほぼ確実) 各問題の考察 A問題 (画像:in …

no image

「AtCoder Beginner Contest 125」に参加しました

コンテストページはこちら 結果 全完 [A(100), B(200), C(300), D(400)] 41:40 ペナルティ: 2 (41:40 -> 51:40) ・順位: 421位 (Unrat …