AtCoder Regular Contest 120 A,C,E問題メモ

AtCoder Regular Contest 120

変な凡ミスがあったけど、別に無くてもそこまで順位は変わらない。そういうもの。

A - Max Add

• 数列 $a=(a_1,a_2,a_3,...,a_k)$ に対して、$f(a)$ を以下に定義する
• $f(a)$ の定義
  • 以下の操作を $i=1～k$ まで1回ずつ行う
    • その時点の $a$ の最大値を $a_i$ に足す
  • 全ての操作終了後の $a$ の総和を $f(a)$ とする
• いま、数列 $A=(A_1,A_2,...,A_N)$ が与えられる
• $k=1～N$ について、$A$ の先頭 $k$ 項を $a$ としたときの $f(a)$ をそれぞれ求めよ
• $1 \le N \le 2 \times 10^5$
• $1 \le A_i \le 10^7$

1個1個に足される数を分解する。

要素は全て正なので、最大値を足したら、次の最大値はさっき足されたその数になる。

    3  1  4  1  5
→  8  1  4  1  5
→  8  9  4  1  5
→  8  9 13  1  5
→  8  9 13 14  5
→  8  9 13 14 19

これは、こう分解される。

   3  1  4  1  5    ← 初期値
+  5  5  5  5  5    ← 初期の最大値
+     3  4  8  9    ← 累積和
   -------------
   8  9 13 14 19

$f(a)$ はこの総和を求めるが、縦に足すより横に足した方が見通しがよい。

$k$ を固定すると、

• $A_1～A_k$ の和
• $\max(A_1～A_k) \times k$
• $A_1～A_{k-1}$ の累積和の和

の合計値が $f(a)$ となる。

Python3

from itertools import accumulate

n = int(input())
aaa = list(map(int, input().split()))
acc_add = list(accumulate(aaa))
acc_max = list(accumulate(aaa, func=max))
acc_acc = [0] + list(accumulate(acc_add))

for k in range(n):
    ans = acc_add[k] + acc_max[k] * (k + 1) + acc_acc[k]
    print(ans)

C - Swaps 2

• 長さ $N$ の2つの数列 $S,T$ が与えられる
• $S$ に以下の操作を繰り返して $T$ に一致させたい
• 操作
  • $S_i$ と $S_{i+1}$ を入れ替える
  • $S_i$ に1加算する
  • $S_{i+1}$ を1減算する
• 可能か判定し、可能なら最小の操作回数を求めよ

操作の相方が何であれ、1つ左に動くと+1され、右に動くと-1される。

たとえばはじめ $i=3$ にあった数が $j=6$ で終わるとき、 どのように入れ替えようと必ず値は $S_3+(3-6)$ になる。

なので、最終的に位置 $j$ に持っていったときに値 $T_j$ になる $S_i$ というのは 何でもよいわけでは無く、限られる。

S   8  5  4 [7] 4 [5]  ← [ ]: i=1 に持っていった時に10になるSi
T  10  5  6  7  4  1

実は、「値と添字の和」が不変である。

i   0  1  2  3  4  5
S   8  5  4  7  4  5
--------------------
S'  8  6  6 10  8 10

S   6↔7  4  7  4  5    i=0,1 入れ替え後
--------------------
S'  6  8  6 10  8 10    S'では値不変で i=0,1 が入れ替わっている

なので、$S'$ と $T'$ で構成要素が異なっていれば不可能。
同じなら、各数字を対応づけていく。

T' 10  6  8 10  8  6
    1  2  3  4  5  6  ← T'の並び順につけた番号

S'  8  6  6 10  8 10
    3  2  6  1  5  4  ← それぞれのS'上での位置に並び替えた列

同じ数字が複数ある場合は、 例えば10なら、$T'$ の中で1番目に出てくる10は $S'$ の中でも1番目に出てくる10と対応づける。
そうしないと無駄に回数が増える。

