【AtCoder解説】PythonでABC191のA,B,C問題を制する！

AtCoder Beginner Contest 191のA,B,C問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

• シンプル：余計なことを考えずに済む
• 実装が楽：ミスやバグが減ってうれしい
• 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッターまでどうぞ！
Twitter: u2dayo

目次

ABC191 まとめ
A問題『Vanishing Pitch』
B問題『Remove It』
C問題『Digital Graffiti』

ABC191 まとめ

全提出人数: 8807人

パフォーマンス

パフォ	AC	点数	時間	順位(Rated内)
200	AB----	300	33分	6656(6422)位
400	AB----	300	17分	5509(5275)位
600	AB----	300	10分	4549(4316)位
800	AB----	300	6分	3544(3312)位
1000	ABC---	600	92分	2615(2387)位
1200	ABC---	600	31分	1854(1630)位
1400	AB--E-	800	59分	1276(1060)位
1600	ABC-E-	1100	84分	851(652)位
1800	ABC-E-	1100	51分	553(373)位
2000	AB--EF	1400	103分	347(196)位
2200	ABCDE-	1500	90分	225(95)位
2400	ABCDE-	1500	55分	148(43)位

色別の正解率

色	人数	A	B	C	D	E	F
灰	3813	89.3 %	90.8 %	7.6 %	0.2 %	1.2 %	0.0 %
茶	1493	97.9 %	98.6 %	24.4 %	0.7 %	6.0 %	0.0 %
緑	1292	98.8 %	99.0 %	43.4 %	3.8 %	25.5 %	0.4 %
水	731	98.9 %	98.9 %	65.5 %	12.2 %	63.3 %	1.1 %
青	363	99.7 %	100.0 %	78.8 %	33.1 %	86.0 %	11.0 %
黄	192	91.7 %	92.2 %	81.2 %	52.6 %	86.5 %	33.3 %
橙	42	95.2 %	95.2 %	95.2 %	73.8 %	88.1 %	64.3 %
赤	13	76.9 %	76.9 %	76.9 %	76.9 %	84.6 %	84.6 %

※表示レート、灰に初参加者は含めず

簡易解説

A問題 (8128人AC)『Vanishing Pitch』

算数するとどこの距離の区間でボールが消えているかわかります。 A問題にしてはかなり難しいです。

B問題 (8215人AC)『Remove It』

要素を1個ずつ見ていって、$X$ と等しい要素だけ取り除けばいいです。 Aより簡単です。

C問題 (2257人AC)『Digital Graffiti』

角の数を数えればいいです。 角の条件は、ある2x2マスの正方形領域を見て、`"#"`が $1$ 個か $3$ 個であれば角です。 すべての正方形領域にこの判定をして数えればいいです。

D問題 (424人AC)『Circle Lattice Points』[この記事では解説しません]

全部の格子点について円内にあるか数えていては当然間に合いません。 数学（三平方の定理）を使えば、ある $x$ 座標上にいくつ条件を満たす格子点があるか数えられます。 ただし、浮動小数点数を使うと誤差が出てしまいWAになります。 $1$ 万倍してすべて整数で計算するなどの工夫をする必要があります。

E問題 (1492人AC)『Come Back Quickly』[この記事では解説しません]

ある特定の頂点の答えを求めるには、スタート地点の距離を $0$ で初期化せずにダイクストラ法をするだけでいいです。 全頂点にダイクストラ法をすれば、$O(N(N+M)logN)$ で解けます。

F問題 (157人AC)『GCD or MIN』[この記事では解説しません]

$A$ から要素をいくつか選んで、最大公約数をとったものが $A$ の最小値より小さければ、最後まで残すことができます。 約数列挙して工夫して計算すると $2$ 秒で求められます。

A問題『Vanishing Pitch』

問題ページ：A - Vanishing Pitch
灰コーダー正解率：89.3 %
茶コーダー正解率：97.9 %
緑コーダー正解率：98.8 %

考察

問題文が長くて読みづらいので、ポイントを書きます。

• ボールが ちょうど $D$ m 離れたときにボールが消えていないならば、打つことができる
• ボールは速さ $V\ \mathrm{m/s}$ で等速直線運動をしている
• ボールは投げた瞬間から $T$ 秒後から $S$ 秒後まで消えている（$T,\ S$ 秒ちょうども消えている）

ボールがちょうど $D$ m 離れたときに消えているか消えていないかを知りたいのですが、$D$ は入力で直接与えられていないので、算数をして求める必要があります。

等速直線運動とは、投げた瞬間から常に速さ $V\ \mathrm{m/s}$ のまま変化しないという意味です。したがって、ボールが $t$ 秒間に進む距離は $V\times{t}\ \mathrm{m}$ です。 ボールが消えるのは $T$ 秒後から $S$ 秒後までですから、距離にすると $V\times{T}\ \mathrm{m}$ から $V\times{S}\ \mathrm{m}$ の間消えていて、それ以外では消えていません。

