AtCoder Regular Contest 123 A,C,D問題メモ

AtCoder Regular Contest 123

A - Arithmetic Sequence

問題

3数 $A,B,C$ がある
「どれか1つに1加える」という操作を繰り返して、 $(A,B,C)$ がこの順に等差数列になるようにしたい
最小の操作回数を求めよ

解法

なんか適切な言い換えがパッとできなかった。

公式Editorialにあるとおり「 $2B-A-C=X$ として $X=0$ なら等差数列」なので、考慮すべきが3数から1つの数 $X$ に減る。 $X$ に2を足すか1引くかして調整すると考えれば楽。

本番では2数を固定して残り1数を調整した。

3数の初期の並びが $\land$ なら $A$ か $C$ を調整する。どちらを選んでも一緒。
$\lor$ なら $B$ を調整する。その場合 $A,C$ の偶奇が異なればどちらかを1だけ調整する必要がある。

Python3

C - 1, 2, 3 - Decomposition

問題

正整数 $N$ を、「全ての桁が1,2,3のみからなる数」の和に分割するとき、最小の分割数を求めよ
1つの入力に $T$ ケースあるので、全てに答えよ
$1 \le T \le 1000$
$1 \le N \le 10^{18}$

解法

0の桁があってはいけないのが厄介。

例えば 412 とかだと、4 は少なくとも2つに分割する必要があるのに、 1 は1つにしか分割できないので、繰り上がりを発生させないといけないことはわかる。

「各桁を何個に分割するか？」を桁毎に考えると、これが広義単調増加になっていればよい。
頭の0は消えるので、桁が下がるにつれ分割数が増えるのはいい。ただ、減るのはアウト。

N     1  4  3  8
----------------
分割  1  2  1  3
(例)     2  1  2
            1  3
----------------
個数  1  2  3  3

なので、各桁、その数を1,2,3に分割できる最小数と最大数を調べ、その間を広義単調増加になるように選んでいけばよい。

N     1  4  3  8
----------------
MIN   1  2  1  3    ←4は分割するのに最低2個必要、8は3個必要
MAX   1  4  3  8
個数  1  2  2  3    ←ここが広義単調増加になるように
                      MIN～MAXの間から（なるべく少なく保ちつつ）選ぶ

じゃあ、412 みたいな例はどうするか？

N    4  1  2
------------
MIN  2  1  1
MAX  4  1  2
     2  x      ←広義単調増加になるように取れない

繰り下げて、「4 1 2」ではなく「3 11 2」として扱えばよい。
更にその次も破綻するので、最終的には「3 10 12」として扱えばよい。

N    3 10 12
------------
MIN  1  4  4
MAX  3 10 12
     1  4  4

でも、上の桁から分割数を決めていくにしても、次の桁以降を見てみないと繰り下げればよいかそのままでよいかわからない。

これは、素直に2通り試して小さい方（あるいは破綻しない方）を取ればよい。
再帰関数で実装すると楽。

1つの桁が取り得るパターンは「上から繰り下げてきたか」「下に繰り下げるか」の4パターンしかないので十分少ないが、メモ化しないと同じケースが何度も呼ばれ、1ケース最大 $2^{17}$ 程度の探索をしてしまうので注意。

Python3

        
          
          
              
              import sys
 
cache = {}
 
 
def recursive(
        give0_take0_min,
        give0_take0_max,
        give0_take1_min,
        give0_take1_max,
        give1_take0_min,
        give1_take0_max,
        give1_take1_min,
        give1_take1_max,
        i,
        t,
        carry,
):
    if (i, t, carry) in cache:
        return cache[i, t, carry]
 
    INF = 1000000
    if i == len(give0_take0_min) - 1:
        if carry:
            if give0_take1_max[i] < t:
                res = INF
            else:
                res = max(t, give0_take1_min[i])
        else:
            if give0_take0_max[i] < t:
                res = INF
            else:
                res = max(t, give0_take0_min[i])
        cache[i, t, carry] = res
        return res
 
    if carry:
        res = INF
        if give0_take1_max[i] >= t:
            res = min(
                res,
                recursive(give0_take0_min, give0_take0_max, give0_take1_min, give0_take1_max,
                          give1_take0_min, give1_take0_max, give1_take1_min, give1_take1_max,
                          i + 1, max(t, give0_take1_min[i]), False),
            )
        if give1_take1_max[i] >= t:
            res = min(
                res,
                recursive(give0_take0_min, give0_take0_max, give0_take1_min, give0_take1_max,
                          give1_take0_min, give1_take0_max, give1_take1_min, give1_take1_max,
                          i + 1, max(t, give1_take1_min[i]), True),
            )
    else:
        res = INF
        if give0_take0_max[i] >= t:
            res = min(
                res,
                recursive(give0_take0_min, give0_take0_max, give0_take1_min, give0_take1_max,
                          give1_take0_min, give1_take0_max, give1_take1_min, give1_take1_max,
                          i + 1, max(t, give0_take0_min[i]), False),
            )
        if give1_take0_max[i] >= t:
            res = min(
                res,
                recursive(give0_take0_min, give0_take0_max, give0_take1_min, give0_take1_max,
                          give1_take0_min, give1_take0_max, give1_take1_min, give1_take1_max,
                          i + 1, max(t, give1_take0_min[i]), True),
            )
 
    cache[i, t, carry] = res
    return res
 
 