3 2 6 1 5 4 を隣り合う2数のスワップによって 1 2 3 4 5 6 にする操作回数が答えとなる。

これは転倒数を求める問題に帰着でき、$O(N\log{N})$ で求められる。

Python3

from collections import defaultdict
from operator import add


class FenwickTreeInjectable:
    def __init__(self, n, identity_factory, func):
        self.size = n
        self.tree = [identity_factory() for _ in range(n + 1)]
        self.func = func
        self.idf = identity_factory
        self.depth = n.bit_length()

    def add(self, i, x):
        tree = self.tree
        func = self.func
        while i <= self.size:
            tree[i] = func(tree[i], x)
            i += i & -i

    def sum(self, i):
        s = self.idf()
        tree = self.tree
        func = self.func
        while i > 0:
            s = func(s, tree[i])
            i -= i & -i
        return s


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

adx = [i + a for i, a in enumerate(aaa)]
bdx = [i + b for i, b in enumerate(bbb)]

if sorted(adx) != sorted(bdx):
    print(-1)
    exit()

a_pos = defaultdict(list)
b_pos = defaultdict(list)
for i, a in enumerate(adx):
    a_pos[a].append(i)
for i, b in enumerate(bdx):
    b_pos[b].append(i)

atr = [0] * n
for b in b_pos.keys():
    for ai, bi in zip(a_pos[b], b_pos[b]):
        atr[ai] = bi + 1

ans = 0
fwt = FenwickTreeInjectable(n + 5, int, add)
for i, a in enumerate(atr):
    fwt.add(a, 1)
    ans += i + 1 - fwt.sum(a)

print(ans)

E - 1D Party

• $N$ 人が、数直線上の位置 $S_1,S_2,...,S_N$ にいる
  • $S_i$ は全て偶数
• 各人は、1秒間に1以下の速さで正または負に自由に移動できる
• 全ての隣接する人の組 $(i,i+1)$ について、同じ座標にいる瞬間が少なくとも1回あるようにしたい
• それが実現できるのは最も早くて何秒後か、答えよ
• $2 \le N \le 2 \times 10^5$

わかってしまえば、実装は簡単な1次元DP。

各人の挙動を、時間を縦軸に取ったグラフで考えると、こんなような感じになる。

o    o      o    o       o
 ＼／        ＼／      ／
   ＼        ／＼    ／
     ＼    ／    ＼／
       ＼／

仮にある人が、自分は動かず相手を待つ（あるいは速さ1未満で動く）挙動を取ったとき、 動き続けた場合と比べて損することはあっても得はしないので、全員、常に速さ1で動き続けるとして問題ない。

1    2           3      1    2           3
o    o           o      o    o           o
 ＼  |         ／   ＝   ＼／          ／
   ＼|       ／            ＼        ／
     ＼    ／                ＼    ／
       ＼／                    ＼／
     ↑2は、1とどこで出会っても、3と出会う時間は変わらない
       むしろ1が2と出会った後に左移動する必要があった場合、徒にそれを遅らせるだけになる

端以外の人は、左の人とごっつんこしてから即座に引き返して右の人とごっつんこする （あるいは左右逆）というような挙動となる。

T字やクロスしている部分は、実際には両者が接触して引き返しているが、 時間を求める上ではそのまますれ違って直進していると考えても問題ない。

すると、グラフ上の全ての線はいずれかの人から伸びる直線となり、 かかる最大時間は「何らかの条件を満たす、初手右に動く $i$ と、初手左に動く $j$ の2点間距離/2」となる。

どういう2人なら問題文の条件に沿うかというと、$(i,j)$ を結ぶとして、

     i                j
o    o    o  o o o    o   o
      ＼／        ＼／
      ／＼        ／＼
          ＼    ／
            ＼／

• $i+1$: 初手左に動いて、$i$ より左のどこかとペアにする
• $j-1$: 初手右に動いて、$j$ より右のどこかとペアにする
• $i+2～j-2$: どう動こうと、$i,j$ から伸びる直線が閉じるまでには両隣と会える

