ABC202まとめ - 黒ココアさんち

A - Three Dice

https://atcoder.jp/contests/abc202/tasks/abc202_a

引いて、終わり！

dice_L = list(map(int, input().split()))  
print(21 - sum(dice_L))

B - 180°

https://atcoder.jp/contests/abc202/tasks/abc202_b

置換して、逆順に並べて、おわり

S = input()  
print(S.replace('6', '*').replace('9', '6').replace('*', '9')[::-1])

C - Secret Number

https://atcoder.jp/contests/abc202/tasks/abc202_c

3つの関係性はだいたい真ん中見たら幸せになれるパターン
カウンターで数えて同じ状態をまとめるから、$O(10^{10})$から$O(10^5)$で済むやつ

from collections import Counter  
  
N = int(input())  
A_L = list(map(int, input().split()))  
B_L = list(map(int, input().split()))  
C_L = list(map(int, input().split()))  
a_c = Counter(A_L)  
c_c = Counter(C_L)  
  
ans = 0  
  
for i, b in enumerate(B_L, 1):  
    ans += a_c[b] * c_c[i]  
print(ans)

D - aab aba baa

https://atcoder.jp/contests/abc202/tasks/abc202_d

#辞書順は、先頭から #TIPS
A+B個ある文字のうち、B個をBにする場合の数→ #nCr
- scipyにもあるけど遅かった、っぽい。math.combが安定感ある？
「1文字目はaかbのどっちか」→それはそう
- じゃあ、先頭がaになるのって何パターン存在する？
  - AとBの残りの数からわかるね！
  - DPとかでもそれ自体は求められそうだけどcombで済ませよせやね
- 「先頭がaになるパターン数」しか、「先頭がaになるパターン」は作れない→それもそう
- じゃあ、「先頭がaになるパターン数」よりも辞書順のKが大きいなら？
  - 先頭はb入れるしかないよねー→それもそう
  - 先頭がbになった時、残りの文字で作る文字列の中で辞書順K番目…？
    - Kがずれるよね。具体的には、「先頭がaになったパターン数」だけ減るね
後は実装するだけ問題

from math import comb  
  
A, B, K = map(int, input().split())  
N = A + B  
ans = []  
while len(ans) != N:  
  
    tmp = comb(A + B - 1, B)  
  
    if tmp >= K:  
        ans.append('a')  
        A -= 1  
    else:  
        ans.append('b')  
        B -= 1  
        K -= tmp  
print(''.join(ans))

E - Count Descendants

https://atcoder.jp/contests/abc202/tasks/abc202_e

根付き木の部分木は、 #オイラーツアーで整理する #TIPS
- 頂点Uを根とした部分木→オイラーツアー上で、頂点Uに行った時〜頂点Uに帰った時の間の区間
  - 今回、再帰しないDFSで、頂点iの帰りがけタイミングに ~iを使った
根から頂点Uへの距離は？
- BFSでも、オイラーツアーのパス辿って+1,-1して、でも。お好きに。
- 前処理で一旦根から全頂点への距離を出しておく
  - オイラーツアーと同時に深さも取得
問題言い換え：オイラーツアー上の特定の区間で、深さがdの頂点はいくつ？
- オイラーツアー時に、その深さになったタイミングを纏める
- オイラーツアー上の特定区間で、深さdになったタイミングの個数を数える
  - 二分探索でいいね！
  - wavelet matrixで、配列のうちL~Rまでの中で、値xが何回出てくるか…みたいなクエリをlogNで叩ける、らしい… #TODO

import bisect  
from collections import deque, defaultdict  
  
N = int(input())  
P_L = list(map(int, input().split()))  
  
edge_L = [[] for i in range(N)]  
for i, p in enumerate(P_L, 1):  
    p -= 1  
    edge_L[i].append(p)  
    edge_L[p].append(i)  

# オイラーツアーパート  
# path_L：オイラーツアーの順番が出てくる  
# depth_L：オイラーツアー時の深さ  
que = deque([~0, 0])  
path_L = []  
done_L = [0] * N  
done_L[0] = 1  
depth_L = []  
cnt = 0  
  
while que:  
    now_ = que.pop()  
    path_L.append(now_)  
    if now_ < 0:  
        depth_L.append(-1)  
        cnt -= 1  
    else:  
        depth_L.append(cnt)  
        cnt += 1  
    if now_ < 0: continue  
    for nex_ in edge_L[now_]:  
        if done_L[nex_]: continue  
        que.append(~nex_)  
        que.append(nex_)  
        done_L[nex_] = 1  

# 深さ毎に、頂点の番号を整理・収集
depth_d = defaultdict(list)  
for i in range(len(depth_L)):  
    if depth_L[i] < 0:
        continue
    depth_d[depth_L[i]].append(i)  

# 頂点番号から、オイラーツアーのインデックスを取得
node_idx_d = defaultdict(int)  
for i, node in enumerate(path_L):  
    node_idx_d[node] = i  

# クエリ解答パート
Q = int(input())  
for _ in range(Q):  
    U, D = map(int, input().split())  
    U -= 1  
  
    l = node_idx_d[U]  
    r = node_idx_d[~U]  
    l_idx = bisect.bisect_left(depth_d[D], l)  
    r_idx = bisect.bisect_right(depth_d[D], r)  
    print(r_idx - l_idx)

スパークリング黒ココア/ABC202まとめ

A - Three Dice

B - 180°

C - Secret Number

D - aab aba baa

E - Count Descendants