ABC 133 に参戦しました。 30 分程度で C までは順調に解けましたが、 D で完全に詰まりました（悔しい）。結果は 3 完。
うぅ… 13 回目にしてはじめてレート下がりました
ABC133 A – T or T
私たちは \(N\) 人で旅行しようとしており、その交通手段として電車とタクシーがあります。
https://atcoder.jp/contests/abc133/tasks/abc133_a
電車を使うと \(1\) 人あたり \(A\) 円かかります。タクシーを使うと \(N\) 人で \(B\) 円かかります。
全員の交通費の合計は最小でいくらになるでしょうか。
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\) は奇数です。
https://atcoder.jp/contests/abc133/tasks/abc133_d
これらの山の間に \(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\) リットルの水が溜まりました。
各山に降った雨の量を求めてください。この問題の制約下では解が一意に定まることが証明できます。
コンテスト中には 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 して管理してみることにしました。暇な方は御覧ください、間違いがあったら指摘してくださるととても嬉しいです。