以上より、 $V\times{T}\le{D}\le{V\times{S}}$ であれば'No'で、そうでなければ'Yes'です。

コード

V, T, S, D = map(int, input().split())

if V * T <= D <= V * S:
    # 消えている間が"No"です
    print("No")
else:
    print("Yes")

B問題『Remove It』

問題ページ：B - Remove It
灰コーダー正解率：90.8 %
茶コーダー正解率：98.6 %
緑コーダー正解率：99.0 %

実装

空のリストansを用意します。書かれているとおりに、$A$ の要素を前から見ていって $X$ でなければansに追加すればいいです。

コード

N, X = map(int, input().split())
A = [*map(int, input().split())]
ans = []

for x in A:
    if x != X:
        ans.append(x)

print(*ans)

内包表記を使ってもいいです。

N, X = map(int, input().split())
A = [*map(int, input().split())]
ans = [p for p in A if p != X]

print(*ans)

JavaScriptなどに慣れている人は、filter()を使ってもいいですね。

N, X = map(int, input().split())
A = [*map(int, input().split())]

print(*filter(lambda x: x != X, A))

C問題『Digital Graffiti』

問題ページ：C - Digital Graffiti
灰コーダー正解率：7.6 %
茶コーダー正解率：24.4 %
緑コーダー正解率：43.4 %

問題の意味

正直に言うと、この問題は、問題文が大変わかりづらく、サンプルも不親切です。（問題として成立はしているので、Unratedにはなりませんが）

ですので、問題の意味を正しく理解できなくても、皆さんのせいではありません。

（AtCoderや問題製作者の方を悪く言う意図はありません。また、実際にAtCoderの方もよくなかったとおっしゃっていました）

n角形とは

サンプルが不親切すぎて、n角形の定義がわからないと思います。

そこで、いくつか具体例をあげます。

例1: 4角形

サンプル1です。これは4角形です。

.....
.###.
.###.
.###.
.....

例2: 8角形

これは3角形ではありません。8角形です。

.....
..#..
.###.
.....

例3: 8角形

凹んだ図形の場合もあります。これは8角形です。

.....
.#.#.
.#.#.
.###.
.....

例4:

こんなものを多角形として認めたくありませんが、数学的には多角形です。
18角形です。（これはテストケースの1つです）

..........
.########.
........#.
.########.
.#........
.########.
........#.
.########.
.#........
..........

自己交叉のない多角形とは

『黒に塗られた部分は一つの自己交叉のない多角形となることが保証されます。』

• 黒に塗られたマスが少なくとも一つ存在する
• 黒に塗られた任意の $2$ マスは、辺を共有するマスへの移動を繰り返し、黒に塗られたマスのみを通って互いに到達可能である
• 白に塗られた任意の $2$ マスは、辺を共有するマスへの移動を繰り返し、白に塗られたマスのみを通って互いに到達可能である(マス目の一番外側のマスは全て白に塗られていることに注意してください)

とあります。後半の $2$ つは、**『白いマス同士・黒いマス同士は、上下左右で必ずつながっている』**という意味です。

具体的には、次のような入力は与えられません。

....
.#..
..#.
....

考察

$n$ 角形とは、角が $n$ 個ある図形のことです。 当たり前ですね。つまり、角の数を数えればいいです。

ということで、角をすべて数えることにします。そのためには、すべての $2\times{2}$ マスの正方形領域を見ます。その $4$ マスのうち '#' が $3$ つ か $1$ つなら角です。

# が $1$ つの場合はわかりやすいです。下の図形は $4$ つ角がありますね。

....
.##.
.##.
....

# が $3$ つの場合を忘れやすいです。凹んでいる部分の角です。以下の図形を見るとわかると思います。この図形は、# が $1$ つの角が $6$ つ、# が $3$ つの角が $2$ つで、$8$ 角形です。

.....
.#.#.
.###.
.....

実装

一番外側のマスはすべて白いマスなので、グリッドからはみ出るような角は存在しません。

$2\times{2}$ マスの正方形領域 $(H-1)\times{(W-1)}$ 個を全探索して、先ほどの方法で角を数えればいいです。

コード

H, W = map(int, input().split())
grid = []

for _ in range(H):
    S = input()
    grid.append(list(1 if c == "#" else 0 for c in S))  # "#"を1, "."を0に変換

ans = 0

for row in range(H - 1):
    for col in range(W - 1):
        cnt = 0
        cnt += grid[row][col]  # 左上
        cnt += grid[row + 1][col]  # 左下
        cnt += grid[row][col + 1]  # 右上
        cnt += grid[row + 1][col + 1]  # 右下

        if cnt == 1:
            ans += 1
        if cnt == 3:
            ans += 1

print(ans)