AtCoder Beginner Contest 158 のA-E問題の考察を書いていきます。

本番は寝過ごしたので終了直後にやってみたところ、ぎりぎりE完 (3WA) という感じでした。

前回: 競プロ参戦記 #73 Yakiniku Optimization Problem | ABC 157
問題一覧: https://atcoder.jp/contests/abc158/tasks

A - Station and Bus

問題概要: 市内には3つの駅がある。i 番目の駅は鉄道会社 S(i) が管理している。鉄道会社 A が管理している駅と、鉄道会社 B が管理している駅の間には、バスが運行することになった。これらの駅の間にバスが運行しているかどうかを判定せよ。

制約:

|S| = 3
S(i) は A または B

A: 考察

S に A と B の両方が含まれていたら、それらの駅の間にバスが運行するので Yes、そうでなければ No となります。

「A と B の両方が含まれる」ような S は6通り、逆に「A と B の片方しか含まれない」のは2通りです。後者を検査した方が短く書けます。

    S != "AAA" && S != "BBB"

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc158/submissions/10640927

B - Count Balls

問題概要: 列の末尾に A 個の青いボールを追加し、列の末尾に B 個の赤いボールを追加する、という操作を 10^100 回行う。列の前から N 個のボールのうち、青いボールの個数を求めよ。

制約: A+B, N≤10^18

B: 考察

整数の端数切り捨ての除算を x//y と書きます。

例えば A=3, B=2 なら、ボールの列は以下のようになります。10^100 が目を引きますが、単に列の長さが N 以上であるといっているだけです。

青青青赤赤 青青青赤赤 青青青赤赤 青青青赤赤...

「青青青赤赤」のような A+B 個のボールからなるブロックは、先頭 N 個のボールに N//(A+B) 個含まれています。そのうち青いボールは、1ブロックあたりA個なので、(N//(A+B))・A 個です。

N が (A+B) の倍数でなければ、最後の1ブロックの途中までが「先頭 N 個」に含まれます。最後のブロックには N % (A+B) 個のボールが含まれています。そのうち青いボールは、前から A 個だけなので min(N % (A+B), A) 個です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc158/submissions/10640826

C - Tax Increase

問題概要: ある商品は、消費税率が 8% のとき A 円の消費税が課され、消費税率が 10% のとき B 円の消費税が課される。商品の税抜き価格がこの条件を満たすことがありうるか判定し、ありうるなら最小の税抜き価格を求めよ。(消費税の端数は切り捨てられる。)

制約: A, B≤100

C: 考察

x 以下の最大の整数を floor(x)、x 以上の最小の整数を ceil(x) と表します。

条件を満たす税抜き価格を X とおくと、次の連立方程式が立ちます。

floor(X・8/100) = A
floor(X・10/100) = B

floor を使わない形に変形します。floor(x) は x を超えないので floor(x) ≤ x であり、最大なので x-1 < floor(x) です。

X・8/100 - 1 < A ≤ X・8/100
X・10/100 - 1 < B ≤ X・10/100

X について変形すると:

X < (A+1)・100/8
A・100/8 ≤ X
X < (B+1)・100/10
B・100/10 ≤ X

まとめると:

max(A・100/8, B・100/10) ≤ X < min((A+1)・100/8, (B+1)・100/10)

したがって、X の最小値 u と最大値 v が求まります。

u = max(ceil(A・100/8), B・100/10)
v = min(ceil((A+1)・100/8), (B+1)・100/10) - 1

u > v なら X は存在せず、u≤v なら X=u が最小です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc158/submissions/10644093

C: 別解

制約から X < 10^4 なので、全探索で求まります。このごろ全探索が見えてなくて反省……

D - String Formation

問題概要: 英小文字からなる文字列 S が与えられる。次の Q 個の操作を順番に行った後の文字列を求めよ。

i 番目の操作は以下の2種類のどちらか:
- T(i)=1 のとき: 文字列 S を反転する。
- T(i)=2 のとき: 整数 F(i) と英小文字 C(i) が与えられる。
  - F(i)=1 のとき: 文字列 S の先頭に C(i) を追加する。
  - F(i)=2 のとき: 文字列 S の末尾に C(i) を追加する。

制約: |S|, Q≤10^5

D: 考察

実際にこれらの操作を行うと TLE します。

反転操作を実際には行わず、文字列が反転状態にあるかどうかをフラグで持てば、反転操作を最後まで遅延できます。また、先頭への追加と末尾への追加は、列を両端キュー (VecDeque) で持つことにより高速化可能です。

全体として O(|S| + Q) 時間で間に合います。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc158/submissions/10641247

