ABC234のA,B,C,D,E問題を、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や拡散していただけると喜びます！
目次
ABC234 まとめ
A問題『Weird Function』
B問題『Longest Segment』
C問題『Happy New Year!』
D問題『Prefix K-th Max』
E問題『Arithmetic Number』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC234 まとめ
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 58分 | 6075(5839)位 |
| 400 | ABC----- | 600 | 66分 | 4921(4694)位 |
| 600 | ABC----- | 600 | 22分 | 4056(3831)位 |
| 800 | ABCD---- | 1000 | 71分 | 3141(2918)位 |
| 1000 | ABCDE--- | 1500 | 136分 | 2291(2076)位 |
| 1200 | ABCDE--- | 1500 | 69分 | 1624(1410)位 |
| 1400 | ABCDE--- | 1500 | 44分 | 1136(922)位 |
| 1600 | ABCDEF-- | 2000 | 104分 | 778(573)位 |
| 1800 | ABCDEF-- | 2000 | 67分 | 516(323)位 |
| 2000 | ABCDEF-- | 2000 | 50分 | 349(171)位 |
| 2200 | ABCDEF-- | 2000 | 31分 | 216(82)位 |
| 2400 | ABCDEFG- | 2600 | 89分 | 131(39)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 2568 | 98.2 % | 82.2 % | 60.4 % | 22.1 % | 5.5 % | 0.2 % | 0.1 % | 0.0 % |
| 茶 | 1217 | 98.9 % | 97.7 % | 91.0 % | 66.7 % | 25.4 % | 1.0 % | 0.0 % | 0.0 % |
| 緑 | 957 | 98.6 % | 98.3 % | 96.5 % | 92.3 % | 70.0 % | 6.6 % | 0.4 % | 0.3 % |
| 水 | 632 | 96.8 % | 96.7 % | 96.5 % | 96.4 % | 91.8 % | 31.5 % | 1.1 % | 0.9 % |
| 青 | 391 | 98.0 % | 97.7 % | 97.7 % | 97.4 % | 97.2 % | 82.9 % | 10.7 % | 5.4 % |
| 黄 | 179 | 90.5 % | 90.5 % | 89.4 % | 89.4 % | 89.4 % | 89.4 % | 36.3 % | 16.2 % |
| 橙 | 40 | 95.0 % | 95.0 % | 97.5 % | 97.5 % | 97.5 % | 97.5 % | 72.5 % | 52.5 % |
| 赤 | 17 | 88.2 % | 88.2 % | 88.2 % | 88.2 % | 88.2 % | 88.2 % | 100.0 % | 88.2 % |
※表示レート、灰に初参加者は含めず
A問題『Weird Function』
問題ページ：A - Weird Function
灰コーダー正解率：98.2 %
茶コーダー正解率：98.9 %
緑コーダー正解率：98.6 %
入力
$t$ : $0$ 以上 $10$ 以下の整数
考察
書かれているとおりにやるだけと言えばそうですが、何も工夫をしないと非常に大変です。この問題は、実装を工夫すると楽にできます。
実装
関数 $f$ を Pythonの関数として定義します。そして、問題文のとおりに $f(f(f(t)+t)+f(f(t)))$ を計算して出力しましょう。問題文の数式をコピー&ペーストすると楽です。
コード
def f(x):
return x ** 2 + 2 * x + 3
t = int(input())
print(f((f(f(t) + t)) + f(f(t)))) # 問題文からコピペしましょう
B問題『Longest Segment』
問題ページ：B - Longest Segment
灰コーダー正解率：82.2 %
茶コーダー正解率：97.7 %
緑コーダー正解率：98.3 %
入力
$N$ : 点の数
$x_i, y_i$ : $i$ 個目の点の座標
考察
『二次元平面上の $2$ 点を結ぶ線分の長さ』とは、『$2$ 点間の距離』のことです。$2$ 点 $(x_i,y_i)$ と $(x_j, y_j)$ の距離は、 $\sqrt{(x_j-x_i)^2 + (y_j-y_i)^2}$ で求められます。（中学・高校数学です。詳しくは検索してください）
$2$ 個の点の組、$\frac{N(N-1)}{2}$ 組を全探索して、最大の距離を出力すればいいです。$N$ は最大で $100$ ですから、$2$ 点の組は最大で $\frac{100\times{99}}{2}=4950$ 組しかありません。
コード
def solve():
ans = 0
for i in range(N):
x1, y1 = XY[i]
for j in range(i):
x2, y2 = XY[j]
l = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
ans = max(ans, l)
return ans
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
print(solve())
Python 3.8以降
PyPy7.3.0では使えませんが、Python3.8のmathモジュールにはdist関数という、$K$ 次元（$K\ge2$）の $2$ 点間のユークリッド距離（二乗の総和の平方根）を求める関数が追加されています。
この関数を使うと、より簡潔に書くことができます。
from math import dist
def solve():
ans = 0
for i in range(N):
for j in range(i):
l = dist(XY[i], XY[j])
ans = max(ans, l)
return ans
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
print(solve())
内包表記とmax関数を使うと、$1$ 行で答えを計算することも可能です。
from math import dist
N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
print(max(dist(XY[i], XY[j]) for i in range(N) for j in range(i)))
"""
1行にしていますが、内包表記で二重ループは読みづらいのでやめたほうがいいです
itertoolsのproductやconbinationsを使うと読みやすくなると思います
"""
C問題『Happy New Year!』
問題ページ：C - Happy New Year!
灰コーダー正解率：60.4 %
茶コーダー正解率：91.0 %
緑コーダー正解率：96.5 %
入力
$K$ : $K$ 番目に小さい、$0,2$ からなる正整数を求める
考察
$0,2$ ではなく、 $0,1$ からなる正の整数を求めて、$1$ を $2$ に置き換えても同じです。
$0,1$ からなる 正の整数で $K$ 番目に小さいものは、以下の例のように、$K$ を $2$ 進法表記した値と同じです。
1: 1
2: 10
3: 11
4: 100
5: 101
6: 110
7: 111
$K$ の $2$ 進数表記を求めて、$1$ を $2$ に置き換えれば良いです。$K$ の $2$ 進数表記は、Pythonのformat関数を使えば簡単にわかります。
コード
K = int(input())
b = format(K, 'b') # bの型はstrです
ans = b.replace('1', '2') # str型であるbの'1'を'2'に置き換えます
print(ans)
D問題『Prefix K-th Max』
問題ページ：D - Prefix K-th Max
灰コーダー正解率：22.1 %
茶コーダー正解率：66.7 %
緑コーダー正解率：92.3 %
入力
$N$ : 順列の長さ
$K$ : $P$ の先頭 $i$ 項のうち、 $K$ 番目に大きい値を求める
$P$ : $(1,2,\dots,N)$ の並び替えによって得られる順列
考察
先頭 $i$ 項のうち $K$ 番目に大きい値を都度ソートして求めるなどの方法は、計算量が $O(NKlogK)$ や $O(NK)$ なので、TLEになります。高速に求める必要があります。
先頭 $K$ 項のうち $K$ 番目に大きい値は、先頭 $K$ 項で最小の値です。
次に、先頭 $K+1$ 項 で、$K$ 番目に小さい値を求めます。$K+1$ 項で最小の値、すなわち $K+1$ 番目に大きい値は、今後 $K$ 番目に大きくなることは絶対にありません。ですので、捨ててしまいます。すると、残った $K$ 個のうち最小の値が 先頭 $K+1$ 項で $K$ 番目に大きい値です。
先頭 $K+2$ 項、先頭 $K+3$ 項……の答えも、同様の手順を繰り返すことで得ることができます。
上記のアルゴリズムでこの問題を解くためには、以下の操作を高速で行う必要があります。
- $K+1$ 個の要素のうち、最小の値を捨てる
- $K$ 個の要素のうち、最小の値を得る
この操作を高速で行えるデータ構造に、優先度付きキューというものがあります。優先度付きキューを使うと、最小の値を捨てる操作 $O(logK)$、最小の値を得る操作を $O(1)$ で行えます。
実装
Pythonで優先度付きキューを使うときは、heapq モジュールを使いましょう。
heapqモジュールは使い方に癖がある、というか使いづらいので、ライブラリにして使いやすくしたほうが良いかもしれません。
コード
from heapq import heapify, heappush, heappop
N, K = map(int, input().split())
P = list(map(int, input().split()))
pq = P[:K]
heapify(pq) # O(K)でリストpqをヒープ化します
print(pq[0]) # pq[0] が 先頭 K 項 で最小です。(ソートしているわけではないので、pq[1]以降は小さい順に並んでいるとは限りません)
for x in P[K:]:
heappush(pq, x) # pqにxを追加します
heappop(pq) # 長さK+1のリストpqで最小の値を捨てます
print(pq[0]) # 長さKのリストpqの最小の値を出力します
優先度付きキューをライブラリにする場合
このライブラリを使うと、heapqを使うよりやや実行速度が遅くなりますが、TLEになることはあまりないです。
desc=Trueとすると、小さい順ではなく大きい順の優先度付きキューになります。
import heapq
class PriorityQueue:
"""
優先度付きキュー
"""
class Reverse:
def __init__(self, val):
self.val = val
def __lt__(self, other):
return self.val > other.val
def __str__(self):
return str(self.val)
def __repr__(self):
return repr(self.val)
def __init__(self, a=None, desc=False):
self.__container = []
if a:
self.__container = a[:]
if desc:
for i, item in enumerate(self.__container):
self.__container[i] = self.Reverse(item)
self.pop = self.__pop_desc
self.push = self.__push_desc
self.top = self.__top_desc
else:
self.pop = self.__pop_asc
self.push = self.__push_asc
self.top = self.__top_asc
heapq.heapify(self.__container)
def __pop_asc(self):
return heapq.heappop(self.__container)
def __pop_desc(self):
return heapq.heappop(self.__container).val
def __push_asc(self, item):
heapq.heappush(self.__container, item)
def __push_desc(self, item):
heapq.heappush(self.__container, self.Reverse(item))
def __top_asc(self):
return self.__container[0]
def __top_desc(self):
return self.__container[0].val
def sum(self):
return sum(self.__container)
def __len__(self):
return len(self.__container)
def __str__(self):
return str(sorted(self.__container))
def __repr__(self):
return self.__str__()
def main():
N, K = map(int, input().split())
P = list(map(int, input().split()))
pq = PriorityQueue(P[:K])
print(pq.top())
for x in P[K:]:
pq.push(x)
pq.pop()
print(pq.top())
main()
E問題『Arithmetic Number』
問題ページ：E - Arithmetic Number
灰コーダー正解率：5.5 %
茶コーダー正解率：25.4 %
緑コーダー正解率：70.0 %
入力
$X$ : $1$ 以上 $10^{17}$ 以下の整数
考察
$1$ 以上 $10^{17}$ 以下の等差数は、全列挙できるほど少ないです。BFS（幅優先探索）で小さい順に列挙して、$X$ 以上の値で最小のものを出力すればいいです。
コード
from collections import deque
def solve():
que = deque(range(1, 100)) # 1以上100未満の数は、すべて等差数です
while que:
num = que.popleft()
if num >= X:
return num
if num >= 10: # 1桁の数から作れる2桁の数はすでにqueに入っているので、弾きます
nf = num % 10 # numの一番目に下の桁
ns = (num // 10) % 10 # numの二番目に下の桁
d = nf - ns # 公差
t = nf + d
if 0 <= t <= 9: # nf + d が 0以上9以下で、新しく末尾に追加できるか判定します
que.append(num * 10 + t)
X = int(input())
print(solve())