目次
AtCoder Beginner Contest 171 C,D,E,F問題メモ
C - One Quadrillion and One Dalmatians
問題
- ある要素列 $S$ は、以下のように定義される
- 各要素は英小文字からなる文字列
- $1～26$ 番目の要素は、
'a'～'z' - $27～702$ 番目の要素は、
'aa','ab',…,'az','ba','bb',…,'zz' - 以下1文字ずつ増え、同様
- $S$ の $N$ 番目の要素を答えよ
- $1 \le N \le 10^{15}+1$
解法
百一匹わんちゃんならぬ千兆一匹わんちゃん。名も無い時代の集落の 名も無い幼いダルメシアンの 誰も知らないおとぎばなし。
$N$ を26進数に変換すればいいかとパッと思ってしまうが、よく考えるとズレてくる。
'a'～'z'→0～25 と対応させたら、1桁のうちはよいが、その次、27番目の'aa'が示す値は単純に置き換えると00であり、26になってくれない。
一般的な10進数で頭の0は省略するのと同様、この記法では頭の'a'は省略してもよいと考えると、たとえば以下の3つは同じものを数えていることになる。
1～ 26番目の a ～ z 27～ 52番目の aa ～ az 703～728番目の aaa ～ aaz
言うなれば、文字数が増えるたびに0にリセットされている、と捉えることができる。
そのため、まず何文字かを決めるとよい。文字数を固定すると、同じ文字数の中では、26進数の考え方が使える。
累積 1文字の個数 26^1 = 26 26 2文字の個数 26^2 = 676 702 3文字の個数 26^3 = 17576 18278 ...
$k$ 文字の個数の累積和を $D_k$ として、$D_{k-1} \lt N \le D_k$ なる $k$ があったら、答えは $k$ 文字である。
よって、$k$ 文字未満の個数を除いて、0始まりとした $N-D_{k-1}-1$ を、26進数に変換し、0～25→'a'～'z' と置き換えればよい。
import string
def solve(n):
digit = 1
digit_sum = 0
d = 0
while n >= digit_sum:
digit *= 26
digit_sum += digit
d += 1
n -= (digit_sum - digit)
ans = ''
for _ in range(d):
n, m = divmod(n, 26)
ans += string.ascii_lowercase[m]
return ans[::-1]
n = int(input())
print(solve(n - 1))
D - Replacing
問題
- 長さ $N$ 個の正整数列 $A=\{A_1,A_2,⋯,A_N\}$ がある
- $Q$ 回、以下の操作を行う
- $i$ 回目の操作では、$A$ の、値が $B_i$ である要素を全て $C_i$ に置き換える
- 各操作後について、$A$ の全要素の和を求めよ
- $1 \le N,Q \le 10^5$
解法
状態管理と差分更新。
現在の $A$ に要素 $a$ が何個あるか、という状態を管理する。これを $count[a]$ とする。
1回のクエリでは、$B_i$ が $C_i$ に置き換わるので、
- 総和は $count[B_i] \times (C_i-B_i)$ だけ増える
- $count[B_i]$ は0になる
- $count[C_i]$ は $count[B_i]$ だけ増える
import sys
from collections import Counter, defaultdict
n = int(sys.stdin.buffer.readline())
aaa = list(map(int, sys.stdin.buffer.readline().split()))
q = int(sys.stdin.buffer.readline())
bc = map(int, sys.stdin.buffer.read().split())
count = defaultdict(int, Counter(aaa))
ans = sum(a * c for a, c in cnt.items())
buf = []
for b, c in zip(bc, bc):
if b not in count:
buf.append(ans)
continue
ans += count[b] * (c - b)
count[c] += count[b]
del count[b]
buf.append(ans)
print('\n'.join(map(str, buf)))
上記では、$count[C_i]$ に足し込むとき、$C_i$ が存在しないかも知れないので、Counterで要素数を数えた後、defaultdictに変換して使っている。
しかし、わざわざ変換せずとも、Counterそれ自身も同じように存在しないキーでアクセスするとエラーにならず0で初期化してくれるらしい。しらんかった。
E - Red Scarf
問題
- $N$（偶数）個の数 $A=\{A_1,A_2,...,A_N\}$ があるが、これは明かされない
- $a_i$ を、「$A_i$ を除く、他の全ての $A$ のXOR」とする
- $a_1,a_2,...,a_N$ が与えられるので、$A_1,A_2,...,A_N$ としてあり得る値の組を1つ、出力せよ
- $2 \le N \le 2 \times 10^5$
解法
$a_i$ を全てXORしたら、各 $A_i$ はそれぞれ $N-1$（奇数）回含まれることになる。
偶数回、同じ数をXORしても打ち消されて0に戻るだけなので、結局これは、$A_1～A_N$ を全て1回ずつXORした数となる。
a1 A2 ⊕ A3 ⊕ A4 各Aiは3回ずつXORされる a2 A1 ⊕ A3 ⊕ A4 a3 A1 ⊕ A2 ⊕ A4 a4 A1 ⊕ A2 ⊕ A3 a1⊕a2⊕a3⊕a4 = A1⊕A2⊕A3⊕A4
これにさらに $a_i$ をXORすると、$A_i$ 以外の全ての要素が打ち消され、$A_i$ だけが残る。
a1⊕a2⊕a3⊕a4 ⊕ a1 = A1⊕A2⊕A3⊕A4 ⊕ A2⊕A3⊕A4
= A1
import sys
n, *aaa = map(int, sys.stdin.buffer.read().split())
all_xor = 0
for a in aaa:
all_xor ^= a
buf = []
for a in aaa:
buf.append(all_xor ^ a)
print(*buf)
F - Strivore
問題
- 英小文字からなる文字列 $S$ と、整数 $K$ が与えられる
- $S$ に、ちょうど $K$ 回、以下の操作を繰り返す
- $S$ の好きな位置に、好きな英小文字を挿入する
- 最終的な文字列としてあり得るものの個数を、$\mod{10^9+7}$ で求めよ
- $1 \le K,|S| \le 10^6$
解法
1日前にAGC046で数え挙げ問題が多く出題されていたので、そこから着想を得やすかった、という部分はあったかも知れない。
こういう問題は、異なる操作手順であっても、最終的な文字列が同じなら1個としか数えられない。 操作手順に着目するのではなく、最終状態としてあり得るものをどう重複無く数えるか、という点を考えることになる。
最終的な文字列があったとき、挿入手順が複数あっても「考えられる最も左の文字が元からあった文字だとし、他は挿入したもの」と見なして、そのパターンのみ数えると、重複せずに考えられる。
S = oof K = 5 foxfooff o o f ←これを元からあった文字として、これのみ数える o o f ←これを元からあった文字と考えても作れるが、数えない o o f [A] [B] [C] [D]
挿入箇所は、4箇所ある。ここで、[A]には'o'は使うことはできない。「考えられる最も左の文字が元からあった文字」という条件に矛盾する。
同様に、[B]には'o'、[C]には'f'を使うことはできない。これ以外の文字なら何でもいいので、取り得る文字種は共通して25通りとなる。
最後の[D]は、何を入れてもいい。取り得る文字種は26通りとなる。
各 [ ] に何文字入れるかを $L_A～L_D$ とすると、$L_A+L_B+L_C+L_D = K$ となる。
$L_A～L_D$ へのある割り振り方を決めると、その場合の挿入文字のパターン数は、以下のようになる。
o o f [2] [0] [1] [2] 25^2 * 25^0 * 25^1 * 26^2 = 25^(2+0+1) * 26^2
$L_A～L_D$ へ合計 $K$ を割り振る全てのパターンについてこれを計算し、足し合わせたものが答えとなる。
26の指数が $a$ である割り振りパターンについては、挿入文字のパターンは全て $25^{K-a} \times 26^a$ でまとめて計算できる。
26以外の $K-a$ 個の文字を $|S|$ 箇所に割り振る場合の数は、重複組み合わせで ${}_{|S|}H_{K-a}$ で計算できる。
従って、各 $a=0～K$ につき、以下を計算し、足し合わせればよい。
- ${}_{|S|}H_{K-a} \times 25^{K-a} \times 26^a$
def prepare(n, MOD):
f = 1
factorials = [1]
for m in range(1, n + 1):
f *= m
f %= MOD
factorials.append(f)
inv = pow(f, MOD - 2, MOD)
invs = [1] * (n + 1)
invs[n] = inv
for m in range(n, 1, -1):
inv *= m
inv %= MOD
invs[m - 1] = inv
return factorials, invs
k = int(input())
s = input()
l = len(s)
MOD = 10 ** 9 + 7
facts, finvs = prepare(k + l, MOD)
ans = 0
for i in range(k + 1):
r = k - i
pat = facts[l + r - 1] * finvs[l - 1] * finvs[r] % MOD
ans = (ans + pat * pow(25, r, MOD) * pow(26, i, MOD)) % MOD
print(ans)
AGC046のとある問題も、これと同じように「動かない文字同士のそれぞれの間に、挿入しうる文字が何文字入るか」で状態をまとめて数え上げていたため、 同様のことを試すとたまたま上手くいった、という感じで、AGC046が無かったり、また時間が経ったりすると、着想できたかどうか。
前から貪欲に決定することにする（何らかの性質が出てくる最も左の位置を固定する）と重複がなくなるかも、というのは、解法を試行錯誤する際に浮かぶようにしたい。
