スクリーンショット_2020-03-08_0.02.36

ABC158【E問題の復習】今回も解説動画を何回も見て、何度も書いて、理解できたと思う

3月7日に、競技プログラミングサイトAtCoderで開催された競技プログラミングコンテスト「AtCoder Beginner Contest 158」に参加した。

【今回の結果】
     順位:1802 位(参加者:約 7106 名 上位 25 %くらい)
    レート:708(前回:654 前回比:+54)
パフォーマンス:1093(前回:765)

全6問出題され、A、B、C、DはACできた。B問題でWAを1回、D問題でTLEを1回出してしまったが、パフォーマンスは過去最高の1093。初めてパフォーマンスが1000を超えた点はよかった。コンテスト中では、E問題は手も足もでなかったが、解説PDFや解説動画を見てなんとか理解できたので、それも整理したい。ということで、今回は、以下の3つを反省・復習する。

1.B問題でWAを出したことの反省
2.D問題でTLEを出したことの反省
3.E問題の復習

【B問題】どうしてWAを出したのか?

問題文は以下のリンクをご確認ください。

間違っていたコード(C++)を以下に抜粋します。
(N,A,Bもlong long型です。)

long long answer = N * A / (A + B);

そして、正しくは以下のようになります。

long long answer = N / (A + B) * A;

間違っていたコードでは、long long型 × long long型 と先に掛け算をしている。
素直にとけば、正しいコードのようになるのだが、「割り算は後にしたほうがいい」と思ってしまい、掛け算を先にしてしまった。

long long × long long はダメ

以後気をつけよう。

【D問題】どうしてTLEを出したのか?

問題文は以下のリンクをご確認ください。

間違っていたコード(C++)を以下に抜粋します。
(Sは文字列で、長さは10の5乗 + 2 × 10の5乗くらいになる場合がある。)

reverse(S.begin(), S.end());

「めちゃくちゃ長い文字列をreverseすること」の計算量について何も考えず、実装してしまったのがTLEの原因。

そりゃ、reverseにも計算量はある。

コンテストでは以下のコード(C++)のように、Sはそのままにし、Sの前に繋ぐ文字列、Sの後に繋ぐ文字列と3の文字列に分けた。

reverse(S.begin(), S.end());
reverse(mae.begin(), mae.end());
reverse(ushiro.begin(), ushiro.end());

そうすれば、文字列は長くても10の5乗とか2×10の5乗だからreverseでき、ACとれた。ちなみに、dequeを使う方法は思いつかなかった。

【E問題】10進数の数を数式で考える。桁の番号を後ろから与えた方が都合がいい。

問題文は以下のリンクをご確認ください。

全くわからなかったので、解説動画を何度も見て復習した。自分にとって、大切なポイントは4つあった。

【ポイント1】10進数の数を数式で考える
【ポイント2】Pが2か5の場合は簡単
【ポイント3】Pが2か5以外の場合の余りを計算する
【ポイント4】組み合わせの数を計算する

【ポイント1】10進数の数を数式で考える

例えば、S=6543は以下の数式で表すことができる。

3 × 10の0乗 + 4 × 10の1乗 + 5 × 10の2乗 + 6 × 10の3乗

Sは文字列なので、本来は6,5,4,3と見ていくが、今回の問題の場合のように3,4,5,6と見ていく方が都合がいい場合もある。そして、上記の式を使って65を以下の式で表すことができる。

65 = (6543 - 43) ÷ 10の2乗

【ポイント2】Pが2か5の場合は簡単

例えば、N=8,P=5,S=80152で考える。(iを文字列の順で0から4までつける)

  i  | 0 1 2 3 4
-----------------------
S[i] | 8 0 1 5 2
S[0]からS[0]までの場合、8なので、5で割り切れない。
S[0]からS[1]までの場合、80なので、5で割り切れる。
S[0]からS[2]までの場合、801なので、5で割り切れない。
S[0]からS[3]までの場合、8015なので、5で割り切れる。
S[0]からS[4]までの場合、80152なので、5で割り切れない。

となり、注意すべきはそれぞれの場合の最も右側の数が割り切れるか否かである。
割り切れる場合は、その桁から左端までで作ることができる数値は全部割り切れる。すなわち、S[i]が割り切れる場合は、答えにi+1を加えればいい。

【ポイント3】Pが2か5以外の場合の余りを計算する

例えば、N=8,P=7,S=43980152で考える。(【ポイント2】では、iを文字列の順で0から7までとしていたが、ここからは数値の桁順に0から7までとして考えます。実装では、0の位置をずらす場合もあります。)

  i  | 7 6 5 4 3 2 1 0
-----------------------
S[i] | 4 3 9 8 0 1 5 2

何桁目をiとし、0から使うとすると、

