ABC164に参加してみました - インフラエンジニアの備忘録とか色々

初めに

参加してから時間が立ってしまいましたが、ABC164に参加したので書いて行こうと思います。
今までは自分が解けた問題のみを記載していたのですが、今回からはコンテスト中に解いている
途中でタイムアップして後日解いた問題や、解説を見て気づきがあった問題のみ書いて行きます。
(なので更新がコンテスト参加日から結構空いてしまいました、、、)

https://atcoder.jp/contests/abc164

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - gacha

この問題は、くじ引きをN回行い何種類の景品を得ることが出来るか求める問題です。
景品は文字列Sで与えられます。

最初の回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

ll N;

cin >> N;

vector<string> S(N);

for(ll i = 0;i < N;++i)    cin >> S[i];

// ①文字列を並び変える
sort(S.begin(), S.end());

// ②・③重複要素を纏めた後に、不要な要素の削除(uniqueは実行後に重複を纏めた範囲の末尾の次のイテレータを返します)
S.erase(unique(S.begin(), S.end()), S.end());

ll ans = S.size();

cout << ans << endl;

return 0;

}

入力されたくじ引き回数より、N個の文字列型の要素を格納可能な配列Sを宣言し、
その配列に景品の文字列を格納していきます。

景品の文字列は重複して入力される場合があり、重複している文字列については種類が
被ってしまうので手に入れた景品の種類としては数えてはいけません。

そのため、景品の文字列を入力した配列に以下の操作①～③を行う必要があり、
その操作の完了後に配列Sの長さを出力することでACすることが出来ます。

　①sortを用いて、文字列を並び替えます。
　　→重複している文字列が隣通しになります。

　②unique(下記リンク参照)にて重複している文字列があった場合は1つにまとめます。
　　→ ex )：aabbbcddaaa ⇒ abcda??????
　　　配列の要素自体が削除されるわけではないので?の部分は何かしらの値が格納されています。

　③uniqueを実行後に残った?の部分をeraseで削除します。
　　→uniqueを行っても配列の要素数自体は変わらないため、不要な部分を削除しています

unique - cpprefjp C++日本語リファレンス

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

ll N;
string S;

cin >> N;

set<string> setS;

for(ll i = 0;i < N;++i){
  cin >> S;
  setS.insert(S);
}

ll ans = setS.size();

cout << ans << endl;

return 0;

}

最初に記載した方法でもACになるのですが、解説にもっとスマートな書き方が記載されていたので
上記のように書き直しました。

setを使用することでユニークな要素の格納が行えます。重複するような値が入力された場合でもsetに格納されることはありません。

そのため、入力された値を格納し、格納した要素数を出力するだけで回答することが出来ます。

※setの詳細は下記リンクを参照。集合を表す時に活用することも出来そうです。

https://cpprefjp.github.io/reference/set/set.html

stlalv.la.coocan.jp

setを使用して思ったこと

最初の回答と比べてメモリ使用量や実行時間が増えており、上記サイトの記載にもある通りvectorのinsertやsortの処理に比べて遅いようなので使用するにあたり、そのへんも頭に入れておいた方が良さそうですね。(入力がやたら多い問題とかだったらTLEになるかも？)
実際に最初に書いたプログラムの実行時間とメモリを比較すると処理速度の違いがわかりますね。

f:id:hgm_blog:20200504230216j:plain

※上がsetを使って解いた時の結果、下がvectorを使って解いた時の結果

D - Multiple of 2019

1 から 9 までの数字のみからなる文字列Sが与えられ、部分文字列の中に2019の倍数がいくつあるか求める問題です。

最初の回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

string S;
ll ans=0;

cin >> S;

for(ll i = 0;i < S.size();++i){

    string subS = "";

　//部分文字列の開始地点をずらすため、インクリメント変数iで初期化
    for(ll j = i;j < S.size();++j){
    
　　//①文字列を長くしていく
        subS = subS + S[j];

　　//②文字列から数値に変換
        ll num = atoi(subS.c_str());

　　//③変換された数値が2019で割り切れる場合は総数ansを1つ増やす
        if(num%2019 == 0) ++ans;

    }

}

cout << ans << endl;

