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,\ldots,A_N\}$ があるが、これは明かされない
  • $a_i$ を、「$A_i$ を除く、他の全ての $A$ のXOR」とする
  • $a_1,a_2,\ldots,a_N$ が与えられるので、$A_1,A_2,\ldots,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が無かったり、また時間が経ったりすると、着想できたかどうか。

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

programming_algorithm/contest_history/atcoder/2020/0621_abc171.txt · 最終更新: 2020/06/22 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0