【AtCoder 】PythonでABC257のAからC問題までを解いた

AtCoder Beginner Contest 257に参加したので自分用のメモを残す。

• 利用言語 : Python

A 問題

愚直に2重ループ

Python

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

alb = [chr(ord("A")+i) for i in range(26)]

cnt = 0
for a in alb:
    for _itr in range(N):
        ans = a
        cnt += 1
        if cnt == X:
            print(ans)
            exit()

B 問題

はじめ問題の条件把握を誤解していた。 1時間くらい無駄にした。

Python

import numpy as np

N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
L = list(map(int, input().split()))

mass = np.zeros(N, dtype=int)
for i in range(len(A)):
    mass[A[i]-1] = i + 1

for i in range(len(L)):
        
    for j in range(len(mass)):
        if mass[j] == L[i]:
            if j != N - 1:
                if mass[j+1] == 0:
                    mass[j+1] = mass[j]
                    mass[j] = 0
            break

ans = []

for i in range(len(mass)):
    if mass[i] > 0:
        ans.append(i+1)

print(*ans)

C 問題

愚直に子供大人を比較すると計算量としては $O(n^2)$ となりTLE起こす。
事前に体重でソートしておいて最大値を大人の人数に設定した後、体重が小さい方から子供に変換していき最大値となる箇所を探索する。そうすると計算量は$O(N\log{N})$まで減らせる。

python

N=int(input())
S=input()
W=list(map(int,input().split()))
# 文字列は各文字が要素となるように分解される
l=zip(W,S)
# 各タプル先頭の要素でソート
l=sorted(l)
# W, S はタプル
W,S=zip(*l)

sum1 = 0
max1 = 0
# 大人の数
co = S.count('1')
# 子供の数
co1= len(S) - co
sum1 = co
# 左の人 (体重では無い！) から見ていく
for i in range(N):
    # 大人であれば
    if S[i]=="1":
        sum1-=1
    # 子であれば
    else:
        sum1+=1
    # 見ている人が末尾でないとき
    if i<N-1:
        # (ここ重要!) 連続して同じ体重でないとき
        if W[i]!=W[i+1]:
            max1=max(sum1,max1)
# 末尾の人とそれ以外までとの比較
max1=max(co1, co, max1)
print(max1)