AtCoder Beginner Contest 101

はじめに

久しぶりの投稿になります。しばらく忙しくて参加できていませんでした。

今回はAtCoderのBeginner Contest 101の解説と勉強です。
問題はこちらを参照してください。

A - Eating Symbols Easy

相変わらず問題Aは簡単ですね。

自分の回答

#include<iostream>
#include<string>

using namespace std;

int main() {
  string str;
  cin >> str;
  int result = 0;

  for (int i = 0; i < str.size(); ++i) {
    if (str[i] == '+') ++result;
    else --result;
  }

  cout << result << endl;
  return 0;
}

改善点

特になし。

B - Digit Sums

問題Bも相変わらず簡単です。

自分の回答

#include<iostream>

using namespace std;

int main() {
  int N;
  cin >> N;

  int sum = 0, buf = N;
  while (buf != 0) {
    sum += buf % 10;
    buf /= 10;
  }

  if (N % sum == 0) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

改善点

特になし。

C - Minimization

少し頭を使うとすごく簡単に解ける問題です。

自分の回答

まず気づくべき大事な点が三点あります。

一点目は「数列内の最小値は1であること」です。$K$個の要素を含む部分要素列を選んだ後、選んだ部分要素列内の最小の値で$K$個の要素を置き換える操作をした場合、必ず$1$を含む部分要素列が存在するため、最終的にすべての要素を同じ値にするためにはすべての要素を$1$にしなければならないことがわかります。

二点目は「なるべく少ない回数で全ての要素が部分要素列に選択されるには、端から重複要素が1要素になるように選択していく方法であること」です（下図）。

三点目は「選び方（選ぶ部分要素列）が決まっている場合、選ぶ順番を自由に入れ替えることができること」です。後出しジャンケンをイメージしてください。選び方が上述のような最小回数で全ての要素を選択できる選び方だった場合、1を含む要素を一番初めに選択し、その後そこから伝搬するように部分要素列を選択していけばよいということです（下図）。

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

using namespace std;

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

  string buf;
  getline(cin, buf);

  cout << ceil((float)(N - 1) / (float)(K - 1)) << endl;
  return 0;
}

最終的に要素列の入力が一切必要がないところが面白いところです。入力時間を短くするために、上のコードではgetlineで一気に入力を済ませてしまっています。

改善点

特になし。

D - Smuke Numbers

やっぱり問題Dはまだ時間内にすらすら解けない。

自分の回答

まずBrute-Forceな方法ではひたすらにすぬけ数を計算していきます。

$$ 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 99 \\ ,199, 299, 399, 499, 599, 699, 799, 899, 999, ... $$

そのように列挙していった結果、下位の桁は9であることに気づきました。そこで最初に最上位の桁を1ずつ増やしてそれ以下の桁はすべて9とするようなアルゴリズムを組んでSubmitしましたが、WAになってしまいました。

そこでもう少し大きなすぬけ数を考えることにしました。

$$ 1099, 1199, 1299, 1399, 1499, 1599, 1699, 1799, 1899, 1999 \\ , 2999, 3999, 4999, 5999, 6999, ... $$

なんだか最上位以外の桁が9じゃない場合が存在していることがわかります。

とりあえずたくさん書き出して法則性からいけそうだったのですが、今回はここでタイムアウトでした。

改善点

解説をご覧になるとわかりますが、数学的な証明は複雑です。
そうやら下位の方の桁が$9$であることには変わりないように見えます。気を付けるべきは桁数が増えたときのようです。
$\cdots, 799, 899, 999$の次が$1099$となっているように桁が増える場合も$100$を足し続けてすぬけ数になる場合があるのです。

また
$$ 10999, 11999, 12999, 13999, 14999, 15999, 16999, 17999, 18999, 19999 \\, 20999, 21999, 22999, \cdots $$
のようになることもあります。
つまり、差分を足し続けたものと、最上位以外の桁がすべて$9$になるもので$ \frac{x}{S(x)} $を比較すればよいことが推測できます。

以上から以下のようなコードが書けます。

#include<iostream>

using namespace std;

#define ull unsigned long long 

ull S(ull x) {
  ull ret = 0;
  while (x > 0) {
    ret += x % 10;
    x /= 10;
  }
  return ret;
}

int main() {
  ull K;
  cin >> K;
	
  ull cnt = 1;
  ull base = 1;
  ull diff = 1;
  while (cnt <= K && cnt < 10) {
    cout << cnt << endl;
    ++cnt;
  }

  ull val = 9;
  ull x = 10;
  ull buf, s1, s2;
  while (cnt <= K) {
    val += x;
    cout << val << endl;

    s1 = S(val + x);
    s2 = S(val + 10 * x);

    if ((val + x * 10) * s1 <= (val + x) * s2) {
      x *= 10;
    }
    ++cnt;
  }

  return 0;
}

最後に

YouTubeでAtCoderの解説をしているのを知りませんでした。
今回の解説はこちらのリンクからいけます。