AtCoder Beginner Contest 466 E,F問題メモ

AtCoder Beginner Contest 466

E - Range Flip

問題文

$N$ 枚のカードが並んでいます。カードには $1, 2, \ldots, N$ の番号が付けられています。
カード $i$ の表面には整数 $A_i$ が、裏面には整数 $B_i$ が書かれています。はじめ、すべてのカードは表面が上を向いています。
あなたは、以下の操作を高々 $K$ 回行うことができます。
- $1 \leq l \leq r \leq N$ なる整数 $l, r$ を選ぶ。$l \leq i \leq r$ なる各整数 $i$ について、カード $i$ を裏返す。ただし、カードを裏返すとは、操作を行う前に下を向いている面を上に向けることを指す。

操作を終えた後、各カードの上を向いている面に書かれている数の総和として考えられる最大値を求めてください。

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq K \leq 10$
$1 \leq A_i, B_i \leq 10^9$
入力される値はすべて整数

解法

区間 $[l,r]$ 内の裏表をまとめて変化させるという操作は、「基本は1つ左と同じ面を採用するが、$l$ と $r+1$ では1つ左と逆の面を採用する」という「裏表切り替えポイント」を2つ作ると言い換えられる。

最大 $2K$ 個まで、切り替えポイントを自由に作れる。

$\mathrm{DP}[i,j,k]:=i$ までの裏表採用を決めて、使った切り替えポイントが $j$ 個で、最後に取ったのが $k=0:表/1:裏$ の時に達成できる最大スコア

としたDPで、$O(NK)$ で求められる。

Python3

def solve(n, k, cards):
    NINF = -1 << 60
    k2 = k * 2
    dp0 = [NINF] * (k2 + 1)
    dp1 = [NINF] * (k2 + 1)
    dp0[0] = 0
    for a, b in cards:
        ndp0 = dp0.copy()
        ndp1 = dp1.copy()
        for j in range(k2 + 1):
            ndp0[j] += a
            ndp1[j] += b
        for j in range(k2):
            ndp0[j + 1] = max(ndp0[j + 1], dp1[j] + a)
            ndp1[j + 1] = max(ndp1[j + 1], dp0[j] + b)
        dp0 = ndp0
        dp1 = ndp1
    ans = max(max(dp0), max(dp1))
    return ans


n, k = list(map(int, input().split()))
cards = [list(map(int, input().split())) for _ in range(n)]
ans = solve(n, k, cards)
print(ans)

F - Many Mod Calculation

問題文

整数 $N,X$ と長さ $N$ の正整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
非負整数 $x$ に対し、 $f(x)=(\ldots((x \bmod A_1) \bmod A_2) \ldots ) \bmod A_N$ と定義します。
$f(x)=0$ となる $1$ 以上 $X$ 以下の整数 $x$ がいくつ存在するか求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1\le T\le 2\times 10^5$
$1\le N\le 2\times 10^5$
全てのテストケースにおける $N$ の総和は $2\times 10^5$ 以下
$1\le X\le 10^{18}$
$1\le A_i\le 10^{18}$
入力される値は全て整数

解法

「$0$ 以上」$X$ 以下の整数の個数を求めた上で、答えから1引くとする。

$\min_{i=1,...,i-1} \le A_i$ なる $A_i$ は操作の意味が無い（その時点でどのような初期値でも必ず $A_i$ 未満になってるので、$bmod{A_i}$ しても値は変化しない）ので、$A$ は狭義単調減少であるとしてよい。

操作を最後から考えると、最終的に $0$ になるには、最後の操作直前では $A_N$ の倍数である必要がある。
その時点で取り得る値は $A_{N-1}$ 未満であることも考慮すると候補は以下のようになる。

A = (28, 19, 7, 2)  X=35

最終       0
 2操作前  [0)[2)[4)[6)
 7操作前  [0  2  4  6)[7  9 11 13)[14 16 18)
19操作前  [0  2  4  6  7  9 11 13  14 16 18)[19 21 23 25 26)
28操作前  [0  2  4  6  7  9 11 13  14 16 18  19 21 23 25 26)[28 30 32 34 35)

「$A_i$ 操作前にこの値であれば、最終的に $0$ になる値の集合」を $S(i)$ とする。

