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辺を決めてしまえばいい

あとは3重ループ・・・でやるともちろんTLE
なのはわかってて考え方合ってるかなくらいのつもりで提出したんですが
TLEでもペナルティの5分がつくってことに初めて気づきました
もったいないことした

一番内側のループは二分探索にしてやればOK

E - Travel by Car

ワーシャルフロイドで最短経路を出す
最短経路<=Lなら1、最短経路>LならINFとしてから再度ワーシャルフロイド

２回適用するというのはまったく思いつかず
コンテスト中に自分で書いてやろうとしてそっちに脳のリソースを
割いてしまったのも原因かもしれないけど
そもそもワーシャルフロイドをちゃんと理解できてなかった
PCADでやってはいたんですが身についてませんでしたね
今回復習してばっちりになったはず

２回適用の技も覚えたし
ワーシャルフロイドだけじゃなくて適用範囲は広そう

で書いてみた

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だと不利なところって何？