ABC143
あるということに気づいてなくてお酒いただいてしましましたが
まあCまで解ければレートも下がらないだろうということで参加してみたら
意外にすんなりDまで解けて茶コーダーに
パフォーマンスも初の1200超え
一時昨日の結果がなかったことになってましたが
Eに after_contest_00 っていうテストケースが増えてたので
このへんをやり直してたのかな
復習します
A - Curtain
a, b = [int(x) for x in input().split()]py
print(0 if a < 2 * b else a - 2 * b)
と書いて通したんだけどmax
使えよなという話である
print(max(0, a - 2 * b))
B - TAKOYAKI FESTIVAL 2019
普通に二重ループで通したんだけど解説見たらO(N)で解けると書いてある
ひと晩明けて歯を磨いてたらひらめいた
こう
n = int(input())
d = [int(x) for x in input().split()]
print((sum(d) ** 2 - sum([x ** 2 for x in d])) // 2)
数字が a、b、c の三つだとしたら知りたいのは ab + bc + ca
(a + b + c)^2 = a^2 + b^2 + c^2 + 2ab + 2bc + 2ca
だからねと
アルゴリズムというより数学の範囲
C - Slimes
文字が変わるところでカウントアップするだけ
D - Triangles
三つ条件が書いてあるけど、一番長い辺がほかの2辺の和よりも短ければいいので
先に長さでソートしてしまって短い2辺を決めてしまえばいい
あとは3重ループ・・・でやるともちろんTLE
なのはわかってて考え方合ってるかなくらいのつもりで提出したんですが
TLEでもペナルティの5分がつくってことに初めて気づきました
もったいないことした
一番内側のループは二分探索にしてやればOK
E - Travel by Car
ワーシャルフロイドで最短経路を出す
最短経路<=Lなら1、最短経路>LならINFとしてから再度ワーシャルフロイド
2回適用するというのはまったく思いつかず
コンテスト中に自分で書いてやろうとしてそっちに脳のリソースを
割いてしまったのも原因かもしれないけど
そもそもワーシャルフロイドをちゃんと理解できてなかった
PCADでやってはいたんですが身についてませんでしたね
今回復習してばっちりになったはず
2回適用の技も覚えたし
ワーシャルフロイドだけじゃなくて適用範囲は広そう
で書いてみた
def froyd(n, d):
for k in range(n):
for s in range(n):
for t in range(n):
d[s][t] = min(d[s][t], d[s][k] + d[k][t])
def main():
N, M, L = [int(x) for x in input().split()]
INF = float("inf")
A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
for i in range(N):
A[i] = [INF] * N
A[i][i] = 0
B[i] = [INF] * N
B[i][i] = 0
for i in range(M):
a, b, c = [int(x) for x in input().split()]
A[a - 1][b - 1] = c
A[b - 1][a - 1] = c
froyd(N, A)
for s in range(N):
for t in range(N):
B[s][t] = 0 if s == t else 1 if A[s][t] <= L else INF
froyd(N, B)
Q = int(input())
for _ in range(Q):
s, t = [int(x) for x in input().split()]
b = B[s - 1][t - 1] - 1
print(-1 if b == INF else b)
main()
51個のテストケースのうち31個でTLE発生
こりゃだめか
通ったうちで最長のテストケースは 02-random-42 で 1950ms
二次元配列は外側のループでいったん変数に入れた方が速いと聞いた
こうね
def froyd(n, d):
for k in range(n):
for s in range(n):
ds = d[s]
for t in range(n):
ds[t] = min(ds[t], ds[k] + d[k][t])
02-random-42 が 1563msに
けっこう変わったけどTLEは1個減っただけ
全然だめだなあ
そのままpypy3で実行してみる
あら通った
02-random-42 が 544 ms に
はじめからpypy3で提出した方がいいのか?
pypy3だと不利なところって何?