ARC096に参加した (411位) - 天色グラフィティ

f:id:ejinote:20180422104032p:plain

ARC096に参加しました。10分遅刻したものの、30分くらいでCとDをやっつけ、残り時間ずっとEに取り組みましたが解けませんでした。レートは1010→1121になりました。水色が見えてきましたよ！！

前回の記事：

amalog.hateblo.jp

振り返り

C: Half and Half

全部AピザorBピザで買ってから、順にABピザに置き換えればよい。

a, b, c, x, y = map(int, input().split())
ans = a*x+b*y
for i in range(1, max(x, y)+1):
    if i <= min(x, y):
        ans = min(ans, ans-a-b+2*c)
    else:
        if x < y:
            ans = min(ans, ans-b+2*c)
        else:
            ans = min(ans, ans-a+2*c)
print(ans)

D: Static Sushi

問題

方向転換は高々1回であることに気づくのが重要。

スタート地点から見て反時計回りに $A$ 番目の寿司で折り返し、時計回りに $B$ 番目の寿司で撤退した場合、得られるカロリーは以下の通り。

$\displaystyle \sum_{i=1}^A v_{N-i} - 2(C-x_{A}) + \sum_{i=1}^B v_{i} - x_B$

そこで、反時計回り・時計回り、それぞれについて

$i$ 番目の寿司までのどこかで撤退した際に得られる最大カロリー
$i$ 番目の寿司までのどこかで反転してスタートに戻った際に得られる最大カロリー

を保存しておいて、後で足せばOKです。

import numpy as np
N, C = map(int, input().split())
x = np.zeros(N, int)
v = np.zeros(N, int)
for i in range(N):
    x[i], v[i] = map(int, input().split())

gain_f = np.cumsum(v)-x
for i in range(1, N):
    gain_f[i] = max(gain_f[i-1], gain_f[i])

gain_b = np.cumsum(v[::-1])-(C-x[::-1])
for i in range(1, N):
    gain_b[i] = max(gain_b[i-1], gain_b[i])
    
turn_f = np.cumsum(v)-x*2
for i in range(1, N):
    turn_f[i] = max(turn_f[i-1], turn_f[i])

turn_b = np.cumsum(v[::-1])-(C-x[::-1])*2
for i in range(1, N):
    turn_b[i] = max(turn_b[i-1], turn_b[i])

turn_f = np.concatenate(([0], turn_f))
turn_b = np.concatenate(([0], turn_b))

ans = 0
for i in range(N):
    ans = max([ans, gain_f[i]+turn_b[N-1-i], gain_b[i]+turn_f[N-1-i]])
print(ans)