ABC353(Atcoder Beginner Contest)のA~F(A,B,C,D,E,F)問題をPythonで解説(復習)
A問題
- 左から1番目のビルを変数
h0として持っておく． - 左から2番目以降のビルと
h0を比較して，大きなビルが見つかれば，そのindexをprintしてプログラムを終了する． - 左から順番に見て，
indexを出力するため，大きなビルが複数存在したとしても，問題ない． - もし，大きなビルが一つも存在しなかったら，最後に
-1をprintしてあげる． -
indexをprintするときは，0-indexedであることに注意する．
A.py
"""
<方針>
- 左から1番目のビルを変数`h0`として持っておく．
- 左から2番目以降のビルと`h0`を比較して，大きなビルが見つかれば，その`index`を`print`してプログラムを終了する．
- 左から順番に見て，`index`を出力するため，大きなビルが複数存在したとしても，問題ない．
- もし，大きなビルが一つも存在しなかったら，最後に`-1`を`print`してあげる．
- `index`を`print`するときは，`0-indexed`であることに注意する．
"""
# 標準入力を受け取る．
N = int(input()) # 全部でビルがいくつあるか．
H = list(map(int, input().split())) # ビルの高さをリストで受け取る．
# 左から1番目のビルを持っておく．
h0 = H[0]
# 左から2番目以降のビルを見ていく．
for i in range(1, N):
# h0よりも大きなビルであるかを判定する．
if(h0<H[i]):
# 0-indexedであることに注意して，i+1を出力する．
print(i+1)
# プログラムを終了させる．
exit()
# h0よりも大きなビルが見つからなかったとき，-1を出力する．
print(-1)
B問題
- アトラクションに今何人乗りながら待っているかを保持する変数
rideを用意する． - アトラクションを何回走らせたかを記録する変数
ansを用意する． - 並んでいる人を順番に見ていき，以下の処理を行う．
- もし，もう乗れるスペースがなければ，
ansをインクリメントし，rideを先頭で並んでいる人数にする． - まだ，乗れるスペースがあれば，
rideに先頭で並んでいる人数を足す．
- もし，もう乗れるスペースがなければ，
- 最後に乗った人の分，アトラクションを走らせる必要があるので，
ansをインクリメントして終了する．
B.py
"""
<方針>
- アトラクションに今何人乗りながら待っているかを保持する変数`ride`を用意する．
- アトラクションを何回走らせたかを記録する変数`ans`を用意する．
- 並んでいる人を順番に見ていき，以下の処理を行う．
- もし，もう乗れるスペースがなければ，`ans`をインクリメントし，`ride`を先頭で並んでいる人数にする．
- まだ，乗れるスペースがあれば，`ride`に先頭で並んでいる人数を足す．
- 最後に乗った人の分，アトラクションを走らせる必要があるので，`ans`をインクリメントして終了する．
"""
# 標準入力を受け取る．
N, K = map(int, input().split())
A = list(map(int, input().split()))
# アトラクションに今何人乗りながら待っているかを保持する変数
ride = 0
# アトラクションを何回走らせたかを記録する変数
ans = 0
# 並んで待っている人を順番にアトラクションに乗せていく．
for i in range(N):
# アトラクションに今回のグループ分乗れるスペースが無い時，
if(ride+A[i]>K):
# アトラクションを走らせる．
ans += 1
# アトラクションに乗っている人を先頭で並んでいる人数にする．
ride = A[i]
# アトラクションにまだ今回のグループ分乗せるスペースがある時，
else:
# アトラクションに乗ってる人数を増やす．
ride += A[i]
# アトラクションに乗って，待っている人がいるので，
if(ride!=0):
# アトラクションを走らせる．
ans += 1
print(ans)
C問題
前提
-
C問題あたりで，TLEなる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の前回の記事 の
C問題の解説に記したので，是非参照してほしい．
方針
- 愚直に長さ
Nのfor文を二重に回すと，O(N^2)となり，TLEする． - どうにか，計算量を減らしたい．
-
A_iの制約条件を見ると，10^8よりも小さいことがわかる． - つまり，任意の
2つのA_i間の和は10^8の2倍よりも大きくなることは無いため，f(x, y)の値は以下のいずれかになる．- 和が
10^8以上なので，f(x, y) = x+y-10^8 - 和が
10^8未満なので，f(x, y) = x+y
- 和が
- 仮に，全ての
2つのA_i間の和が10^8以上とならなかった場合は，答えは単純に[A_iの総和]と[N-1]の積となる． -
2つのA_i間の和が10^8以上となる回数cntが分かれば，それを{[A_iの総和]と[N-1]の積}から{cnt*(10**8)}を引けば良いことがわかる． - では，効率よく
cntを求めるにはどうすれば良いか． -
A_iを昇順にsortする． -
A_iを小さい順番に見て，そのA_i以降で，そのA_iとの和が10^8を超える境目を見つける． - この境目を見つけるのは，
sortされているため，二分探索で求められるため，O(LogN)の計算量で済む． - よって，
A_i一つ一つに注目するのに，O(N)かかり，その中で二分探索O(LogN)をするため，全体でO(NLogN)の計算量で済んだ． - 二分探索は「めぐる式二分探索」がバグりにくいためおすすめである．気になる人は調べてみてほしい．
C.py
"""
<前提>
- `C`問題あたりで，`TLE`なる人は，制約条件を見る癖をつけよう．
- `A`と`B`問題では，基本的に制約条件を見ずにやっても解ける．
- しかし，`C`問題以降では，制約条件を見ないと必ず`TLE`すると思っても良い．
- 詳しい話は私の前回の記事(https://qiita.com/mattsunkun/items/837444254f03e6105922)の`C`問題の解説に記したので，是非参照してほしい．
<方針>
- 愚直に長さ`N`の`for文`を二重に回すと，`O(N^2)`となり，`TLE`する．
- どうにか，計算量を減らしたい．
- `A_i`の制約条件を見ると，`10^8`よりも小さいことがわかる．
- つまり，任意の`2`つの`A_i`間の和は`10^8`の`2`倍よりも大きくなることは無いため，`f(x, y)`の値は以下のいずれかになる．
- 和が`10^8`以上なので，`f(x, y) = x+y-10^8`
- 和が`10^8`未満なので，`f(x, y) = x+y`
- 仮に，全ての`2`つの`A_i`間の和が`10^8`以上とならなかった場合は，答えは単純に[`A_i`の総和]と[`N-1`]の積となる．
- `2`つの`A_i`間の和が`10^8`以上となる回数`cnt`が分かれば，それを{[`A_i`の総和]と[`N-1`]の積}から{`cnt*(10**8)`}を引けば良いことがわかる．
- では，効率よく`cnt`を求めるにはどうすれば良いか．
- `A_i`を昇順に`sort`する．
- `A_i`を小さい順番に見て，その`A_i`以降で，その`A_i`との和が`10^8`を超える境目を見つける．
- この境目を見つけるのは，`sort`されているため，二分探索で求められるため，`O(LogN)`の計算量で済む．
- よって，`A_i`一つ一つに注目するのに，`O(N)`かかり，その中で二分探索O(LogN)をするため，全体で`O(NLogN)`の計算量で済んだ．
- 二分探索は「めぐる式二分探索」がバグりにくいためおすすめである．気になる人は調べてみてほしい．
"""
N = int(input())
A = list(map(int, input().split()))
# 10^8
MOD = 10**8
# Aを昇順にして，二分探索できるようにする．
A.sort()
# 和がMOD(10^8)を超えた回数を記録する変数．
cnt = 0
# Aを一つ一つ注目する．最後のAは注目しなくて良い．
for i in range(N-1):
## <めぐる式二分探索>
l = i # 左端は注目しているAの位置
r = N # 右端は一番右で良い
while r-l>1:
m = (l+r)//2
# MOD(10^8)を和が超える境目を見ている．
if(A[m]+A[i]>=MOD):
r = m
else:
l = m
## </めぐる式二分探索>
# 和がMOD(10^8)を超えた回数を記録する．
cnt += N-r
# 総和のN-1倍から，MOD(10^8)を超えた回数とMOD(10^8)の積を引いて出力
print(sum(A)*(N-1)-(cnt*MOD))
D問題
- 当然，長さ
Nの二重ループはTLEする． - また，
f(x, y)とf(y, x)は等しく無いため，sortは望ましくない． -
f(x, y)の挙動を考える．数字を連結すると，左側の数字は右側の数字の桁数分だけ，10の累乗倍される． - なので，ある
Aとそれより右側に存在するAとのf(x, y)は以下のことがO(1)で分かれば，行けそうな感じがする．- 右側に存在する
Aの中で，i桁の数字が何個あるか - 右側に存在する
Aの総和
- 右側に存在する
- これらは前計算で
A全てにおいて求めておき，あるAに注目するごとに，それらの値を減少させればよい． - 適宜，
MODを取ることを忘れないようにする．
D.py
"""
<方針>
- 当然，長さ`N`の二重ループは`TLE`する．
- また，`f(x, y)`と`f(y, x)`は等しく無いため，`sort`は望ましくない．
- `f(x, y)`の挙動を考える．数字を連結すると，左側の数字は右側の数字の桁数分だけ，`10`の累乗倍される．
- なので，ある`A`とそれより右側に存在する`A`との`f(x, y)`は以下のことがO(1)で分かれば，行けそうな感じがする．
- 右側に存在する`A`の中で，`i`桁の数字が何個あるか
- 右側に存在する`A`の総和
- これらは前計算で`A`全てにおいて求めておき，ある`A`に注目するごとに，それらの値を減少させればよい．
- 適宜，`MOD`を取ることを忘れないようにする．
"""
N = int(input())
A = list(map(int, input().split()))
MOD = 998244353
# 右側に存在するAの中で，`i`桁の数字が何個あるかを管理する変数．制約条件的に，桁数は高々10桁
## index: i桁
## value: 何個あるか
di = [0]*(10 + 1)
for i in range(N):
di[len(str(A[i]))] += 1
# 右側に存在するAの総和を管理する変数．初期値は，Aの総和
su = sum(A)
ans = 0
# Aを一つずつみる．最後のAは見なくて良い．
for i in range(N-1):
# 今見ているAの値
a = A[i]
# 今見ているAの桁数はデクリメントする．
di[len(str(a))] -= 1
# 今見ているAの値は総和から減らす．
su -= a
# 今のAの値を右側にある桁数の分だけ10の累乗倍して，答えを増やす．
ans += a*sum([(10**i)*di[i] for i in range(len(di))])
# 右側にあるAの総和分を増やす．
ans += su
# MODを取る．
ans %= MOD
print(ans)
E問題
- 公式解説と一緒です．
- Trie木を作るだけです．
- 解説にあったPythonコードの一部にコメントを付与したものになります．
E.py
"""
<方針>
- 公式解説と一緒です．
- Trie木を作るだけです．
- 解説にあったPythonコードの一部にコメントを付与したものになります．
"""
N = int(input())
S = list(map(str, input().split()))
# Trie木の根の参照を持つ．
root = {}
# LCPした文字の個数
ans = 0
# 文字列を順番に見ていく．
for s in S:
## Trie木を根っこから見ていく．
# key: 英小文字
# value: list(同じ部分文字列の個数, 再帰的なTrie木(部分木))
tree = root
# 文字列の文字を一つずつ見ていく．
for c in s:
# その文字を「現在のTrie木(部分木)の中で」，見たことがある時，
if c in tree:
# 文字が一致したとして，LCPした文字の個数を増やす．
ans += tree[c][0]
# 文字の並びを登録する．
tree[c][0] += 1
else:
# 新しいTrie木(部分木)を作成する．
tree[c] = [1, {}]
# Trie木の探索を深める(さらなる部分木へ行く)
tree = tree[c][1]
print(ans)
F問題
- 細かい実装はコメントを見てほしい．
- 本番でACしたコードをちょっと見やすくしただけです．
- 関数をどこで使っているか明示するために，関数が入れ子にしてみました(わかりづらくなってたらごめん)．
- 前提として，距離が遠いほど，大タイルを利用して移動した方が明らかに効率が良さそう．
-
SまたはTが小タイルにいたとき，- 最寄の
4方の大きいタイルに最短距離で出ることで，大タイル間の移動の話に持ち込む． -
SとTが互いに小タイルにいても，高々4x4通りしか無いので，計算時間は特に問題ない．
- 最寄の
-
SとTが大タイルにいるときのコストの考え方．- タイルを斜めに移動して，斜め移動一つの度に
2コスト使う計算になる． - 結局，
xまたはy方向で互いに最も離れている方向だけを考えれば良いことがわかる． - しかし，
K==2の時は，直進した方が早いことがあるため，なるべく斜めで進んで，残りは直線で進むものとする．
- タイルを斜めに移動して，斜め移動一つの度に
- また，
K==1のときや，4方が同じ大タイルとなる小タイルにSとTがあったときを考慮して，コストの初期値をマンハッタン距離としておく．
F.py
"""
<方針>
- 細かい実装はコメントを見てほしい．
- 本番でACしたコードをちょっと見やすくしただけです．
- 関数をどこで使っているか明示するために，関数が入れ子にしてみました(わかりづらくなってたらごめん)．
- 前提として，距離が遠いほど，大タイルを利用して移動した方が明らかに効率が良さそう．
- `S`または`T`が小タイルにいたとき，
- 最寄の`4`方の大きいタイルに最短距離で出ることで，大タイル間の移動の話に持ち込む．
- `S`と`T`が互いに小タイルにいても，高々`4x4`通りしか無いので，計算時間は特に問題ない．
- `S`と`T`が大タイルにいるときのコストの考え方．
- タイルを斜めに移動して，斜め移動一つの度に`2`コスト使う計算になる．
- 結局，`x`または`y`方向で互いに最も離れている方向だけを考えれば良いことがわかる．
- しかし，`K==2`の時は，直進した方が早いことがあるため，なるべく斜めで進んで，残りは直線で進むものとする．
- また，`K==1`のときや，`4`方が同じ大タイルとなる小タイルに`S`と`T`があったときを考慮して，コストの初期値をマンハッタン距離としておく．
"""
K = int(input())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
# 大タイル間を移動した時のコストを計算する．引数の座標は大タイルの規模．
# 最後のpSとpTをフルメッシュで計算しているfor文の中で使う関数．
def diaCost(S, T):
# xとy方向の距離を取得
xD = abs(S[0]-T[0])
yD = abs(S[1]-T[1])
# 距離の最大値と最小値の取得
ma = max(xD, yD)
mi = min(xD, yD)
# K==2のときには，
if(K==2):
# まずはできるだけ斜めに移動する．
ret = mi*2
# 長い方の分だけ，直進して進む．
ret += ((ma-mi)//2)*3
return ret
# 基本的には(K!=2のときには)
else:
# 距離の長い方を，1マスに2コスト使って移動．
return ma*2
# 小タイルの集合を大タイル一つとみなしたときに，大タイルの規模でどの座標にいるかを取得する．
# もし，初期場所が小さいタイルだった場合は，そこから4方の大タイルに移動する際のコストも取得する．
# 戻り値はList = [(このタプルの2つ目の値に記された座標へ移動するためのコスト, 大タイル規模の座標), (...), (...), (...)]
def points(s):
# 大タイルにいるか小タイルにいるかを判定して，大タイル上の座標と，場合によっては，小タイル上の座標を返す関数．
def norm(s):
# 小タイルの集合を大タイル一つとみなしたときに，奇数番目の大タイルの位置にいるかを判定する関数．
def isO(x):
return ((x//K)%2)==1
# 今いるタイルの場所の左下の角を(0, 0)に合わせる関数．引数は1次元なので，実際に左下の角を合わせる時は，2回並列に使う必要がある．
def nor(x):
return x - x//K*K
# 小タイルの集合を大タイル一つとみなしたときに，何番目の大タイルにいるかを返す関数．
def dia(X):
return X//K
# 絶対的なx, y座標を取り出す．
_x, _y = s
# xとyの位置の偶奇が一致している時，
if(isO(_x) == isO(_y)):
# 小タイルにいる．
# 小タイルの左下を(0, 0)とした時の座標を取得
x = nor(_x)
y = nor(_y)
# 小タイルの集合を大タイル一つとみなしたときに，大タイルの規模でどの座標にいるかを取得
X = dia(_x)
Y = dia(_y)
return 0, x, y, X, Y
else:
# 大タイルにいる．
# 小タイルの集合を大タイル一つとみなしたときに，大タイルの規模でどの座標にいるかを取得
X = dia(_x)
Y = dia(_y)
return 1, X, Y
# 左下が(0, 0)の前提で，小タイルにいるとして，4方のいずれかの大タイルに移動した時のコストを出力．
def cost4(s):
# 座標を取得．
x, y = s
l = x+1 # 左の大タイルへ移動した時の最小コスト
r = K-x # 右の大タイルへ移動した時の最小コスト
b = y+1 # 下の大タイルへ移動した時の最小コスト
t = K-y # 上の大タイルへ移動した時の最小コスト
return l, r, b, t
# 初期場所が小タイルかどうかのフラグをsFに格納する．
sF, *other = norm(s)
# 戻り値となる空のリスト
ret = []
# 初期場所が大タイルのとき
if(sF==1):
# 小タイルの集合を大タイル一つとみなしたときに，大タイルの規模でどの座標にいるかを取得する．
X, Y = other
# 自分の大タイルへのコストは当然0である．
ret.append((0, [X, Y]))
# 初期場所が小タイルのとき
else:
# 左下を(0, 0)にした時の座標を取得する．
# 小タイルの集合を大タイル一つとみなしたときに，大タイルの規模でどの座標にいるかを取得する．
x, y, X, Y = other
# 4方の大タイルに移動した時のコストを取得する．
l, r, b, t = cost4([x, y])
# 4方の大タイルへの移動コストと，その座標を格納する．
ret.append((l, [X-1, Y]))
ret.append((r, [X+1, Y]))
ret.append((b, [X, Y-1]))
ret.append((t, [X, Y+1]))
return ret
# 開始位置の大タイル座標とそれに至るコストを計算する．
pS = points(s)
# 終了位置についても同様．
pT = points(t)
# sとtのマンハッタン距離をコストの初期値とする．
ans = abs(s[0]-t[0])+abs(s[1]-t[1])
# SとTをフルメッシュで計算する．
for itemS in pS:
for itemT in pT:
# 大タイルに至るためのコストと大タイル規模の座標を取得する．
sC, sXY = itemS
tC, tXY = itemT
# 大タイルに至るまでのそれぞれのコストと大タイル間の移動コストを合わせる．
tmp = sC + tC + diaCost(sXY, tXY)
# 最小コストを更新する．
ans = min(ans, tmp)
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回の成績(ooooxo-)
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
- 解説で示したE問題の提出
- 解説で示したF問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 初めての🟦パフォ！初めての🟨ディフAC!