ABC221参戦記

プログラミング

ABC221の参加記録です。
使用言語はPython3、レートは600前後の私が自分の理解した内容で記載していきます。
A問題からC問題までのACコード付きです。

A – Seismic magnitude scales

標準入出力と、指数計算が出来るかが問われる問題。

問題文で与えられる設定では、マグニチュードが1増えるたびにエネルギーは32倍になるということなので、32を(A-B)乗した数を出力すれば良いですね。

# AtCoder Beginner Contest 221
# A - Seismic magnitude scales

A,B=map(int,input().split())
print(32**(A-B))

そのほか、繰り返し処理や、32が2の5乗であることを利用したビットシフトでも解けますね。

繰り返し処理のコード

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

ans=1
for _ in range (A-B):
    ans*=32
print(ans)

ビットシフトを用いたコード

A,B=map(int,input().split())
print(1<<(5*(A-B)))

B – typo

繰り返し処理と、位置の入れ替えが出来るかが問われる問題。

隣り合う文字を入れ替えて、SとTが一致するかを判定して、一致していたらその場で”Yes”を出力しプログラムを終了させます。
もし、隣り合う文字を入れ替えてSとTが異なる場合、入れ替えた部分をもとに戻して、次に進むようにします。最後まで進んでプログラムが終了していなければ”No”を出力したらOKですね。

# AtCoder Beginner Contest 221
# B - typo

S=list(input())
T=list(input())
N=len(S)

if S==T:
    print("Yes")
    exit()

for i in range (N-1):
    S[i],S[i+1]=S[i+1],S[i]
    if S==T:
        print("Yes")
        exit()
    else:
        S[i],S[i+1]=S[i+1],S[i]

print("No")

C – Select Mul

ビット全探索が出来るかが問われる問題。

以下、この問題を解くときの方針を書きます。

  • 数字の各桁を使用する数字の集まり、数1と数2を作る。
  • 二つの数の積を大きくするには、それぞれの数の上位の桁に大きい数を使用する。
  • 数1、数2は、ビット全探索を用いてすべての組み合わせを列挙する。
  • 答えを更新していく。
# AtCoder Beginner Contest 221
# C - Select Mul

N=input()
N=list(map(int,N))

ans=0

# bit全探索
for i in range(2**len(N)):
    n1=[]   # 分離した数1で使用する数字の集まり
    n2=[]   # 分離した数2で使用する数字の集まり
    for j in range(len(N)):
        if i>>j & 1 ==1:
            n1.append(N[j])
        else:
            n2.append(N[j])
    if len(n1)==0 or len(n2)==0:    # 分離していない場合はcontinue
        continue
    else:
        # 積が大きくなるためには、上位の桁に大きい数を使用する
        n1.sort(reverse=True)
        n2.sort(reverse=True)

        # 配列で持っているため、int型に変換
        n1=list(map(str,n1))
        n1=int("".join(n1))
        n2=list(map(str,n2))
        n2=int("".join(n2))

        # 答え用の変数の更新
        ans=max(ans,n1*n2)

print(ans)

ビット全探索は、以下のコードを毎回テンプレートとして使用しています。

N=3
for i in range(2**N):
    P=[]    
    for _ in range(N):
        if i>>_ & 1 ==1:
            P.append(1)
        else:
            P.append(0)
    print(P)
# [0, 0, 0]
# [1, 0, 0]
# [0, 1, 0]
# [1, 1, 0]
# [0, 0, 1]
# [1, 0, 1]
# [0, 1, 1]
# [1, 1, 1]

コメント

タイトルとURLをコピーしました