PythonでABC398

AtCoder Beginer Contest 398 をPythonで解きました。

A問題

問題文

以下の条件を全て満たす長さ$N$の文字列を求めてください。

各文字は - または = である
回文である
文字列中に = は 1 個または 2 個含まれる。
2 個含まれる場合、それらの = は隣接している
なお、そのような文字列はちょうど 1 つ存在します。

制約

$1≤N≤100$
$N$は整数である

"-" を$N$個含む配列を作り、$N$が奇数なら中央の１つ、偶数なら中央の２文字を"="に変える。空文字で連結して返す。

A

N = int(input())
ans = ["-"] * N
if N%2 == 1:
    ans[int((N-1)/2)] = "="
else:
    ans[int(N/2)] = "="
    ans[int(N/2)-1] = "="
print("".join(ans))

B問題

問題文

7 枚のカードがあります。
$i$ 番目 (i=1,…,7) のカードには整数$A_i$が書かれています。
これらのカードから 5 枚を選び、フルハウスとできるか判定してください。
ただし、 5 枚組のカードは以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

異なる整数 $x,y$ について、 $x$ が書かれたカード 3 枚と $y$ が書かれたカード 2 枚からなる。

制約

$A_i$ は 1 以上 13 以下の整数

カードにかかれた数字をキーに、そのカードの位置をdictに保持する。カードにかかれた数字に対して、カードが２枚以上の組が２つ以上、３枚以上かかれた組が１つ以上あればフルハウスを作れる。

$True$になる条件を勘違いしており、ぴったり２枚・３枚の組が存在することで判定する実装をしたためWAを出してしまった。

B

A = list(map(int, input().split()))
T = {}
for i in range(len(A)):
    if A[i] not in T:
        T[A[i]] = [i]
    else:
        T[A[i]].append(i)
flg2 = 0
flg3 = 0
for t in T.keys():
    if len(T[t]) >= 2:
        flg2+=1
    if len(T[t]) >= 3:
        flg3+=1

if flg2>=2 and flg3>=1:
    print("Yes")
else:
    print("No")

C問題

問題文

$1$ から $N$ の番号がついた $N$ 人の人がいます。人$i$ は数 $A_i$を持っています。
「自分と同じ数を持っている人が自分以外の $N−1$ 人の中に存在しない」という条件を満たす人のうち、持っている数が最大である人の番号を求めてください。

条件を満たす人が存在しない場合、代わりにそのことを報告してください。

制約

$1≤N≤3×10^5$
$1≤A_i≤10^9$
入力は全て整数である

$A_i$をキーに、$i$を持つような辞書をつくる。
キーを降順でソートして、初めて人数が１になる$i$を報告すればよい。
$A_i≤10^9$のため、配列で持つには要素が多すぎる。dictなら登場しない数字はキーとして持たなくていいので、要素の数がたかだか$N≤3×10^5$で済む。

C

N = int(input())
A = list(map(int, input().split()))
T = {}
for i in range(N):
    if A[i] not in T:
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
ans = -1
for key in sorted(T.keys(), reverse=True):
    if len(T[key]) == 1:
        ans = T[key][0]
        break
print(ans)

F問題

問題文

$S$ を接頭辞に持つ最短の回文を
$1$ つ求めてください。

制約

$S$は英大文字からなる長さ $1$ 以上$500000$ 以下の文字列

D問題とE問題がよくわからず、解けそうなF問題に（調子に乗って）挑戦した。
先頭から文字列を読みつつdeque（seek）に保持。文字列の後半から回文にできる場合を、折り返し地点が２文字（even）と１文字（odd）の２通りのdequeで検査する。読み取る文字が検査用dequeの右端と一致すれば続行、異なるときは検査用dequeをseekからコピーしたものに初期化する。

動作は問題ないようです。ただ、TLEになってしまいました。計算量は$O(N)$のはずなのにどうして……
【2025/03/24追記】
copyの計算量が$O(N)$らしい。実際には全体で$O(N^2)$になっていてTLEになったと。

F_TLE

from collections import deque
strS = input()
S = [strS[i] for i in range(len(strS))]
seek = deque()
even = deque()
odd = deque()
evenOK = True
oddOK = True

for i in range(len(S)):
    if i <= int((len(S)-1)/2):
        seek.append(S[i])
        continue
    
    if not evenOK or len(even) == 0:
        even = seek.copy()
        evenOK = True
    if not oddOK or len(odd) == 0:
        odd = seek.copy()
        odd.pop()
        oddOK = True
    
    if even.pop() != S[i]:
        evenOK = False
    if len(odd) == 0:
        oddOK = False
    elif odd.pop() != S[i]:
        oddOK = False
    
    seek.append(S[i])

ansEven = ""
if evenOK:
    tmpEven = seek.copy()
    while len(even)>0:
        tmpEven.append(even.pop())
    ansEven = "".join(tmpEven)
ansOdd = ""
if oddOK:
    tmpOdd = seek.copy()
    while len(odd)>0:
        tmpOdd.append(odd.pop())
    ansOdd = "".join(tmpOdd)
ansAll = ""
tmpAll = seek.copy()
tmpAll.pop()
while len(tmpAll)>0:
    seek.append(tmpAll.pop())
    ansAll = "".join(seek)

if not evenOK and not oddOK:
    print(ansAll)
elif evenOK and oddOK:
    if len(ansEven) < len(ansOdd):
        print(ansEven)
    else:
        print(ansOdd)
elif evenOK:
    print(ansEven)
else:
    print(ansOdd)