AtCoder Beginner Contest 126[ABC126]の復習

いまさらながらふくしゅー

atcoder.jp

A - Changing a Character

小文字を大文字にする。大文字小文字は32離れている。

Asciiコード調べるのに時間かかった。

#include <iostream>
#include <string>

int main() {
  int N, K;
  std::string S;
  std::cin >> N >> K;
  std::cin >> S;

  S[K - 1] += 32;

  std::cout << S << std::endl;
}

B - YYMM or MMYY

12がどうなっているか判定するだけ。'0'は48だよ。 Ascii調べたから文字→数字は計算で。

#include <iostream>
#include <string>

int main() {
  std::string S;
  std::cin >> S;
  int prev = (S[0] - 48) * 10 + (S[1] - 48);
  int next = (S[2] - 48) * 10 + (S[3] - 48);

  bool prev_flag = false;
  bool next_flag = false;

  if ((0 < prev) && (prev < 13)) {
    prev_flag = true;
  }
  if ((0 < next) && (next < 13)) {
    next_flag = true;
  }

  std::string result;

  if (prev_flag & next_flag) {
    result = "AMBIGUOUS";
  } else if (prev_flag) {
    result = "MMYY";
  } else if (next_flag) {
    result = "YYMM";
  } else {
    result = "NA";
  }

  std::cout << result << std::endl;
}

C - Dice and Coin

すごく初手で決まるゲームだなと思った(こなみ

while (v <= K) {

って書いててテストケースが合致しない？なんで？ってなって辛かった。 出力printfで書けばsetprecisionとかしなくていいのにね。

#include <iomanip>
#include <iostream>

int main() {
  int N, K;
  std::cin >> N >> K;

  double over_K = 0.0;

  double sum = 0.0;
  for (int i = 1; i <= N; ++i) {
    int v = i;
    double prov = 1.0;
    while (v < K) {
      prov *= 0.5;
      v *= 2;
    }
    sum += prov;
  }

  double result = sum / N;

  std::cout << std::setprecision(20) << result << std::endl;

  return 0;
}

D - Even Relation

解説読んでも問題文の意味が分からない。なんで。

当日は意味が分からない？？？でタイムアップ。Eやればよかったのにね。

E - 1 or 2

異世界転生してカードに書かれた整数を知ることができるのでゴリゴリと書くだけ。

最初LUTで解こうとしたけど大変だったので、適当に書いた。 これグラフで連結数っていうのかって解説見て思った。

queue使ったほうが実装楽だけど、vectorでごり押したほうがpop無い分速そう。 hintのclearはおまけ。やる必要ないしやるだけ遅くなるよ(多分

#include <iostream>
#include <queue>
#include <vector>

int main() {
  int N, M;
  std::cin >> N >> M;
  std::vector<std::vector<int>> hint(N);
  std::vector<int> lut(N);

  for (int i = 0; i < M; ++i) {
    int x, y, z;
    std::cin >> x >> y >> z;
    hint[x - 1].push_back(y - 1);
    hint[y - 1].push_back(x - 1);
  }

  std::vector<int> chain;
  int num = 0;

  for (int i = 0; i < N; ++i) {
    int table;
    if (lut[i] == 0) {
      ++num;
      lut[i] = num;
      chain.clear();
    } else {
      continue;
    }

    chain.push_back(i);

    for (int i = 0; i < chain.size(); ++i) {
      auto c = chain[i];
      for (auto &h : hint[c]) {
        if (lut[h] == 0) {
          lut[h] = num;
          chain.push_back(h);
        }
      }
      hint[c].clear();
    }
  }

  int result = num;

  std::cout << result << std::endl;

  return 0;
}

F - XOR Matching

M=2とM=3の時にどうすればいいのか、紙に書いてたら真ん中と端に目的の値おいて、あとは他の値でサンドイッチすればいいことに気付いた。

M=2、K=1なら、1 0 2 3 1 3 2 0

1と1の間は0 xor 2 xor 3=1になる。

0と0の間は2 xor 3 xor 1 xor 3 xor 2=1になる。

2のM乗未満の値を1つずつ取り出して排他的論理和を取ると、M=2の場合は0 xor 1 xor 2 xor 3=0、という感じで0になるので、そこから目的の値を引っこ抜いて端と中央に配置すればOK。 もちろん2のM乗<=Kの時点で解けない。

例示は理解の試金石。

例外ケースが入力例にあったので例外ケースはスムーズに書けた。

出力でstringstream使ったほうがいいかなと思ったけど、とりあえず書いたら通ったのであまり気にしないことにした。

#include <cmath>
#include <iostream>
#include <vector>

int main() {
  int M, K;
  std::cin >> M >> K;

  int max = 1 << M;
  std::vector<int> result(max * 2);

  if (max <= K) {
    std::cout << -1 << std::endl;
    return 0;
  }

  if (M == 0) {
    if (K == 1) {
      std::cout << -1 << std::endl;
      return 0;
    } else {
      result[0] = 0;
      result[1] = 0;
    }
  } else if (M == 1) {
    if (K == 1) {
      std::cout << -1 << std::endl;
      return 0;
    } else {
      result[0] = 0;
      result[1] = 0;
      result[2] = 1;
      result[3] = 1;
    }
  } else {
    // 最初と真ん中らへんにKを配置する
    result[0] = result[max] = K;

    int val = 0;
    for (int i = 1; i < max; ++i) {
      if (val == K) {
        ++val;
      }
      result[i] = result[result.size() - i] = val;
      ++val;
    }
  }

  for (auto r : result) {
    std::cout << r << " ";
  }
  std::cout << std::endl;
}