ABC-369

A

$URL\:\to$

解法

B

$URL\:\to$ https://atcoder.jp/contests/abc369/tasks/abc369_b

#全探索 #シュミレーション

Python

N = Integer().content
    L, R = [], []
    for i in range(N):
        a,s = String().content
        L.append(int(a)) if s=="L" else R.append(int(a))

    ans = INF

    for i in range(1,100+1):
        for j in range(1,100+1):
            l,r = i,j
            lsum, rsum = 0, 0

            for k in range(len(L)):
                lsum += abs(l-L[k])
                l = L[k]

            for k in range(len(R)):
                rsum += abs(r-R[k])
                r = R[k]

            ans = min(ans, lsum+rsum)

    print(ans)

解法

$L,R$ の置く位置を事前にリストで仕分けしたのちに、 $L,R$ の開始位置をそれぞれ $0 \to 100$ でシュミレーションし、最小値を求める。

C

$URL\:\to$ https://atcoder.jp/contests/abc369/tasks/abc369_c

#尺取り法

int main(void) {
    ll N; scanf("%lld", &N);
    ll A[N+1]; rep(i,0,N) scanf("%lld", &A[i]); A[N]=PINF;

    ll p=0, d=0, ans=0;

    rep(i,0,N) {
        while (1) {
            d = (p+1-i<=1) ? A[p+1]-A[i]:d ;
            if ((A[p+1]-A[p])!=d || (p==N-1)) {
                ans += p-i+1;
                break;
            }
            p = min(p+1, N-1);
        }
    }
    printf("%lld\n", ans);

    return 0;
}

解法

常に $i$ 番目と $i+1$ 番目の数列は成り立つので公差を常に持って置き、尺取りと尺取り $-1$ の差と公差が一致すると尺取りを進め、一致しないならば、カウンタを進める。という風にすると題意を満たすことができる。

D

$URL\:\to$ https://atcoder.jp/contests/abc369/tasks/abc369_d

#DP

Python

N = Integer().content
A = IntegerList().content

do = [0]*(N+1)
de = [0]*(N+1)

for i in range(N):
  do[i+1] = max(do[i], de[i]+A[i])
  if i>0: de[i+1] = max(de[i], do[i]+2*A[i])
print(max(max(do), max(de)))

int main(void) {
    ll N; scanf("%lld", &N);
    ll A[N]; rep(i,0,N) scanf("%lld", &A[i]);

    // 0: even kill,   1: odd kill
    ll dp[2][N+1]; dp[0][0]=dp[1][0]=dp[0][1]=0;
    rep(i,0,N) {
        dp[1][i+1] = max(dp[1][i], dp[0][i]+A[i]);
        if (i>0) dp[0][i+1] = max(dp[0][i], dp[1][i] + 2*A[i]);
    }
    printf("%lld\n", max(dp[0][N], dp[1][N]));

    return 0;
}

解法

$i$ 番目の敵を倒したとき、その敵は奇数目の敵だったのか偶数目だったのかで $2$ 行の $DP$ を持って置くと題意を満たすことができる。のだが、最初の敵を倒したときは必ず奇数目の敵であるのでその例外処理を忘れてはいけない。

E

$URL\:\to$