ABC178
今回Eまではずいぶん短く解けました
https://gyazo.com/57c09e21b8a9b3e3c0b6bc0f73545c95
https://gyazo.com/45df0047d1abaafd8b01e9f272eb7b0c
B
code:python
A, B, C, D = map(int, input().split())
print(max(x * y for x in A, B for y in C, D)) C
状態遷移図を書いて計算
実装してからPN/NPの2つの値が同じだと気づいたけど、まあタイムアウトはしないだろうと思ってそのまま提出
https://gyazo.com/20f29cbcecb773b285054c7c6b69a665
code:python
def solve(N):
for i in range(N - 1):
pp = (pp * 10 + np + pn) % MOD
pn = (pn * 9 + nn) % MOD
np = (np * 9 + nn) % MOD
nn = (nn * 8) % MOD
return pp
公式解説
一般式を求めてから計算してる
Nが10^10くらい大きかったら僕のコードや公式のコードはO(N)だからダメだろうね
D
最初Cの問題の影響で「各項は3〜9」と思い込んでて大きな数の時に答えが合わなくて悩んだ
数列としか言ってないので任意の数だと気付いて、sumのところをrange(3, 10) からrange(3, i + 1)に変えた
加算の対象がSのオーダーで増えるのでダメかな、累積和使う必要があるかな？と思ったがそのままで通った
Sが0,1,2の時それぞれ1,0,0通り。3以上の時は、初項が3なら残りはf(S-3)、4ならf(S-4)…とそこまでに計算した値を足し合わせて求められる
2000までなのに2020で確保してるのは番兵。
最初の、題意の勘違いでは9個手前をみるから、負の時に0になるように末尾に十分な余裕を持たせた
code:python
def solve(S):
for i in range(3, S + 1):
tablei = sum(tablei - d for d in range(3, i + 1)) 公式解説
上記の遷移式を式変形で定数長さに変換してる
https://gyazo.com/8b97a305a09a3177bcf64ae72f20056a
E
最も遠い点のペアは2通りの斜めの直線に射影した時に、どちらかでの最も遠いペアである
1次元の直線上での最も遠いペアは最大値と最小値である
コードではargmin/argmax使ってるけど「具体的にどのペアか」を特定しなくても距離だけわかれば良いのでmin/maxでよい
code:python
def solve(N, XY):
S = XY.sum(axis=1)
p1 = np.argmax(S)
p2 = np.argmin(S)
p3 = np.argmax(D)
p4 = np.argmin(D)
https://gyazo.com/ebc4a71fdf7ba663577c52f71c7f4570
最近はPyPyを使うことが多いのだけど、これはNumpyにベストフィットだと思ったのでNumpyでやりました
ってこの二つが背反なのはAtCoderがPyPy環境にNumpyを入れてないだけなので、入れてもらえると気にしなくて良くなるのだけど。
公式解説