【競プロ精進日記】AtCoder ABC158

2020.03.08
競プロ
ABC

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Station and Bus
最近のA問題の中では読解に時間がかかりました。
全て同じ文字”AAA”か”BBB”でなければいいだけですね。
コンテストでは焦って下のように実装してしまいました。

if (s.find('A') != string::npos && s.find('B') != string::npos)
    cout << "Yes" << endl;
else
    cout << "No" << endl;

https://atcoder.jp/contests/abc158/submissions/10589292

B

B – Count Balls
境界が複雑になりそうですが、青いボール（最初の方）で安心しました。
青・赤が何回繰り返すかを考えてはみ出た青だけを足せばよいです。

cout << (n / (a + b)) * a + min(n % (a + b), a) << endl;

https://atcoder.jp/contests/abc158/submissions/10592743

C

C – Tax Increase
この問題でタイムロスしてしまいました。
\(1\leq A \leq B \leq 100 \) なので税抜き価格は最大でも1009円ですね。
全探索すればいいものの無駄に計算で解こうとして時間を捨てました。
全探索書いて通せば青パフォいけたのに…
https://atcoder.jp/contests/abc158/submissions/10603331

D

D – String Formation
一瞬難しいDが来たかと思いましたがシミュレーションするだけですね。
反転フラグをもって先頭・末尾に挿入すればよいです。
Twitterではdequeで実装した方が多そうでしたが私はlistで実装しました。
私はdequeあまり使ったことないので知らなかったのですがランダムアクセスができるそうですね。これは優秀ですね。
https://atcoder.jp/contests/abc158/submissions/10608514

E

E – Divisible Substring
解けませんでした。
割り切れるかを和の形式に直して（3桁の数が3で割り切れるかを\(100a+10b+c=(99a+9b+9c)+(a+b+c)\equiv a+b+c\ (mod 3)\) みたいに）桁DPするのかと思いました。
が、これができるのは下位の桁だけで割り切れるかが判断できる2か5の場合のみで不可能です。
区間和を累積和で\(O(1)\)で計算できてもどうしても区間の両端を見る方法しか思いつかずダメでした。
解説を見て精進します。
解けたら追記します。