[ABC371] ABC 371(Atcoder Beginner Contest)のA~E(A,B,C,D,E)問題をPythonで解説(復習)
A問題
- 入力を
strで受け取るように注意する． - それぞれ，
A,B,Cが次男になる必要条件は，自分が関わっている大小関係だけを見ればよい．それぞれ，2パターンあるのを注意
A.py
"""
<方針>
- 入力を `str` で受け取るように注意する．
- それぞれ， `A`, `B`, `C` が次男になる必要条件は，自分が関わっている大小関係だけを見ればよい．それぞれ， `2` パターンあるのを注意
"""
# 入力(str)
x, y, z = map(str, input().split())
# Aが次男
if (
(x == "<" and y == ">") or
(x == ">" and y == "<")
):
print("A")
# Bが次男
if (
(x == "<" and z == "<") or
(x == ">" and z == ">")
):
print("B")
# Cが次男
if (
(y == "<" and z == ">") or
(y == ">" and z == "<")
):
print("C")
B問題
- それぞれの家で男の子が生まれたかどうかを管理する配列
taro_existsを作成する． - 入力を上から順に受け取って，名前が
taroになるかどうかを判定する．
B.py
"""
<方針>
- それぞれの家で男の子が生まれたかどうかを管理する配列 `taro_exists` を作成する．
- 入力を上から順に受け取って，名前が `taro` になるかどうかを判定する．
"""
# 入力
N, M = map(int, input().split())
# 男の子が生まれたかどうかを管理する配列
taro_exists = [False]*(N+1)
# 順に入力を受け取る
for _ in range(M):
# 入力を受け取る
A, B = input().split()
# Aの入力を数値として受け取る
A = int(A)
# 初めてお家Aで男の子が生まれた
if(B == "M" and not taro_exists[A]):
print("Yes")
# 男の子が生まれたことを記録する．
taro_exists[A] = True
# 女の子が生まれた
else:
print("No")
C問題
方針
- 今回は全ての頂点を入れ替えるパターンが
O(N!)である． - 全部の辺を確かめても，
O(N^2)である．- 全ての頂点の間を辺の有無に関わらずみていき，
GとHで辺の有無が合致しないところだけをコストとして払えば，同型になる．
- 全ての頂点の間を辺の有無に関わらずみていき，
- 計算量は
O(N! x N^2)程度なので，問題なく処理できる．実装できるかどうかだ． - 補足
-
0-indexedで数える． -
GとHの受け取り方は一緒なので，関数化して，実装を軽くする．
-
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 今回は全ての頂点を入れ替えるパターンが `O(N!)` である．
- 全部の辺を確かめても，`O(N^2)` である．
- 全ての頂点の間を辺の有無に関わらずみていき， `G` と `H` で辺の有無が合致しないところだけをコストとして払えば，同型になる．
- 計算量は `O(N! x N^2)` 程度なので，問題なく処理できる．実装できるかどうかだ．
- 補足
- `0-indexed` で数える．
- `G` と `H` の受け取り方は一緒なので，関数化して，実装を軽くする．
"""
# ノードの数
N = int(input())
# グラフを受け取る関数
def getEdges():
M = int(input())
Edges = [[False]*N for _ in range(N)]
for _ in range(M):
u, v = map(int, input().split())
# 0-indexed
u -= 1
v -= 1
Edges[u][v] = True
return Edges
# Gを構築
G = getEdges()
# Hを構築
H = getEdges()
# Aを構築
A = [list(map(int, input().split())) for _ in range(N-1)]
import itertools
ans = float("inf")
# 頂点を入れ替える
for table in itertools.permutations(range(N)):
# コストの計算
tmp = 0
# 辺の有無を全て確認する．
for i in range(N):
for j in range(N):
# 重複を防ぐ
if(i>=j):continue
# 並び替えを考慮する(I<Jとする)
I = min(table[i], table[j])
J = max(table[i], table[j])
# 辺の有無が一致しない時
if(G[I][J] != H[i][j]):
tmp += A[i][j-i-1] # indexに注意
# 最小コストの更新
ans = min(ans, tmp)
print(ans)
D問題
- セグメント木で区間取得を早くする．
- 取得する場所は2分探索で早くとる．
D.py
"""
<方針>
- セグメント木で区間取得を早くする．
- 取得する場所は2分探索で早くとる．
"""
from atcoder.segtree import SegTree
N = int(input())
X = list(map(int, input().split()))
P = list(map(int, input().split()))
# セグ木
st = SegTree(lambda x,y:x+y, 0, P)
Q = int(input())
for _ in range(Q):
L, R = map(int, input().split())
# 左端を取得
ng = -1
ok = N
while abs(ok - ng) > 1:
mid = (ok+ng)//2
if(L<=X[mid]):
ok = mid
else:
ng = mid
l = ok
# 右端を取得
ok = -1
ng = N
while abs(ok - ng) > 1:
mid = (ok+ng)//2
if(X[mid]<=R):
ok = mid
else:
ng = mid
r = ok
# セグ木を使って，値を取得
print(st.prod(l, r+1))
E問題
- 公式解説と一緒です．
E.py
"""
<方針>
- 公式解説と一緒です．
"""
N = int(input())
A = list(map(int, input().split()))
# 種類ごとにどこのインデックスにあるか
table = [[-1] for _ in range(N+1)]
for i, a in enumerate(A):
table[a].append(i)
# 答え
ans = 0
# 全ての種類を見る
for indices in table:
# 数字が存在したとき
if(len(indices) > 1):
# 余事象で考える
ans += (N*(N+1)//2)
# 番兵
indices.append(N)
# 間を見ていく
for i in range(len(indices)-1):
# 間の長さを取得
le = indices[i+1] - indices[i] - 1
# 長さがある時
if(le>0):
# 引いていく
ans -= (le*(le+1)//2)
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回は不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．