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