ABC249のA,B,C,D,E,F問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル:余計なことを考えずに済む
- 実装が楽:ミスやバグが減ってうれしい
- 時間がかからない:パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ!
Twitter: u2dayo
マシュマロ: https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー(質問や記事の感想・リクエストなどどうぞ!) : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます!
目次
ABC249 まとめ
A問題『Jogging』
B問題『Perfect String』
C問題『Just K』
D問題『Index Trio』
E問題『RLE』
F問題『Ignore Operations』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC249 まとめ
全提出人数: 8309人
パフォーマンス
パフォ | AC | 点数 | 時間 | 順位(Rated内) |
---|---|---|---|---|
200 | -B------ | 200 | 11分 | 5776(5534)位 |
400 | AB------ | 300 | 40分 | 4624(4383)位 |
600 | AB------ | 300 | 11分 | 3779(3539)位 |
800 | ABC----- | 600 | 54分 | 2886(2658)位 |
1000 | ABC----- | 600 | 14分 | 2143(1918)位 |
1200 | ABCD---- | 1000 | 73分 | 1537(1316)位 |
1400 | ABCD---- | 1000 | 46分 | 1079(861)位 |
1600 | ABCD---- | 1000 | 27分 | 742(531)位 |
1800 | ABCDE--- | 1500 | 91分 | 490(302)位 |
2000 | ABCDE--- | 1500 | 63分 | 328(162)位 |
2200 | ABCDEF-- | 2000 | 102分 | 225(84)位 |
2400 | ABCDEF-- | 2000 | 82分 | 140(39)位 |
色別の正解率
色 | 人数 | A | B | C | D | E | F | G | Ex |
---|---|---|---|---|---|---|---|---|---|
灰 | 2770 | 71.5 % | 85.3 % | 17.6 % | 3.8 % | 0.1 % | 0.1 % | 0.0 % | 0.0 % |
茶 | 1400 | 93.9 % | 98.2 % | 70.6 % | 20.1 % | 0.5 % | 0.8 % | 0.0 % | 0.0 % |
緑 | 996 | 95.8 % | 98.0 % | 91.6 % | 57.6 % | 0.6 % | 3.0 % | 0.1 % | 0.0 % |
水 | 650 | 97.1 % | 98.0 % | 96.2 % | 88.9 % | 9.5 % | 20.8 % | 0.0 % | 0.0 % |
青 | 367 | 93.7 % | 95.4 % | 94.3 % | 93.2 % | 36.0 % | 52.0 % | 0.3 % | 0.0 % |
黄 | 183 | 92.9 % | 93.4 % | 92.3 % | 91.8 % | 63.9 % | 76.5 % | 6.0 % | 0.0 % |
橙 | 36 | 86.1 % | 86.1 % | 83.3 % | 83.3 % | 77.8 % | 77.8 % | 47.2 % | 2.8 % |
赤 | 24 | 95.8 % | 100.0 % | 100.0 % | 100.0 % | 95.8 % | 95.8 % | 66.7 % | 12.5 % |
※表示レート、灰に初参加者は含めず
A問題『Jogging』
問題ページ:A - Jogging
灰コーダー正解率:71.5 %
茶コーダー正解率:93.9 %
緑コーダー正解率:95.8 %
おそらく、歴代のABC-A問題で最も難しい問題です。難しいB問題並の難易度でしょう。
入力
$A,B,C$ : 高橋君は「$A$ 秒間歩き、$C$ 秒間休む」ことを繰り返す。歩く速度は秒速 $B$ メートル。
$D,E,F$ : 青木君は「$D$ 秒間歩き、$F$ 秒間休む」ことを繰り返す。歩く速度は秒速 $E$ メートル。
$X$ : $X$ 秒後に高橋君と青木君のどちらが長い距離を進んだかを判定する。
- $1\le{X}\le{100}$
- 入力は全て整数
考察
$X$ が小さいので、高橋君と青木君の動きを $1$ 秒ずつ、$X$ 秒後までシミュレートすれば解けます。
$A+C$ 秒が $1$ 周期であることに注目すると、算数で $O(1)$ で解くこともできます。
コード
シミュレート
t % (p + r) < p
という式を使えば、t
から t+1
秒の間歩いているか休んでいるかを判定できますが、あえて使わずに単純にしています。 わかる人は使うとコードが短くなります。
def solve():
def calc(p, q, r):
"""p秒間秒速qメートルで歩き、r秒間休むことを繰り返す人がx秒で進む距離を計算"""
t = 0 # 経過時間
dist = 0 # 進んだ距離
while True:
# p秒間歩く
for _ in range(p):
t += 1
dist += q
if t == x: # x秒経過したら終了
return dist
# r秒間休む
for _ in range(r):
t += 1
if t == x:
return dist
a, b, c, d, e, f, x = map(int, input().split())
tak = calc(a, b, c)
aok = calc(d, e, f)
if tak == aok:
return "Draw"
if tak > aok:
return "Takahashi"
else: # tak < aok
return "Aoki"
print(solve())
算数
calc
関数以外は上のコードと同じなので省略します。
def calc(p, q, r):
"""p秒間秒速qメートルで歩き、r秒間休むことを繰り返す人がx秒で進む距離を計算"""
return p * q * (x // (p + r)) + q * min(p, x % (p + r))
B問題『Perfect String』
問題ページ:B - Perfect String
灰コーダー正解率:85.3 %
茶コーダー正解率:98.2 %
緑コーダー正解率:98.0 %
入力
$S$ : 長さ $1$ 以上 $100$ 以下で、英大文字と英小文字からなる文字列
考察
$3$ つの条件を別々に判定して、すべて満たすかを調べればいいです。
以下の方法が簡単ですが、思いつかなくてもforループで $1$ 文字ずつ調べればいいです。
英大文字が文字列の中に現れる
制約より、$S$ に英大文字、英小文字以外の文字は出現しません。$S$ に英大文字がないとしたら、$S$ はすべて英小文字です。
すべて英小文字の文字列とは atcoder
, fffff
, x
などで、英大文字はありません。反対に、この問題においてすべて英小文字でない文字列とはAtCoder
, A
, Perfect
などで、英大文字が含まれます。
文字列 S
がすべて英小文字からなるかを判定するのには、S.islower()
が使えます。英大文字が含まれるかどうかは、 not S.islower()
で判定できます。
英小文字が文字列の中に現れる
英大文字の場合と同様に、not S.isupper()
で判定できます。
すべての文字が相違なる
すべての文字が異なるならば、『文字列 S
に現れる文字の種類数』と『文字列S
の長さ』は等しいです。
文字列 S
に現れる文字の種類数は、len(set(S))
で求められます。(set
型に変換して重複を省いて要素数を調べています)
len(S) == len(set(S))
で判定できます。
コード
def judge():
S = input()
b1 = not S.islower()
b2 = not S.isupper()
b3 = len(S) == len(set(S))
return b1 and b2 and b3
print("Yes" if judge() else "No")
C問題『Just K』
問題ページ:C - Just K
灰コーダー正解率:17.6 %
茶コーダー正解率:70.6 %
緑コーダー正解率:91.6 %
入力
$N$ : 文字列の個数
$S_i$ : $i$ 番目の文字列(英小文字からなり、同じ文字は $2$ 個以上含まれない)
$K$ : 「選んだ文字列の中でちょうど $K$ 個の文字列に登場する英小文字」の種類数の最大値を求める
- $1\le{N}\le{15}$
- $S_i$ の長さは $26$ 以下(同じ文字が $2$ 個以上含まれないため)
考察
**ありえる文字列の選び方を全て試して、最大の値を求めればいいです。**文字列の選び方は $2^N$ 通りなので、最大でも $2^{15}=32768$ 通りだけしかありません。
ある $1$ つの選び方に対する種類数の答えは、そのまま選んだ文字列に 各英小文字が出てくる回数をカウントして、ちょうど $K$ 回出てくるものを求めればいいです。
ありえる選び方をすべて試すのには、いわゆるbit全探索というアルゴリズムを使います。名前は強そうですが、ただの全探索です。知らない方は、下の記事を読んでみてください。
こわくないbit全探索1 入門編: bit全探索ってなに?【競プロ解説】
コード
from collections import Counter
from itertools import product
def solve():
def calc(pro):
"""選び方 pro に対する答えを求める"""
C = Counter() # 空のカウンターを用意する
for i in range(N):
if pro[i]:
# S[i]を選ぶ場合、S[i]に含まれる文字のカウントにそれぞれ1足す C.update(S[i])なら1行
for ch in S[i]:
C[ch] += 1
score = 0
for ch, cnt in C.items():
if cnt == K: # K回"ちょうど"の種類数です
score += 1
return score
N, K = map(int, input().split())
S = [input() for _ in range(N)]
ans = 0
for pro in product((True, False), repeat=N):
ans = max(ans, calc(pro))
return ans
print(solve())
D問題『Index Trio』
問題ページ:D - Index Trio
灰コーダー正解率:3.8 %
茶コーダー正解率:20.1 %
緑コーダー正解率:57.6 %
入力
$N$ : 整数列の長さ
$A_i$ : 数列の $i$ 番目の要素は $A_i$
- $1\le{A_i}\le2\times{10^5}$
考察
全探索解法
$(i,j,k)$ の組として考えられる組み合わせは $N^3$ 組あるので、$3$ つの数字の選び方を全探索はできません。高速に数えられないか考えてみます。
$\dfrac{A_i}{A_j}=A_k$
右辺の $A_k$ は正の整数ですから、左辺の $\dfrac{A_i}{A_j}$ は正の整数でなければいけません。
$A_i, A_j$ も正の整数ですから、$\dfrac{A_i}{A_j}$ が正の整数になるには、分子の $A_i$ が分母の $A_j$ で割り切れる必要があります。つまり、$A_i$ は $A_j$ の倍数である必要があります。
$A$ の要素の値が最大で $2\times10^5$ までと比較的小さいことを利用して、左辺の分母・分子の値を $1$ から $2\times{10^5}$ まで全探索します。
ただし、普通に二重ループを書くと $4\times{10^{10}}$ 組調べることになります。そこで、分母を先に決めてから、分子はその倍数だけを調べることで、左辺が整数にならない組を調べないようにします。
一見調べる組み合わせ数が大きく減りそうには思えませんが、**実はそのような組は、分母・分子の最大値を $K$ とすると、 $O(K\log{K})$ 組であることが知られています。**具体的には、 $K=2\times{10^5}$ とした場合、$2472113$ 組しかありません。(証明は公式解説にあります)
左辺の分母・分子が決まれば右辺の値も決まりますから、あらかじめ $A$ に 整数 $x$ が現れる回数を数えておけば、各値が $A$ に出てくる回数を掛けることで、その値の組み合わせを取る選び方が何組あるかわかります。
計算量は $K=2\times{10^5}$ として、 $O(N\log{K})$ です。
約数列挙解法
左辺の分子 $A_i$ を決めたとき、分母としてありえるのは $A_i$ を割り切る値だけです。$A_i$ を割り切る値を高速に全列挙すればいいです。**ある正の整数 $x$ を割り切る正の整数 $y$ のことを、$x$ の約数と呼びます。**約数列挙の計算量は、整数 $L$ に対して$O(\sqrt{L})$ ですから、十分高速です。
計算量は $K=2\times{10^5}$ として、 $O(N\sqrt{K})$ です。全探索解法と同様のアルゴリズムで約数を前計算しておけば、$O(N\log{K})$ になります。
コード
全探索
from collections import Counter
def main():
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = 0
A_max = 2 * 10 ** 5
for den in range(1, A_max + 1):
for num in range(den, A_max + 1, den):
k = num // den
ans += C[den] * C[num] * C[k]
print(ans)
if __name__ == '__main__':
main()
約数列挙
PyPyで提出してください。
from collections import Counter
def enum_divisors(n):
"""約数列挙 O(√N)"""
divs_smaller = []
divs_larger = []
i = 1
while i * i <= n:
if n % i == 0:
divs_smaller.append(i)
divs_larger.append(n // i)
i += 1
if divs_smaller[-1] == divs_larger[-1]:
divs_smaller.pop()
divisors = divs_smaller + divs_larger[::-1]
return divisors
def main():
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = 0
for num, cnt in C.items():
divs = enum_divisors(num)
for den in divs:
k = num // den
ans += cnt * C[den] * C[k]
print(ans)
if __name__ == '__main__':
main()
E問題『RLE』
問題ページ:E - RLE
灰コーダー正解率:0.1 %
茶コーダー正解率:0.5 %
緑コーダー正解率:0.6 %
入力
(省略)
- $N\le{3000}$
- 素数 $P$ で割った余りを求める
考察
動的計画法で解けそうです。まずは、単純なDPを考えてみます。
状態
$\mathrm{dp}[i][j]$ : $T$ としては $i$ 文字で、 $S$ としては $j$ 文字である文字列の個数
初期値
$\mathrm{dp}[0][0]=1$
遷移
$T$ に英小文字 $char$、個数 $num$ からなる文字列 $Y$ を追加します。$num$ の $10$ 進表記での桁数を $d$ とすると
- $T$ としては $d+1$ 文字増える
- $S$ としては $num$ 文字増える
ことになります。したがって、遷移は $char$ として使える英小文字の種類数を $c$ として
- $\mathrm{dp}[i+d+1][j+num]+=c\times{\mathrm{dp}[i][j]}$
です。
$c$ は $i=0$ のとき $26$ 、それ以外のとき $25$ です。(直前に使った英小文字と同じ文字は使えないため)
遷移を高速化する
このDPは状態数が $O(N^2)$、遷移が $O(N)$ ですから、計算量が $O(N^3)$ となり間に合いません。
**ある $i,j$ から遷移するとき、桁数 $i+d+1$ が同じで、$j+num$ が連続する区間に同じ値を足していることに着目すると、遷移を高速化できそうです。**具体的には、累積和(いもす法)を使えば、$O(1)$ で区間への一律加算ができます。$d$ は $O(\log{N})$ 通りですから、遷移を $O(\log{N})$ に高速化でき、この問題を解くことができます。
全体の計算量は $O(N^2\log{N})$ です。
コード
def solve():
N, P = map(int, input().split())
dp = [[0] * 4100 for _ in range(3100)]
dp[0][0] = 1
dp[0][1] = -1
for i in range(N):
for j in range(N + 1):
dp[i][j] += dp[i][j - 1]
dp[i][j] %= P
c = 26 if i == 0 else 25
for j in range(N + 1):
x = dp[i][j]
dp[i + 2][j + 1] += c * x
dp[i + 2][j + 10] -= c * x
dp[i + 3][j + 10] += c * x
dp[i + 3][j + 100] -= c * x
dp[i + 4][j + 100] += c * x
dp[i + 4][j + 1000] -= c * x
dp[i + 5][j + 1000] += c * x
ans = 0
for i in range(N):
ans += dp[i][N]
ans %= P
return ans
print(solve())
F問題『Ignore Operations』
問題ページ:F - Ignore Operations
灰コーダー正解率:0.1 %
茶コーダー正解率:0.8 %
緑コーダー正解率:3.0 %
考察
操作 $1$ を行うと、それ以前に行った操作は一切その後に影響を及ぼしません。ある操作 $1$ を無視せず行うのなら、それ以前の操作を無視するのは回数の無駄なので、一切しないべきです。
最後に行う操作 $1$ を採用する操作 $1$ と呼ぶことにします。採用する操作 $1$ を後ろから全探索し、それぞれについて $x$ の最大値を求めればいいです。
まず、採用する操作 $1$ 以降の操作 $1$ はすべて無視しなければいけません。採用する操作 $1$ 以降に操作 $1$ が出現する回数を $m$ とすると、$i$ 回目以降に出現する操作 $2$ のうち、最大で $K-m$ 個を無視できます。
どの操作 $2$ を無視すべきか考えます。
- $y_i\ge{0}$ は無条件で採用すべき
- $y_i\lt{0}$ のうち、絶対値が大きいものから優先して無視するのが最適
**無視した操作 $2$ の値を、優先度付きキューを使って絶対値が小さい順に管理します。**符号が負の操作 $2$ はすべて優先度付きキューに入れます。ただし、無視できる回数を超えた場合、キューから一番絶対値の小さい値を取り出して、無視せずに使ったことにします。
コード
from heapq import heappop, heappush
INF = (1 << 62) - 1
def main():
def solve():
N, K = map(int, input().split())
A = [0] * (N + 1)
flag = [False] * (N + 1) # i回目の操作が操作1ならTrue
flag[0] = True # 0回目にt=1, y=0があることにします
for i in range(1, N + 1):
t, y = map(int, input().split())
A[i] = y
flag[i] = (t == 1)
pq = []
ans = -INF # 答えの初期値は十分に絶対値の大きい負の値にします(答えは負になる場合もあります)
s = 0 # ここまで無視しなかった操作2の値の総和
for i in reversed(range(N + 1)):
if len(pq) > K:
s -= heappop(pq) # 負の値の絶対値を入れたので、無視を取り消した場合は引きます
if flag[i]:
ans = max(ans, A[i] + s)
K -= 1 # この操作1は無視します
if K < 0: # 無視できる操作1は最大K個までです
break
else:
if A[i] < 0:
heappush(pq, -A[i]) # 負の値の絶対値、-A[i]をpqに入れます
else:
s += A[i] # 無視しないほうが良いので、足します
return ans
print(solve())
if __name__ == '__main__':
main()