参加記 yukicoder contest 358 - しょぼんブログ

記録

6完, 122人中30位でした超調子がいいので嬉しい！

B問題が難しいのに多くの人類通して怖かった.

A - 非力なレッド (★1.5)

No.2056 非力なレッド - yukicoder
提出 18:23 (0)

解法

B - Ising Model (★2)

No.2057 Ising Model - yukicoder
提出 1:55:04 (1)

解法

すべて $-1$ にすれば $A\times (N-1) + B\times N$ となってどうみても最大値が達成できるからギャグかと思ったが, よく見ると求めるのは最小値だった.
すべて $1$ にすれば $A\times (N-1) - B\times N$ となる. これは $B$ が強いときに良い感じだと思う. 奇数のとき $- A\times (N-1) - B$ , 偶数のとき $-A \times (N-1)$ が $A$ が強いときに良い感じだと思った. この2つでminを取って出力したがWA.
実験してみると, $A$ の係数は $2$ ずつ変えられて,そのときの $B$ の係数は $A$ の係数が $4$ 変わるごとに $2$ ずつ変えられる.
たとえば $(Aの係数, Bの係数)$ で $N=6$ のとき $(-5,0), (-3,2), (-1,2), (1,4), (3,4), (5,6)$ となる.

import itertools
n = int(input())
a = []
for i in itertools.product([-1,1], repeat=n):
    v = 0
    w = 0
    for j in range(n-1):
        v += i[j] * i[j+1]
    for j in range(n):
        w += i[j]
    a.append((v, w))

a.sort()
print(*a,sep="\n")

$A$ を固定して $B$ の最大値を求めたとしても, 「良くない」 $A$ の場合がある. 奇数の $- A\times (N-1) - B$ は良いが, 偶数の $-A \times (N-1)$ は良くない. その一個上の $A$ の $-A \times (N-3) - B\times 2$ は良いやつで, こっちが最適になる可能性があるので, こっちにもminを取る. 結局コードは次のようになる.

n,a,b = map(int,input().split())
ans = a * (n-1) - b * n

if n % 2 == 0:
    ans = min(ans, - a * (n-1))
    ans = min(ans, - a * (n-3) - b * 2)
else:
    ans = min(ans, - a * (n-1) - b)

print(ans)