ブログで書いてほしい内容受付中!! 詳しくはこちら

AtCoder Beginner Contest 133 に参加したよ【Python3】【ABC 133】

ABC133に参加したよ

ABC 133 に参戦しました。 30 分程度で C までは順調に解けましたが、 D で完全に詰まりました(悔しい)。結果は 3 完。

サトゥー

うぅ… 13 回目にしてはじめてレート下がりました

ABC133 A – T or T

私たちは \(N\) 人で旅行しようとしており、その交通手段として電車とタクシーがあります。
電車を使うと \(1\) 人あたり \(A\) 円かかります。タクシーを使うと \(N\) 人で \(B\) 円かかります。
全員の交通費の合計は最小でいくらになるでしょうか。

https://atcoder.jp/contests/abc133/tasks/abc133_a

min(A * N, B) が答えになりますね。

回答案

以下のコードで Python3 で 21 ms で AC でした。

N, A, B = map(int, input().split())
print(min(N * A, B))

ABC133 B – Good Distance

\(D\) 次元空間上に \(N\) 個の点があります。 \(i\) 番目の点の座標は \((X_{i1}, X_{i2}, …, X_{iD})\) です。
座標 \((y_1, y_2, …, y_D)\) の点と座標 \((z_1, z_2, …, z_D)\) の点の距離は \( \sqrt{(y_1 − z_1)^2 + (y_2 − z_2)^2 + … + (y_D − z_D)^2} \)です。
\(i\) 番目の点と \(j\) 番目の点の距離が整数となるような組 \((i, j) (i < j)\) はいくつあるでしょうか。

https://atcoder.jp/contests/abc133/tasks/abc133_b

点 \(i, j\) について、この 2 点間の距離を求め、コレが整数かどうかを判定します。

dist(a, b) という関数を定義し、 \(D\) 次元平面上の 2 点 \(a, b\) 間の距離を計算できるようにしておきます。( dist は distance の略)

これが整数かどうかについては、 dist(X[i], X[j]).is_integer() で判定できます。

回答案

以下のコードで Python3 で 18 ms で AC でした。

def dist(a, b):
	res = 0
	for i in range(D):
		res += (a[i] - b[i]) ** 2
	res = res ** 0.5
	return res


N, D = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		if dist(X[i], X[j]).is_integer():
			ans += 1
print(ans)

ABC133 C – Remainder Minimization 2019

非負整数 \(L, R\) が与えられます。 \(2\) つの整数 \(i, j\) を \(L \leq i < j \leq R\) を満たすように選びます。 \((i × j) mod 2019\) の最小値を求めてください。

https://atcoder.jp/contests/abc133/tasks/abc133_c

\((i × j) mod 2019\) という一般的には見慣れない表現がありますが、これは \(i × j\) を \(2019\) で割ったあまりのことです。

普通に考えてしまうと、 \(O((R – L)^2)\) となって時間切れになってしまいます。そこで、ある数を 2019 で割った余りには周期が存在することに着目します。

具体的にいうと、 \(1\) を \(2019\) で割ったあまりと \(1 + 2019 = 2020\) を \(1\) で割った余りは同じになります。少し一般化すると、 \(n \equiv n + 2019\) となりますね。

また、答えとしてありえる値の最小は \(0\) であり、これは \(L\) から \(R\) までに \(2019\) の倍数が存在すれば必ず実現できるとわかります。

\(2019\) の倍数が \(L\) から \(R\) までに存在するためには、\(R – L\) が \(2018\) 以上であれば良いことが分かります。これは \(2019\) の倍数が出てこないときの \(R – L\) の最大が、例えば \(R = 2018, L = 1\) で達成できる \(2017\) になることからわかりますね。

これで計算量はかなり削減できたので、残りは全探索でしらみつぶしに解きましょう。

サトゥー

連続する 2019 個の数字の積は 2019 、その理由もこれに似たような感じですよね。

回答案

以下のコードで Python3 で 785 ms で AC でした。

L, R = map(int, input().split())
if R - L >= 2018:
	print(0)
else:
	ans = 2019
	for i in range(L, R):
		for j in range(i + 1, R + 1):
			ans = min(ans, i * j % 2019)
	print(ans)

ABC133 D – Rain Flows into Dams

円形に \(N\) 個の山が連なっており、時計回りに山 \(1\) , 山 \(2\) , …, 山 \(N\) と呼ばれます。 \(N\) は奇数です。
これらの山の間に \(N\) 個のダムがあり、ダム \(1\) , ダム \(2\) , …, ダム \(N\) と呼ばれます。ダム \(i (1 \leq i \leq N)\) は山 \(i\) と山 \(i+1\) の間にあります (山 \(N + 1\) は山 \(1\) のことを指します)。
山 \(i (1 \leq i \leq N)\) に \(2x\) リットルの雨が降ると、ダム \(i − 1\) とダム \(i\) にそれぞれ \(x\) リットルずつ水が溜まります (ダム \(0\) はダム \(N\) のことを指します)。
ある日、各山に非負の偶数リットルの雨が降りました。
その結果、ダム \(i (1 \leq i \leq N)\) には合計で \(A_i\) リットルの水が溜まりました。
各山に降った雨の量を求めてください。この問題の制約下では解が一意に定まることが証明できます。

https://atcoder.jp/contests/abc133/tasks/abc133_d

コンテスト中には numpy を利用して N 元連立方程式を解こうとしたがうまくいかず。よく考えてみると、どこか 1 頂点が求まれば連鎖的に求まっていくので終わりですね。

あとは、\( X_{i + 1} = 2 A_i – X_i \) に従ってそれぞれを求めます。

回答案

以下のコードで Python3 で 102 ms で AC でした。

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

X[0] = sum(A) - 2 * (sum([A[i] for i in range(N) if i % 2 == 1]))

for i in range(N - 1):
	X[i + 1] = 2 * A[i] - X[i]

print(" ".join(map(str, X)))

余談になりますが、 Github のリポジトリに AtCoder の解いた問題の解答を UP して管理してみることにしました。暇な方は御覧ください、間違いがあったら指摘してくださるととても嬉しいです。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)