AtCoder初心者振り返りメモ ABC329

ABC329の回

ABの2完。
振り返ると先にD問題にチャレンジすれば良かったのですが、C問題でTLEを取ることができず時間だけを失ってしまいました。

A-問題

問題文
英大文字からなる文字列 S が与えられます。S の各文字を空白で区切り、その順で 1 文字ずつ出力してください。

ポイント
Pythonには、空白区切りで出力する「*S」があるのですぐに回答できました。

A.py

# 入力 
S = str(input())

print(*S)

B-問題

問題文
N 個の整数 A1,A2,…,ANが与えられます。 このうち最大でない整数の中で最大である整数を求めてください。

ポイント
最初に最大値を求め、リストAからリストBへ最大値以外を転記してから最大値を求めました。

※コンテスト中は、set に格納してから　2番目の値を求めようとしたが、VScodeでサンプル問題の回答がすぐにできなかったので、上記方針に変更しました。

リスト → set → リスト　で解決できることがわかったので良かったです。

B.py

MA = max(A)
B = []
for i in range(N):
    if A[i] != MA:
        B.append(A[i])
    else:
        continue

MB = max(B)

print(MB)

B2.py

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

# 一度 setに格納して重複を削除する
B = set(A)

# もう一度リストにしてソートする
C = list(B)
C.sort()

# 後ろから2番目の値が、最大値の次の値となる
print(C[-2])

C-問題

ポイント
a,aa,aaa の順に検索する実装で正解に辿りつけず。
連続する文字の最大値を集計する方針を思いつきませんでした。

C.py

N = int(input())
S = input()

# A ～ Z のテーブルを用意する
X = [0] * 26

cnt = 0

# 英小文字の連続を見つけて連続数のMAXをテーブルに記録しておく
for i in range(N):
    if i >= 1 and S[i] == S[i-1]:
        cnt += 1
    else:
        cnt = 1

    # 英小文字を数値化
    t = ord(S[i])-97

    # A-Z テーブルの最大値を記録する
    X[t] = max(X[t], cnt)

# 最大値の集計が、答え　a,aa,aaa  とある場合は、個数 = 最大値
print(sum(X))

D-問題

ポイント
投票の都度max値を求める実装ではサンプルは正答でも、TLEを崩せませんでした。ここでタイムアップ。
前回最大値投票者と今回投票者の比較だけの判定で計算量が収まる問題でした。

D.py

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

C = [0] + [0] * N

ans= 1 #前回の答えとして管理

for i in range(M):
    X = A[i]
    C[X] += 1

#  今回の投票で X 番目の人の数が前の投票の人より多い場合は更新する
    if C[X] > C[ans]:
        ans = X

#　同数の場合
    elif C[X] == C[ans]:
        # かつ番号が若い場合は更新する
        if X < ans:
            ans = X
    
    print(ans)