HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)F,G 問題メモ

HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)

GがEの上位互換でほぼ同じロジックを使えるので「問題ページに書いておいてほしかったなあ」とちょっと思った。
ABC386でもFがCの上位互換となっていて、こちらは問題ページにその旨の言及があったけど、なんで今回は無かったんだろうね。
ABC386は入力形式まで完全に一緒の問題だったからかな。

F - Dangerous Sugoroku

• $N$ 個のマスが $1$ 列に並んでおり、順に $1, 2, \ldots, N$ の番号が付けられています。
• $M$ 個の整数組 $(L_1, R_1), \ldots, (L_M, R_M)$ が与えられます。
• マス $j$ はある $i$ に対して $L_i \leq j \leq R_i$ を満たすとき、またそのときに限り 悪いマス であると定めます。
• マス $1$ から以下の行動を繰り返すことでマス $N$ に移動できるか判定してください。
  • 現在位置しているマスをマス $x$ とする。以下の条件をすべて満たすような整数 $i$ を選び、マス $x + i$ に移動する。
    • $A \leq i \leq B$（$A$ 以上 $B$ 以下から好きな目を選んで進める）
    • $x + i \leq N$（$N$ にはちょうどで止まらなければならない）
    • マス $x + i$ は悪いマスでない

• $2 \leq N \leq 10^{12}$
• $0 \leq M \leq 2 \times 10^4$
• $1 \leq A \leq B \leq 20$
• $1 \lt L_i \leq R_i \lt N (1 \leq i \leq M)$
• $R_i \lt L_{i + 1} (1 \leq i \leq M - 1)$
• 入力される値はすべて整数

場合分けして考えることが多くて、漏れなく実装するのに注意を要する。

まず、$R_i+1=L_{i+1}$ のような2つの禁止区間が連続しているものは、ややこしいので事前処理で1つにまとめておく。
以下、$R_i+1 \lt L_{i+1}$ とする。（禁止区間 $i$ と $i+1$ の間には必ず止まれるマスが存在する）

$A,B$ の制約が小さい。
区間長 $R_i - L_i + 1 \ge B$ なる $i$ が1つでもあるなら、その禁止区間を飛び越せないので“No”である。
以下、各禁止区間の長さは $B-1$ 以下とする。

毎回進めるマスが決まっている。
以下の2つを同時に満たせば到達できる。

• $N-1$ を $A$ で割ったあまりが0である
• $(N-1)/A=k$ として、$1+A,1+2A,1+3A,...,1+(k-1)A$ に悪いマスが存在しない

悪いマスは $O(BM)$ 個以下なので、1つ1つについて $1+xA$ の形で表せないことを確認すればよい。

$N$ は馬鹿でかいので、「$\mathrm{DP}[i]:=$ マス $i$ に到達可能」を $O(N)$ などで解くのは無理。
ただし、禁止区間1つずつの長さは $B-1 \le 19$ で非常に短いと見なせる。
禁止区間は $N$ マス全体からするとスカスカなので、禁止区間同士の間を一気に計算できればよい。

     Ri-1                                  Li     Ri
 X X X X o o o o o o o ..... o o o o o o o X X X X X o o o o o o o ...
禁止区間 `---P1--'               `---P2--' 禁止区間  `---P3--'

長さ $B-1$ の区間 $P_1,P_2,P_3$ を、禁止区間の前後にとる。
$i$ 番目の禁止区間を越えるには、$P_2$ のどこかに止まって、次に $P_3$ のどこかに止まることになる。

$P_1$ の中で、1から到達できるマスの集合を $S_1$ とし、既知とする。
$P_2$ の中で $S_1$ から到達できるものを計算し、$S_2$ とする。
さらに、$P_3$ の中で $S_2$ から悪い区間を飛び越して到達できるマスを計算し $S_3$ とする。

$S_3$ を次の $S_1$ として、次の区間 $i+1$ の計算をする、ということを繰り返せばよい。 （最後に、ちょうど $N$ に止まれるか？ということも、似たようにして確認できる）

$S_1→S_2$ を計算したい。

ここで、実は $P_1$ と $P_2$ がある程度離れていれば $P_2$ の全てに到達可能と見なせる。

よって、$(P_2 の最初のマス)-(P_1 の最初のマス)+1 \ge 400$ なら全てに到達可能。
そうでない場合、$t=1,2,...,400$ に対して「何回かの行動で $t$ 進むことは可能か？」を事前計算しておいて、 (出発点, 到着点) の組それぞれを $O(|S_1||P_2|)$ かけて求めればよい。

