AtCoder Beginner Contest 183のA,B,C,D問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
ご質問・ご指摘はコメントかツイッターまでどうぞ
Twitter: u2dayo
目次
ABC183 まとめ
A問題『ReLU』
B問題『Billiards』
C問題『Travel』
D問題『Water Heater』
ABC183 まとめ
全提出人数: 7199人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 32分 | 5526(5365)位 |
| 400 | ABC--- | 600 | 99分 | 4586(4426)位 |
| 600 | ABC--- | 600 | 38分 | 3791(3632)位 |
| 800 | ABCD-- | 1000 | 88分 | 2963(2807)位 |
| 1000 | ABCD-- | 1000 | 46分 | 2194(2038)位 |
| 1200 | ABCD-- | 1000 | 21分 | 1554(1399)位 |
| 1400 | ABCDE- | 1500 | 70分 | 1060(911)位 |
| 1600 | ABCDEF | 2100 | 122分 | 700(557)位 |
| 1800 | ABCDEF | 2100 | 77分 | 440(315)位 |
| 2000 | ABCDEF | 2100 | 59分 | 273(164)位 |
| 2200 | ABCDEF | 2100 | 46分 | 161(78)位 |
| 2400 | ABCDEF | 2100 | 37分 | 100(35)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 2960 | 99.5 % | 69.2 % | 35.0 % | 12.5 % | 1.9 % | 0.8 % |
| 茶 | 1377 | 99.7 % | 91.7 % | 87.5 % | 57.4 % | 5.8 % | 2.5 % |
| 緑 | 1086 | 99.6 % | 96.9 % | 97.0 % | 90.7 % | 26.4 % | 7.6 % |
| 水 | 664 | 99.8 % | 97.4 % | 99.5 % | 98.6 % | 69.7 % | 34.5 % |
| 青 | 333 | 100.0 % | 99.7 % | 100.0 % | 100.0 % | 94.6 % | 76.0 % |
| 黄 | 124 | 95.2 % | 94.3 % | 94.3 % | 95.2 % | 96.0 % | 91.9 % |
| 橙 | 28 | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 100.0 % | 96.4 % |
| 赤 | 9 | 88.9 % | 88.9 % | 88.9 % | 88.9 % | 88.9 % | 100.0 % |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (7152人AC)『ReLU』
- if文で場合分けします。
- B問題 (5919人AC)『Billiards』
- 「$x$ 方向の速さ」と「$y$ 方向の速さ」の比を考えるとわかります。
- C問題 (4633人AC)『Travel』
- 最大 $(8-1)!=7!=5040$ 通りの訪問順をすべて試せばいいです。Pythonでは、
itertools.permutationsを使うと、簡単に全ての順列を生成できます。 - D問題 (3400人AC)『Water Heater』
- 累積和（imos法）を使うと、各時間にどれだけお湯が使われるか $O(N)$ で求められます。
- E問題 (1393人AC)『Queen on Grid』[この記事では解説しません]
- 累積和DPです。
- F問題 (789人AC)『Confluence』[この記事では解説しません]
- Unionfindと、$N$ 個のCounterを使います。連結成分のサイズが大きいほうのCounterに、サイズが小さい方のCounterを足せば間に合います。
- 「$S_i$ から 配列の最後まで、$+P_i$ する」
- 「$T_i$ から 配列の最後まで、$-P_i$ する」
私（うにだよ）の結果（参考）
23時間だけ青コーダーでした。
A問題『ReLU』
問題ページ：A - ReLU
灰コーダー正解率：99.5 %
茶コーダー正解率：99.7 %
緑コーダー正解率：99.6 %
ReLu関数は、ディープラーニングの伝達関数としてよく使われる関数です。
コード
x = int(input())
if x >= 0:
print(x)
else:
print(0)
B問題『Billiards』
問題ページ：B - Billiards
灰コーダー正解率：69.2 %
茶コーダー正解率：91.7 %
緑コーダー正解率：96.9 %
考察
$G_x - S_x = T_x$ , $S_y + G_y = T_y$ とします。公式解説の図より、下の三角形を考えることができます。
三角形の相似・比より、以下の関係が成り立ちます。
Δx = \frac{S_y}{T_y}・T_x
$Δx$ は $S_x$ から壁の反射地点までの長さなので、答えは $S_x + Δx$ です。なお、目標が左側（$x$ 軸のマイナス方向）にあるとき、$T_x$ および $Δx$ はマイナスになります。よって、場合分けする必要はありません。
コード
sx, sy, gx, gy = map(int, input().split())
tx = gx - sx
ty = sy + gy
dx = tx * sy / ty
print(sx + dx)
C問題『Travel』
問題ページ：C - Travel
灰コーダー正解率：35.0 %
茶コーダー正解率：87.5 %
緑コーダー正解率：97.0 %
考察
※配列の添字にあわせたほうがわかりやすいので、都市 $0$ からスタートすることにします。
はじめは都市 $0$ で、最後に都市 $0$ なのは、どのような順番で都市を訪れても固定です。
都市 $1$ から $N - 1$ まで訪問する方法は、全部で $(N-1)!$ 通りあります。最大でも $N=8$ なので、$7!=5040$ 通りしかありません。
したがって、全ての訪問順を試してみて、ちょうど $K$ であるものの数を数えても間に合います。
実装
Pythonでありえる順列をすべて生成するときは、itertoolsモジュールのpermutationsを使うといいです。
今回の問題では、(1, 2, 3, ..., N - 1)を並び替えてできる順列をすべて作りたいです。そのためには、permutationsの引数に、range(1, N)を渡せばいいです。
具体的には、下のように書けばいいです。
for per in permutations(range(1, N)):
# 処理
コード
from itertools import permutations
N, K = map(int, input().split())
T = []
for _ in range(N):
s = list(map(int, input().split()))
T.append(s)
ans = 0
for per in permutations(range(1, N)):
score = 0 # 今回の訪問順でかかった時間です
prev = 0 # 最初は都市0からスタートします
for i in range(N - 1):
cur = per[i]
score += T[prev][cur] # 都市prevから都市curに向かいます
prev = cur
score += T[prev][0] # 最後に都市0へ行きます
if score == K:
# K ちょうど で一周できた場合、答えに+1します
ans += 1
print(ans)
D問題『Water Heater』
問題ページ：D - Water Heater
灰コーダー正解率：12.5 %
茶コーダー正解率：57.4 %
緑コーダー正解率：90.7 %
考察
時間は整数で区切られていて、最大でも $200000$ しかありません。そこで、各時間ごとのお湯の消費量を記録した配列を作ることを考えます。もちろん、$N$ 人全員の区間すべてにいちいち $P_i$ 足していては間に合いません。
そこで、累積和を使います。「$S_i$ から $T_i - 1$ に、$P_i$ を足す」というのは、このように言い換えられます。
いつもの累積和でやる最初の操作だけだと、$T_i$ 以降にまで $P_i$ が余計に足されてしまいます。そこで、$T_i$ 以降から $P_i$ を引いて打ち消してあげると、区間に対する加算を累積和で行うことができます。
$1$ 人ずつ配列にこの $2$ つの操作をします。最後に累積和を求めて、お湯の消費量が全ての時間で $W$ 以下かどうか確認すればいいです。そのために、累積和の最大値が $W$ 以下かmax関数で判定すればいいです。
なお、今回の問題で使った「累積和を使って区間加算をするアルゴリズム」は、開発者の名前よりimos法と呼ばれることがあります。一次元配列に対して行う場合は、累積和の操作を $2$ 回やるだけの単純なアルゴリズムです。
コード
@c-yanさんのコメントより、最後の判定にmax関数を使うよう改良しました。ありがとうございます！
from itertools import accumulate
C = 200005 # 累積和の配列の長さCです。適当に200000より大きい数にしておきます。
N, W = map(int, input().split())
seq_a = [0] * C
for _ in range(N):
s, t, p = map(int, input().split())
seq_a[s] += p
seq_a[t] -= p
S = list(accumulate(seq_a))
if max(S) <= W:
print('Yes')
else:
print('No')