【ABC360】緑コーダーの競プロ参加記録 #26
今回はAtCoder Beginner Contest 360。使用言語はPythonです。
A問題 - A Healthy Breakfast
コンテスト中の提出
https://atcoder.jp/contests/abc360/submissions/55046332
長さ$${3}$$の文字列$${S}$$が与えられる。
$${S}$$に含まれる 'R' が 'M' より左にあるか判定してね。
index メソッドを利用することで、文字列に含まれる特定の文字の位置を求められます。
’R' のインデックスが 'M' のインデックスより小さければ答えは 'Yes' です。
""" AC コード """
S = input()
if S.index('R') < S.index('M'):
print('Yes')
else:
print('No')B問題 - Vertical Reading
コンテスト中の提出
https://atcoder.jp/contests/abc360/submissions/55056515
文字列$${S,T}$$が与えられる。
操作: $${S}$$を先頭から$${w}$$文字ごとに区切り、$${c}$$文字以上のものだけに対して、それらの$${c}$$文字目を順に並べる。
操作の結果$${T}$$と一致する$${(c, w)}$$の組が存在するか判定してね。
問題文がとてもややこしい。
操作の内容はさておき、「条件を満たす$${(c, w)}$$の組が存在するか」を問われています。
文字列$${S}$$の長さを$${N}$$として、$${1 \le c \le w < N}$$の範囲で$${(c, w)}$$の組を全探索します。
$${N \le 100}$$なので、$${O(N^2)}$$でも問題ありません。
""" 全体のイメージ """
S, T = input().split()
N = len(S)
for c in range(1, N):
for w in range(c, N):
if solve(c, w):
print('Yes')
exit()
print('No')肝心の操作が難しいです。
先頭から$${w}$$文字ずつ区切ることを考えるとき、最後のかたまりが$${w}$$文字に満たないケースに注意が必要です。
$${w}$$文字に満たない場合でも、$${c}$$文字以上であれば$${c}$$文字目を取り出さなければなりません。
Pythonのスライスを利用すると比較的シンプルな実装になります。
スライスの終点$${i+w}$$は文字列$${S}$$の長さを超えていてもエラーになりません。
""" (c, w) が条件を満たすか判定 """
def solve(c, w):
i = 0
res = ""
while i < N:
Sw = S[i:i + w]
if len(Sw) >= c:
res += Sw[c - 1]
i += w
return res == TB問題にしてはかなり難しかったように思います。
C問題 - Move It
コンテスト中の提出
https://atcoder.jp/contests/abc360/submissions/55060183
$${N}$$個の箱と、$${N}$$個の荷物がある。
$${i}$$番目の荷物は箱$${A_i}$$に入っており、重さ$${W_i}$$。
操作: 荷物を1つ選んで別の箱に移動させる。重さ分のコストがかかる。
全ての箱に1つずつ荷物を入れるための最小コストを出力してね。
まず、箱ごとに入っている荷物を調べます。
""" 入力を受け取る """
N = int(input())
A = list(map(int, input().split()))
W = list(map(int, input().split()))
""" B[i]: 箱 i に入っている荷物の重さの一覧 """
B = [[] for _ in range(N)]
for i in range(N):
B[A[i] - 1].append(W[i])それぞれの箱について、軽い荷物から順に移動させることでコストを抑えることができます。
よって、それぞれの箱に入っている荷物のうち、最も重いもの以外の荷物をすべて取り出せばよいです。
""" 箱 i に入っている荷物のうち、最も重いものだけ残す """
ans = 0
for i in range(N):
if B[i]:
ans += sum(B[i]) - max(B[i])
print(ans)この部分の解法は、ソートしたり優先度付きキューを使ったり、いくつか方法があるのでお好みで。
D問題 - Ghost Ants
コンテスト中の提出
https://atcoder.jp/contests/abc360/submissions/55068938
正整数$${N, T}$$と文字列$${S}$$が与えられる。
$${i}$$番目の蟻ははじめ座標$${X_i}$$にいる。
$${S}$$の$${i}$$文字目が '0' なら蟻$${i}$$は左向き、 '1' なら蟻$${i}$$は右向きに、単位時間あたり速さ$${1}$$で進む。
時間$${T}$$の間に、すれ違う蟻$${(i, j)}$$の組の個数を出力してね。
ABC355 - D - Intersecting Intervals と同じ方法で解きます。
区間$${[l_i, r_i]}$$と$${[l_j, r_j]}$$が共通部分をもつとき、共通部分に含まれる数$${a}$$の範囲は以下のようになります。
$${\max(l_i, l_j) \le a \le \min(r_i, r_j)}$$
（参考）ABC343 - E - 7x7x7
よって、$${\max(l_i, l_j) \le \min(r_i, r_j)}$$となる区間の個数を数えることができればよいです。
すべての蟻の進む速さは同じなので、同じ向きに進んでいる蟻同士ですれ違うことはありません。
よって、左向きと右向きの蟻を分けて考えます。
左向きの蟻は、座標$${x}$$からスタートし$${x - T}$$まで移動する。
右向きの蟻は、座標$${x}$$からスタートし$${x + T}$$まで移動する。
ある左向きの蟻$${i}$$について$${(l_i, r_i) = (X_i - T, X_i)}$$、右向きの蟻$${j}$$について$${(l_j, r_j) = (X_j, X_j + T)}$$とします。
そうすると、区間$${[l_i, r_i]}$$と$${[l_j, r_j]}$$が共通部分をもつとき、蟻$${(i, j)}$$はすれ違います。
よって、$${\max(l_i, l_j) \le \min(r_i, r_j)}$$となる区間の個数を数えることができればよいです。
これは、ある$${i}$$における、$${l_j \le r_i}$$である区間$${j}$$の個数$${x}$$、$${r_j < l_i}$$である区間$${j}$$の個数$${y}$$に対して、$${x - y}$$となります。
$${x,y}$$は独立して数えてよいです。
$${l_j, r_j}$$を別々のリストに分けてソートしておくと、$${x,y}$$を二分探索で求めることができます。
from bisect import bisect_right
""" 入力を受け取る """
N, T = map(int, input().split())
S = input()
X = list(map(int, input().split()))
""" 右向きに進む蟻の区間 [lj, rj] を調べる """
Lj, Rj = [], []
Ri = []
for i in range(N):
if S[i] == '1':
Lj.append(X[i])
Rj.append(X[i] + T)
else:
Ri.append(X[i])
""" 二分探索で共通部分をもつ区間の個数を求める """
Lj.sort()
Rj.sort()
ans = 0
for ri in Ri:
li = ri - T
x = bisect_right(Lj, ri)
y = bisect_right(Rj, li - 1)
ans += x - y
print(ans)整数において$${r_j < l_i}$$と$${r_j \le l_i - 1}$$は同じなので、bisect_right に$${l_i - 1}$$を渡しています。
$${l_i - 1}$$とせず、bisect_left を使ってもよいです。
y = bisect_left(Rj, li)E問題 - Random Swaps of Balls
コンテスト中の提出
https://atcoder.jp/contests/abc360/submissions/55089674
$${N -1}$$個の白ボールと$${1}$$個の黒ボールが横一列に並んでいる。
はじめ黒ボールは左から1番目にある。
操作: $${1 \le a, b \le N}$$を満たす整数$${a, b}$$をランダムに選んで、左から$${a}$$番目のボールと$${b}$$番目のボールを入れ替える。
$${K}$$回の操作のあと、黒ボールの位置の期待値を出力してね。$${\pmod{998244353}}$$
$${a, b}$$の選ばれ方のうち、黒ボールの「位置が変わらないケース」と「位置が変わるケース」についてそれぞれ考えます。
ある時点での、黒ボールの現在位置を$${x}$$とします。
黒ボールの位置が変わらないケース
位置が変わらない$${a,b}$$の選ばれ方は、以下の2パターンあります。
$${a, b}$$のどちらも$${x}$$でない。その確率は$${\displaystyle\Big(\frac{N -1}{N}\Big)^2}$$。
$${a, b}$$のどちらも$${x}$$である。その確率は$${\displaystyle\Big(\frac{1}{N}\Big)^2}$$。
よって、黒ボールの位置が変わらない確率は$${{\displaystyle\Big(\frac{N -1}{N}\Big)^2} + {\displaystyle\Big(\frac{1}{N}\Big)^2}}$$です。
以下、この確率を$${P}$$とします。
$$
P = \Big(\frac{N -1}{N}\Big)^2 + \Big(\frac{1}{N}\Big)^2
$$
黒ボールの位置が変わるケース
位置が変わる$${a,b}$$の選ばれ方は、位置が変わらない選ばれ方の余事象になります。
つまり、黒ボールの位置が変わる確率は$${1 - P}$$です。
移動先は現在位置を除いた$${N-1}$$通りあります。
よって、黒ボールが現在位置$${x}$$から位置$${y}$$に移動する確率を$${Q}$$とすると、以下のようになります。
$$
Q = \frac{1 - P}{N-1}
$$
問題を解く
黒ボールの現在位置$${x}$$に対して操作のあと、
黒ボールが位置$${x}$$にある確率は$${P}$$
黒ボールが位置$${y (\not=x)}$$にある確率は$${Q}$$
となり、操作後に黒ボールのある位置の期待値$${E}$$は、以下のように計算できます。
$$
E = Px + \displaystyle\sum_{y = 1}^N Qy - Qx
$$
確率$${Q}$$は$${y}$$によらず一定なので、$${S =\displaystyle\sum_{y = 1}^N y= \frac{N(N+1)}{2}}$$として次が成り立ちます。
$$
E = Px + QS -Qx \\
\hArr E = (P - Q)x + QS
$$
そして実は、$${i}$$回目の操作における黒ボールの現在位置$${x_i}$$は、$${i-1}$$回目の操作後における黒ボールの位置の期待値$${E_{i-1}}$$としてよいです。
$$
E_i = (P - Q)E_{i-1} + QS
$$
黒ボールの初期位置は左から1番目なので$${E_0 = 1}$$です。
""" 入力を受け取る """
N, K = map(int, input().split())
""" N - 1 で割る処理があるので気を付ける """
if N == 1:
print(1)
exit()
""" 確率 P, Q と、S = Σ[y=1..N]y の前計算 """
mod = 998244353
P = (pow(N - 1, 2, mod) * pow(N, -2, mod) + pow(N, -2, mod)) % mod
Q = (1 - P) % mod * pow(N - 1, -1, mod) % mod
S = N * (N + 1) // 2 % mod
""" 黒ボールの現在位置 E を、操作後の位置の期待値で更新する """
E = 1
for i in range(K):
E = ((P - Q) % mod * E % mod) + (Q * S % mod)
E %= mod
print(E)$${\mathrm{mod}}$$の世界なので、分数の計算をするために逆元を求める必要があります。
Python なら pow 関数の第2引数を負の値にするだけで求まります。
あとがき
今回は ABCDE 5完 2ペナ 91分で 1125位、1145 perfでした。
久しぶりにE問題を解けてよかった。
ではまた～。
【更新履歴】
2024/07/01 (20時頃)：記事投稿。
2024/07/04 (21時頃)：コンテスト成績証とDifficultyの画像を追加。