$S_2→S_3$ も、$S_2$ からそれぞれ $A～B$ マス進んだ場合について $O(|S_2|B)$ かけて求められる。

ここで、いくつかのケースに注意しなければならない。

• $P_3$ と、次以降の禁止区間 $L_{i+1}～R_{i+1},L_{i+2}～R_{i+2},...$ が被っている場合

$S_3$ の計算後、先の禁止区間を全て除いておくなどする必要がある。

  Ri-1                        Li Ri
X X X o o o o o ... o o o o o X X X o X o X o
      `---P1--'     `---P2--'       `---P3--'

• 複数の禁止区間を一気に飛び越す場合

        v計算中の禁止区間
o o X o X o X o o o ...
     |----P1---|
     |-| |----P3---|
     P2                計算中の禁止区間の前後のマスは使わず、
  a           b        aから一気にbへ飛ぶ場合

さっきの解法は1区間ずつ到達可能区間を引き継いでいくことを想定しているので、こういうのが上手く計算できない。

禁止区間後の $P_1,P_3$ は長さ $B-1$ をフルで使うとし、禁止区間前の $P_2$ は前の区間と被らないように定義する。

$S_1→S_2$ を行う際、$j \in S_1$ かつ $R_i \gt j$ である要素については、直接的に $S_3$ に入れると良い。

これで、$O(MB^2)$ （集合から集合を除く計算量によっては $O(MB^2 \log{MB})$ など）で計算できる。

Python3

def solve(n, m, a, b, bans):

    # 隙間のないのはまとめる
    bans2 = [[-1, -1]]
    for l, r in bans:
        if bans2[-1][1] + 1 == l:
            bans2[-1][1] = r
        else:
            bans2.append([l, r])
    bans = bans2[1:]

    bans_set = set()
    for l, r in bans:
        if r - l + 1 >= b:
            return False
        bans_set.update(range(l, r + 1))

    lim = 400
    can_go = [False] * (lim + b)
    can_go[0] = True
    for i in range(lim):
        if not can_go[i]:
            continue
        for j in range(i + a, i + b + 1):
            can_go[j] = True

    dp = {1}
    prev_r = 0
    for l, r in bans:
        p = max(prev_r + 1, r + 1 - b)
        prev_r = r
        if l <= p:
            return False
        q = l - 1
        ndp = set()
        ndp2 = set()
        check = set()

        for i in dp:
            if r < i:
                ndp2.add(i)
            else:
                check.add(i)

        for i in check:
            if p <= i <= q:
                ndp.add(i)
            if p - i > lim:
                if a < b:
                    ndp = set(range(p, q + 1))
                    break
                else:
                    k = (max(i, p) - i - 1) // a + 1
                    ndp.update(range(i + k * a, q + 1, a))
            else:
                for j in range(max(i + 1, p), q + 1):
                    if can_go[j - i]:
                        ndp.add(j)
        ndp -= bans_set
        for i in ndp:
            for j in range(max(a, r + 1 - i), b + 1):
                ndp2.add(i + j)
        ndp2 -= bans_set
        # print(f'{l=} {r=} {dp=} {ndp=} {ndp2=}')
        dp = ndp2

    for i in dp:
        if i == n:
            return True
        if i > n:
            continue
        if n - i > lim:
            if a < b:
                return True
            if (n - i) % a == 0:
                return True
        elif can_go[n - i]:
            return True

    return False


n, m, a, b = map(int, input().split())
bans = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, a, b, bans)
if ans:
    print('Yes')
else:
    print('No')

G - Simultaneous Kagamimochi 2

• $N$ 個の餅が小さいほうから順に並んでいます。
• $i$ 番目 $(1\leq i\leq N)$ の餅の大きさは $A _ i$ です。
• $2$ つの餅 $A,B$ の大きさをそれぞれ $a,b$ としたとき、$a$ が $b$ の半分以下であるとき、かつそのときに限り、餅 $A$ を餅 $B$ の上に乗せて鏡餅を $1$ つ作ることができます。
• 整数の $2$ つ組が $Q$ 個与えられます。
• $i$ 番目 $(1\leq i\leq Q)$ の $2$ つ組を $(L _ i,R _ i)$ として、次の問題をすべての $i$ について解いてください。
  • $L _ i$ 番目から $R _ i$ 番目までの $R _ i-L _ i+1$ 個の餅だけを使って、同時にいくつの鏡餅を作ることができるか求めてください。
  • より厳密には、以下ができるような最大の非負整数 $K$ を求めてください。
    • $L _ i$ 番目から $R _ i$ 番目までの $R _ i-L _ i+1$ 個の餅から $2K$ 個の餅を選んで $K$ 個の $2$ つ組に分け、それぞれの組について一方をもう一方の上に乗せることで鏡餅を $K$ 個作る。

