ABC246の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や拡散していただけると喜びます！
目次
ABC246 まとめ
A問題『Four Points』
B問題『Get Closer』
C問題『Coupon』
D問題『2-variable Function』
E問題『Bishop 2』
F問題『typewriter』
アプリ AtCoderFacts を開発しています
コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。
- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス
今後も機能を追加していく予定です。使ってくれると喜びます。
ABC246 まとめ
全提出人数: 9358人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB------ | 300 | 56分 | 6359(6095)位 |
| 400 | AB------ | 300 | 12分 | 5195(4931)位 |
| 600 | ABC----- | 600 | 72分 | 4180(3924)位 |
| 800 | ABC----- | 600 | 39分 | 3245(2995)位 |
| 1000 | ABC----- | 600 | 20分 | 2419(2172)位 |
| 1200 | ABCD---- | 1000 | 70分 | 1710(1473)位 |
| 1400 | ABC-E--- | 1100 | 88分 | 1187(955)位 |
| 1600 | ABCD-F-- | 1500 | 80分 | 790(576)位 |
| 1800 | ABCDEF-- | 2000 | 103分 | 519(327)位 |
| 2000 | ABCDEF-- | 2000 | 77分 | 342(173)位 |
| 2200 | ABCDEF-- | 2000 | 57分 | 215(79)位 |
| 2400 | ABCDEFG- | 2600 | 102分 | 119(37)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F | G | Ex |
|---|---|---|---|---|---|---|---|---|---|
| 灰 | 3137 | 92.0 % | 76.4 % | 36.5 % | 4.0 % | 0.9 % | 0.6 % | 0.1 % | 0.0 % |
| 茶 | 1437 | 97.7 % | 94.4 % | 83.0 % | 13.4 % | 3.1 % | 1.4 % | 0.0 % | 0.0 % |
| 緑 | 1137 | 96.8 % | 94.8 % | 93.9 % | 41.5 % | 15.0 % | 4.0 % | 0.3 % | 0.0 % |
| 水 | 729 | 97.4 % | 96.2 % | 96.2 % | 69.8 % | 47.5 % | 24.0 % | 1.5 % | 0.4 % |
| 青 | 397 | 96.0 % | 95.7 % | 94.7 % | 87.4 % | 77.8 % | 72.5 % | 9.3 % | 1.5 % |
| 黄 | 207 | 87.0 % | 87.0 % | 85.5 % | 84.1 % | 77.8 % | 81.6 % | 35.3 % | 9.7 % |
| 橙 | 39 | 84.6 % | 84.6 % | 84.6 % | 87.2 % | 79.5 % | 82.0 % | 76.9 % | 38.5 % |
| 赤 | 20 | 80.0 % | 80.0 % | 80.0 % | 80.0 % | 80.0 % | 90.0 % | 80.0 % | 80.0 % |
※表示レート、灰に初参加者は含めず
A問題『Four Points』
問題ページ：A - Four Points
灰コーダー正解率：92.0 %
茶コーダー正解率：97.7 %
緑コーダー正解率：96.8 %
入力
$x_i,y_i$ : $i$ 番目の点の $x$ 座標と $y$ 座標（$1\le{i}\le3$）
考察
サンプルを見るとわかりますが、$x$ 座標と $y$ 座標それぞれについて、$1$ 回しか出てこないものが答えです。
図を書いてみるとよりわかりやすいかもしれません。
実装
実装はやや長くなりますが、リストに入れて数えてしまうのが手っ取り早いです。
実装が楽な方法に、$3$ 点のxorを取ると答えがわかるというものがあります。$2$ 回出てくる座標はxorで打ち消しあって $0$ になるので、$1$ 回だけ出てくる座標がわかります。すぐに思いついた場合はこちらを使うといいです。（私はxorを使う方法自体は思いつきましたが、負の数に対するxorの仕様がわからなかったので、調べる前に何も考えずに回数を数えました。本当にどちらでもいいです）
コード
リストを使ってがんばる
X, Y = [], []
for _ in range(3):
x, y = map(int, input().split())
X.append(x)
Y.append(y)
ax, ay = 0, 0
for i in range(3):
if X.count(X[i]) == 1:
ax = X[i]
if Y.count(Y[i]) == 1:
ay = Y[i]
print(ax, ay)
xorの性質を利用
ax, ay = 0, 0
for _ in range(3):
x, y = map(int, input().split())
ax ^= x
ay ^= y
print(ax, ay)
B問題『Get Closer』
問題ページ：B - Get Closer
灰コーダー正解率：76.4 %
茶コーダー正解率：94.4 %
緑コーダー正解率：94.8 %
入力
$A,B$ : 点の $x$ 座標、$y$ 座標
考察
点 $(A,B)$ を点 $P$ とします。位置ベクトル $\overrightarrow{P}$ と同じ向きで、長さが $1$ のベクトルがわかればいいです。
位置ベクトル $\overrightarrow{P}$ の長さ $|P|$ は、$\sqrt{A^2+B^2}$ です。向きが長さ $\sqrt{A^2+B^2}$ の位置ベクトル $\overrightarrow{P}$ と同じで、長さが $1$ の位置ベクトルは、 $(\dfrac{A}{\sqrt{A^2+B^2}},\ \dfrac{B}{\sqrt{A^2+B^2}})$ です。これがそのまま答えです。
コード
A, B = map(int, input().split())
d = (A ** 2 + B ** 2) ** 0.5
ax = A / d
ay = B / d
print(ax, ay)
おまけ: 複素数で解いてみる
複素平面を考えると、複素数 $A+Bj$ を絶対値で割ることで答えがわかります。実質的にやっていることは、上の方法と同じです。
A, B = map(int, input().split())
z = A + B * 1j
ans = z / abs(z)
print(ans.real, ans.imag)
C問題『Coupon』
問題ページ：C - Coupon
灰コーダー正解率：36.5 %
茶コーダー正解率：83.0 %
緑コーダー正解率：93.9 %
入力
$N$ : $N$ 個の商品がある
$A_i$ : $i$ 番目の商品の値段は $A_i$ 円
$K,X$ : $K$ 枚のクーポンがあって、$1$ 枚につき商品 $1$ 個 $X$ 円引きで買える（ただし、商品の値段は $0$ 円未満にはならない）
考察
クーポンを $1$ 枚も使わないと、$\mathrm{sum}(A)$ 円かかります。
基本的にはクーポンを $1$ 枚使うと $X$ 円安くなりますが、商品は $0$ 円未満にはならないので、$X$ 円 未満の商品に対してクーポンを使うと値引き額が小さくなってしまいます。
クーポンがあるだけ、以下の貪欲法を行えば最適解を得られます。
- 全商品が $X$ 円未満になるまでクーポンを使う
- 全商品が $X$ 円未満になったら、価格が高い順にクーポンを使って $0$ 円にする
実装
$A_i = Xq_i+r_i$ （$q_i,r_i$はそれぞれ$A_i$ を $X$ で割った商と余り）と表せます。$\mathrm{sum}(q)$ 回まで、$X$ 円値引きすることができます。まだクーポンが残っている場合、$r_i$ が大きい順にクーポンを使っていきます。
したがって、以下のことを行えば良いです。
- $q_i$ の総和を求める
- $r_i$ をソートして大きい順に並べる
コード
N, K, X = map(int, input().split())
A = list(map(int, input().split()))
ans = sum(A)
rem = K # クーポンの残り枚数
Q = sum(x // X for x in A) # X円引きできる回数
R = sorted((x % X for x in A), reverse=True) # X円引きし終わったあとの余りを大きい順に並べる
ans -= X * min(Q, rem) # Qとクーポンの枚数の少ない方だけX円引きできる
rem -= min(Q, rem) # X円引きに使った分クーポンを減らす
ans -= sum(R[:rem]) # 大きい順に使う（スライスは配列外参照を起こさないので、remが巨大でも問題ありません）
print(ans)
D問題『2-variable Function』
問題ページ：D - 2-variable Function
灰コーダー正解率：4.0 %
茶コーダー正解率：13.4 %
緑コーダー正解率：41.5 %
入力
$N$ : 非負整数（$0\le{N}\le{10^{18}}$）
考察
$a$ を全探索します。$N$ は最大で $10^{18}$ ですから、$a^3=10^{18}$ より、$a=10^6$ まで調べればいいです。
$b$ も全探索すると $O(N^{\frac{2}{3}})$ でTLEになります。そこで、『$a$ をある値に固定したとき、$b$ をいくつにすれば $X$ が $N$ 以上で最小になるか』という問題をある程度高速に解くことができれば、この問題を解けます。
$a=m$ （$m\ge{0}$）に固定すると、$X=b^3+b^2m+bm^2+m^3$ になります。
$X$ は $b$ について単調増加しますから、二分探索を使って『$X$ が $N$ 以上になる最小の $b$ 』を求められます。求めた $b$ を代入すれば、『$a=m$ に固定したときの、$N$ 以上で最小の $X$ 』を求められます。
計算量は$M=N^{\frac{1}{3}}$ として、 $O(M\log{M})$ です。
備考: 尺取法でも解ける
なお、二分探索を使わずに尺取法の要領で解くことも可能です（公式解説の方法）。
一般に、尺取法で解ける問題の多くは二分探索で解けます。どちらも単調性が必要だからです。これは私個人の意見ですが、二分探索のほうが実装も考察も簡単なことが多いので、どちらも使える場合は二分探索を使うことをおすすめします。
コード
PyPyで提出してください。Pythonでは通りませんが、尺取法ならば通るかもしれません。
def main():
def f(b):
return a ** 3 + b * a ** 2 + a * b ** 2 + b ** 3
N = int(input())
ans = float("INF")
for a in range(10 ** 6 + 5):
ng = -1
ok = 10 ** 6 + 5
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if f(mid) >= N:
ok = mid
else:
ng = mid
ans = min(ans, f(ok))
print(ans)
if __name__ == '__main__':
main()
E問題『Bishop 2』
問題ページ：E - Bishop 2
灰コーダー正解率：0.9 %
茶コーダー正解率：3.1 %
緑コーダー正解率：15.0 %
入力
省略（わかるよね）
- TL 6sec
考察
2種類の解法を紹介します。
- 向きを状態に加えて01BFS
- 枝刈りBFS
前者の方法がオーソドックスな解法ですが、後者は実装が楽で速度も高速です。どちらも使えると強いと思います。
向きを状態に加えて01BFS
今いる行・列に加えて、$4$ 方向のうちどの向きを向いているかも状態に加えます。
遷移（状態の変更、移動）は以下の $2$ 種類です。
- 今向いている向きにコスト $0$ で $1$ 回移動する
- 現在のマスから移動せずに、コスト $1$ で向いている向きを変更する
これを01BFSで実装すると高速です。01BFSは、コストが $0$ と $1$ だけのときに使えるダイクストラ法の高速な亜種です。とくに難しいアルゴリズムではありません。
01BFSとは
ダイクストラ法では優先度付きキュー（heapq）を使いますが、01BFSでは通常のBFSと同じ両端キュー（deque）を使います。
キューに要素を追加するとき、以下の基準で左から入れるか、右から入れるかを変えます。
- コスト $0$ の遷移はdequeの左に追加（
appendleft） - コスト $1$ の遷移はdequeの右に追加（
append）
こうすることで、ダイクストラ法の優先度付きキューと同じことを両端キューで行えます。
優先度付きキューは値の削除の計算量が $O(\log{N})$ ですが、両端キューは $O(1)$ のため、計算量が改善されます。
計算量は $O(N^2)$（定数倍重め）です。ダイクストラ法の場合は、$O(N^2\log{N})$ です。
枝刈りBFS
この問題 のユーザー解説のchokudaiさん解法と同じことをします。（そもそも今回の問題は、こちらの問題とかなり似た問題で、ほとんどのコードを流用できてしまいます）
状態は今いる行・列だけで、向きは考慮しません。 そして、今いるマスからいけるマスすべてに対してコスト $1$ で移動する、普通のBFSをします。
そのままでは計算量が $O(N^3)$ ですから、TLEになります。そこで、枝刈りを行います。
$4$ 方向それぞれについて、始点から近い順にマスを見ていきます。
始点のコスト + $1$ と比較して
- コストが大きいマスはコストを更新してキューに追加（普通のBFSです）
- コストが同じマスは何もせず素通り（更新は不要ですが、その先にまだ未訪問のマスがあった場合は今の移動で更新すべきなため）
- コストが小さいマスに当たったらその先は見ない（そのマスを始点にすればいいため）
- 障害物に当たってもその先は見ない（当然ですね）
私は厳密な証明をできていませんが、マスを見る回数の合計は最大で $\dfrac{5\times{N^2}}{2}$ 回程度になる気がします。（$2$ で割るのは、斜め移動だけではパリティが違うマスに到達不可能なため）
よって、計算量は $O(N^2)$ だと思われます。赤コーダー・AtCoder社長のchoukudaiさんがツイッターで言及していた解法ですから、アルゴリズム自体の正当性はかなり信用できると思います。
コード
01BFS
PyPyで2500ms程度です。Pythonでも5600msでギリギリ通ります。
ダイクストラ法は定数倍高速化をすごく頑張ると通ります。（後述のおまけコード）
from collections import deque
INF = (1 << 62) - 1
def main():
def solve():
N = int(input())
N2 = N + 2
ar, ac = map(int, input().split())
br, bc = map(int, input().split())
# 周辺を壁で埋めて、判定を楽にします
S = ["#" * N2]
S.extend("#" + input() + "#" for _ in range(N))
S.append("#" * N2)
dist = [[[INF] * N2 for _ in range(N2)] for _ in range(4)]
que = deque()
for i in range(4):
dist[i][ar][ac] = 1 # 初期値は1です
que.append((ar, ac, i, 1)) # 行, 列, 向き, コスト
DR = [-1, 1, -1, 1]
DC = [-1, -1, 1, 1]
while que:
cr, cc, d, cost = que.popleft()
if cost > dist[d][cr][cc]:
continue
# コスト0で今向いている向きに移動
dr, dc = DR[d], DC[d]
nr, nc = cr + dr, cc + dc
if S[nr][nc] == "." and cost < dist[d][nr][nc]:
dist[d][nr][nc] = cost
que.appendleft((nr, nc, d, cost))
# コスト1でその場で方向変換
for i in range(4):
if cost + 1 < dist[i][cr][cc]:
dist[i][cr][cc] = cost + 1
que.append((cr, cc, i, cost + 1))
ret = INF
for i in range(4):
ret = min(ret, dist[i][br][bc])
return ret if ret < INF else -1
print(solve())
if __name__ == '__main__':
main()
枝刈りBFS
PyPyで570ms程度です。Pythonでも通ります。
from collections import deque
INF = (1 << 62) - 1
def main():
def solve():
N = int(input())
N2 = N + 2
ar, ac = map(int, input().split())
br, bc = map(int, input().split())
# 周辺を壁で埋めて、判定を楽にします
S = ["#" * N2]
S.extend("#" + input() + "#" for _ in range(N))
S.append("#" * N2)
dist = [[INF] * N2 for _ in range(N2)]
que = deque()
dist[ar][ac] = 0
que.append((ar, ac))
DR = [-1, 1, -1, 1]
DC = [-1, -1, 1, 1]
while que:
cr, cc = que.popleft()
ncost = dist[cr][cc] + 1
for dr, dc in zip(DR, DC):
nr, nc = cr + dr, cc + dc
while S[nr][nc] == ".":
if ncost < dist[nr][nc]:
que.append((nr, nc))
dist[nr][nc] = ncost
elif ncost > dist[nr][nc]:
break
nr += dr
nc += dc
ret = dist[br][bc]
return ret if ret < INF else -1
print(solve())
if __name__ == '__main__':
main()
おまけ: ダイクストラ
定数倍高速化をがんばると、01BFSではなくダイクストラでも通ります。5500msでした。
提出コード: https://atcoder.jp/contests/abc246/submissions/30699324
3次元配列を1次元配列に変換することで、定数倍高速化しています。すごくめんどくさいですが、定数倍高速化の最終手段としては有効です。
F問題『typewriter』
問題ページ：F - typewriter
灰コーダー正解率：0.6 %
茶コーダー正解率：1.4 %
緑コーダー正解率：4.0 %
入力
$N$ : タイプライターの段数（$1\le{N}\le{18}$）
$S_i$ : タイプライターの上から $i$ 段目のキーでは、$S_i$ に含まれる英小文字が打てる
$L$ : ルールに従って打てる $L$ 文字の文字列の数を数える
考察
$x$ 種類の文字を使えるとき、$L$ 文字の文字列は $x^L$ 通りあります。
しかし、 単純に $N$ 段それぞれの答えを足すと、同じ文字列を重複して数えてしまいます。 以下の入力を考えてみましょう。
2 2
ab
ac
$1$ 行目 : $2^2=4$ 通り aa ab ba bb
$2$ 行目 : $2^2=4$ 通り aa ac ca cc
そのまま足すと、$4+4=8$ 通りになります。しかし、実際は $1$ 行目、$2$ 行目ともに aa を作れるので、aaを $2$ 回数えてしまっています。正しい答えは、$8-1=7$ 通りです。
包除原理 ～ベン図を利用した数え上げの一般化みたいなやつ～
重複しない文字列の数を数えるために、包除原理を利用します。
先ほどの例が、包除原理の集合が $2$ つの場合の例になっています。$A\cup{B}=A+B-A\cap{B}$ です。これを、集合の数が任意の場合に拡張したものが包除原理です。
例えば、以下の入力を考えます。
3 5
abc
abd
bce
包除原理より、答えは、$\sum(ある1行の文字で作れる文字列の数)-\sum(ある2行に共通する文字で作れる文字列の数)+\sum(ある3行に共通する文字で作れる文字列の数)$ です。
$S_1\cap{S_2}=$ab、$S_1\cap{S_3}=$bc、$S_2\cap{S_3}=$b、$S_1\cap{S_2}\cap{S_3}=$b です。したがって、答えは $(3^5+3^5+3^5)-(2^5+2^5+1^5)+1^5=665$ 通りです。
一般化すると、奇数個の行を選んで共通する文字で作れる文字列の数は足して、偶数個の行を選んで共通する文字で作れる文字列の数は引きます。
bit全探索ですべての行の選び方を列挙する
bit全探索の要領で、行の組み合わせを全列挙できます。選んだ行すべてに共通する英小文字の種類数 $x$ を求め、組み合わせ数 $x^L$ を計算します。選んだ行の数が奇数なら答えに足して、偶数なら引きます。
英小文字もbitで管理すると楽
各行に $26$ 種類の英小文字のうちどれが含まれているかは、$26$ bitの整数のどのbitの $1$ が立っているかで管理すると良いです。こうすると、共通する文字の集合を求めるのを、論理積&を取るだけできます。
1が立っているbitの個数（popcount）の求め方
共通する文字の種類数・選んだ行の数は、popcount（$1$ が立っているbitの個数）を求めればわかります。これは、bin(bit).count("1")でできます。
コード
MOD = 998244353
def main():
def pop_count(x): # より高速な方法もあるので、興味のある方は調べてください
return bin(x).count("1")
def solve():
N, L = map(int, input().split())
S = []
for _ in range(N):
s = input()
x = 0
for ch in s:
p = ord(ch) - ord('a')
x |= (1 << p)
S.append(x)
ans = 0
P = (1 << 26) - 1 #111...111（26個）
for bit in range(1, 1 << N):
st = P
for i in range(N):
if bit >> i & 1:
st &= S[i] # 共通する英小文字の集合を知りたいので、論理積をとる
x = pop_count(st)
pcnt = pop_count(bit) # 奇数なら足して、偶数なら引く
ans += pow(x, L, MOD) * (1 if pcnt % 2 == 1 else -1)
ans %= MOD # 余りを取るのを忘れずに！
return ans
print(solve())
if __name__ == '__main__':
main()
popcountについて
bin(x).count("1") を使いましたが、この方法はかなり低速です。より高速なアルゴリズムもあるので、興味のある方は調べてみてください。
Python3.10ではint.bit_count()というメソッドが追加されており、高速なアルゴリズムで実装されています。AtCoderのジャッジサーバーではまだPythonのバージョンが古いので使えませんが、言語アップデート後はこちらを使うといいでしょう。