| About me | Archives | Tags |
Apr 20, 2020, 05:28 #Procon
残念ながらコンテストは Unrated になってしまった…。ハマって時間内に解けなかったので反省。
AtCoder Beginner Contest 163 D - Sum of Large Numbers
みてくださった方へ
Tex 記法つかえないので数式がめちゃくちゃよみづらいです。すみません。
N + 1 個の整数 10^(100), 10^(100) + 1, …, 10^(100) + N から K 個以上えらんで和をつくる。
この和としてあり得る整数の数を 10^(9) + 7 で割ったあまりを求めよ。
問題文みてぎょっとしたけど、たとえば N = 3, K = 2 のとき
から 2 つ以上えらんで和をつくるということ。
「じゃあ端数を組み合わせて和をつくってそれを数えればいいから二項定理つかえばいいのかな」
とおもって実装してみるも 3 つめのサンプルケースが通らず見事撃沈。
実験や深い考察をせずに、組み合わせの総数を求める問題に読みかえてしまった。
2^(N+1) - (N+1_C_K) を求める実装をしてみたら 1 つめのサンプルケースは通った。N = 3, K = 2 のとき
2^(4) - (4_C_2) = 16 - 6 = 10
となり、出力例とおなじになる。
2 つめは通らなかった。これは K が最大（K = N + 1）の場合なので、コーナーケースとして対応した。
しかし 3 つめは通らない。
なぜかというと、1 つめの出力例をよくみればわかるのだが、和が 2 * 10^(100) + 3 になるえらびかたは 2 通りある。
これを見落としているので通るわけがなかった。ちゃんと出力例を精査しましょう…。
コンテストは時間制限があるので手を動かしていないと不安になるので手を動かしてしまいがち。
見切り発車の実装が正しいことはまずないのできちんと考察をする。
今回でいえばサンプルケースひとつだけにあてはまる論理を見切り発車で実装してしまっている。
N = 3, K = 2 のときはあてはまるけど、じゃあ N = 4 のときは？ N = 5 のときは？ という考察をしていないので論理が飛躍している。
さすがにこれは基本中の基本というか「考察しないなら競プロやる意味あんのか」というかんじなので改めたい。
紙とペンで実験するのもありだけど、エディタで同じことをやるのもいいかなとおもった。
ひとつのサンプルケースにあてはまるコードを愚直に書いてみて、法則性をさぐるとか…。
今回の問題でやってみる。わかりづらいので 10^(100) = x とおく。
出力例をよくみると
という具合になっている。
和の最小と最大に注目すると
というふうにだんだん法則がみえてきた。どうやら
(最大の和) - (最小の和 - 1) = (和の個数)
すこしわかりやすくすると
(最大の和) - (最小の和) + 1 = (和の個数)
っぽいので、コードに落とし込む。
ans = ((N - 0) + (N - 1)) - (0 + 1) + 1 // 数を 2 つえらぶ場合
+ ((N - 0) + (N - 1) + (N - 2)) - (0 + 1 + 2) + 1 // 数を 3 つえらぶ場合
+ ((N - 0) + (N - 1) + (N - 2) + (N - 3) - (0 + 1 + 2 + 3) + 1; // 数を 4 つえらぶ場合
// ans = 2N - 2(0 + 1) + 1
// + 3N - 2(0 + 1 + 2) + 1
// + 4N - 2(0 + 1 + 2 + 3) + 1
前の項へ法則にしたがってなにかを足すと次の項が求められるようだ（累積和）。
// 数を i 個えらぶ
sum[1] = N + 1; // i == 1
sum[i] = sum[i-1] + i*N - (i-1)*i + 1; // 1 < i && i <= N+1
// -2(0 + 1 + ... の部分は等差数列の和の公式に変形した
ということで累積和をつかえば数を K 個以上えらんだ和の個数が求められそうだ、ということがわかった。
「とりあえず実装」ではなく「とりあえず書き出す」で方針を立てるようにしてみたい。トータルで圧倒的にはやくなるとおもう。
#include <iostream>
using namespace std;
const int MOD = 1000000007;
int main(void) {
int N, K;
cin >> N >> K;
long long sum[1000000];
for (long long i = 1; i <= N+1; i++) {
if (i == 1) {
sum[1] = N + 1;
continue;
}
long long d = N * i - ((i - 1) * i) + 1;
sum[i] = sum[i-1] + d;
}
long long ans = sum[N+1] - sum[K-1];
cout << ans % MOD << endl;
}
実装上のハマりポイントは
for (long long i = 1; i <= N+1; i++) {
の部分でカウンタを int で宣言してしまうと
long long d = N * i - ((i - 1) * i) + 1;
ここにカウンタ同士の乗算があるのでオーバーフローするところ。
最近 JS で BOT つくったりしてたので精進できてなかったけど、ぼちぼち再開したいな…。