yukicoder982を解いた

はじめに (ネタバレ無し)

こんにちは
ひぽたふです。

解きながらの考察、実際の解法をまとめておこうかなと思います。

今回解いた問題はこれです。

No.982 Add - yukicoder

星2の問題です。
あんまりよろしくない解き方をしちゃいました。

以下はネタバレがあるので見る際は注意してください。

解きながらの考察 (ネタバレ　方針まで)

ここからはネタバレがあります。 問題を解いている際に考えていたことをまとめておこうかなと思います。

---

問題概要

正の整数A, Bが与えられる。

非負整数x, yを使って N = Ax + By と表せるならNは「いい整数」。
何個「いい整数」でないものは何個存在するか。

そのような数が有限個じゃない時は-1。

考察

片方が1の場合はどんな数でも作れそうだね。
互いに素じゃない場合は、min(A, B)の倍数しか作れないから-1だね。

互いに素な時・・・例えば2, 5を考えると・・・。
3は作れない、4は作れる、5, 6, 7, 8, 9, ... 1と3以外全部作れる！

なんでだろう。

偶数は2のおかげで全部作れて、5以上の奇数は5を入れれば作れるね。

4, 5を考えるとどうだろう。
4, 8, 12, 16...4つ飛びの隙間に5を差し込めば好きな数値を作れそう。
例えば、21が作りたい！って時には19 % 4の3回5を差し込めば作れるね(3 * 5 + 4)

つまり、(a - 1)回5を足す事が出来れば好きな数値を作れそうだね。
5 * 3の15以上の数値は全部作れそうかな。

3, 5を考えるとどうだろう。
(3 - 1)で2、5 * 2で10以上は全部作れるのかな？
11は (11 % 3) * 5 が10になって作れないかと思ったけど、3 * 2 + 5で作れるね。

まだ規則性を見出せてないからもうちょっと考える必要がありそう・・・。

わからないなあ

3000くらいまでで全探索して数え上げてみようかな。
x, y両方やるから計算量は3000²で10⁷は行かないくらいだね。

ちょっとだけ帳尻合わせしたら通っちゃった・・・。

あとがき + 解法(ネタバレ全開)

自分がやった方法と、解説記事に書いてあった方法を書いておこうと思います。

自分がやった方法

x, yを0 ~ 3000で全部試して、Nをソートして出てきてない数値を数え上げました。

3000に根拠はないです。
計算時間が間に合う範囲で取りました。最悪です。

素直に全探索してると、後ろの方で考慮できない数値が出てきて、本来作れるはずのNが出てこない事があります。
ただ、最後に数えた数値ととても離れた位置で齟齬が出始める形だったので、今回は数えてる数値が1000飛んだら計算を打ち切りにしました。

A, Bが小さい値だった事もありそれで通してしまいました。

解説記事より

https://yukicoder.me/problems/3872/editorial

上記の解説を見て納得しました。

探索範囲だけちゃんと考えれば全探索でも良さそうですね。

互いに素な場合を考えるところまでは合っていたみたいです。

そういった場合に ( (A - 1) * (B - 1) ) / 2 をしたら答えが出るみたいです。

ソースコード

int main() {
  ll input(A, B);
  print((A - 1) * (B - 1));

  if (A == 1 || B == 1) {
    print(0);
    return 0;
  }

  vector<ll> result;
  REP(x, 3000) {
    REP(y, 3000) {
      result.push_back(A * x + B * y);
    }
  }

  sort(result.begin(), result.end());
  ll p = 0;
  ll check = 0;
  int ans = 0;
  for(auto v: result) {
    int range = max((v - p) - 1, 0ll);
    if (range > 0) {
      if (v - check > 1000) {
        print(ans);
        return 0;
      }
      check = v;
    }
    ans += range;
    p = v;
  }
  print(-1);
}

マクロに関しては別の記事でまとめてあります。

テンプレート - 競プロを頑張るブログ

REPと入出力のみ使用しています。
REPは半開区間となっています。

https://yukicoder.me/submissions/494150

出てきてない数値を、(出てきた数値 - 直前に出てきた数値 - 1)で求めています。

3と6の間にある整数の個数は 6 - 3 - 1 の2個(4, 5)ですよね。

間に数値が無いと5 - 5 - 1のように-1になるので、0とmaxしています。

難しい問題でした。。。＞＜

それでは、またっ！

おまけ

大変お世話になる<algorithm>のライブラリ。

今回はソートするために使っていますね。

c++20でも追加があるみたいで、要素のシフトができるようになるみたいです。

{1, 2, 3, 4, 5}の{3, 4, 5}を左に2回シフトで{3, 4, 5, 4, 5}になるようです。
使いどころが難しそうですね！