ここで、$i+1$ が初手右に動いたりすると、$(i,j)$ が有効な組み合わせでなくなる。

     i                j
o    o   ◎  o o o    o   o
      ＼  ＼／    ＼／
        ＼／＼    ／＼
        ／＼  ＼／
      ／  ↑
          ここの軌跡は実際は◎のものであり、
          もう両隣と出会えているため必要なくなる

ので、やはり $i+1$ は初手左、$j-1$ は初手右に動くと考えてよい。

すると、$i+1,j-1$ の2点は別の点であり、 少なくともペアにする2点の間には、さらに2点がないといけないことがわかる。

（※$i=1$ や $j=N$ の場合は、左右いずれか片方とペアにするための点が必要ないので、1点でよい）

時間を短くするためにはなるべく近い2点を結ぶのがよく、それなら2点おきずつに結べばよさそう。
この各人の軌跡は、ちゃんと両隣の人との接触を満たしている。

このように結んだ中の、縦軸の最大値が答えとなる。

o   o   o   o   o   o   o ...
 ＼  ＼／    ＼／    ＼／
   ＼／＼    ／＼    ／＼
         ＼／    ＼／

だが、2点間距離に差があると、1つずらした方が良いこともある。

  o   o   o   o           o   o           o   o ...
1  ＼  ＼／    ＼        ／    ＼        ／
2    ＼／＼      ＼    ／        ＼    ／
3          ＼      ＼／            ＼／
4            ＼    ／＼            ／＼
5              ＼／    ＼        ／
6                        ＼    ／
7                          ＼／

  o   o   o   o           o   o           o   o ...
1  ＼      ＼／            ＼／            ＼／
2    ＼    ／＼            ／＼            ／
3      ＼／    ＼        ／    ＼        ／
4                ＼    ／        ＼    ／
5                  ＼／            ＼／

その場合でも、間に3点（端なら2点）が挟まれるケースを考えれば十分で、 4点以上偶数点挟むとズレが戻り2点と同じことになり、奇数点だと3点と同じことになる。

なので、以下のDPを考えればよい。

• $DP[i]=$ 先頭 $i$ 人目までで問題を考え、$i-1$ 人目は初手右に動けるような状態における最大時間の最小値

$DP[i]$ は、以下の小さい方となる。

• $\max(DP[i-2], \frac{A_i-A_{i-3}}{2})$
  • 3つ前の点と結び、間に2点を挟む
• $\max(DP[i-3], \frac{A_i-A_{i-4}}{2})$
  • 4つ前の点と結び、間に3点を挟む

ただ前述の通り、端のペアだけは、挟むのは1点or2点でいいので処理を別にする。

また、$N$ が小さいケースは例外処理として別途片付けておく。

Python3

def solve(n, aaa):
    if n == 2 or n == 3:
        return (aaa[-1] - aaa[0]) // 2
    if n == 4:
        return max(aaa[2] - aaa[0], aaa[3] - aaa[1]) // 2

    aaa.append(aaa[0])

    # DP[i]: i番目までを満たすようにする（i番目の人は初手左移動）のにかかる時間
    dp1 = aaa[2] - aaa[0]  # 1つ前のDPの値
    dp2 = 0  # 2つ前のDPの値
    dp3 = 0  # 3つ前のDPの値

    for i in range(3, n - 1):
        dp0 = min(
            max(dp2, aaa[i] - aaa[i - 3]),
            max(dp3, aaa[i] - aaa[i - 4]),
        )
        dp3 = dp2
        dp2 = dp1
        dp1 = dp0

    ans = min(
        max(dp1, aaa[n - 1] - aaa[n - 3]),
        max(dp2, aaa[n - 1] - aaa[n - 4]),
    ) // 2

    return ans


n = int(input())
aaa = list(map(int, input().split()))

print(solve(n, aaa))