Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）E,F問題メモ

Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）

E - Crossing Table Cloth

問題文

$N$ 個のマスが左右一列に並んでいます。左から $i$ 番目 $(1\le i\le N)$ のマスをマス $i$ と呼びます。
$M$ 枚の布があり、布 $i$ $(1\le i\le M)$ を敷くとマス $L_i$ からマス $R_i$ までを覆うことができます。
$Q$ 個のクエリに答えてください。
- $q$ 番目 $(1\le q\le Q)$ のクエリでは整数 $S_q,T_q$ が与えられるので、以下の問題に答えてください。
- $M$ 枚の布の中からちょうど $2$ 枚の布を選んで敷くことで、以下の条件を満たすことができるか判定せよ。
  - マス $S_q$ からマス $T_q$ までは $1$ 枚以上の布で覆われており、それ以外のマスは布で覆われていない。

制約

$1\le N\le 2\times 10^5$
$2\le M\le 2\times 10^5$
$1\le L_i \le R_i\le N$
$1\le Q\le 2\times 10^5$
$1\le S_q \le T_q\le N$
入力される値は全て整数

解法

「ちょうど2枚」というところを読み飛ばし、無駄な実装をしていた。

以下の2通りに限られる。これを効率的に見つける実装をすればよい。

    l                r
①  |---------|         左端が l の布と、右端が r の別々の布が交差する
             |-------|

②  |----------------|  [l,r]を1枚でちょうど覆う布と、それに包含される布からなる
          |----|

以下のようにデータを整理しておけばよい。

$R[l]:=$ 左端が $l$ である布の、右端 $r$ のリスト（ソート済）
$L[r]:=$ 右端が $r$ である布の、左端 $l$ のリスト（ソート済）
$l_{\max}:=$ 左から布とクエリを順に見ていく中で、右端 $r$ を通過した布の中での左端 $l$ の最大値

$i=1,2,...$ の順に、以下をおこなう。

$i=T_q$ であるクエリ $q$ の答えを求める。
- $L[T_q]$ を二分探索し、$S_q$ 以上で最小のものを求め、$x$ とする。存在しなければクエリの答えは No
- $x=S_q$ の場合、1枚で覆える。他に内包される布が1枚あればいい。
  - $L[T_q]$ に、他に左端が $x$ 以上の布がある場合、Yes
  - $S_q \le l_{\max}$ の場合、右端が $T_q$ 未満、左端が $S_q$ 以上の他の布が存在しているので、Yes
  - どちらでも無い場合、No
- $x \gt S_q$ の場合、$S_q$ を左端とした布が必要。
  - $R[S_q]$ を二分探索し、$T_q$ 以下で最大のものを求め、$y$ とする。存在しなければNo
  - $y+1 \ge x$ ならYes。そうでなければNo
$l_{\max}$ を、$L[T_q]$ 内の要素で更新する。

Python3

from bisect import bisect, bisect_left


def solve(n, m, cloths, q, queries):
    lll = [[] for _ in range(n + 1)]
    rrr = [[] for _ in range(n + 1)]
    for l, r in cloths:
        lll[l].append(r)
        rrr[r].append(l)
    for ls in lll:
        ls.sort()
    for rs in rrr:
        rs.sort()
    # print(f'{lll=}')
    # print(f'{rrr=}')

    qqq = [[] for _ in range(n + 1)]
    for qi, (s, t) in enumerate(queries):
        qqq[t].append((qi, s))

    buf = [''] * q
    max_l = -1
    for i in range(1, n + 1):
        for qi, s in qqq[i]:
            li = bisect_left(rrr[i], s)
            if len(rrr[i]) == li:
                buf[qi] = 'No'
                continue
            l = rrr[i][li]
            if l == s:
                if li + 1 == len(rrr[i]):
                    if max_l >= s:
                        buf[qi] = 'Yes'
                    else:
                        buf[qi] = 'No'
                else:
                    buf[qi] = 'Yes'
                continue
            ri = bisect(lll[s], i) - 1
            if ri == -1 or ri == len(lll[s]):
                buf[qi] = 'No'
                continue
            r = lll[s][ri]
            if r + 1 >= l:
                buf[qi] = 'Yes'
            else:
                buf[qi] = 'No'

        if rrr[i]:
            max_l = max(max_l, rrr[i][-1])

    return buf


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