「操作列の変形」という視点で考えると面白いと思います。

先頭に文字 c を追加する操作を「先頭(c)」、末尾への追加操作を「末尾(c)」と書くことにします。

例えば S=cde, 操作=(先頭(b), 末尾(f), 反転, 先頭(g), 末尾(a), 反転) という入力をやってみると、以下の通りです。

操作	操作後
	cde
先頭(b)	bcde
末尾(f)	bcdef
反転	fedcb
先頭(g)	gfedcb
末尾(a)	gfedcba
反転	abcdefg

「反転→先頭(c)」という操作列は「末尾(c)→反転」に、「反転→末尾(c)」という操作列は「先頭(c)→反転」という操作列に、それぞれ変形しても最終結果が変わりません。この変形を可能なかぎり適用すると、反転操作を操作列の最後に移動できます。

操作	操作後
	cde
先頭(b)	bcde
末尾(f)	bcdef
末尾(g)	bcdefg
先頭(a)	abcdefg
反転	gfedcba
反転	abcdefg

2回連続の反転は無視していいので、反転は最大1回になります。

また、先頭への追加操作と末尾への追加操作も交換できます。つまり「先頭(a)→末尾(b)」と「末尾(b)→先頭(a)」は、最終的には同じ結果になります。そのため、先頭(c)を前方に、末尾(c)を後方にまとめても OK です。

操作	操作後
	cde
先頭(b)	bcde
先頭(a)	abcde
末尾(f)	abcdef
末尾(g)	abcdefg

したがって、操作列は「先頭に文字列 X を追加する」「末尾に文字列 Y を追加する」「n 回反転する」というかたちに変形できます。クエリを見て X, Y, n を求め、(X + S + Y) を計算して、n 回反転したら答えが得られます。

実際に書くコードは上記の回答とだいたい同じです。

E - Divisible Substring

問題概要: 数字からなる長さ N の文字列 S と、素数 P が与えられる。S の空でない区間で、それを10進表記の整数をみなした際に素数 P で割り切れるものの個数を数えよ。(先頭が 0 で始まる10進表記の整数も認める。)

制約: N≤10^5

E: 考察

例えば S=31415, P=3 だと、次の4つの区間があります。

    31415
    ^       3
    ^^^^    3141
     ^^^    141
       ^^   15

S の l 文字目から r-1 文字目までの文字列を10進表記の整数とみなしたものを f(l, r) とおきます。f を使って問題を形式的に書きなおすと:

f(l, r) ≡ 0 (mod P) となるペア (l, r) の個数を求めよ (0 ≤ l < r ≤ N)

となります。

f(l, r) をすべて計算するのは O(N^2) 時間かかって間に合いませんが、r=N に固定した f(l, N) だけなら、累積和により O(N) 時間で計算できます。一般の f(l, r) は f(l, N) の式で表せそうなので、そのあたりから考察が進みそうです。

f(l, r) を f(r, N) の桁数だけずらしたものに f(r, N) を足すと f(l, N) に等しくなる (例えば 31415 = 31 * 1000 + 415 のようになる) ことから、次が成り立ちます。

$$
f(l, N) = 10^{N-r} f(l, r) + f(r, N)
$$

もし P が 10 と互いに素なら 10^(N-r) で両辺を割れるので、f(l, r) について変形して:

$$
f(l, r) = 10^{r-N} (f(l, N) - f(r, N))
$$

を得ます。こうして次が分かりました。

\begin{align}
    f(l, r) & ≡ 0 \\
    ⇔ f(l, N) & ≡ f(r, N) \quad (\text{mod}\ P)
\end{align}

言い換えると、f(i, N) % P の値が等しいような i を2つもってきてそれぞれ l, r とすれば f(l, r) ≡ 0 (mod P) が成り立つということです。

したがって、f(i, N) % P の値で i を分類し、各剰余に対応する i の個数が n 個であれば n(n-1)/2 個のペアを計上すれば OK です。全体として O(N) 時間で解けました。

忘れてはいけないのが P が10と互いに素でないケース、つまり P = 2 と P = 5 です。このとき 10 ≡ 0 (mod P) だから 10 は逆元を持たないので、上記の「両辺を 10^(N-r) で割る」操作は NG です。

P = 2 のケースは簡単で、偶数の10進表記は一番下の桁が偶数なので、

f(l, r) ≡ 0 (mod 2)
⇔ S(r-1) が偶数

といえます。したがって、r に関してループを回すことで O(N) 時間で解けます。

P=5 も同様に、5の倍数の10進表記は一番下の桁が 0 か 5 であることを利用して解けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc158/submissions/10645641