def solve(n):
    give0_take0_min = [(c - 1) // 3 + 1 for c in n]
    give0_take0_max = n.copy()
    give0_take1_min = [(c + 9) // 3 + 1 for c in n]
    give0_take1_max = [c + 10 for c in n]
    give1_take0_min = [(c - 2) // 3 + 1 for c in n]
    give1_take0_max = [c - 1 for c in n]
    give1_take1_min = [(c + 8) // 3 + 1 for c in n]
    give1_take1_max = [c + 9 for c in n]
 
    cache.clear()
 
    return recursive(give0_take0_min, give0_take0_max, give0_take1_min, give0_take1_max,
                     give1_take0_min, give1_take0_max, give1_take1_min, give1_take1_max,
                     0, 0, False)
 
 
input = sys.stdin.readline
t = int(input())
buf = []
for _ in range(t):
    n = list(map(int, input()[:-1]))
    buf.append(solve(n))
 
print('\n'.join(map(str, buf)))

            

        
      

D - Inc, Dec - Decomposition

あと5分早く思いつきたかった。

問題

長さ $N$ の整数列 $A_1,A_2,...,A_N$ が与えられる
次の条件を満たす2つの整数列 $B,C$ を考える
条件
- 各 $i$ に対し、 $B_i+C_i=A_i$
- $B$ は広義単調増加（ $B_i \le B_{i+1}$ ）
- $C$ は広義単調減少（ $C_i \ge C_{i+1}$ ）
そのような $B,C$ の中で、以下の値が最小となるものを作り、その最小値を求めよ
- $\displaystyle \sum_{i=1}^{N}|B_i|+|C_i|$
$1 \le N \le 2 \times 10^5$
$-10^8 \le A_i \le 10^8$

解法

まず最小値はともかく、条件を満たす $B,C$ の作り方を考える。

$i=1$ のとき
- $A_1$ が非負なら $B_1=A_1,C_1=0$ とする
- $A_1$ が負なら $B_1=0,C_1=A_1$ とする
$i \ge 2$ のとき
- $A_{i-1} \lt A_i$ なら、 $B_i$ をその増分だけ増やす（ $C_i$ はそのまま）
- $A_{i-1} \gt A_i$ なら、 $C_i$ をその減分だけ減らす（ $B_i$ はそのまま）

とすると、 $B_1$ 、 $C_1$ を上記のように設定した中では $|B_N|$ 、 $|C_N|$ を最小に抑えて構成できる。

A   1  -2   3  -4   5
B   1   1   6   6  15
C   0  -3  -3 -10 -10

ここから、適当な非負整数 $d$ を決め、 $B$ 全体を $d$ 減らし、 $C$ 全体を $d$ 増やすことをしても条件は満たされたままである。
そんな中で、 $\displaystyle \sum_{i=1}^{N}|B_i-d|+|C_i+d|$ を最小化させる $d$ を見つけたい。

絶対値の中身は正負反転させても良いので、 $|C_i+d|→|-C_i-d|$ とする。
すると、「全ての $B_i$ と $-C_i$ を $-d$ だけ平行移動させて、絶対値の和を最小化させる」問題になる。

これは、中央値を0とするような移動が答えの1つとなる。（全体を1増やすと、負である個数だけ答えが減り、正である個数だけ答えが増えてしまうので、正と負の個数が釣り合う点が答えとなる）

$B$ と $-C$ をまとめてソートすると、 $N$ 番目の数が $d$ となる。後は $\displaystyle \sum_{i=1}^{N}|B_i-d|+|C_i+d|$ をその通りに求めればよい。

Python3