return 0;

}

for文の2重ループを用いて、部分文字列の開始地点をずらしながら以下の操作①～③を行い、
すべての部分文字列に対して2019で割り切れるか計算を行います。

　①部分文字列格納用の変数subSにループ毎に文字列Sの文字を1つずつ格納していきます。

　②部分文字列subSを数値(num)に変換します。

　③numが2019で割り切れる場合は総数ansを1つ増やします。

で、これを提出するとTLEになります。

計算量O(n²)で文字列Sの入力の制約が 1≤|S|≤200000 だったので、「まぁ、たぶんTLEだろうなぁ」と思って提出したら案の定TLEでした。これを提出してから実行時間を削れる方法が無いか悶々と考えているうちにタイムアップしてしまいました。

解説を見てからの回答

入力された文字列の右側から n 個分からなる数字を $a_n$ とおき以下のように記載します。
※以降、例として「1817181712114」が入力された想定で記載していきます。

　 $a_1 = 4$
　 $a_2 = 14$
　 $a_3 = 114$
　 $a_4 = 2114$
　・・・

例えば「1817181712114」より黒太文字で記載されている数字を取り出す場合は、
以下のような計算を行う事で取り出すことが出来ます。

　　 $\frac{(a_9 - a_4)}{10^ 4} = \frac{181712114 - 2114}{10^ 4} = 18171$

$10^ 4$ で割っているのはBの長さが4桁で、Bの桁数分だけ0が続いているからです。
上記よりある区間 $[l,r$ ]の数字は以下を満たせば2019で割り切れると言えます。

　　 $\frac{(a_r - a_{l-1})}{10^ l} \equiv 0　mod (2019)$

f:id:hgm_blog:20200505223345p:plain — イメージ

ここで、2019と10は互いに素(最大公約数が1のみ)であり、上記式を満たす上で $a_r - a_{l-1}$ が2019の倍数である必要があるため、以下のように表すことが出来ます。

　　 $a_r - a_{l-1} \equiv 0　mod (2019)$

さらに以下のように式を変形することが出来ます。

　　 $a_r \equiv a_{l-1}　mod (2019)$

mathtrain.jp

このことから、文字列の右から $l$ 個までの数字と $r$ 個までの数字を2019で割った余りが同様な場合、
2019の倍数であると言うことが出来ます。

つまり、右端から順々に数字を見ていき2019で割った余りが同様な数字の出現回数
(=余りが同様になる数字の個数)をそれぞれ集計し、集計した中から2組の数字を選ぶ方法( $_n C_2$ )を
計算し、結果を足し合わせることで、文字列に含まれた2019の倍数の総数が求める事が出来ます。

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main(){

string S;

cin >> S;

ll x = 1;
ll tot = 0;
ll ans=0;
ll mod = 2019;
vector<ll> cnt(mod);

// 0桁の値を2019で割った余りは0なので、cnt[0]に1を代入します。
//<例>数字が21145で、5桁すべての数字を取得する場合は21145の後ろに(a0)位置に敷居(|)が来るのでそのパターンを表している→21145|
cnt[0] = 1;

// 入力された文字列は一番最後の要素に1桁目の数字が格納されているため、計算しやすくするために逆順にしています。
reverse(S.begin(),S.end());

for(ll i = 0;i < S.size();++i){

    // ①i桁目の数字を取得しています。
    ll num = S[i] - '0';

    // ②「①」で求めたi桁目の数字を変数totに足します。
    tot = (tot + (num*x)) % mod;

    // ③配列の添え字として変数totを利用し、
    cnt[tot] = cnt[tot] + 1;

    // ④桁数を計算しています。
    x = (10 * x) % mod;

}

//⑤「余りが同様になる数字」の中から2個を選択する方法([tex:_n C_2])をそれぞれ計算します。
for(ll n : cnt) ans += (n * (n - 1)) / 2;

cout << ans << endl;

return 0;

}

各桁の数字は下記の例のように、各桁の累積和で表すことができます。

　　 $2114 = ( 2 × 10^ 3 ) + ( 1 × 10^ 2 ) + ( 1 × 10^ 1 ) + ( 4 × 10^ 0 )$