−目次

HHKBプログラミングコンテスト2025(AtCoder Beginner Contest 388)F,G 問題メモ
- F - Dangerous Sugoroku
  - 問題文
  - 制約
  - 解法
- G - Simultaneous Kagamimochi 2
  - 問題文
  - 制約
  - 解法

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$ 以下とする。

$A=B$ の場合

毎回進めるマスが決まっている。
以下の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$ の形で表せないことを確認すればよい。

$A \lt B$ の場合

$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$ の全てに到達可能と見なせる。

悪いマスが存在しない場合、ある正整数 $k$ に対し、今の位置から $kA～kB$ 先のマスはすべて到達可能である。
$k$ 回の行動で全て $A$ 進んだ場合は $kA$ 進める。
その状態から、どれかの行動で1多く進んだことにすると、 $kA+1$ 進める。
これを繰り返して「 $k$ 回の行動で全て $B$ 進み、計 $kB$ 進んだ」状態にできるので、 $kA～kB$ 進むことは全て可能である。

$kB+1 \ge (k+1)A$ であれば、次の到達可能区間と連続し、以降の全てのマスに到達可能であるといえる。
式を整理すると $k \ge \dfrac{A-1}{B-A}$ より、少なくともざっくり $kA \le A^2 \le 400$ 以上離れていれば、必ず到達可能であると言える。

よって、 $(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})$ で計算できる。