F - Second Gap

問題文

整数 $N$ と長さ $N - 1$ の整数列 $D = (D_1, D_2, \ldots, D_{N-1})$ が与えられます。
$(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ であって、次の条件を満たすものの個数を $998244353$ で割った余りを求めてください。
- すべての $1 \le i \le N - 1$ について、 $(P_i, P_{i+1}, \ldots, P_N)$ の中で最大の値を持つ要素を $P_a$ 、 $2$ 番目に大きい値を持つ要素を $P_b$ とすると $|a - b| = D_i$ である。

制約

$2 \le N \le 2 \times 10^5$
$1 \le D_i \le N - i$
入力される値はすべて整数

解法

細かく条件を整理する必要がある。

後ろからTop2を更新していく過程を考えたとき、$D$ の条件を満たす $i \le N-2$ の各要素は以下の3種類のどれかに分類される。

①そこでTop2の更新が発生してはいけない
②そこでTop2の更新が必ず発生する
③Top2の更新が発生してもしなくてもよい（する場合、$i+D_i$ で更新が発生している必要がある）

以下のようになる。「*」の付いていない箇所は①である。

      i  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
      D  2  2  2  2  2 11 11  5  5  5  5  5  5  2  2  2  2  2  2  2  2  2  1
②(a)                *     *                 *                          *
②(b)                                                       *     *
③(c)    *     *
③(d)                                                 *

②となる箇所
- (a) $D_i \neq D_{i+1}$ である $i$
  - $i$ で更新が発生しない場合、$D_i$ は $D_{i+1}$ の値を引き継ぐ。変化しているということは更新が発生している。
- (b) ②となった $i$ について、連鎖的に $i→i+D_{i}$ を末尾まで辿っていった先
  - $i$ の相方 $i+D_i$ も $i$ の更新時点でTop2で無くてはならない。ならば $i+D_i$ でもTop2を更新している必要がある。
③となる箇所
- (c) 最も左の②(a)を $i$ とした時、$i-D_i,i-2D_i,i-3D_i,...$ のように $D_i$ ずつ遡った箇所
- (d) 以下で示される箇所
  - ②となった $i$ を $i+D_{i}$ が同じグループ毎に分類する。各グループにつき、
    - その中の最小値を $j$ とする。
    - $D_{j-D_j}$ から $D_j$ までが全て同じ値であるとき、$j-D_j$ が③となる。

これらの分類を求める過程で、矛盾が発生する可能性がある。 $i$ を更新するとき、$i+D_i$ はTop2に入っていないといけないので、「直近の更新」が $j$ で発生していたとき、$i+D_i=j$ または $i+D_i=j+D_j$ が成り立っていないといけない。

つまり、更新の発生する $i$ について $[i,i+D_i]$ の区間を考えたとき、以下のどちらかとなるような2区間が存在すれば矛盾する。

交差する
（端を共有せず）完全に内包される

②となった $i$ について矛盾が発生していたら $0$ 通りとなる。
③については、上記の条件で矛盾が発生しないようになっている。

③(d)について補足

      i  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
      D  2  2  2  2  2 11 11  5  5  5  5  5  5  2  2  2  2  2  2  2  2  2  1
②                   *     *                 *              *     *     *
③(d)                                                 *

②に分類された $i$ のうち、$i+D_i=20$ となるような $i$ は $i=18$ のみである。
よって、そこから $D_i=2$ 遡った $16$ は③とできる。

一方で、$i+D_i=18$ となるのは $i=7,13$ の2通りある。この時、末尾から更新していって $i=7$ の時点までは、$i=18$ がTop2であり続けなければならない。よって、例えば $i=13$ から $5$ 遡った $i=8$ で更新すると、$i=7$ を前にTop2から $i=18$ が排除されてしまうため不適。更新することはできないため、①となる。

（index がおかしなことになるが）もし仮に、上例で $i=7$ から左側に $11$ がずっと続いていたら、$i=-4$ は③とできる。

この①～③の分類ができたら、末尾から $i=N-2,N-3,...,1$ の順に挿入DPする。

$a_1$: 直近の②または③で更新した場合の、$P_i～P_N$ の大小関係としてあり得る並びの数
$a_0$: 直近の②または③で更新しなかった場合の、$P_i～P_N$ の大小関係としてあり得る並びの数

2つに分けているのは、③と③が連続する箇所の更新では、直前の③で更新したかどうかで遷移が変わるためである。

初期値は $a_1=2$、$a_0=0$ とする。$a_1$ は末尾2要素の大小関係が定まっていないため、$2$ となる。

①
- $P_i$ がTop2を更新しない場合、Top2以外のどの大小関係の並びに挿入しても良い。候補は $N-i-1$ 箇所
- $a_0←a_0 \times (N-i-1)$
- $a_1←a_1 \times (N-i-1)$
②
- 以下の差し引きで、倍加は発生しない。
  - 今まで大小関係の分からなかったTop2の関係が後付けで確定するので $1/2$
  - $P_i$ が最大値か2番目のどちらになるかで2通り
- $a_1←(a_0+a_1)$
- $a_0←0$
③
- ①と②のハイブリッドとなる。更新する場合は、直近でも更新した場合（$a_1$）からしか遷移できない点に注意。
- $a_1$ はそのまま
- $a_0←(a_0+a_1) \times (N-i-1)$

計算量は $O(N)$

Python3

def solve(n, aaa):
    def make_updatable():
        # 末尾から見ていったとき、そこでTop2が 0:更新されない 1:必ず更新される 2:どちらでもよい
        updatable = [-1] * n

        rightmost_update = -1
        for i in range(n - 1):
            is_updater = False
            if updatable[i] == 1:
                is_updater = True
            elif i < n - 2 and aaa[i] != aaa[i + 1]:
                updatable[i] = 1
                is_updater = True

            if is_updater:
                j = i + aaa[i]

                if rightmost_update != -1 and rightmost_update != j and rightmost_update != i:
                    return None

                if updatable[j] == -1:
                    updatable[j] = 1
                    if i >= aaa[i] and updatable[i - aaa[i]] == 0 and all(
                            aaa[k] == aaa[i] for k in range(i - aaa[i], i)):
                        updatable[i - aaa[i]] = 2

                rightmost_update = j

            else:
                updatable[i] = 0

        for i in range(n - 1):
            if updatable[i] != 0:
                for j in range(i - aaa[i], -1, -aaa[i]):
                    updatable[j] = 2
                break
        else:
            # 全てが1
            for i in range(n - 2):
                updatable[i] = 2

        return updatable

    updatable = make_updatable()
    # print(f'{updatable=}')
    if updatable is None:
        return 0

    ans1 = 2  # 直近の更新できる機会（updatable = 1 or 2）において、更新した場合の数
    ans2 = 0  # 直近の更新できる機会において、更新しなかった場合の数
    MOD = 998244353
    for i in range(n - 3, -1, -1):
        insertable = n - i - 2
        if updatable[i] == 0:
            ans1 = ans1 * insertable % MOD
            ans2 = ans2 * insertable % MOD
        elif updatable[i] == 1:
            ans1 = (ans1 + ans2) % MOD
            ans2 = 0
        else:
            ans2 = (ans1 + ans2) * insertable % MOD

        # print(f'{i=} {updatable[i]=} {others=} {ans1=} {ans2=}')

    ans = (ans1 + ans2) % MOD
    return ans

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

目次

Polaris.AI プログラミングコンテスト 2026（AtCoder Beginner Contest 457）E,F問題メモ

E - Crossing Table Cloth

問題文

制約

解法

F - Second Gap

問題文

制約

解法