Atcoder-ABC202をpythonで問題を解いてみた

目的

• Atcoderで上を目指すべく頑張っている中でABC202を解いたので、解説してみる
  • pypy7.3を使って解いている

A問題

atcoder.jp

考察

• 反対面の目は、それぞれa, b, cから7引いた値になるので、それらを足し合わせれば良い

実装

a, b, c = map(int, input().split())

ans = 7-a + 7-b + 7-c
print(ans)

結果

• 無事に解けた

B問題

atcoder.jp

考察

• 入力の文字列を反転させた上で、6, 9のみに着目して処理すれば良い
  • 6は9に変換
  • 9は6に変換する
• Sは最大10⁵程度の文字列であるが、O(n) 程度の処理なら十分間に合う

実装

S = list(input())

S.reverse()

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


print(*S, sep="")

結果

• 無事に解けた

C問題

atcoder.jp

考察

• max(N) = 10⁵ なのでO(n²) では間に合わない
• 配列A, B[C]を作成し、sortして、Aの値で、B[C]を2分探索するのであれば間に合いそう
  • O(NlogN) くらいになるはず
• 数列内には同じ数値を含むため、注意する
  • 今回は、 bisect_left と bisect_right を利用した

実装

import bisect

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

L = []

ans = 0
for j in range(N):
    L.append(B[C[j]-1])

L.sort()
A.sort()

for i in range(N):
    j = bisect.bisect_left(L, A[i])
    k = bisect.bisect_right(L, A[i])
    ans += k-j

print(ans)

結果

• 無事に解けた

D問題

方針は立てられたが、実装できず時間切れに

atcoder.jp

考察

• 全探索した場合、 max = 2³⁰ なので間に合わない
• そのため、工夫して高速に探索する必要がある
• 重複組合せによって場合の数を求める
  • Kの数に応じて、頭の文字からa or bを決めていくことを繰り返していく

実装

from math import factorial

A, B, K = map(int, input().split())

ans = []


def num_of_case(a, b):
    return factorial(a+b)//(factorial(a)*factorial(b))


def gen_strings(a, b, k):
    if a == 0:
        ans.append("b" * (a + b))
    elif b == 0:
        ans.append("a" * (a + b))
    elif num_of_case(a - 1, b) >= k:
        ans.append("a")
        gen_strings(a-1, b, k)
    else:
        ans.append("b")
        gen_strings(a, b-1, k-num_of_case(a-1, b))


gen_strings(A, B, K)

print(*ans, sep="")

結果

• 無事に解けた

まとめ

• またしてもD問題が解けなかったので、定型のアルゴリズムの勉強を続けていきたい
• C問題までの回答時間の削減も続けていきたい、20分程度で安定して終えられるようにしたい

#Atcoder #Python #競技プログラミング