kichi2004's BLOG

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

競プロ

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

投稿日:

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

結果

5完 [A(100), B(200), C(300), D(400), E(500)] 57:43 ペナルティ: 0
・順位: 662位 (Unrated)

各問題の解法

A問題 (100点)

提出詳細
SのK文字目がAだったらa、Bだったらb、Cだったらcにして出力する。
計算量 O(1)

int N, K;
string S;
cin >> N >> K >> S;
K--;
if (S[K] == 'A') S[K] = 'a';
else if (S[K] == 'B') S[K] = 'b';
else S[K] = 'c';
cout << S << endl;

B問題 (200点)

提出詳細
計算量 O(1)
上2桁をA、下2桁をB、isOK(X) = X > 0 && X < 12 とすると、 isOK(A) && isOK(B) : "AMBIGUOUS" isOK(A) && not isOK(B) : "MMYY" not isOK(A) && isOK(B) : "YYMM" not isOK(A) && not isOK(B) : "NA"

int tmp;
cin >> tmp;
int A = tmp / 100;
int B = tmp % 100;
if (A && A <= 12) {
 cout << (B && B <= 12 ? “AMBIGUOUS” : “MMYY”) << endl; 
} else {
  cout << (B && B <= 12 ? “YYMM” : “NA”) << endl;
}

C問題 (300点)

提出詳細
言われたことをそのまま実装するだけ

計算量 O(N log K)

int N, K;
cin >> N >> K;

double ans = 0;

for (int i = 0; i < N; i++) {
  int a = i + 1, cnt;
  for(cnt = 0; a < K; a *= 2, cnt++);
  ans += (1.0 / N) * pow(0.5, cnt);
}

cout << fixed << setprecision(12) << ans << endl;

D問題 (400点)

提出詳細
頂点からの距離が偶数の頂点を0、奇数の頂点を1にすればOK。実装重め?

int N;
cin >> N;
vector<vector<pair<int, bool>>> graph(N, vector<pair<int, bool>>());
for (int i = 0; i < N - 1; i++) {
  int u, v, w;
  cin >> u >> v >> w;
  u--; v--;
  graph[u].emplace_back(v, w & 1);
  graph[v].emplace_back(u, w & 1);
}

vector<int> ans(N, -1);
vector<bool> visited(N);
ans[0] = 0;
visited[0] = true;

queue<pair<int, bool>> que;
que.emplace(0, false);

while(!que.empty()) {
  pair<int, bool> p = que.front();
  que.pop();
  for (auto r : graph[p.first]) {
    if (visited[r.first]) continue;
    visited[r.first] = true;

    ans[r.first] = p.second != r.second;
    que.emplace(r.first, p.second != r.second);
  }
}

for (int i = 0; i < N; i++) cout << ans[i] << endl;

E問題 (500点)

提出詳細
Union-Findで、各X[i]・Y[i]を結合し、残った親ノードの個数が答えとなる。
※Union-FindはC#でしか実装していないため、サンプルコードは省略します。提出詳細をご覧ください。

感想

2週連続Unratedで、+32が失われてしまいました。結果としては500まで解けたので、それなりに順調だと思います。
推定パフォーマンスは1551でした。

-競プロ

執筆者:


comment

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

CAPTCHA


関連記事

no image

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

コンテストページはこちら 結果 4完 [A(100), B(200), C(300), D(400)] 72:50 ペナルティ: 4 (-> 92:00) ・順位: 896位 (Rated) ・パフォ …

no image

「エクサウィザーズ 2019」に参加しました

コンテストページはこちら 結果 2完 [A(100), B(200)] 2:00 ペナルティ: 0 ・順位: 550位 (Rated内533位) ・パフォーマンス: 1721 [パフォーマンス最高値] …

no image

競技プログラミングから身を引くことにしました

お詫び 競プロについては、既に復帰しています。記事を書いたからには心情の変化等をお伝えするべきかと思いますが、余裕ができてからにさせていただければと考えています。今後ともよろしくお願いします。 また、 …

no image

JOI 2020 / 2021 二次予選 参加記

はじめに おひさしぶりです.kichi2004 です.競プロ関係の記事は今年の 3 月以来 9 か月ぶりなので,まずはそれについて簡単にお話します.今年の 2 月に,JOI に二次予選落ちしたことや …

no image

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

コンテストページはこちら 結果 3完 [A(100), B(200), C(300)] 11:16 ペナルティ: 0 ・順位: 1006位 ・パフォーマンス: 1108 ・Rating変化: 1039 …