AtCoder Beginners Contest 354 (ABC354) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Exponential Plant
問題
植物があります。 $0$ 日目の時点で高さは $0 \mathrm{cm}$です。
この植物は $i$ ( $0 \le i$ ) 日目の夜に ${2^i} \mathrm{cm}$ だけ伸びます。
毎日お昼に植物の高さを測定します。
この植物が $H \mathrm{cm}$ を超えたのを観測するのは何日目ですか？
考察
$i$ 日目のお昼で植物の高さが $H$ 以下のとき、植物の高さを $2^i$ だけ増やして $i+1$ 日目のお昼の観測に移ります。
似たような処理の繰り返しなので、for文やwhile文をつかって解くことができます。
Pythonでは、累乗は以下のように書けます。
"""累乗の書き方"""
# どっちをつかってもok！
x = 3**4 # 81(=3^4)
y = pow(5, 3) # 125(=5^3)
コード
H = int(input())
i = 0
plant_height = 0
while plant_height <= H:
plant_height += 2**i
i += 1
print(i)
別解
for文をつかった解法
H = int(input())
plant_height = 0
for i in range(100):
if plant_height > H:
print(i)
break
plant_height += 2**i
累乗の書き方(pow関数)
$3^4(=81)$ を表したいとき、 x = 3**4 のように書きます。
もう1つ有名な書き方があって、 x = pow(3, 4) と書いても $3^4$ を表せます。
"""pow関数のつかい方"""
x = pow(3, 4) # 81(3^4)
y = pow(5, 4) # 123(=5^3)
# 第3引数に値を入れられる。第3引数で割ったあまりを求められる
a = pow(3, 4, 7) # 4(81÷7のあまり)
b = pow(7, 3, 4) # 3(343÷4のあまり)
第3引数を設定したとき、内部では繰り上がり二乗法という手法で累乗の計算をしています。
これによる高速化をつかう問題も多く、気になる方は調べてみてもいいかもしれません。
B - AtCoder Janken 2
問題
$N$ 人のAtCoderユーザーがいます。 $i$ 人目のユーザーは名前が $S_i$ でレート $C_i$ です。
以下のルールで勝負をしたとき、勝者は誰になりますか？
- それぞれのユーザーに、ユーザー名の辞書順に $0,1,…,N−1$ の番号を割り当てる
- $N$ 人のレートの総和を $T$ とする。番号 $T \mod N$ を割り当てられたユーザーが勝者となる
考察
まず、1つ目の条件「ユーザー名の辞書順に $0,1,…,N−1$ の番号を割り当てる」を処理します。
辞書順に並べるということは、Python的に言うと「ソートする」ということです。
つまり、こういう感じ。
# 入力の受け取り
N = int(input())
user_array = []
for _ in range(N):
s, c = input().split()
user_array.append((s, int(c)))
user_array.sort() # 辞書順にユーザーを並べる
そして2つ目の条件「 $N$ 人のレートの総和を $T$ とする。番号 $T \mod N$ を割り当てられたユーザーが勝者となる」です。
条件の文自体は短いですが、見た目以上に処理することは多いです。条件の通りに実装してみると、こんな感じになります。
T = 0 # 全ユーザーのレーティングの総和
for user in user_array:
_name, rating = user
T += rating
winner_index = T % N
winner = user_array[winner_index]
winner_name = winner[0]
print(winner_name)
これらをまとめると、以下のコードになります。
コード
N = int(input())
user_array = []
for _ in range(N):
s, c = input().split()
user_array.append((s, int(c)))
user_array.sort()
T = 0
for user in user_array:
_name, rating = user
T += rating
winner_index = T % N
winner = user_array[winner_index]
winner_name = winner[0]
print(winner_name)
別解
sum関数+内包表記 の書き方
レーティングの総和 $T$ を求めたコードを再掲します。
T = 0
for user in user_array:
_name, rating = user
T += rating
これは、sum関数と内包表記を合わせて以下のように書けます。
T = sum(user[1] for user in user_array)
簡単に書けるので、余裕のある方は積極的につかってみてもいいかもしれません。
C - AtCoder Magics
問題
$N$ 枚のカードがあります。 $i$ 枚目のカードはコスト $C_i$ で強さ $A_i$ です。
$A_x \lt A_y, \enspace C_x \gt C_y$ を満たす $(x, y)$ の組があれば、カード $x$ を捨てます。
この操作をできるまで続けます。残ったカードはどれですか？
考察1 (問題文通りに解いてみる)
すべてのカードの組をチェックしてみます。コードはこんな感じでしょうか。
N = int(input())
card_array = []
for i in range(1, N + 1):
a, c = map(int, input().split())
card_array.append((c, a, i))
discard_set = set() # 捨てる予定のカード番号を格納するset
for i in range(N - 1):
for j in range(i + 1, N):
ai, ci, ni = card_array[i]
aj, cj, nj = card_array[j]
if ai < aj and ci > cj:
discard_set.add(i)
# (出力は省略)
2重ループの部分が計算量的にかなり重く、全体として $O(N^2)$ の処理です。
制約を見てみると、 $2 \le N \le 2 \times 10^5$ なので、これは実行時間制限に間に合いません。
素直にカードの組み合わせを全パターン試すのはダメだと分かりました。
考察2 (カードを事前に並べる)
条件がいくつかあって、その中に $C_i \lt C_j$ のような不等式が含まれているような問題はAtCoderでよく出題されます。
このような問題では、事前に $C$ の順番にオブジェクト(今回はカード)を並べて置くと、計算量を改善できることがあります。
(もっと気になる人は、「平面捜査」で調べてみるといいかもです！)
ということで、カードを捨てるかどうかチェックしていく前に、事前にコストの順にカードを並び替えておきます。
コストの小さいほうから順にカードを見ていきます。
捨てなかった直前のカード $i$ と現在見ているカード $j$ を比べます。
コストの順に並べてあるので、 $C_i \lt C_j$ が成り立ちます。
したがって、 $A_i \gt A_j$ であれば、カード $j$ は破棄することになります。
この処理はカードを1枚ずつ見ているだけで計算量は $O(N)$ です。
事前にコストの順にソートするところで $O(N \log N)$ だけかかっていて、問題全体としては計算量 $O(N \log N)$ でこの問題を解けます。
コード
N = int(input())
card_array = []
for i in range(1, N + 1):
a, c = map(int, input().split())
card_array.append((c, a, i))
card_array.sort()
ans_lst = []
max_power = -1
for card in card_array:
cost, power, card_number = card
if max_power < power:
max_power = power
ans_lst.append(card_number)
ans_lst.sort()
print(len(ans_lst))
print(*ans_lst)
D - AtCoder Wallpaper
問題
問題の図形について、左下の座標が $(A, B)$ 右上の座標が $(C, D)$ の長方形に含まれる黒色の部分の面積はいくつですか？
考察1 (規則性を見つける)
問題の図形は下の通りです。
図をじっくり見てみると、 $0 \le x \le 1$ の部分と $4 \le x \le 5$ の部分は、まったく同じ図形なことがわかります。
ほかにも同じ構造になっているところはたくさんあります。
一般化すると、 $a \le x \le a + 1$ の部分と $a + 4 \le x \le a + 5$ の部分はまったく同じになります。
考察2 ([0, 1] の範囲だけを考える)
(問題では面積を $2$ 倍した数値を出力すると書かれていますが、この解説では面積を $2$ 倍された数値のことを単に「面積」と呼ぶことにします)
先ほどの規則性から、どの $a \le x \le a+1$ を選んでも $0 \le x \le 1,\enspace 1 \le x \le 2,\enspace 2 \le x \le 3,\enspace 3 \le x \le 4 $ の $4$ つのどれかと同じ図形になっていることが分かります。
ここではいったん $0 \le x \le 1$ の範囲だけ考えてみます。
たとえば、$0 \le x \le 1, \enspace 0 \le y \le 6$ の赤枠の範囲を考えてみます。
これなら、答えは $9$ になります。
$0 \le y \le 2$ の範囲にある台形1つで面積は $3$ で、それが計 $3$ つある形です。
$0 \le y \le 6$ だったのを $-1 \le y \le 5$ にしてみるとどうでしょうか？
これも答えは $9$ です。
$y$ の長さが偶数の時の処理は上記の通りです。
次は $y$ の長さが奇数のときを考えます。
図も多くなるので省略しますが、 $0 \le y \le 5$ や $-1 \le y \le 4$ のときにどうなるかを考えてみるといいでしょう。
これをまとめると、以下のような関数になります。
# 0<=x<=1, bottom<=y<=top 黒色の面積
def black_area0(bottom, top):
length = top - bottom
if length % 2 == 0:
return length // 2 * 3
else:
result = (length - 1) // 2 * 3
if bottom % 2 == 0:
result += 2
else:
result += 1
return result
考察3 (残り3パターンも考える)
(図形を再掲)
まず $1 \le x \le 2$ について考えます。
$1 \le x \le 2, \enspace a \le y \le b$ の範囲の黒色の面積と、 $0 \le x \le 1, \enspace a - 1 \le y \le b - 1$ の範囲の黒色の面積は、同じになります。
この性質を使うと、以下のように関数をつくれます。
# 1<=x<=2, bottom<=y<=top 黒色の面積
def black_area1(bottom, top):
return black_area0(bottom - 1, top - 1)
$2 \le x \le 3$ の範囲については、 $0 \le x \le 1$ と比べて黒白が逆転しているだけです。
$3 \le x \le 4$ と $1 \le x \le 2$ の関係も同じです。
次のように関数をつくれます。
# 2<=x<=3, bottom<=y<=top 黒色の面積
def black_area2(bottom, top):
return (top - bottom) * 2 - black_area0(bottom, top)
# 3<=x<=4, bottom<=y<=top 黒色の面積
def black_area3(bottom, top):
return (top - bottom) * 2 - black_area1(bottom, top)
考察4 (各関数を使う回数)
ここまでで、 $0 \le x \le 1,\enspace 1 \le x \le 2,\enspace 2 \le x \le 3,\enspace 3 \le x \le 4 $ それぞれについて、 $y$ の範囲が分かれば $O(1)$ で面積を求められるようになっています。
あとは、それぞれの図形が何度出現するのかが分かればいいです。
言い換えると、以下のような問題を解くことになります。
- $\cdots , -4 \le x \le -3, \enspace 0 \le x \le 1, \enspace 4 \le x \le 5, \cdots$ の範囲に1つずつ旗が置いてあります
- $A \le x \le C$ の範囲の中に旗はいくつありますか？
( $1 \le x \le 2,\enspace 2 \le x \le 3,\enspace 3 \le x \le 4 $ についても同様の問題を解きます)
解説は省きますが、$\cdots , -4 \le x \le -3, \enspace 0 \le x \le 1, \enspace 4 \le x \le 5, \cdots$ の範囲の小問題については、 $\left\lfloor\frac{C - 1}{4}\right\rfloor - \left\lceil\frac{A}{4}\right\rceil + 1$ が答えになります。
(類題: ABC334-B Christmas Trees)
他3つの範囲については、 $x$ 軸方向にシフトして考えることで同様に解くことができます。
コード
# 0<=x<=1, bottom<=y<=top 黒色の面積
def black_area0(bottom, top):
length = top - bottom
if length % 2 == 0:
return length // 2 * 3
else:
result = (length - 1) // 2 * 3
if bottom % 2 == 0:
result += 2
else:
result += 1
return result
def black_area1(bottom, top):
return black_area0(bottom - 1, top - 1)
def black_area2(bottom, top):
return (top - bottom) * 2 - black_area0(bottom, top)
def black_area3(bottom, top):
return (top - bottom) * 2 - black_area1(bottom, top)
A, B, C, D = map(int, input().split())
ans = 0
for m in range(4):
left_idx = (A - m + 3) // 4
right_idx = (C - 1 - m) // 4
cnt = right_idx - left_idx + 1
match m:
case 0: ans += black_area0(B, D) * cnt
case 1: ans += black_area1(B, D) * cnt
case 2: ans += black_area2(B, D) * cnt
case 3: ans += black_area3(B, D) * cnt
print(ans)
E - Remove Pairs
問題
$N$ 枚のカードがあります。 $i$ 枚目のカードは表に $A_i$ が、裏に $B_i$ が書かれています。
2人ゲームを行います。先手から交互に以下の操作を繰り返します。
- 場にあるカードの中から表面同士に同じ数が書かれている、または裏面同士に同じ数が書かれている $2$ 枚のカードの組を選び、そのカードを場から取り除く。このようなカードの組が存在しない場合、操作を行えない
操作を行えなくなったほうの負けです。両者が最適に行動するとき、どちらが勝ちますか？
考察
メモ化再帰で解きます。
場に残っているカードのパターン数は、全部で $2^N$ 通りあります。
今回の問題では $N \le 18$ なので、パターン数自体はそこまで多くありません。
カードを $2$ 枚だけ取り除いてできる盤面の中に後手必勝盤面が存在するとき、その盤面は先手必勝盤面です。
逆にこれ以外の盤面はすべて後手必勝盤面です。
これを利用してメモ化再帰を実装することでACできます。
盤面のパターン数が $O(2^N)$ 個あり、1つの盤面からの遷移は $O(N^2)$ なので、全体として $O(2^N \times N^2)$ で解くことができます。
コード
from functools import cache
from itertools import combinations
BitIndexDict = {1 << i: i for i in range(18)}
# 立っている最下位ビットのみを返す
def tail_bit(x):
return x & -x
# 立っているビットのインデックスiterator
def bits_iter(x):
v = x
while v:
tail = tail_bit(v)
yield BitIndexDict(tail)
v ^= tail
@cache
def first_win(state):
result = False
card_idxs = list(bits_iter(state))
for ci, cj in combinations(card_idxs, 2):
after_state = state ^ (1 << ci) ^ (1 << cj)
if can_remove(ci, cj) and not first_win(after_state):
result = True
break
return result
# ci, cjのカードのペアを選んで取り出せるか
def can_remove(ci, cj):
return any(vi == vj for vi, vj in zip(cards[ci], cards[cj]))
N = int(input())
cards = [tuple(map(int, input().split())) for _ in range(N)]
print("Takahashi" if first_win((1 << N) - 1) else "Aoki")
別解
functools.cache について
メモ化再帰でつかわれるデコレータとして、 functools.cache と functools.lru_cache の $2$ つがあります。
cache は lru_cache のキャッシュ制限を指定しなかったものと同じです。
競プロでキャッシュ制限を使うことはないと思うので、どちらを使用してもよさそうです。
以下は、functools.cache の定義が書かれたコードです。そのまま lru_cache を呼び出しています。
################################################################################
### cache -- simplified access to the infinity cache
################################################################################
def cache(user_function, /):
'Simple lightweight unbounded cache. Sometimes called "memoize".'
return lru_cache(maxsize=None)(user_function)