1桁目(i=0)を2×10の0乗、
2桁目(i=1)を5×10の1乗、
3桁目(i=2)を1×10の2乗、
...
8桁目(i=7)を4×10の7乗

とした場合、それぞれを7で割った余りは以下のA[i]のようになる。
例えば、2桁目(i=1)は50÷7=7...1と余り1となる。

  i  | 7 6 5 4 3 2 1 0
-----------------------
S[i] | 4 3 9 8 0 1 5 2
A[i] | 5 3 3 4 0 2 1 2

S[0]からS[1]までを数値で見ると、52となる。この52を7で割った余りは、A[0]+A[1]を7で割った余り、すなわち3となる。このようにS[0]からS[i]までを7で割った余りをD[i]に入れていく。D[0]はA[0]と同じ値となる。

  i  | 7 6 5 4 3 2 1 0
-----------------------
S[i] | 4 3 9 8 0 1 5 2
A[i] | 5 3 3 4 0 2 1 2
D[i] |             3 2

S[0]からS[2]までは、152となる。この152を7で割った余りは、D[1]+A[2]を7で割った余り、5となる。すなわち、累積和を求めるように求めることができる。D[7]まで埋めると以下のようになる。

  i  | 7 6 5 4 3 2 1 0
-----------------------
S[i] | 4 3 9 8 0 1 5 2
A[i] | 5 3 3 4 0 2 1 2
D[i] | 6 1 5 2 5 5 3 2

ここで、S[3]からS[5]まで、すなわち980の余りを求めたいとする。ここで【ポイント1】の考え方を利用する。

980 = (980152 - 152) ÷ 10の3乗

であり、余りについても

980 ÷ 7 の余り = (D[5] - D[2]) ÷ 10の3乗

ということができる。上記の式を計算すると0となり、980は7で割り切れると確認できる。

(D[5] - D[2]) ÷ 10の3乗 = 0

に注目すると、両辺を10の3乗でかけると、

D[5] - D[2] = 0

となり、

D[5] = D[2]

と式変形することができる。
以上より、

D[j] = D[k](j > k)ならばS[j]からS[k+1]までの数値は、Pで割り切れる

といえる。そうすると、Dについていろいろな範囲を試すことなく、D[i]で使われている数値の個数を数えることで、何個割り切れる数値があるかを計算することができる。すなわち、2個あれば2個の組み合わせが1個作れるので、割り切れる数は1個、3個あれば3×2÷2=3(組み合わせの公式より)個となる。

上記の例でいえば、余りとして使う数値は0から6までであり、それぞれ

D[i] | 6 1 5 2 5 5 3 2
0は0回なので、割り切れる数値は0個
1は1回なので、割り切れる数値は0個
2は2回なので、割り切れる数値は1個
3は1回なので、割り切れる数値は0個
4は0回なので、割り切れる数値は0個
5は3回なので、割り切れる数値は3個
6は1回なので、割り切れる数値は0個

の作ることができ、これらの合計4が答えとなる。

【ポイント4】組み合わせの数を計算する

最後で組み合わせの数を計算するときに、組み合わせの公式を利用しているが、実際の実装では、

1個目が見つかったら変数に0を加え、
2個目が見つかったら変数に1を加え、
3個目が見つかったら変数に2を加え、
...

と見つかった個数-1を都度加えていけばいい。

以上をもとに実装しACしたコードは以下の通りです。

#include <bits/stdc++.h>
using namespace std;

int main() {

 int N, P;
 cin >> N >> P;

 string S;
 cin >> S;

 //【ポイント2】
 if (P == 2 || P == 5) {
   long long answer = 0;
   for (int i = 0; i < N; i++) {
     if ((S[i] - '0') % P == 0) {
       answer += i + 1;
     }
   }
   cout << answer << endl;
   return 0;
 }

 //【ポイント3】
 vector<int> d(N+1);
 int count = 1;
 for (int i = N-1; 0 <= i; i--) {
   int a = (S[i] - '0') * count % P;
   d[i] = (d[i+1] + a) % P;
   count *= 10;
   count %= P;
 }

 //【ポイント4】
 vector<int> sum(P);
 long long answer = 0;
 for (int i = N; 0 <= i; i--) {
   answer += sum[d[i]];
   sum[d[i]]++;
 }

 cout << answer << endl;

 return 0;
}

今回もいい勉強になった。13から始まったレートもコツコツと700を超え、C問題で頭を抱えていたのに、いつの間にかE問題をやるようになってきた。やっぱり続けていれば、スピードに個人差はあれどできるようになってくるんだなぁ。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

スキありがとうございます!
三重県伊勢市でiOS・AndroidアプリのUX設計・UIデザイン・実装、Webサイト、Webアプリの情報設計、UIデザイン、実装を行なっています。また、競技プログラミングに参加したり、読書をしたり、2羽の文鳥と遊んだり、写真を撮ったり、洋菓子を作ったりしています。