• $2\leq N\leq 2\times 10 ^ 5$
• $1\leq A _ i\leq 10 ^ 9\ (1\leq i\leq N)$
• $A _ i\leq A _ {i+1}\ (1\leq i\lt N)$
• $1\leq Q\leq 2\times 10 ^ 5$
• $1\leq L _ i\lt R _ i\leq N\ (1\leq i\leq Q)$
• 入力はすべて整数

ある区間に対する答えが $k$ 個として、

• $a$（上）になる方の餅は区間の先頭 $k$ 個
• $b$（下）になる方の餅は区間の末尾 $k$ 個
• 左から順番にペアにする

と考えてよい。

A: 4  5  6  7  8  9 10 11 12 13
   a           b
      a                       b    こんなペア群は
         a                 b

A: 4  5  6  7  8  9 10 11 12 13
   a                    b
      a                    b       こんなペア群と置き換えても必ず大丈夫
         a                    b

各 $i$ から、「$2A_i \le A_j$ になる最初の $j$」に対し、「$j-i$」を事前計算し、$C$ とする。
そのようなものが無い場合、$N-i$ とする。
$C$ の意味合いは「自身が上となる場合に、下に置ける餅は最低何個先でなければならないか」となる。

i: 1  2  3  4  5  6  7  8  9 10
A: 4  5  6  7  8  9 10 11 12 13
C: 4  5  6  7  6  5  4  3  2  1
                                 例: i=2, Ai=5 が上になる場合、
      |------------> o  o  o  o      下になる餅はCi=5個先の j=7, Aj=10 以降である必要がある

仮に以下の区間先頭 $k=4$ 個を $a$ 側として使おうと思うと、

A: 4  5  6  7  8  9 10 11 12 13
C: 4  5  6  7  6  5  4  3  2  1
   ~~~~~~~~~~

この中の $C$ の最大値である「$7$」だけindexをずらせば、$b$ として使えるindex群になる。
（逆に言うと、$b$ として使うには、$7$ 以上ずらす必要がある）
これが区間末尾をはみ出る場合、$k$ ペア作るのは無理であることが分かる。

A: 4  5  6  7  8  9 10 11 12 13
C: 4  5  6  7  6  5  4  3  2  1
   ~~~~~~~~~~
   -------------------> ~~~~~~~~~~  この例では、区間をはみ出るので k=4 はNGとわかる。

A: 4  5  6  7  8  9 10 11 12 13
C: 4  5  6  7  6  5  4  3  2  1
   ~~~~~~~
   ----------------> ~~~~~~~        K=3 なら、6ずらしても区間内に収まるのでOKとわかる。

$C$ を事前計算し Sparse Table などに載せれば、区間最大値を $O(1)$ で取得できる。
つまり、クエリに対して $k$ を決め打ったとき、それが可能かどうかが $O(1)$ で判定できる。

各クエリに対して $k$ を二分探索すればよい。$O((N+Q) \log{N})$ で計算できる。

Python3

class SparseTableMax:
    def __init__(self, aaa):
        self.n = len(aaa)
        self.log_n = (n - 1).bit_length() + 1
        self.tables = self._build(aaa)

    def _build(self, aaa):
        n = self.n
        result = [aaa.copy()]
        for i in range(self.log_n - 1):
            prev = result[-1]
            width = 1 << i
            tmp = []
            for j in range(n - width * 2 + 1):
                tmp.append(max(prev[j], prev[j + width]))
            result.append(tmp)
        return result

    def query(self, l, r):
        d = r - l
        if d == 1:
            return self.tables[0][l]
        k = (d - 1).bit_length() - 1
        k2 = 1 << k
        result = max(self.tables[k][l], self.tables[k][r - k2])
        return result


def solve(n, aaa, q, queries):
    r = 0
    bbb = []
    for i, a in enumerate(aaa):
        while r < n and a * 2 > aaa[r]:
            r += 1
        bbb.append(r - i)

    spt = SparseTableMax(bbb)
    ans = []

    for ql, qr in queries:
        ql -= 1
        l = 0
        r = (qr - ql) // 2 + 1
        while l + 1 < r:
            m = (l + r) // 2
            skip = spt.query(ql, ql + m)
            if ql + m + skip <= qr:
                l = m
            else:
                r = m
        ans.append(l)

    return ans


n = int(input())
aaa = list(map(int, input().split()))
q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(q)]
ans = solve(n, aaa, q, queries)
print('\n'.join(map(str, ans)))