[ABC234] E - Arithmetic Number

Q. https://atcoder.jp/contests/abc234/tasks/abc234_e
1. 等差数ってそんなに多くなさそうだから、全部調べ上げちゃう。
どうやら339個しかなさそうです。

1,2,3,4,5,6,7,8,9,
10,11,12,13,14,15,16,17,18,19,
20,21,22,23,24,25,26,27,28,29,
30,31,32,33,34,35,36,37,38,39,
40,41,42,43,44,45,46,47,48,49,
50,51,52,53,54,55,56,57,58,59,
60,61,62,63,64,65,66,67,68,69,
70,71,72,73,74,75,76,77,78,79,
80,81,82,83,84,85,86,87,88,89,
90,91,92,93,94,95,96,97,98,99,
111,123,135,147,159,
210,222,234,246,258,
321,333,345,357,369,
420,432,444,456,468,
531,543,555,567,579,
630,642,654,666,678,
741,753,765,777,789,
840,852,864,876,888,
951,963,975,987,999,
1111,1234,1357,
2222,2345,2468,
3210,3333,3456,3579,
4321,4444,4567,
5432,5555,5678,
6420,6543,6666,6789,
7531,7654,7777,
8642,8765,8888,
9630,9753,9876,9999,
11111,12345,13579,
22222,23456,
33333,34567,
43210,44444,45678,
54321,55555,56789,
65432,66666,
76543,77777,
86420,87654,88888,
97531,98765,99999,
111111,123456,222222,234567,...

実装どうしよう?
1. 等差を-9 ~ 9の19通り
2. 最上位桁の値を1~9の9通りから始める
この条件で作られた値をひたすらlistsにいれていけばいい。

ll X;
set<ll> lists;

void init() {
 for (ll d = -9; d < 10; ++d) { // 等差
   for (ll s = 1; s < 10; ++s) { // 最初の値
     ll ns = s; // 1桁目の値
     ll N = 0;
     rep(i, 18) { // せいぜい18桁まで
       N *= 10; // 桁上げ
       N += ns; // 1桁目を入れる
       if (N > oo) break;
       if (N < 0) break;
       lists.insert(N);

       ns += d; // 次の1桁目の値
       if (ns > 9 || ns < 0) break;
     }
   }
 }
}

int main() {
 cincout();

 init();
 cin >> X;
 auto it = lists.lower_bound(X);
 cout << *it << endl;
}

https://atcoder.jp/contests/abc234/submissions/28426621



Q. 負の値なのに、負の判定に入らないのはなぜ??

int main() {
 cincout();
 ll N = 0;
 ll inf = 2e18;
 while(1) {
   N *= 10;
   N += 1;
   if (N < 0) break;
   if (N > inf) break;
   cout << N << endl;
 }
}
19行目がおかしい。
1
11
111
1111
11111
111111
1111111
11111111
111111111
1111111111
11111111111
111111111111
1111111111111
11111111111111
111111111111111
1111111111111111
11111111111111111
111111111111111111
1111111111111111111
-7335632962598440505 // なんで if (N<0) break; に入っていないんだろう
430646668853801415

A. わからない。
18桁目まで求める、という条件にしないとあぶない。

この記事が気に入ったらサポートをしてみませんか?