ARC-084-D Small Multiple

問題文

https://beta.atcoder.jp/contests/arc084/tasks/arc084_b

この回じつは 0 完だった。C 問題が解けなかったことに当時深く反省して、

「順序関係のある 3 つのものを決定するには真ん中のものを先に決め打ちしとくとよい」という教訓を得たのを覚えている。

解法

上記 URL から解説 pdf が上がっているので、そっち読むとよい。

感想・教訓

この問題の肝は mod で考えて探索範囲を落とすこと（だと思う）。

普通だと「正整数の範囲でしょ？探索範囲無限じゃん！」

ってなるところを

「倍数がらみだし mod で考えて探索範囲を落とせないか考えてみよう！」

って持っていけたら答えに近づきそう。

もちろん倍数の問題で mod をとることの重要性も再確認

コード

 #include <bits/stdc++.h>

using namespace std;

int main() {
  int k;
  cin >> k;
  vector<int> node(k, 1e9);
  deque<int> dq;
  dq.push_front(1);
  node[1] = 1;
  while (true) {
    int now = dq.front();
    if (now == 0) {
      cout << node[0] << endl;
      return 0;
    }
    dq.pop_front();
    if (node[(now * 10) % k] > node[now]) {
      dq.push_front((now * 10) % k);
      node[(now * 10) % k] = node[now];
    }
    if (node[(now + 1) % k] > node[now] + 1) {
      dq.push_back((now + 1) % k);
      node[(now + 1) % k] = node[now] + 1;
    }
  }
}