ABC202 参加記録 - Xenous の精進記録

4完0ペナ 56分でした

A - Three Dice

サイコロの反対の値は、出た目を $x$ とおくと、 $7-x$ で表せます。あとは加算して答えです。

a, b, c = map(int, input().split())
a = 7-a; b = 7-b; c = 7-c
print(a+b+c)

B - 180°

180度回転で行わないといけない操作が問題文に定義されているので、それを行います。先に数字を変換してから逆順に出力しました。

S = input()
ans = []
for s in S:
    if s == '6':
        ans.append('9')
    elif s == '9':
        ans.append('6')
    else:
        ans.append(s)
ans.reverse()
print(''.join(ans))

C - Made Up

$B_{C_j}$ の解釈から考えます。サンプル 1 を例にとります。

Cとして 2 3 2 が与えられています。最初の値( $j=1$ )は $C_{1} = 2$ です。したがって $B_{C_j} = B_{2} = 1$ です。

さて、このとき $A_i = 1$ となる $i$ の個数を求めます。これは単純に、数列 A の中で 1 が何個あるか先に数えておけば良さそうです。

同じ要領で $j=2$ 、すなわち $B_{C_j} = B_{1} = 3$ と同じになるような $i$ の個数を数えて、... を繰り返し、全ての $j$ について数え上げればOKです。

あらかじめ A の要素のカウントを collections.Counter で行うと良いと思います。Cの値はBのインデックスになるので、あらかじめ 1 を引いておきます。

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [x-1 for x in map(int, input().split())]

Acounter = Counter(A)
ans = 0
for c in C:
    x = B[c]
    ans += Acounter[x]
print(ans)

D - aab aba baa

まず制約で $1 \leq A, B \leq 30$ とあります。a と b の並び替えで一番大きな計算は $_{60}\mbox{C}_{30}$ ですが、python はこの計算をオーバーフローを気にせず実行できます。オーバーフローに気をつけて計算する場合は、パスカルの三角形を用いて計算しておくと良さそうです(たぶん)。

後は b の位置で数え上げを行います。例えば a の個数が 4 つ、b の個数が 3 つの場合、まずは左から見て 1 つ目の b の位置で場合分けをして、数え上げていきます。

f:id:Xenous:20210523142246p:plain — b の位置で分ける数え上げのイメージ

例えば $K = 15$ としたとき、11〜20 の部分に含まれるので、左の ab は確定します。次は、残りの aaabb について同様にして調べれば良いです。

f:id:Xenous:20210523145051p:plain — K = 15 のときの探索の流れ

本番では結構バグって時間がかかってしまいました。スパゲティコードになってますが一応参考までに載せておきます。

D問題提出コード

def nCk(n:int, k:int) -> int:
    """
    nCk の値を O(n) で計算する. (n-k)! // k! の計算を行う.

        Parameters:
        -----------
        n, k: int
            nCk に該当する0以上の整数
        
        Return:
        -------
        int
            nCk の計算結果.
            n または k が 0 より小さい場合は 0 を返す.
            n が k より小さい場合も 0 を返す.
    """
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    k = min(k, n-k)
    numer = 1
    for i in range(n, n-k, -1):
        numer *= i
    denom = 1
    for i in range(k, 1, -1):
        denom *= i
    return numer // denom


def main():
    A, B, K = map(int, input().split())
    if K == 1:
        ans = 'a'*A + 'b'*B
        print(ans)
        return

    cnt = 0; Acnt = A; Bcnt = B
    ans = ''
    # K がどこにあるか探索する
    while True:
        for i in range(0, Acnt+1):
            # b の位置を固定したときの場合の数
            res = nCk(i+(Bcnt-1), min(i, Bcnt-1))
            if res == 0:
                # a または b の数が 0 になったら脱出
                break
            if cnt < K <= cnt+res:
                break
            cnt += res
        if res == 0:
            # a または b の数が 0 になったら、後ろに残りの a の数分くっつけるだけ
            ans += 'a'*Acnt
            break
        # 確定した部分を入れる
        ans += 'a'*(Acnt - i) + 'b'*(Bcnt > 0)
        Acnt = i
        if Bcnt > 0: Bcnt -= 1
        if Bcnt == 0 and Acnt == 0:
            break
    print(ans)


if __name__ == "__main__":
    main()

E - Count Descendants

解説ACです。本番では二重の辞書(dict 型の value に dict を持つ)で、DFSで戻ってくる際に、各頂点の「深さ」と「頂点番号」を集合管理することでクエリに答えようとしましたが、マージする際に木の情報を上書きしてしまい、うまくいきませんでした。

解説にあるように、DFS で巡った順に番号を振っていくと、かなり見通しが良くなります。以下は例です。

f:id:Xenous:20210525125825p:plain — 頂点に初めて訪れたとき(青色)と、最後にその頂点から出ていくとき(赤色)の時刻

深さごとに、それぞれ入りの時刻を保持しておくと、以下のように整理できます。ここで例えば「頂点 $2$ を含む長さ $2$ のパスが作れる頂点の個数」を考えたとき、depth が 2 の行において、頂点 $2$ の入った時刻と出た時刻の間にある要素の個数を見ると、それが頂点 $2$ を通る長さ $2$ のパスになっていることがわかります。