【ABC355】緑コーダーの競プロ参加記録 #19
今回はAtCoder Beginner Contest 355。使用言語はPythonです。
A問題 - Who Ate the Cake?
コンテスト中の提出
https://atcoder.jp/contests/abc355/submissions/53828931
犯人の候補に人$${1}$$、人$${2}$$、人$${3}$$がいる。
$${A}$$さんと$${B}$$さんは犯人ではない。
犯人を特定できるか判定してね。
問われていることはシンプルですが、地味に実装が悩ましい問題です。
$${A = B}$$のときは犯人を特定できません。
それ以外のとき、$${1, 2, 3}$$のうち$${A}$$でも$${B}$$でもない数を答えます。
""" ACコード """
A, B = map(int, input().split())
if A > B:
A, B = B, A
if A == B:
print(-1)
else:
if A == 1:
if B == 2:
print(3)
else:
print(2)
elif A == 2:
print(1)公式解説にないコードを選んで載せてみました。
他の解法も見てみると、なにか新しい発見があるかもしれません。
B問題 - Piano 2
コンテスト中の提出
https://atcoder.jp/contests/abc355/submissions/53833681
長さ$${N}$$の数列$${A}$$、長さ$${M}$$の数列$${B}$$が与えられる。
$${A, B}$$のすべての要素は互いに相異なる。
数列$${C}$$を「数列$${A + B}$$の要素を昇順に並べたもの」とする。
数列$${C}$$で$${A}$$の要素が連続することがあるかどうか判定してね。
最近、B問題も結構むずかしいですよね。
Python ではリストを '+' 演算子で連結できます。
ソートは sorted() 関数か、sort() メソッド のどちらかを使います。
""" 数列 C をつくる """
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(A + B)「$${A}$$の要素が連続する」とは、「$${C}$$について$${i}$$番目の要素、$${i + 1}$$番目の要素がどちらも$${A}$$に含まれる」ということになるので、これを判定します。
含まれるかどうかの判定は、リストに対して行うと要素数$${N}$$に対して毎回$${O(N)}$$かかります。
$${1 \le N, M \le 100}$$なので、今回の問題では TLE になりません。
set を使うと判定を$${O(1)}$$で行えます。
""" A を set に変換して判定 """
A = set(A)
for i in range(N + M - 1):
if C[i] in A and C[i + 1] in A:
print('Yes')
exit()
print('No')C問題 - Bingo 2
コンテスト中の提出
https://atcoder.jp/contests/abc355/submissions/53843125
$${N \times N}$$のビンゴカードがある。
マス$${(i, j)}$$には整数$${N(i - 1) + j}$$が書かれている。
ビンゴが成立するターンを出力してね。
ビンゴになっているかどうかは、ヨコ列・タテ列・ナナメ列の中のどれかで印がついているマスの個数が$${N}$$個であるものがあるかどうかが分かればよいです。
よって、各マスの状態を厳密に管理する必要はなく、宣言された整数がタテ・ヨコ・ナナメのどれに属しているかを調べ、そのそれぞれで印の個数をカウントします。
印の個数が$${N}$$個になった列ができたターンが答えになります。
ナナメ列に属する条件は、0-index として$${i = j}$$または$${i + j = N -1}$$です。
""" 入力を受け取る """
N, T = map(int, input().split())
A = list(map(int, input().split()))
col = [0] * N
row = [0] * N
slash_1 = 0
slash_2 = 0
bingo = False
for turn, a in enumerate(A):
""" マス(i, j) を特定する """
i = (a - 1) // N
j = (a - 1) % N
""" 列ごとに印の個数をカウントする """
row[i] += 1
col[j] += 1
if i == j:
slash_1 += 1
if i + j == N - 1:
slash_2 += 1
""" ビンゴ成立を判定する """
bingo |= row[i] == N
bingo |= col[j] == N
bingo |= slash_1 == N
bingo |= slash_2 == N
if bingo:
print(turn + 1)
exit()
print(-1)なお、$${2 \le N \le 2 \times 10^3}$$なので$${N \times N}$$のビンゴカードを表現できます。
しかし、ビンゴの成立を毎ターン判定をしていると$${O(N^2T)}$$で TLE になります。
すべての印をつけてから判定すればよいです。
実装を頑張ると解けます。
（参考コード）
https://atcoder.jp/contests/abc355/submissions/53953993
D問題 - Intersecting Intervals
コンテスト中の提出
https://atcoder.jp/contests/abc355/submissions/53873229
$${N}$$個の区間が与えられる。
$${i}$$番目の区間は$${[l_i, r_i]}$$。
共通部分をもつ区間の組み合わせの個数を出力してね。
$${N}$$個の区間から2つ選ぶ組み合わせは$${_nC_2 = \Large\frac{N(N-1)}{2}}$$通りあります。
すべての組み合わせから、共通部分をもたない組み合わせを除外すれば、求めたい答えが求まります。
「区間$${i}$$と区間$${j}$$が共通部分をもたない」条件は$${r_j < l_i}$$または$${r_i < l_j}$$です。
$${r_j < l_i}$$である$${j}$$の個数は、$${R}$$をソートしておくと二分探索で求めることができます。
""" L, R を分けてソート """
from bisect import bisect_right
N = int(input())
L, R = [], []
for _ in range(N):
l, r = map(int, input().split())
L.append(l)
R.append(r)
R.sort()
""" 共通部分をもたない組み合わせの個数を二分探索で調べる """
ans = N * (N - 1) // 2
for l in L:
ans -= bisect_right(R, l - 1)
print(ans)公式解説や上記では、「条件を満たさないもの」の個数を数える、すなわち余事象を考えることで解きました。
「条件を満たすもの」を数える解法もあります。
区間$${[l_i, r_i]}$$と$${[l_j, r_j]}$$が共通部分をもつとき、共通部分に含まれる数$${a}$$の範囲は以下のようになります。
$$
\max(l_i, l_j) \le a \le \min(r_i, r_j)
$$
よって、$${\max(l_i, l_j) \le \min(r_i, r_j)}$$となる区間の個数を数えることができればよいです。
これは、ある$${i}$$における、$${l_j \le r_i}$$である区間$${j}$$の個数$${x}$$、$${r_j < l_i}$$である区間$${j}$$の個数$${y}$$に対して、$${(x -1) - y}$$となります。
（$${x - 1}$$となるのは$${l_i < r_i}$$であるためです。）
$${x, y}$$は独立して数えてよいです。
$${i, j}$$を入れ替えても$${\max(l_i, l_j), \min(r_i, r_j)}$$の値は変わらないので、同じ組み合わせが2回カウントされます。
よって、最後に$${2}$$で割ったものが答えになります。
""" L, R を分けてソート """
from bisect import bisect_right
N = int(input())
L, R = [], []
for _ in range(N):
l, r = map(int, input().split())
L.append(l)
R.append(r)
L.sort()
R.sort()
""" 共通部分をもつ組み合わせの個数を調べる """
ans = 0
for l, r in zip(L, R):
x = bisect_right(L, r) - 1
y = bisect_right(R, l - 1)
ans += x - y
print(ans // 2)E問題 - Guess the Sum
$$
\Huge{ diff 2299 }
$$
あとがき
今回は ABCD 4完 56分 で 2446 位、1103 perf でした。
E問題は ABC349 - D - Divide Interval と同じ問題かと思ったら、想像以上に難しい問題でした。
解説を読んでもよく分かりませんでしたし、どういう発想でこれを思いつくのかも見当がつきません。
強い人、強すぎる。
ではまた～。
【更新履歴】
2024/05/28 (0時頃)：記事投稿。