【Python3】【ABC 133】AtCoder Beginner Contest 133 参加記録

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)$ の点の距離は

$$\begin{align*} \sqrt{(y_1 − z_1)^2 + (y_2 − z_2)^2 + … + (y_D − z_D)^2} \end{align*}$$

です。
$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 して管理してみることにしました。暇な方は御覧ください、間違いがあったら指摘してくださるととても嬉しいです。