ABC221のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッター、マシュマロまでどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
よかったらLGTMや拡散していただけると喜びます！
目次
ABC221 まとめ
A問題『Seismic magnitude scales』
B問題『typo』
C問題『Select Mul』
D問題『Online games』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC221 まとめ
全提出人数: 8297人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 42分 | 6119(5891)位 |
| 400 | AB------ | 300 | 14分 | 5022(4794)位 |
| 600 | ABC----- | 600 | 80分 | 4125(3904)位 |
| 800 | ABC----- | 600 | 35分 | 3214(2994)位 |
| 1000 | ABCD---- | 1000 | 86分 | 2377(2163)位 |
| 1200 | ABCD---- | 1000 | 51分 | 1698(1486)位 |
| 1400 | ABCD---- | 1000 | 30分 | 1185(976)位 |
| 1600 | ABCDE--- | 1500 | 91分 | 803(605)位 |
| 1800 | ABCDE--- | 1500 | 60分 | 536(349)位 |
| 2000 | ABCDE--- | 1500 | 37分 | 343(185)位 |
| 2200 | ABCDEF-- | 2000 | 99分 | 203(91)位 |
| 2400 | ABCDEF-- | 2000 | 79分 | 125(42)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | H |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3674 | 96.4 % | 76.7 % | 27.5 % | 4.8 % | 0.5 % | 0.0 % | 0.0 % | 0.0 % |
| 茶 | 1415 | 99.1 % | 96.3 % | 77.2 % | 33.6 % | 2.4 % | 0.6 % | 0.0 % | 0.0 % |
| 緑 | 1134 | 99.0 % | 98.7 % | 93.0 % | 77.4 % | 9.0 % | 1.3 % | 0.0 % | 0.1 % |
| 水 | 663 | 99.4 % | 98.9 % | 98.0 % | 94.4 % | 43.7 % | 3.8 % | 0.0 % | 0.1 % |
| 青 | 375 | 98.7 % | 98.9 % | 98.1 % | 98.4 % | 84.8 % | 24.5 % | 0.5 % | 0.8 % |
| 黄 | 184 | 91.8 % | 90.8 % | 89.7 % | 90.2 % | 88.6 % | 53.3 % | 4.9 % | 7.6 % |
| 橙 | 27 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 92.6 % | 18.5 % | 18.5 % |
| 赤 | 19 | 94.7 % | 94.7 % | 94.7 % | 94.7 % | 94.7 % | 94.7 % | 52.6 % | 73.7 % |
※表示レート、灰に初参加者は含めず
A問題『Seismic magnitude scales』
問題ページ：A - Seismic magnitude scales
灰コーダー正解率：96.4 %
茶コーダー正解率：99.1 %
緑コーダー正解率：99.0 %
入力
$A, B$ : マグニチュードを表す整数（$B\le{A}$)
考察
問題文に、マグニチュードが $1$ 大きくなると、エネルギーは $32$ 倍になるとあります。
マグニチュードが $2$ 大きくなると、エネルギーは $32$ 倍の $32$ 倍なので、$32\times32=1024$ 倍になります。
マグニチュードが $3$ 大きくなると、$32$ 倍の $32$ 倍の $32$ 倍 になるので、 $32\times{32}\times{32} = 32^3$ 倍になります。
一般化すると、マグニチュードが $X$ 大きくなると、エネルギーは $32^{X}$ 倍になります。（$32$ の $X$ 乗）
マグニチュード $A$ は、マグニチュード $B$ より $A-B$ 大きいので、答えは $32^{A-B}$ 倍です。
コード
A, B = map(int, input().split())
print(32 ** (A - B))
B問題『typo』
問題ページ：B - typo
灰コーダー正解率：76.7 %
茶コーダー正解率：96.3 %
緑コーダー正解率：98.7 %
入力
$S,T$ : 長さの同じ文字列（長さは $1$ 文字以上 $100$ 文字以下）
考察
『$S$ の隣り合う $2$ 文字を選び、入れ替える』という操作を高々 $1$ 回（$0$ 回以上 $1$ 回以下）行って、$S$ と $T$ を同じ文字列にできるかどうかを判定します。
まず、操作を $0$ 回行う場合、つまり何もしなくても $S$ と $T$ が同じかどうか判定します。
同じでなければ、操作を $1$ 回だけ行う場合を考えます。操作を行う位置の候補は、文字列の長さを $N$ とすると、$N-1$ 通りあります。すべての入れ替える位置を試してみて、一つでも $S$ と $T$ が一致する入れ替え方があればYes で、 一つもなければ Noです。
実装
$S$ を文字列として受け取って、以下のコードのようにそのまま入れ替え操作をしようとすると、エラーになります。
S = input()
T = input()
N = len(S)
for i in range(N - 1):
S[i], S[i + 1] = S[i + 1], S[i] # エラーになります
string型（文字列型）は、変数の中身そのものを変更させることができないからです。（イミュータブルといいます）
$S$ をリストに一旦変換し、リストの隣り合う要素を入れ替えて、その後リストを文字列に戻すことで対応します。
コード
def judge():
if S == T: # 何もしなくても一致しています
return True
N = len(S)
# Sのi文字目とi+1文字目を入れ替えた文字列をTと比較して、1つでも一致すればYesです
for i in range(N - 1):
L = list(S) # string（文字列）は文字を入れ替えることができないので、リストにします
L[i], L[i + 1] = L[i + 1], L[i] # i文字目とi+1文字目を入れ替えます
S2 = ''.join(L) # 文字列のリストを連結して、1つの文字列にします
if S2 == T:
return True
return False
S = input()
T = input()
print('Yes' if judge() else 'No')
C問題『Select Mul』
問題ページ：C - Select Mul
灰コーダー正解率：27.5 %
茶コーダー正解率：77.2 %
緑コーダー正解率：93.0 %
入力
$N$ : 整数（$10$ 桁以下で、$0$ ではない桁を $2$ つ以上含む）
考察
$N$ の各桁を $2$ つのグループに分けることを考えます。一旦数字の並べ方は忘れます。
例えば、$1342$ を $\lbrace1,3\rbrace$ と $\lbrace4,2\rbrace$ に分けたとします。そして、グループごとに数字を好きな順に並び替えて整数を作ります。$\lbrace1,3\rbrace$ は $13,31$、 $\lbrace4,2\rbrace$ は $42,21$ にすることができます。
グループの分け方を決めたときの最適解
作った $2$ つの整数の積が最も大きくなるようにしたいです。どのようにすればいいでしょうか。これは、各グループで一番大きい数字を作って、それを掛け合わせた値が最大になります。
$1$ つのグループの数字を並び替えて、一番大きい数字を作る方法を考えます。これは、一番上の桁からまだ使っていない大きい数字を使えばいいです。上の例では、 $\lbrace1,3\rbrace$ を $31$ に、 $\lbrace4,2\rbrace$ を $42$ にして掛け合わせた $31\times{42}=1302$ が最大になります。
グループの分け方は少ないので、全探索できる
$2$ つのグループの分け方は、各桁ごとに『1つ目のグループに入れる』か『$2$ つ目のグループに入れる』の $2$ 通りあるので、グループの分け方は $2^{N}$ 通りあります。$N$ は最大 $10$ 桁ですから、分け方は最大で $2^{10}=1024$ 通りしかありません。グループの分け方をすべて試して、グループの分け方ごとに掛けた値を計算し、その中で最大のものを出力すればいいです。
実装
整数の受け取り方
$N$ の桁ごとに数字を取り出すのを楽にするために、文字列で受け取るといいです。
グループの分け方の実装
いわゆる『bit全探索』というアルゴリズムを使って、桁ごとにどちらのグループに分けるか $0$ か $1$ で表した列を全列挙します。
itertools モジュールの product 関数を使うと楽です。（詳細はコードを見てください）
最大の整数の作り方
グループを表す $2$ つの空のリストを作ります。桁ごとに取り出した数字（長さ $1$ の文字列'0'や'9'などです）を、リストにappendします。
グループ分けが終わったら、$2$ つのリストを降順にソートすることで、9876543210の順に並び替えます。そして、リストを''.join(list)文字列に戻して、int関数で整数にして、最後にかけ合わせます。
コード
from itertools import product
def solve():
ans = 0
# Nのi文字目をどちらのグループに入れるかを、全探索します
for pro in product((0, 1), repeat=len(N)):
first = []
second = []
for i, b in enumerate(pro): # in zip(N, pro)
if b == 1:
first.append(N[i])
else:
second.append(N[i])
if len(first) == 0 or len(second) == 0: # 片方のグループが空の場合は飛ばします
continue
first.sort(reverse=True) # 文字列のリストを9876543210の順に並ぶように、逆順にソートします
second.sort(reverse=True)
a = int(''.join(first)) # 文字列のリストを文字列にして、さらに整数に変換します
b = int(''.join(second))
ans = max(ans, a * b) # 最大値を更新します
return ans
N = input()
print(solve())
D問題『Online games』
問題ページ：D - Online games
灰コーダー正解率：4.8 %
茶コーダー正解率：33.6 %
緑コーダー正解率：77.4 %
入力
$N$ : プレイヤー数
$A_i$ : プレイヤー $i$ は $A_i$ 日目からログインする
$B_i$ : プレイヤー $i$ は $A_i$ 日目を含めて $B_i$ 日間ログインする（$A_i$ 日目 ～ $A_i + B_i - 1$ 日目までログインして、$A_i + B_i$ 日目にはログインしていない ）
考察
もちろん、$1$ 日ずつ人数をシミュレートしていてはTLEになります。
ログインしている人数が変わる日は、誰かがログインする日と誰かがログアウトする日だけなので、多くても $2N$ 日しかありません。当然ですが、ログインしている人数が変わる日以外は、ログインしている人数は一定です。
人数が変わる日に何人増えるか減るかをCounterで記録して、日付が早い順に処理していきます。現在ログインしている人数を増減させる前に、$(今回人数が変わった日)-（前回人数が変わった日）$だけ、変化前のログイン人数の日数に足せばいいです。
コード
from collections import Counter
def main():
N = int(input())
C = Counter()
for _ in range(N):
a, b = map(int, input().split())
C[a] += 1 # a日目に1人増えます
C[a + b] -= 1 # a + b 日目に1人減ります
ans = [0] * (N + 1) # ans[i]: ちょうどi人がログインしていた日数
days = sorted(C.keys()) # 人数が変化する日のリストを昇順
prev_day = 0 # 前回人数が変化した日
cnt = 0 # ログインしている人数
for curr_day in days:
ans[cnt] += curr_day - prev_day
cnt += C[curr_day]
prev_day = curr_day
print(*ans[1:]) # 0人の日は出力しません
if __name__ == '__main__':
main()