【AtCoder】ABC202 感想戦 - RONの技術ブログ

2021/5/22に開催されたABC202を振り返ります。
結果はA~Cの3完でした。順位：3205位、パフォーマンス：819、レート：679→694(茶)
今回はCまではスラスラ解けてこの順位なので、Cが簡単だったみたいです。

A問題： A - Three Dice
3つのサイコロのでた目に関する問題です。
出た目と反対側の目の値を足すと7になることを利用して、21からa+b+cを引けば答えになります。

def main():
    A, B, C = map(int,input().split())
    return 21 - (A+B+C)

print(main())

B問題：B - 180°
0, 1, 6, 8, 9からなる文字列(S)を180度回転させた文字列を出力する問題です。
回転させた際、6を9に、9を6に、それ以外はそのまま、に変換します。
私はまずSを逆順に並び替え、その後6→9, 9→6に変換しました。
単純にreplaceなどで変換しようとすると、6→9に変換した後、9→6にする際にまた戻ってしまうため、少し注意が必要です。
今回の制約条件的に先頭から1文字ずつ見ていっても間に合いますし、6→Q、9→6、Q→9など違う文字を経由してreplaceするか、どちらでもよいかと思います。私は前者で実装しました。

def main():
    S = input()
    S = list(S[::-1])

    for i in range(len(S)):
        if S[i] == "6":
            S[i] = "9"
        elif S[i] == "9":
            S[i] = "6"
    
    return "".join(S)

print(main())

C問題：C - Made Up
3つのリスト(A, B, C)が与えられ、条件を満たす整数(i, j)が何通りあるか、という問題です。
制約条件的に1重のイテレーションで解きたいです。
私はCをイテレーションしました。
CからBの要素を特定し、その要素がAに何個あるかを求める、を繰り返します。
TLE対策として、予めcollectionsライブラリのCounterメソッドを利用してAの各要素数を求めておきます。

from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    ans = 0
    cnt = Counter(A)

    for c in C:
        b = B[c-1]
        ans += cnt.get(b, 0)
    
    return ans

print(main())

D問題：D - aab aba baa
A個の"a"、B個の"b"からなる文字列において、辞書順でK番目のものを求める問題です。
まず、文字列のパターン数はA+B個の中からA個を選べばよいので、(A+B)CAで求められます。
方針としては、先頭の文字から順番に確定させていきます。
先頭を"a"としたとき、残りの文字列のパターン数がK以上の場合、先頭の文字は"a"、小さい場合は"b"を選ぶ、を繰り返します。
イテレーション毎に累積をとっておくことも忘れないようにしましょう。

def calc_combinations_count(n, r):
    import math
    if n < r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    A, B, K = map(int,input().split())
    acm = 0
    ans = []

    # 先頭の文字から順番に決めていく。
    for _ in range(A+B):
        # aが無ければ自動的にbを選ぶ。
        if not A:
            ans.append("b")
        else:
            # 先頭の文字をaと過程し、先頭以降の文字列の総数を計算する。
            cnt = calc_combinations_count(A+B-1, A-1)
            
            if acm + cnt >= K:
                A -= 1
                ans.append("a")
            # どのパターンでもまだK番目にならないため、先頭文字としてbを選ぶ。
            else:
                acm += cnt
                B -= 1
                ans.append("b")
    
    return "".join(ans)

print(main())

まとめ
今回は解ける問題を着実に解いた、という印象です。
D問題は復習すれば納得ですが、なかなか本番で解くのは難しいです。
とりあえずレートの最高値を更新できたのでよかったです。
緑色を目指して来週も取り組んでいきます。
お疲れ様でした。