$S(i)$ は、$S(i+1)$ をひとまとまりと考えて、「$S(i+1)$ そのままの列」「$S(i+1)$ の各項に $A_i$ を足した列」「$2A_i$ を足した列」… を、 $A_{i-1}$ になる直前まで繰り返すことで得られる。

便宜的に $A_0=X+1,S(N+1)=\{0\}$ とすると、端も統一的に考えられる。

ただ、$X \le 10^{18}$ なので、これをそのまま実装するわけにはいかない。

逆（逆の逆なので $i$ の昇順）から考えると、操作は以下のように言い換えられることが分かる。

はじめ、長さ $X+1$ の棒が1本だけある。
$i=1,2,...$ の順に、
- 各棒を左から長さ $A_i$ ずつの長さに切っていく。最後に端数が余ったらそれも1本の棒とする。
最終的な棒の個数が答え

（切った各棒の左側断面が“0”に相当するので、左側断面の個数＝本数＝“0”の個数と見なせる）

1本の棒の処理は divmod で $O(1)$ で計算できる。ある時点で同じ長さの棒はその後もずっと同じ処理となるのでまとめて考えれば良い。各 $i$ 処理時には「その時点での棒の長さの種類数」が計算量にかかってくることになる。

メイン棒（長さ $A_i$ の棒）は大量に発生するのでまとめる効果が高いとして、問題は端数となる棒である。 $A_i$ 処理前に、1種類のメイン棒と、$k$ 種類の端数棒があったとして、最悪の場合、$k+1$ 種類それぞれから別の端数棒が発生する。つまり、$i$ が進むにつれ端数棒の種類数は $1$ つずつ増えていく。 $i=1,2,...,N$ を通しての棒の長さの種類数は $O(N^2)$ となり、間に合わない。

だが、「ある時点で端数である棒」を主軸におき、それが以降にどのような端数に変化していくかの値の変遷を辿ってみると、

棒の長さ $x$ が $x \lt A_i$ の時、処理不要（長さが $i→i+1$ にかけて維持される）
棒の長さ $x$ が $x \ge A_i$ の時、$1$ 個以上のメイン棒と、新たな端数棒（長さ $y$）に分かれる
- メイン棒の方は他からもたくさんできるので、まとめてしまえば実質ノーカウント
- 端数棒の方は、$x \ge 2y$ が成り立ち、$x$ の半分未満である。

よって、値が変化する更新というのは、1つの端数に付き高々 $\log{x}$ 回程度であると言える。
「今の $A_i$ では値が変化しない $x$」を適切に処理対象から外せれば、計算処理回数は $O(N \log{X})$ に限られる。

HeapQue や、SortedContainer を使い、(棒の長さ, その個数) を棒の長さが長い方から取り出せるようにすれば、 $x \lt A_i$ となる $x$ については処理をスキップできる。

そのデータ構造の操作に $O(\log{N})$ かかるとして、全体は $O(N \log{N} \log{X})$ となる。

制約を当てはめるとちょっと厳しそうだが、実装してみると意外と高速に動作する。計算量のかかるケースは「別の長さの棒から生成される端数に重複が少ないこと」と「各端数の初期値（メイン棒からはじめて切り出された端数）が $N$ 回の操作を通していずれも大きく、また処理回数も多い（$\log{初期値}$ 回、しっかり処理対象となる）こと」が両立する必要があるが、それが難しいなどが原因か。

Python3

from sortedcontainers import SortedDict


def solve(n, x, aaa):
    sd = SortedDict({x + 1: 1})
    for a in aaa:
        while sd.peekitem()[0] > a:
            x, c = sd.popitem()
            d, m = divmod(x, a)
            sd.setdefault(a, 0)
            sd[a] += d * c
            if m > 0:
                sd.setdefault(m, 0)
                sd[m] += c
    ans = sum(sd.values()) - 1
    return ans


t = int(input())
for _ in range(t):
    n, x = list(map(int, input().split()))
    aaa = list(map(int, input().split()))
    ans = solve(n, x, aaa)
    print(ans)

目次

AtCoder Beginner Contest 466 E,F問題メモ

E - Range Flip

問題文

制約

解法

F - Many Mod Calculation

問題文

制約

解法