−目次

AtCoder Beginner Contest 171 C,D,E,F問題メモ
- C - One Quadrillion and One Dalmatians
  - 問題
  - 解法
- D - Replacing
  - 問題
  - 解法
- E - Red Scarf
  - 問題
  - 解法
- F - Strivore
  - 問題
  - 解法

AtCoder Beginner Contest 171 C,D,E,F問題メモ

AtCoder Beginner Contest 171

C問題に一番時間かかった。。。

逆にD,Eは比較的、解法が思い浮かびやすい方だったと思う。

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が無かったり、また時間が経ったりすると、着想できたかどうか。

前から貪欲に決定することにする（何らかの性質が出てくる最も左の位置を固定する）と重複がなくなるかも、というのは、解法を試行錯誤する際に浮かぶようにしたい。