【ABC343】緑コーダーの競プロ参加記録 #6
ふわふわした解説を目指しています。
今回はAtCoder Beginner Contest 343。使用言語はPythonです。
A問題 - Wrong Answer
コンテスト中の提出
https://atcoder.jp/contests/abc343/submissions/50770860
整数$${A, B}$$が与えられる。
$${A + B}$$と異なる 0 以上 9 以下の整数を1つ出力してね。
まず入力を受け取ります。入力は整数$${A, B}$$の2つなので以下のように受け取ります。
""" 入力を受け取る """
A, B = map(int, input().split())input(): 入力を1行まるまる文字列として受け取る。
split(): 文字列を空白区切りで文字列のリストにする。
map(int, X): リスト X の中身ひとつひとつを int にする。
リストをアンパックして$${A, B}$$に代入する。
という一連の処理を行っています。
（厳密にはmap関数はリストではなくmapオブジェクトを返します。）
さて「0 以上 9 以下の整数を1つ出力してね」ということなので答えは「0 以上 9 以下の整数」のどれかです。forループで全部調べましょう。
整数$${i}$$が$${A + B}$$と異なるときに整数$${i}$$を出力すればよいので if文を使って条件分岐を書きます。出力にはprint関数を使います。
""" 入力を受け取る """
A, B = map(int, input().split())
""" 問題を解く """
for i in range(10):
if i != A + B:
print(i)これでよさそうに見えますが、このままだと整数が9つ出力されてしまいます。競プロでは出力に過不足があると答えが正しくても不正解として扱われます。
1つ出力したらforループを抜けるようにすることで正解を得られます。forループを抜ける処理は break です。
""" 入力を受け取る """
A, B = map(int, input().split())
""" 問題を解く """
for i in range(10):
if i != A + B:
print(i)
break「forループを抜ける」ではなく「プログラムを終了させる」としてexit関数を呼んでもよいです。
""" 入力を受け取る """
A, B = map(int, input().split())
""" 問題を解く """
for i in range(10):
if i != A + B:
print(i)
exit()問題を解く部分を関数として実装し、return で処理を終わらせる方法もあります。
""" 問題を解く関数 """
def solve():
for i in range(10):
if i != A + B:
return i
""" 入力を受け取る """
A, B = map(int, input().split())
""" 問題を解く """
ans = solve()
""" 答えを出力 """
print(ans)
以上で問題が解けました。
なお公式解説にはこれ以外の解法がいくつか紹介されています。
【余談】
プログラミングにおいて「同じ処理を2回書いたら関数化する」などと言われますが、競プロ (ABC) においては return を利用して記述を楽にしたり、コードの見通しを良くしてバグを起こしにくく・見つけやすくする目的で関数化します。
Pythonで関数を使うにあたって、グローバル変数の扱いに少しクセがあるので気になる方はいろいろと試してみてください。
""" 出力はどうなる ? """
def solve(k):
value = A[k] + n
ans = max(ans, value)
A = [0, 1, 2, 3, 4, 5]
n = 100
ans = -1
solve(3)
print(ans)(出力結果は記事の最後に載せておきます。)
B問題 - Adjacency Matrix
コンテスト中の提出
https://atcoder.jp/contests/abc343/submissions/50777746
$${N}$$頂点のグラフが隣接行列$${A}$$の形で与えられる。
$${A_{ij} = 1}$$のとき頂点$${i}$$と頂点$${j}$$が直接繋がっている。
全ての$${i}$$について、直接繋がっている頂点を昇順で出力してね。
グラフ問題における入力部分が出題されています。
頂点、単純無向グラフ、辺などの専門用語はさておいて「$${A_{ij}=1}$$である$${(i, j)}$$を指定の形式で教えてね」という問題です。
そうなると、単純に$${N \times N}$$のリストを全探索する問題といえます。$${N \leq 100}$$なので二重ループを実装しても 2 sec に間に合います。
「昇順に出力」とありますが、基本的にforループは昇順で行うのでソートをしなくても問題ないです。0-indexを1-indexに直すことに注意しましょう。
""""""
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
res = []
for j in range(N):
if A[i][j] == 1:
res.append(j + 1)
print(*res)空白区切りの出力ではリストをアンパックすると楽です。
print関数の end キーワードを使って空白区切りすることもできます。その場合、1行ごとに改行が必要なことに注意しましょう。
""" end キーワード """
for i in range(N):
for j in range(N):
if A[i][j] == 1:
print(j + 1, end=' ')
print()C問題 - 343
コンテスト中の提出
https://atcoder.jp/contests/abc343/submissions/50804260
正整数$${N}$$が与えられる。
回文立方数 $${K}$$: 正整数$${x}$$について$${x^3 = K}$$かつ$${K}$$が回文。
$${N}$$以下の回文立方数のうち最大のものを出力してね。
$${N \leq 10^{18}}$$なので$${N}$$以下の正整数の全探索は無理そうです。
回文について考えてみます。
回文である数は18桁の数だけでも$${9 \times 10^8}$$個あります。こちらも全探索は無理そうです。
立方数について考えてみます。
$${x^3 \leq N}$$の条件を満たす正整数$${x}$$の最大値は$${\sqrt[3]{N} \leq 10^6}$$です。こちらは全探索できそうです。
$${N = 1}$$のときのコーナーケースに気を付けて$${1 \leq x \leq N}$$の範囲でforループを回します。途中でforループを抜けないと$${O(N)}$$になるので注意しましょう。
N = int(input())
""" 立方数の全列挙 """
K = []
for x in range(1, N + 1):
if x ** 3 > N:
break
K.append(x ** 3)長さ$${T}$$の文字列に対する回文判定は$${O(T)}$$であり、最大19桁となる全ての立方数$${K}$$に対して回文判定を行っても全体で$${O(10^7)}$$程度なので 2 sec に間に合いそうです。
""" 回文判定 """
def ok(k: int):
s = str(k)
m = len(s)
for i in range(m // 2):
if s[i] != s[m - i - 1]:
return False
return True
ans = 0
for k in K:
if ok(k):
ans = k
print(ans)
以上で解けました。
「回文である数は18桁の数だけでも$${9 \times 10^8}$$個あります。こちらも全探索は無理そうです。」
と言いましたが、それなりに時間をかければ全探索できます。
そのうえで、立方数のものだけ列挙するようにします。
立方数であるかどうかの判定は、小数誤差を加味して以下のようにします。
""" 立方数の判定 """
from math import ceil, floor
def ok(num: int):
p = pow(num, 1/3)
return ceil(p) ** 3 == num or floor(p) ** 3 == num""" 回文立方数の列挙 """
res = []
for i in range(1, 10**9 + 1):
s = str(i)
p = int(f'{s}{s[::-1]}')
q = int(f'{s[:-1]}{s[::-1]}')
if ok(p):
res.append(p)
if ok(q):
res.append(q)
print(sorted(res))全列挙した回文立方数をコピペすることで問題を解けました。
""" コピペ """
X = [1, 8, 343, 1331, 1030301, 1367631, 1003003001, 10662526601, 1000300030001, 1030607060301, 1334996994331, 1000030000300001, 1033394994933301, 1331399339931331]
N = int(input())
ans = 0
for x in X:
if x <= N:
ans = x
print(ans)私のよわよわPCでは全列挙に70分かかりました。
D問題 - Diversity of Scores
コンテスト中の提出
https://atcoder.jp/contests/abc343/submissions/50809287
$${N}$$人の選手がいる。
$${T}$$個の得点情報が与えられる。
$${i}$$秒後に選手$${A_i}$$が$${B_i}$$点を得る。
得点獲得後のタイミングにおける、得点の種類数を出力してね。
まず、選手$${i}$$の得点$${S_i}$$を管理するリストは必要そうです。
種類数といえば set を使いたいですが、長さ$${N}$$のリストから set を作る処理は$${O(N)}$$なので毎回行っていると全体で$${O(TN)}$$となり TLE になってしまいます。
set に値を追加したり削除したりして計算量を削ろうにも、同じ得点の人が何人いるかの情報がないと値を削除してよいかどうかが分かりません。
というわけで、ある得点をもつ人数を管理する dict を用意します。（リストにすると$${B_i \leq 10^9}$$の制約により TLE します。）
そうすると、得点の種類数は「dict 内の 0 以上の値をもつキーの個数」になります。選手$${A}$$の得点が$${X \rarr X + B}$$と変化するとき、$${X}$$点をもつ人数が -1 され、$${X+B}$$点をもつ人数が +1 されます。
「dict 内の 0 以上の値をもつキーの個数」を愚直に数えようとすると全探索となり dict の要素数を$${M}$$として$${O(M)}$$かかってしまいますが、値が 0 になるたびにキーを削除しておくと len関数 を使って$${O(1)}$$で済みます。
""" キーの個数を数える解法 """
from collections import defaultdict
N, T = map(int, input().split())
S = [0] * (N + 1)
D = defaultdict(int)
D[0] += N
for _ in range(T):
a, b = map(int, input().split())
x = S[a]
D[x] -= 1
if D[x] == 0:
del D[x]
D[x + b] += 1
S[a] = x + b
print(len(D))各タイミングにおいて、得点の種類数は「1つ増える」「1つ減る」「変わらない」のどれかです。差分だけ考える方法でも AC になります。
""" 差分を数える解法 """
from collections import defaultdict
N, T = map(int, input().split())
S = [0] * (N + 1)
D = defaultdict(int)
D[0] += N
ans = 1
for _ in range(T):
a, b = map(int, input().split())
x = S[a]
D[x] -= 1
if D[x] == 0:
ans -= 1
if D[x + b] == 0:
ans += 1
D[x + b] += 1
S[a] = x + b
print(ans)解説はここまでです。ありがとうございました。
E問題 - 7x7x7
コンテスト中に解けませんでした。
https://atcoder.jp/contests/abc343/submissions/50880512
座標空間上に一辺 7 の立方体を3つ配置する。
立方体が重なっていない部分の体積を$${V_1}$$
立方体が2つ重なっている部分の体積を$${V_2}$$
立方体が3つ重なっている部分の体積を$${V_3}$$
与えられる$${V_1, V_2, V_3}$$が実現可能か判定してね。
取っ掛かりが無さそうで、いかにも全探索問題なので計算量を考えます。
平行移動の幅を$${D}$$として$${x, y, z}$$3方向の移動を考えると1つの立方体について$${O(D^3)}$$、3つで$${O(D^9)}$$です。1辺の長さが 7 で固定なので$${D \leq 7}$$としても、3つの立方体すべてを動かすわけにはいかなさそうです。
1つの立方体を固定すると$${O(D^6)}$$となり、$${0\leq D \leq 21}$$くらいなら全探索できそうです。
平行移動を全探索するコードは簡単に書けます。
""" 実装イメージ """
from itertools import product
V1, V2, V3 = map(int, input().split())
c1 = (0, 0, 0)
D = 21
for c2 in product(range(D), repeat=3):
for c3 in product(range(D), repeat=3):
if solve(c1, c2, c3):
print('Yes')
print(*c1, *c2, *c3)
exit()
print('No')3つの立方体の配置が決まったとはいえ、複数の立方体が重なった部分の体積を求めるのが難しいです。
簡単なことから考える
$$
\begin{rcases}
3 < x < 10 \\
かつ \\
5 < x < 12
\end{rcases}
\rArr 5 < x < 10
$$
これは感覚的に分かりやすいですね。共通部分$${5 < x < 10}$$の長さ$${L_x}$$は$${L_x = 10 - 5 = 5}$$です。
プログラミングで扱えるような式に直すと次のようになります。（これに気付けるかどうかの問題のような気もします。）
$$
\begin{rcases}
3 < x < 10 \\
かつ \\
5 < x < 12
\end{rcases}
\rArr \max(3, 5) < x < \min(10, 12)
$$
次に、共通部分がない場合はどうでしょうか。
$$
\begin{rcases}
3 < x < 10 \\
かつ \\
15 < x < 22
\end{rcases}
\rArr 15 < x < 10 (?)
$$
上と同じように$${15 < x < 10}$$の長さ$${L_x}$$を求めようとすると$${L_x= 10 - 15 = -5}$$です。負の長さは困るので$${L_x = 0}$$とみなします。
2つの立方体について考える
3つの立方体が重なるのはややこしいので2つずつ考えます。
$${x}$$座標のみ見ると、2つの立方体が重なっている領域は
$$
a_1 < x < a_1 + 7 かつ a_2 < x < a_2 + 7
$$
を満たします。前節の考え方を使ってみると、
$$
\begin{rcases}
a_1 < x < a_1 + 7 \\
かつ \\
a_2 < x < a_2 + 7
\end{rcases}
\rArr \max(a_1, a_2) < x < \min(a_1 + 7, a_2 + 7)
$$
です。長さ$${L_{x}}$$は$${s = \max(a_1, a_2), t = \min(a_1 + 7, a_2 + 7)}$$として、$${L_{x} = \max(0, t - s)}$$です
$${y, z}$$軸も同様に$${L_{y}, L_{z}}$$を求めることで、2つの立方体が重なっている領域の体積が判明します。
$${_3C_2}$$通りそれぞれについて体積$${v_i = L_{x_i} \times L_{y_i} \times L_{z_i}}$$を求めておき、ここでは仮に$${V_{2}' = v_1 + v_2 + v_3}$$とします。
3つの立方体について考える
2つの立方体について考えるときと同様の方法に、変数を1つ増やします。
$$
\begin{rcases}
a_1 < x < a_1 + 7 \\
かつ \\
a_2 < x < a_2 + 7 \\
かつ \\
a_3 < x < a_3 + 7
\end{rcases}
\rArr \max(a_1, a_2, a_3) < x < \min(a_1 + 7, a_2 + 7, a_3 + 7)
$$
$${L_{x}, L_{y}, L_{z}}$$を求めることで求めたい体積が判明します。
ここでは仮に$${V_3' = L_{x} \times L_{y} \times L_{z}}$$としておきます。
それぞれの領域の体積は？
まずそれぞれの立方体の体積の総和は$${V_{sum}= 3 \times 7^3}$$です
3つの立方体が重なっている領域の体積$${V_3}$$は前節で求めた$${V_3'}$$と一致します。
2つの立方体が重なっている領域の体積$${V_2}$$も同様ですが、一部「3つの立方体が重なっている領域」が含まれるのでその分を除きます。
3つの立方体それぞれが「3つの立方体が重なっている領域」を保有していることから$${V_2 = V_2' - 3V_3}$$となります。
残った領域の体積$${V_1}$$も一部重なっている領域の体積を除きます。考え方は2つの立方体の時と同じで、$${V_1 = V_{sum} - 2V_2 - 3V_3}$$となります。
平行移動の範囲をどうするか
はじめに「1つの立方体を固定すると$${O(D^6)}$$となり、$${0 \leq D \leq 21}$$くらいなら全探索できそうです。」と言いましたが、$${0 \leq D \leq 21}$$だと無駄があります。
1辺の長さ 7 の立方体3つを重ならないよう一列に並べることをイメージすると、$${0 \leq D \leq 14}$$で十分そうです。$${-7 \leq D \leq 7}$$でも同様です。
実際に、PythonのFirst ACの方のコードを見ると$${15^6}$$でACとなっています。
ところが私の実装では間に合いませんでした。
公式解説には$${-1 \leq D \leq 7}$$まで範囲を絞ってもよいとありますが「理論的証明の有無については不明」ともあるので納得性に欠けます。コンテスト中に思いつけるような、もっと直感的な絞り方がないか (イメージを簡単にするために1次元で) 考えてみます。
1つは$${0 \leq D \leq 7}$$でよくて、残りの1つだけ$${-7 \leq D \leq 7}$$にすればいいんじゃないかな？
この直感をもとに$${15^3 \times 8^3}$$で実装すると AC になりました。
""" upsolve !!! """
from itertools import product
def calc_length(*points: int):
""" 重なっている領域の辺の長さを計算 """
s = max(*points)
t = min(*points) + 7
return max(0, t - s)
def calc_v(*vertexes):
""" 重なっている領域の体積を計算 """
res = 1
for points in zip(*vertexes):
res *= calc_length(*points)
return res
def solve(c1, c2, c3):
""" この配置で条件を満たすか判定 """
v3 = calc_v(c1, c2, c3)
if v3 != V3:
return False
v2 = -v3 * 3
v2 += calc_v(c1, c2)
v2 += calc_v(c2, c3)
v2 += calc_v(c3, c1)
if v2 != V2:
return False
v1 = total - v2 * 2 - v3 * 3
return v1 == V1
V1, V2, V3 = map(int, input().split())
total = 3 * (7 ** 3)
if V1 + V2 * 2 + V3 * 3 != total:
print('No')
exit()
c1 = (0, 0, 0)
for c2 in product(range(-7, 8), repeat=3):
for c3 in product(range(8), repeat=3):
if solve(c1, c2, c3):
print('Yes')
print(*c1, *c2, *c3)
exit()
print('No')入力時点で不可能判定をすると 600 ms、しなくても1700 msでした。
""" 不可能判定 """
if V1 + V2 * 2 + V3 * 3 != total:
print("No")
exit()
$${15^6}$$でも通るようなコードを実装しましょう。
F問題 - Second Largest Query
長さ$${N}$$の数列$${A}$$と$${Q}$$このクエリが与えられる
クエリ1 : $${A_p}$$の値を$${x}$$に変更する。
クエリ 2: $${(A_l, A_{l+1}, …, A_r)}$$における2番目に大きい値の個数を出力してね。
問題文を読んですぐにセグ木の骨組みを作る。
で、終わりました。本記事の投稿時点でまだ解きなおしをしていないので頑張ります。
【追記: 2024/03/05】
解きました。
https://atcoder.jp/contests/abc343/submissions/50932400
公式解説の通りセグ木にこれを乗せるだけです。
とはいえ、この発想に至るまでの道のりと$${op}$$の書き方次第で TLE になるのが難しいところです。
""" (1番目に大きい数, 1番目に大きい数の個数, 2番目に大きい数, 2番目に大きい数の個数) """
def op(x, y):
x1, xc1, x2, xc2 = x
y1, yc1, y2, yc2 = y
if x1 < y1:
x1, y1 = y1, x1
xc1, yc1 = yc1, xc1
elif x1 == y1:
xc1 += yc1
y1, yc1 = 0, 0
if x2 < y2:
x2, y2 = y2, x2
xc2, yc2 = yc2, xc2
elif x2 == y2:
xc2 += yc2
if x2 < y1:
x2, y1 = y1, x2
xc2, yc1 = yc1, xc2
elif x2 == y1:
xc2 += yc1
return x1, xc1, x2, xc2$${x_1, y_1}$$を比較して$${x_1}$$を最大の数として確定させる。
$${x_2, y_2}$$を比較して$${y_2}$$を最小の数として確定させる。
$${x_2, y_1}$$を比較して$${x_2}$$を2番目に大きい数として確定させる。
あとがき
今回のコンテストの結果はABCD4完 38分、順位は3809位、886 perfでした。
C問題で$${x^3 = K}$$の条件を見落としていて10分ほどロスしたのが痛かった…と見せかけて10分早くても1000 perfないので関係なかったかも。
早解きがどうというよりは E か F どっちか解きたかったです。
ではまた～。
【クイズの答え】
""" 出力はどうなる ? """
def solve(k):
value = A[k] + n
ans = max(ans, value)
A = [0, 1, 2, 3, 4, 5]
n = 100
ans = -1
solve(3)
print(ans)
この記事が気に入ったらサポートをしてみませんか？