AtCoder Beginner Contest 178 - AtCoder
今回Eまではずいぶん短く解けました
B 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つの値が同じだと気づいたけど、まあタイムアウトはしないだろうと思ってそのまま提出
python
def solve(N):
nn, pn, np, pp = [8, 1, 1, 0]
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
- 集めるDP
- 公式解説
- 一般式を求めてから計算してる
- 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になるように末尾に十分な余裕を持たせた python
def solve(S):
table = [0] * 2020
table[0] = 1
# [1], [2] = 0
for i in range(3, S + 1):
table[i] = sum(table[i - d] for d in range(3, i + 1))
return table[S] % MOD
- 集めるDP
- 公式解説
- 上記の遷移式を式変形で定数長さに変換してる
E
- 最も遠い点のペアは2通りの斜めの直線に射影した時に、どちらかでの最も遠いペアである
- 1次元の直線上での最も遠いペアは最大値と最小値である
- コードではargmin/argmax使ってるけど「具体的にどのペアか」を特定しなくても距離だけわかれば良いのでmin/maxでよい python
def solve(N, XY):
S = XY.sum(axis=1)
p1 = np.argmax(S)
p2 = np.argmin(S)
D = XY[:, 0] - XY[:, 1]
p3 = np.argmax(D)
p4 = np.argmin(D)
return max(S[p1] - S[p2], D[p3] - D[p4])
