ABC365(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
-
Yを数字で受け取る． - 順番に
if-elseで条件分岐をする．
A.py
"""
<方針>
- `Y` を数字で受け取る．
- 順番に `if-else` で条件分岐をする．
"""
# Yを数値で受け取る．
Y = int(input())
# Yが4の倍数で無い
if(Y%4 != 0):
print(365)
# Yが4の倍数だが，100の倍数で無い
elif(Y%4==0 and Y%100 != 0):
print(366)
# Yが100の倍数だが，400の倍数で無い
elif(Y%100 == 0 and Y%400 != 0):
print(365)
# Yが400の倍数
elif(Y%400 == 0):
print(366)
B問題
-
AをソートしたものBを用意する． - 二番目に大きい値は，
B[-2]である． -
Aを順番に見ていき， 値がB[-2]と一緒になった時に，0-indexedに注意して，i+1を出力し，exit関数でプログラムを終了する．
B.py
"""
<方針>
- `A` をソートしたもの `B` を用意する．
- 二番目に大きい値は， `B[-2]` である．
- `A` を順番に見ていき， 値が `B[-2]` と一緒になった時に， `0-indexed` に注意して， `i+1` を出力し， `exit` 関数でプログラムを終了する．
"""
# 標準入力を受け取る．
N = int(input())
A = list(map(int, input().split()))
# AをソートしたBを用意する(Aの順番はそのまま)．
B = sorted(A)
# Aを順番にみる．
for i in range(N):
# 値が二番目に大きい値と一致した時，
if(A[i]==B[-2]):
# i+1を出力する．
print(i+1)
# プログラムを終了する．
exit()
C問題
方針
-
Mが大きすぎるので，Mを一つずつみるのは不可能．だから，Mで二分探索をしよう． - 支払う金額を確認するのに，
O(N)である． - つまり，計算量は
O(NlogM)となり，十分間に合う． - 高橋くんが
MAXまで払えたら，infiniteと出力すれば良い．
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- `M` が大きすぎるので， `M` を一つずつみるのは不可能．だから， `M` で二分探索をしよう．
- 支払う金額を確認するのに， `O(N)` である．
- つまり，計算量は `O(NlogM)` となり，十分間に合う．
- 高橋くんが `MAX` まで払えたら， `infinite` と出力すれば良い．
"""
# 標準入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
# Mの想定よりも大きい値
MAX = 2*10**14 + 1
# めぐる式二分探索
ok = 0
ng = MAX + 1
while ng - ok > 1:
# 高橋くんが設定する補助額
mid = (ng+ok)//2
# みんなに支払う総額を計算
cost = 0
for i in range(N):
if(A[i] < mid):
cost += A[i]
else:
cost += mid
# 高橋くんは払い切れるよ．
if(cost<=M):
ok = mid
# 高橋くんは払えないよ．
else:
ng = mid
if(ok == MAX):
# 何円にでも設定できる．
print("infinite")
else:
print(ok)
D問題
-
dpで一個前に何を出したかを記録してやればできる．
D.py
"""
<方針>
- `dp` で一個前に何を出したかを記録してやればできる．
"""
# 入力
N = int(input())
S = input()
# dp[i][j]: i回目に自分がjを出した時に勝った回数の最大値
dp = [{"R": 0, "S": 0, "P": 0} for _ in range(N+1)]
for i in range(N):
s = S[i]
# 相手がRのとき，
if(s=="R"):
# 自分がRを出せば引き分ける．
dp[i+1]["R"] = max(dp[i]["S"], dp[i]["P"])
# 自分がPを出せば勝てる
dp[i+1]["P"] = max(dp[i]["R"], dp[i]["S"]) + 1
# 同上
if(s=="S"):
dp[i+1]["S"] = max(dp[i]["R"], dp[i]["P"])
dp[i+1]["R"] = max(dp[i]["P"], dp[i]["S"]) + 1
# 同上
if(s=="P"):
dp[i+1]["P"] = max(dp[i]["S"], dp[i]["R"])
dp[i+1]["S"] = max(dp[i]["R"], dp[i]["P"]) + 1
# 最後はどの手にしたら一番勝てたかな．
print(max(dp[N].values()))
E問題
- ユーザー解説と一緒です．
E.py
"""
- ユーザー解説と一緒です．
"""
N = int(input())
A = list(map(int, input().split()))
ans = 0
# Aでありえるbitの2**K > 10**8
K = 27
# XORは桁ごとで考えれば十分
for i in range(K):
# dp[i][j]: 区間 [0, i] までの長さ1~i+1までの全ての区間におけるxorした結果，j となる個数．
dp = [[0]*2 for _ in range(N)]
# A[0]のibit目の値
a = int(bool(A[0]&1<<i))
# 初期値を設定
dp[0][a] = 1
for j in range(N-1):
# A[j+1]のibit目の値
a = int(bool(A[j+1]&1<<i))
dp[j+1][0] = dp[j][a] + (a^1) # 演算子の順序的に，()で括らないとだめ．
dp[j+1][1] = dp[j][a^1] + a
# i桁のみに注意した時の答え．
tmp = sum(map(lambda x: x[1], dp))
# 本問題では，自身のxorは除くため．
tmp -= sum([int(bool(a&1<<i)) for a in A])
# i桁目なので，2**i倍してる．
tmp <<= i
ans += tmp
print(ans)
補足
関係するリンク(参考文献など)
筆者について
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 明日は院試です．．．頑張ってきます．．．
- 院試前に何やってんだろ．．．