kichi2004's BLOG

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

競プロ

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

投稿日:

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

結果

5完 [A(100), B(200), C(300), D(400), E(500)] 20:16 ペナルティ: 0
・順位: 84位 (Rated内39位) [ABC最高順位]
・パフォーマンス: 2395 (黄) [パフォーマンス最高値]
・Rating変化: 1291 -> 1463 (+172) [Rating最高値]

お知らせ

しばらく記事の更新をお休みしていましたが,ぼちぼち再開したいと思います。
今回から,main関数だけではなく,cppファイルのすべての内容を書く予定です。(意見があれば教えてください。)
また,各問題の解説等にご意見やご質問等がありましたら,Twitter等に気軽にお問い合わせください。

各問題の解法

A問題 “Red or Not” (100点)

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

if文などを使用して,問題文の通りの実装をします。

計算量 O(1)

#include <iostream>

using namespace std;

int main() {
  int a;
  string s;
  cin >> a >> s;
  cout << (a >= 3200 ? s : "red");

  return 0;
}

B問題 “Resistors in Parallel” (200点)

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

問題文通りの実装をします。浮動小数点数を扱う場合は double 型を使います。逆数を求める場合は,1から割ればよいです。
なお,誤差が10^-5まで許容される場合は,出力精度の指定は不要です。

計算量 O(N)

#include <iostream>

using namespace std;

int main() {
  int N; cin >> N;
  double sum = 0;
  for (int i = 0; i < N; ++i) {
    int a; cin >> a;
    sum += 1.0 / a;
  }
  cout << 1.0 / sum << endl;

  return 0;
}

C問題 “Alchemist” (300点)

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

価値が小さい順に鍋に入れていけばよいです。小さい順か大きい順かはサンプル2からエスパーしましょう。

計算量 O(N log N)

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int N; cin >> N;
  vector<int> v(N);
  for (int i = 0; i < N; ++i) cin >> v[i];
  sort(v.begin(), v.end());
  double ans = v[0];
  for (int i = 1; i < N; ++i) {
    ans = (ans + v[i]) / 2;
  }
  cout << ans << endl;

  return 0;
}

D問題 “Ki” (400点)

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

各操作のxを配列に残しておいて,dfsやbfsによって根から順に探索していくことで答えを求めることができます。
各頂点の値は,親の値 + 配列の自分の頂点の値 となります。

計算量 O(N + Q)

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int main() {
  int N, Q;
  cin >> N >> Q;
  vector<vector<int>> G(N);
  for (int i = 0; i < N - 1; ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  vector<int> add(N);
  for (int i = 0; i < Q; ++i) {
    int p, x;
    cin >> p >> x;
    add[--p] += x;
  }

  stack<int> stack;
  stack.push(0);
  vector<int> ans(N);
  vector<bool> vis(N);
  while (!stack.empty()) {
    int now = stack.top();
    vis[now] = true;
    stack.pop();
    ans[now] += add[now];
    for (int next : G[now]) {
      if (vis[next]) continue;
      ans[next] += ans[now];
      stack.push(next);
    }
  }

  for (int i = 0; i < N; ++i) {
    cout << ans[i];
    cout << (i == N - 1 ? '\n' : ' ');
  }

  return 0;
}

この問題の解法について

コンテスト中は,a_iがb_iの親である(b_iがa_iの子である)という保証がされているという誤読をしていて,テストケースでもそのようなケースしか存在せず,この解法でもACすることができました
そのため,コンテスト後に追加された “after_contest” のテストケースは通過せず,WAとなりました
逆向きの辺を張った上で,無限ループ防止のために訪問済みのフラグをたてることで対策可能で,今回の解説に使用したコードでもその対策を使用しています。

E問題 “Strings of Impurity” (500点)

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

はじめに,’a’-‘z’の各文字が,sの何文字めに出現するかをメモします。(11-14行目)
tに出現するすべての文字がsにも出現しない場合は,題意を満たせないため -1 を出力して終了します。
まず, p = 0, q = -1 とおきます。
これは,i-1 文字めが,結合した文字列内で,(sの長さを基準に)何周めの何文字めに出現したかの値 (0-indexed) です。
たとえば, s = “abcd” であって,これを結合した文字列内から示すとき, “abcdabcdabcdabcd….” の下線で示した文字の場合は,p = 2, q = 1 となります。

続いて,各 i (0 <= i < |t|) に対して,以下の処理をします。  t[i] = s[j] (q < j < |s|) を満たす j が存在するならば,q を j の最小の値 にする。 (なお,この j は二分探索によって求めることができます。)
 そうでないなら,pの値をインクリメントし,q を s[j] (0 <= j < |s|) を満たす j の最小の値にする。
以上の操作をすると,p * |s| + q + 1 が答えとなります。

計算量 O(|s| + |t| log |s|)

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main() {
  string s, t; cin >> s >> t;

  map<char, vector<int>> cnt;
  for (int i = 0; i < s.size(); ++i) {
    cnt[s[i]].push_back(i);
  }

  for (char c : t) {
    if(cnt[c].empty()) {
      cout << -1 << endl;
      return 0;
    }
  }

  int p = 0, q = -1;
  for (char c : t) {
    const auto& v = cnt[c];
    int a = upper_bound(v.begin(), v.end(), q) - v.begin();
    if (a != v.size()) {
      //j = v[a]
      q = v[a];
      continue;
    }
    // 条件を満たす j が存在しない場合
    p++;
    q = v[0];
  }

  cout << long(p) * s.size() + q + 1 << endl;

  return 0;
}

全体の感想

約20分で5完し,初めて黄色パフォを取ることができて,レートも爆上がりでした。(なお,順位があと1つ上であれば2400だったようです。ちょっと悔しい。)
新ABCに吸われたレートを取り戻すどころか,Highest を3か月以上ぶりに,109も更新することができました!
この調子で,次回の企業コンでもレートを上げたいなと思います。

-競プロ

執筆者:


comment

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

CAPTCHA


関連記事

no image

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

コンテストページはこちら 結果 2完 [A(400), B(600)] 49:18 ペナルティ: 3 (-> 64:18) ・順位: 736位 (Rated) ・パフォーマンス: 1552 ・Rati …

no image

「AtCoder Beginner Contest 145」A~E問題解説 / 参加記

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 53:22 ペナルティ: 1 (-> 58:22) ・順位: 321位 (Rat …

no image

「Tenka1 Programmer Beginner Contest 2019」に参加しました

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:53 ペナルティ: 0 ・順位: 8位 ・パフォーマンス: 1600 (Inner: 2556) ・Rat …

no image

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

コンテストページはこちら 結果 5完 [A(100), B(200), C(300), D(400), E(500)] 46:53 ペナルティ: 1 (-> 51:53) ・順位: 329位 (Rat …

no image

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

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