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 \lt 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を更新していく過程を考えたとき、$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
   D  2  2  2  2  2 11 11  5  5  5  5  5  5  2  2  2  2  2  2  2  1
②                *     *                 *              *     *
③    *     *                                      *

• ②となる箇所
  • $D_i \neq D_{i+1}$ である $i$
    • 更新が発生しないと当然、$D_i$ は $D_{i+1}$ の値を引き継ぐ。変化しているということは更新が発生している。
  • ②となった $i$ について、連鎖的に $i→i+D_{i}$ を末尾まで辿っていった先
    • $i$ の相方 $i+D_i$ も $i$ の更新時点でTop2で無くてはならない。ならば $i+D_i$ でもTop2を更新している必要がある。
• ③となる箇所
  • 最も左の②を $i$ とした時、$i-D_i,i-2D_i,i-3D_i,...$ のように $D_i$ ずつ遡った箇所
  • 「$i+D_{i}$ を指しているような②の中で、最も左側の $i$」を $j$ とする。
    • $D_{j-D_j}$ から $D_j$ までが全て同じ値であるとき、$j-D_j$ が③となる。

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

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

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

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

③となる箇所の2項目目について、再掲した以下の例で補足する。

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

例では $i+D_i=20$ となるような $i$ は、$i=18$ のみである。
$i+D_i=20$ となるような $i$ の中で $18$ が最も左であり、そこから $D_i=2$ 遡った $16$ は③とできる。

一方で、$i+D_i=18$ となるのは $i=7,13,16$ の3通りある。 この時、末尾から更新していって $i=7$ の時点までは、$i=18$ がTop2であり続けなければならない。 よって、例えば $i=13$ から $5$ 遡った $i=8$ は、同じ数字が $D_i$ だけ続いてはいるが、③にはならない。
（更新してしまったら $i=7$ を前にTop2から $i=18$ が排除されてしまう）

この①～③の分類ができたら、末尾から $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)

G - Catch All Apples

• 数直線上に $N$ 個のリンゴが落ちてきます。リンゴ $i$ は時刻 $T_i$ に座標 $X_i$ に落ちてきます。
• あなたは数直線上にいくつかのリンゴロボを置いて $N$ 個のリンゴを全て回収したいです。リンゴロボは好きな座標に配置することができます。
• リンゴロボは時刻 $0$ から作動し、数直線上を左右に速さ $1$ 以下で自由に動かすことができます。複数のリンゴロボが同じ時刻に同じ座標にいることもできます。各リンゴロボは時刻 $T_i$ に座標 $X_i$ にいる時、またその時に限りリンゴ $i$ を回収することができます。
• 全てのリンゴを回収するために必要なリンゴロボの台数の最小値を求めてください。

• $1\le N\le 3\times 10^5$
• $0\le T_i\le 3\times 10^5$
• $0\le X_i\le 3\times 10^5$
• $(T_i,X_i) \neq (T_j,X_j)$ $(i\neq j)$
• 入力される値は全て整数

言い換えに気付けば単純。

   x→
t↓        🤖
         ↙  ↘
       ↙      ↘

ロボットの動ける範囲はナナメ45度線に挟まれた範囲となる。適切に座標回転させると、

y↑ ↑
 │ ↑
 │ 🤖→→
 ┼───→x

上か右にしか動けない、と考えることができる。こうするには、$(x,y)=(T_i-X_i,T_i+X_i)$ とすればよい。

回転後のリンゴの座標 $(x,y)$ をソートして、$y$ 座標だけ取り出したものを $Y=(y_1,...,y_N)$ とする。
この時、$y_i$ を取るのに使ったロボットは、$i+1$ 以降は $y_i \le y_j$ であるような $y_j$ しか取れないことになる。

直感的には、「$y_i$ を取るのは、その時点で $y_i$ 以下で最大の $y$ 座標にいるロボット。無ければ追加する」という 貪欲的なアルゴリズムが良さそうに見える。

そして実際にそれが成り立つ。

答えは「$Y$ をいくつかの増加部分列に分割するとき、最小でいくつに分割すれば十分ですか」という問題となる。
これは Dilworth の定理より「$Y$ の最長減少部分列の長さ」が答えとなることが知られている。

• 競プロで使う Dilworth の定理 - miscalc のブログ

Python3

from bisect import bisect_left


def solve(n, apples):
    rotated = [(t - x, t + x) for t, x in apples]
    rotated.sort()

    lds = []
    for x, y in rotated:
        i = bisect_left(lds, -y)
        if i == len(lds):
            lds.append(-y)
        else:
            lds[i] = -y

    ans = len(lds)
    return ans


n = int(input())
apples = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, apples)
print(ans)