[ABC413] ABC 413(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
-
sumをとってみよう。
A.py
"""
<方針>
- `sum` をとってみよう。
"""
# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
sumA = sum(A)
# カバンに入る時
if(sumA <= M):
print("Yes")
else:
print("No")
B問題
- フルメッシュで２文字列間の
catを確認する。 - 重複なく文字列を管理するために、
setにcatした結果を入れる。
B.py
"""
<方針>
- フルメッシュで２文字列間の `cat` を確認する。
- 重複なく文字列を管理するために、`set` に `cat` した結果を入れる。
"""
# 入力
N = int(input())
S = [input() for _ in range(N)]
# 重複なく文字列を管理する変数
se = set()
# フルメッシュで確認する。
for i in range(N):
for j in range(N):
# 一緒の文字列は cat しない
if(i==j):
continue
# 連結
Si_Sj = S[i] + S[j]
# 登録する
se.add(Si_Sj)
# 個数を出力
print(len(se))
C問題
方針
- 愚直に実装すると間に合わない。
c, x, kが10^9もあるので、これらは線形時間もかけられない。 - クエリ数
Qはどうしても線形時間使うから、一つ一つのクエリをなんとか対数時間以下に抑える必要がある。 - タイプ１のクエリは
c個実際にキューに追加することはできないので、c個xを追加したことだけを記録する。- 整数の個数の総和と数値の総和はそれぞれ累積和で持たせておく。
- タイプ２のクエリは、前方から削除すると時間がかかるので、どこまで処理したかを保存しておき、2分探索で良い感じに整数の個数の総和を求める。
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 愚直に実装すると間に合わない。`c, x, k` が `10^9` もあるので、これらは線形時間もかけられない。
- クエリ数 `Q` はどうしても線形時間使うから、一つ一つのクエリをなんとか対数時間以下に抑える必要がある。
- タイプ１のクエリは `c` 個実際にキューに追加することはできないので、`c` 個 `x` を追加したことだけを記録する。
- 整数の個数の総和と数値の総和はそれぞれ累積和で持たせておく。
- タイプ２のクエリは、前方から削除すると時間がかかるので、どこまで処理したかを保存しておき、2分探索で良い感じに整数の個数の総和を求める。
"""
Q = int(input())
## 番兵として0を入れておく
q = [[1, 0]] # タイプ１のキュー
now = 1 # どれだけ先頭から削除したか
qSumCnt = [1] # 整数の個数の累積和
qSumVal = [0] # 整数の数値の累積和
acc = 0 # クエリ２の答えの総和
for _ in range(Q):
match list(map(int, input().split())):
# タイプ１
case [1, c, x]:
q.append([c, x]) # qに追加
qSumCnt.append(qSumCnt[-1] + c) # 個数の累積和
qSumVal.append(qSumVal[-1] + c*x) # 数値の累積和
# タイプ２
case [2, k]:
## 2分探索で効率よくまとまった個数を見つける
ok = -1
ng = len(qSumCnt)
while abs(ok-ng)>1:
mid = (ok+ng)//2
if(now + k >= qSumCnt[mid]):
ok = mid
else:
ng = mid
## はみ出た部分 add を計算
diff = (now + k) - qSumCnt[ok] # はみ出た個数
# はみ出たら
if(diff):
c, x = q[ok+1]
add = x*diff
# はみ出てないなら
else:
add = 0
## 出力
# 出力=まとまった部分+はみ出た部分-今までの出力
ans = qSumVal[ok] + add - acc
# 出力
print(ans)
## 後処理
acc += ans # 出力（数値）を蓄積する
now += k # 個数を蓄積する
D問題
- 公比 == ±1 かどうかで場合分けする。
- 公比 != ±1 のとき、abs でソートして、公比が全て等しければOK
- 公比 == ±1 のとき、全ての要素が等しい（公比 == +1）or全ての要素が ±A[0] で個数が半分ずつ（公比 == +1）
- P.S. もうなんかソースコードめちゃくちゃだよ。最近まじで競プロpowerが落ちてる
D.py
"""
<方針>
- 公比 == ±1 かどうかで場合分けする。
- 公比 != ±1 のとき、abs でソートして、公比が全て等しければOK
- 公比 == ±1 のとき、全ての要素が等しい（公比 == +1）or全ての要素が ±A[0] で個数が半分ずつ（公比 == +1）
- P.S. もうなんかソースコードめちゃくちゃだよ。最近まじで競プロpowerが落ちてる
"""
T = int(input())
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))
A.sort(key=lambda x: abs(x))
r = A[0]
R = A[1]
pos = (r*R > 0)
same = (abs(r) == abs(R))
# 公比 != ±1 のとき、
if not (same):
ok = True
for i in range(N-1):
if not (pos == (A[i]*A[i+1] > 0)):
ok = False
break
if not (A[i]*R == A[i+1]*r):
ok = False
break
print("Yes" if ok else "No")
# 公比 == ±1 のとき、
else:
# 公比 == +1
if (all([A[0] == a for a in A])):
print("Yes")
continue
# 公比 == -1
posCnt = 0
negCnt = 0
for a in A:
if(A[0] == +a):
posCnt += 1
if(A[0] == -a):
negCnt += 1
if (posCnt + negCnt == N and min(posCnt, negCnt) == N//2):
print("Yes")
continue
print("No")
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 復習記事書いてたから、（吉良吉影みたいに）ある程度競プロできると思ってたんすよ。
- けれでも、友人と記念受験したICPCでてんやわんやしてしまい、結局一問も貢献できなくて萎えた。
- ハングリー精神が足りなかったかもしれない。