ABC 101 (AtCoder Beginner Contest 101) 参加結果 & 解説

参加結果

参加結果は、ABCの3完。
D問題は、かなり粘ったけど力及ばず。
今回のD問題は、いつもより解ける気がしたので悔しい。

レートの上がりが何故か今回良かったので、運が良ければ、次のABCで緑に上がれるかも。
次に期待。

解説

自分で解けたものは、解説。

ABC101 A - Eating Symbols Easy

問題概要

最初、0の数がある。
入力として、'+' か '-' のどちらかの記号を合計で4つ受け取る。
'+' を受け取った場合、数を+1する。
'-' を受け取った場合、数を-1する。
数は最終的にいくらになるか。

解法

string型で入力を受け取り、1文字ずつ確認して答えを求める。

#include <bits/stdc++.h>
using namespace std;

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

  int ans = 0;

  for (int k = 0; k < (int)s.size(); k++) {
    if (s[k] == '+') ans++;
    else ans--;
  }
  cout << ans << endl;
}

ABC101 B - Digit Sums

問題概要

整数 n に対して、n を十進法で表したときの各桁の和を S(n) で表すことにする。
たとえば、S(101)=1+0+1=2 である。
整数 N が与えられたとき、N が S(N) で割り切れるかどうかを判定せよ。

解法

問題としては、各桁の和を求められるかという問題。
各桁の和は、1桁ずつ分割していけばいいので、10で割った余りを足していけば良い。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  int s = 0, tmp = n;

  while (tmp > 0) {
    s += tmp % 10;
    tmp /= 10;
  }
  cout << (n % s == 0 ? "Yes" : "No") << endl;
}

ABC101 C - Minimization

問題概要

1〜N の数列が与えられる。以下の操作を最小回数繰り返すことにより、全部 1 にせよ。
* 数列のうち、連続したk個の要素を選択し、選択した要素の中の最小値で置き換える。

最小回数は、いくらか？

解法

この問題は、難しく考える必要がない。
例えば、このような数列が与えられ、k=3と与えられた場合。 1を含んだ3つを選択していき、すべてを1に変えればいい。
最初の選択で、1を含んだ3つを変更すると考え、その後は、1を含んで2つを変更させていくと考える。
この場合だと、最小回数は、3である。
このように、1を1つだけ含むように選択していくと、最小回数が分かる。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  int ans = 0;

  while (1) {
    if (n <= 0) {
      cout << ans << endl;
      return 0;
    }
    if (ans == 0) {
      ans++;
      n -= k;
    }
    else {
      ans++;
      n -= (k - 1);
    }
  }
}

ABC101 D - Snuke Numbers

問題概要

整数nに対して、各桁の和をS(n)で表す。
正の整数nであって、n < m であるような任意の整数mに対して、n / S(n) <= m / s(m) が成り立つ数を、すぬけ数という。 整数Kが与えられたとき、すぬけ数を小さい方からK個列挙せよ。

解法

自分は、解けなかったが、こちらの解説が分かりやすかった。
分かりやすい解説
自分も、参考にさせて頂いた。
簡単に解説すると、0からすぬけ数を求めていくのではなく、すぬけ数の候補をあらかじめ用意しておき、すぬけ数に当てはまらない数を除いていくというもの。
自分は、0からすぬけ数を求めていこうとしていたので、計算に時間がかかってTLEや要素が足りずWAになったりした。

#include <bits/stdc++.h>
using namespace std;

long long f(long long n) {
  long long res = 0;
  while (n > 0) {
    res += n % 10;
    n /= 10;
  }
  return res;
}

double g(long long n) {
  return (double)(n)/f(n);
}

int main() {
  vector<long long> res;
  long long base = 1;

  // まずは候補を (1〜150)99999 的なやつを全列挙
  for (int k = 0; k < 15; k++) {
    for (int l = 1; l < 150; l++) {
      res.push_back(base * (l + 1) - 1);
    }
    base *= 10;
  }
  sort(res.begin(), res.end());
  res.erase(unique(res.begin(), res.end()), res.end());

  // ダメなやつを除く
  for (long long k = 0; k < res.size(); k++) {
    for (long long l = k + 1; l < res.size(); l++) {
      if (g(res[k]) > g(res[l])) {
        res.erase(res.begin() + k--);
        break;
      }
    }
  }

  long long num;
  cin >> num;
  for (long long k = 0; k < num; k++) {
    cout << res[k] << endl;
  }
}

反省

そろそろ4完したいなーというお気持ち。
前回と今回のD問題は解ける気がしたが、解けなかったので、過去のD問題を漁る予定。 ただ、いい解説がなかったりするので、どうしようか迷い中＞＜