[ABC427] ABC 427(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)

合計回答時間：60分

A問題

自分の回答

かかった時間：3分

S = input()

index = len(S)//2
print(S[0:index]+S[index+1:])

終了後考えた最適な回答

listとして入力を受け取って、delで削除も考えたけどコード量増えるからこっちでいい気がする

S = input()

index = len(S)//2
print(S[0:index]+S[index+1:])

B問題

自分の回答

かかった時間：20分

# AtCoder用のPythonテンプレート
# コンテスト番号: 427

N = int(input())

A = [1]
ans = 0
temp = 0
for i in range(N):
    temp = sum(A)
    ans = sum(map(int, str(temp)))
    A.append(ans)
print(temp)

終了後考えた最適な回答

# f(123)=1+2+3=6を計算する関数
def f(x):
    return sum(map(int,str(x)))

N = int(input())

A = [1]
for i in range(N):
    x = sum(A)
    # A5=16のf(16)=7であることを求める
    ans = f(x)
    A.append(ans)
print(x)

C問題

自分の回答

かかった時間：35分
解けなかった、方針から間違っていそう

# 無向グラフとは　グラフにおいて辺に方向がないグラフのこと

# 1.グラフが二部グラフであるか判定する
# 2.二部グラフでないなら適切な辺を削除する
# 3.二部グラフであれば答えを出力する

def is_graf():
    flag = False

    return flag


N,M = map(int,input().split())

G = {}

for i in range(N):
    G[i] = set()

print(G)

for i in range(M):
    u,v = map(int,input().split())
    G[u - 1].add(v - 1)
    G[v - 1].add(u - 1)

# 二部グラフでない限りループする
while flag == false:
    ans = is_graf()
    if ans:
    else:

終了後考えた最適な回答

N, M = map(int, input().split())

edges = [tuple(map(int, input().split())) for _ in range(M)]

# 削除するべき辺の数、つまり答え
ans = M

# 2^N 通りの塗り方を全部探索する
# 例：5個の頂点を白黒で塗り分ける方法は32通り
# 0〜31の値を５ビットの２進数で表現すると白黒での塗り分けを表現できる
# 00001なら一番右の1が頂点1の色、一番左の0が頂点5の色である
for bit in range(2 ** N):
    # ある塗り方をした時に、削除するべき辺の数
    delete_count = 0
    print(bit)
    for u ,v in edges:
        # ビットを頂点番号分右にシフトし、その最下位ビットが0か1かを判定
        # 両方が0,または1ならTrue、そうでないならFalse
        if (1 & (bit >> u)) == (1 & (bit >> v)):
            delete_count += 1
    # 今回の塗り方で削除した辺の数の合計が、今までの塗り方の最小値ならansに登録
    ans = min(ans,delete_count)
print(ans)

次に向けてやること

・128、147C問題解く

感想

おそらくアルゴリズムを知っていないと解法をそもそも思いつかないような問題だった、愚直に実装すると実装量がすごそう。

補足

関係するリンク(参考文献など)

・今回のコンテスト

回答の正当性は保証できません。ベストエフォート方式です。