JPRSプログラミングコンテスト2026#2 （AtCoder Beginner Contest 470）E,F,G問題メモ

JPRSプログラミングコンテスト2026#2 （AtCoder Beginner Contest 470）

E - Concentration

問題文

高橋君は神経衰弱のような $1$ 人ゲームで遊んでいます。

$N$ ペア $2N$ 枚のカードがあります。
- $i$ ペア目の2枚のカードにはいずれも整数 $A_i$ が書かれています。
- 異なるペアのカードに書かれた整数は異なります。
$L$ 回失敗するか全てのカードを取るとゲーム終了です。取れたペアに書かれた整数の総和をスコアとします。
スコアを最大化するように最適に行動したときの、ゲーム終了時のスコアの期待値を求めてください。

ゲームに関するより厳密な説明は以下の通りです。
- 高橋君は、以下に述べるこのゲームのルールを知っている。
- 高橋君は $A_1,\dots,A_N$ の値を知っている。
- 長さ $2N$ の列 $(A_1,A_1,A_2,A_2,\ldots,A_N,A_N)$ の並び替えを一様ランダムに $1$ つ取り $B$ とする。
- 最初、高橋君は $B$ のどの値も知らない。高橋君は一度知った $B_i$ の値をそれ以降完全に記憶する。
- ライフを $L$ 、スコアを $0$ 、 $S$ を $\{1,2,3,\ldots,2N\}$ とする。これらの値を高橋君は常に知っている。
- ライフが $0$ になるか、 $S$ が空になるまで以下を繰り返す。
  - 高橋君はこの時点までに得られた情報に基づいて $S$ から要素を $1$ つ選択し $i$ とする。
  - $B_i$ の値が公開され、高橋君はその値を知る。
  - 高橋君はこの時点までに得られた情報($B_i$ の値を含む)に基づいて $S\setminus\{i\}$ から要素を $1$ つ選択し $j$ とする。
  - $B_j$ の値が公開され、高橋君はその値を知る。
  - $B_i=B_j$ ならば、 $S$ から $i,j$ を取り除き、スコアに $B_i$ を加算する。
  - $B_i \neq B_j$ ならば、ライフを $1$ 減らす。
- 高橋君は、ゲーム終了時のスコアの期待値を最大化するように、最適に行動する。

制約

$1 \leq N \leq 200$
$1 \leq L \leq 200$
$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq 10^5$
入力される値は全て整数

解法

丁寧な場合分けとメモ化再帰。

見るからに実装が面倒、かつF,Gが過去問や典型を知ってれば解きやすくてみんなそちらに行ったためか、本番時のAC人数が少なめだが、やることは素直。

神経衰弱そのままなので、ルールや最適な行動はイメージしやすい。
どうするのが最適かというと、以下があったとして、

今までに取れたペアの集合 $S$
一度めくってペアの片割れだけ場所を知ったカードの集合 $T$
まだめくってないカードの集合 $U$

  S      |---T---| |--------U--------|
22 77     1  5  8   ? ? ? ? ? ? ? ? ?

1手目で $T$ をめくるのは情報が増えず意味が無い。 $U$ からめくるのが最適だが、その際、以下の場合分けがあり、各場合の最適な行動も決まっている。

$T$ に含まれる値のもう片方が出る。ペア成立。
まだ出てない値 $a$ が出る。もう一度別の $U$ をめくる。
- ラッキー！今めくった $a$ が出る。ペア成立。
- $T$ のもう片方が出る。今回はミス。ライフが残っていたら次、取れる。
- $T$ でも $a$ でもない新規の値が出る。ミス。めくったのは $T$ に移る。

ここまでで、ある点に気付く。

特定の $A_i$ を狙ってペアを揃えられるわけではない

スコアを高めるためにはなるべく大きい $A_i$ を揃えたいが、どのペアを揃えられるかは完全に運次第となる。

つまり、$S,T,U$ の中の具体的な $A_i$ の構成は考慮しなくてよく、個数さえわかればよい。例えば $|S|=3$ の場合の何らかの確率があったとして、その $3$ ペアの具体的な内訳は、$A$ から3要素選ぶ全ての場合が同様に確からしく確率に含まれている。

よって「スコアの期待値」は、「最終的に取れるペア数の期待値」×「$A$ の平均」で以下のように求められる。

スコア期待値 $=\dfrac{\sum(A)}{N} \times$ ペア数期待値

以下の関数を定義する。

$f(s,t,l):=s$ ペアが完成し、$t$ 個の片割れの場所が判明し、残りライフが $l$ である状態から取れる最終的なペア数期待値

関数内では、上記の $U$ からめくった場合分けのそれぞれを実装してやるとよい。
$s,t \le N, l \le L$ より、$O(N^2L)$ で全ての状態を求められる。

Python3

def solve(n, l, aaa):
    memo = {}

    def recur(s, t, l):
        """ s ペア完成、t 個ペアの片割れ判明、残りライフ l、という状態からのペア完成期待値 """
        if (s, t, l) in memo:
            return memo[s, t, l]
        if s == n or l == 0:
            return s
        rem = n * 2 - s * 2 - t
        res = 0.
        if t > 0:
            # 既存のが出る→1ペア完成
            res += recur(s + 1, t - 1, l) * t / rem
        if rem - t >= 2:
            # 未知のが出る→もう1枚未知のを引く→合う
            res += recur(s + 1, t, l) * (rem - t) / rem / (rem - 1)
            # 未知のが出る→もう1枚未知のを引く→t の中のが出る（次で取れる）
            if t > 0 and l > 1:
                res += recur(s + 1, t, l - 1) * (rem - t) / rem * t / (rem - 1)
            elif t > 0 and l == 1:
                res += s * (rem - t) / rem * t / (rem - 1)

        if rem - t >= 4:
            # 未知のが出る→もう1枚未知のを引く→2枚ともどれとも合わない
            res += recur(s, t + 2, l - 1) * (rem - t) / rem * (rem - t - 2) / (rem - 1)
        memo[s, t, l] = res
        return res

    exp = recur(0, 0, l)
    ans = sum(aaa) * exp / n
    return ans


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

F - Googol Swaps

問題文

英小文字からなる長さ $N$ の文字列 $S$ が与えられます。
また、$M$ 個の $1～N$ の値のペア $(A_1,B_1),...,(A_M,B_M)$ が与えられます。
以下の操作をちょうど $10^{100}$ 回実行したあとの $S$ としてあり得るものの個数を $998244353$ で割ったあまりを求めてください。
- $1$ 以上 $M$ 以下の整数 $i$ をひとつ選び、$S$ の $A_i$ 文字目と $B_i$ 文字目を入れ替える。

制約

$N, M$ は整数
$2 \leq N \leq 2 \times 10^5$
$1 \leq M \leq 2 \times 10^5$
$S$ は英小文字からなる長さ $N$ の文字列
$A_i, B_i$ は整数
$1 \leq A_i \lt B_i \leq N$
$(A_1, B_1), \dots, (A_M, B_M)$ は相異なる

解法

奇置換と偶置換を知っていれば、E問題より手間は少ないかも。

$S$ の各文字を頂点とするグラフを考え、操作可能なindexペア $(A_i,B_i)$ をグラフの辺と見なす。
グラフはいくつかの連結成分に分かれる。各文字は、連結成分を超えて移動させることはできないが、（十分多くの操作を繰り返せる場合）連結成分内なら好きなように並べ替えられる。

,---, ,-,    mとr, iとiとaは自由に並べ替えられる。
m i r i a
  `-----'

1つの連結成分のサイズを $x$、各文字の出現回数を $c_a,c_b,...,c_z$ として、この連結成分内の並べ方は $\dfrac{x!}{c_a!c_b!...c_z!}$ となる。
基本的にはこの値の、全ての連結成分の積が答えとなる。（$F$ とする）

ただし、ある列にswap操作を好きなだけ繰り返して作ることが可能な列というのは、「奇数回の操作で作れる列」と「偶数回の操作で作れる列」が明確に分かれており、それぞれ同数ずつ存在する。

a b c   偶数回のswapで作れる並び: abc, bca, cab
        奇数回のswapで作れる並び: acb, bac, cba

もし、どの連結成分も全て別々の文字で構成されている場合、「ちょうど」$10^{100}$ 回の操作をするためには、どれか1個の連結成分は偶置換か奇置換のいずれかしか達成できない。
よって答えは $F/2$ となる。

一方、いずれかの連結成分に同じ文字が2個以上ある場合、同じ文字を入れ替えた結果は奇置換と偶置換に分かれて存在する。都合のいい方で解釈すればよいので、答えは $F$ となる。

Python3

from collections import Counter

from atcoder.dsu import DSU


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


def solve(n, m, s, pairs):
    uft = DSU(n)
    for a, b in pairs:
        a -= 1
        b -= 1
        uft.merge(a, b)

    MOD = 998244353
    facts, finvs = precompute_factorials(n, MOD)

    found_same = False
    ans = 1
    for grp in uft.groups():
        l = len(grp)
        cnt = Counter(s[i] for i in grp)
        if len(cnt) < l:
            found_same = True
        ans *= facts[l]
        ans %= MOD
        for v in cnt.values():
            if v > 1:
                ans *= finvs[v]
                ans %= MOD

    if found_same == False:
        ans *= pow(2, -1, MOD)
        ans %= MOD

    return ans


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

G - Σex

問題文

長さ $N$ の非負整数列 $A = (A_1, \dots, A_N)$ が与えられます。
$1 \leq l \leq r \leq N$ を満たす整数の組 $(l, r)$ に対する $\mathrm{mex}({A_l, \cdots, A_r})$ の総和を求めてください。
ここで、$\mathrm{mex}({A_l, \cdots, A_r})$ は $A_l, \cdots, A_r$ に含まれない最小の非負整数を表します。

制約

$1 \leq N \leq 3 \times 10^5$
$0 \leq A_i \leq N$
入力される値はすべて整数

解法

答えは、以下のように言い換えられる。

$x=0,1,2,...$ に対しての「$0～x$ を全て含む区間の個数」の総和

ある区間に $0～x-1$ および $x$ が含まれていると、その $x$ はMEXを1上げるのに貢献している、と捉えられる。
ただし複数個含まれていても寄与は $1$ なので、重複には注意する必要がある。「その貢献は、区間で最も左の $x$ のもの」だと決めると重複を除ける。

  i       1  2  3  4  5  6
  A       2  1  0  2  1  4     0～xを含む区間数
  0:     [  [  [*]  ]  ]  ]    左候補3 × 右候補4 = 12
左1:     [  [*   ]  ]  ]  ]    左候補2 × 右候補4 =  8
右1:         x [      *]  ]    左候補1 × 右候補2 =  2  ※左1を含む区間は除く
左2:     [*      ]  ]  ]  ]    左候補1 × 右候補4 =  4
右2+左1:  x [*     *]  ]  ]    左候補1 × 右候補3 =  3  ※左2を含む区間は除く
右2+右1:     x [   *  *]  ]    左候補1 × 右候補2 =  2  ※左2・左1を含む区間は除く
                                                 計 31

$x$ ごとに考える

まずは $x$ ごとに考える。上記の「右2」のように、$x$ 自体の位置は変わらなくても、 $0～x-1$ のどれか1個の位置が変わったら、区間数も変わってくる。
ただし、区間は尺取りっぽい変化をしそうなので、その線で考えていく。

$0～x$ それぞれの最も左の位置の集合を $S=\{p_0,...,p_x\}$ とする。このセットに対する区間数は、以下の2つの候補数の積となる。

左候補は $\min(S)$ より左から、伸ばしていって $0～x$ のいずれかが出現する手前まで
右候補は $\max(S)$ より右であればよい。

セットの中身を変化させるとき、$\min(S)$ の要素を、1つ右の要素に進めれば、尺取りっぽく変化させられる。

x=4
A   ... 3 0 5 1 4 2 0 3 ...
        o o   o o o            この組がそれぞれ「同じ値なら区間内の最も右端」となる区間は、
     ←[           ]→         この範囲

        x o   o o o   o        左端の"3"を1個進める。右端が拡張される。
        |[             ]→     この時、左を伸ばせるのは x の手前まで。

          x   o o o o o        左端の"0"を1個進める。
          |←[         ]→     右端は最大を更新しないので変化しない。

以下の手順によって、$x$ を固定した時の答えが求められる。

$b_x$ を「ここより左に区間を広げてはいけないindex」とし、$b=0$ で初期化する。
$c_x$ を、その時点の $\max(S)$ とする。
以下を繰り返す。
- $m=\min(S)$ とする。
- 今の $0～x$ の構成で取れる区間数は、$(m-b_x)(N-c_x+1)$ となる。これを答えに加算する。
- $m$ を $S$ から削除する。
- $A_m$ の次のindexを $S$ に加える
  - つまり、$A_m=A_r$ かつ $m \lt r$ である最小の $r$ を $S$ に加える。存在しなければ $r=N+1$ とする
- $b_x=m$ で更新する。
- $c_x=\max(c_x,r)$ で更新する。

$S$ を優先度付きキューで管理すれば、$O(N \log{N})$ などで答えを求められる。

だが、これを $x=0,1,2,...$ で毎回おこなうと、TLEとなる。

$x$ をまとめて考える

前述の操作で、更新操作（$S$ から $m$ を削除、次の位置を追加、$b_x,c_x$ の更新）は、複数の $x$ 間で共通している部分が多い。これを上手くまとめれば高速化できそう。

$i=1,2,...$ の順に、その時点の $\min(S)=i$ となるような $x$ に対しての答えを求め、更新処理を行っていく。
そのような $x$ は、「$x \ge A_i$ であるような $x$」が該当する。

i  0 1 2 3 4 5 6 7 8 9
A    3 0 6 1 4 2 0 3 5    bx  cx
x
0     [o]                  0   2
1     [o   o]              0   4
2     [o   o   o]          0   6
3   [o o   o   o]          0   6
4   [o o   o o o]          0   6
5   [o o   o o o     o]    0   9
:

各 $x$ に対する答えへの寄与 $(m-b_x)(N-c_x+1)$ は、$i$ が、各 $x$ の区間左端に来たタイミングで処理する。

例えば $i=1$ について処理する時、影響するのは $x \ge A_i=3$ の範囲である。まず答えへの寄与を求める。

3   [o o   o   o]          0   6    i=1 における寄与は、
4   [o o   o o o]          0   6    x=3,4,... についての (i-bx)*(N-cx+1) の総和
5   [o o   o o o     o]    0   9    (1-0)(N-6+1) + (1-0)*(N-6+1) + (1-0)(N-9+1) + ...

その後、$b_x,c_x$ の更新処理をする。

i  0 1 2 3 4 5 6 7 8 9
A    3 0 6 1 4 2 0 3 5    bx  cx
x
0     [o]                  0   2
1     [o   o]              0   4
2     [o   o   o]          0   6
3    x[o   o   o   o]      1   8    x>=3 について、
4    x[o   o o o   o]      1   8      bx は i で上書き
5    x[o   o o o   o o]    1   9      cx は r で chmax
:

$x \ge A_i$ の範囲について、$b_x$ はそのまま $i$ で上書きすればいい。

$c_x$ は、$A_i$ が次に出現するindexを $r$ として（上例では $r=8$）、$r$ でchmaxする必要がある。存在しない場合は、便宜的に $r=N+1$ としておく。

これを繰り返すと答えとなる。以上を実現できるデータ構造を考える。

$x$ をindexとして遅延セグ木を構築する。 $x$ の実質的な上限は「$A$ に出現しない最小の値 $-1$」だが、場合分けが面倒な場合は $N$ でいい。

載せる値: $b_x$ と $c_x$（およびその管理に必要なデータ）
取得したい値:
- prod(l,r): $[l,r)$ の、$\sum b_x, \sum c_x, \sum b_xc_x$ をそれぞれ求める
必要な更新操作:
- update_b(l,r,k): $[l,r)$ における $b_x$ を $k$ に上書き更新する
- update_c(l,r,k): $[l,r)$ における $c_x$ を $k$ に上書き更新する

各 $x$ に対する初期値は、$b_x=0$、$c_x$ は $O(N)$ で調べられる。
取得したい値は、$i,N$ が所与の時に、$(i-b_x)(N-c_x+1)$ を求めるのに必要な値となる。

ただし、$c_x$ の更新処理 chmax については、工夫が必要となる。一般に、区間chmax・区間和のデータ構造は遅延セグ木では不足で、SegmentTreeBeats が必要となる。（逆に言うと、Beats なら実装できるのだが）

ここで、$c_0,c_1,...,c_{N}$ は、常に広義単調増加が保たれていることが利用できる。
よって、二分探索により「$A_i$ より大きく、$c_x \ge r$ となる最小の $x$」を求めれば（$y$ とする）、 update_c($A_i,y,r$) によって正しく更新できる。

Python3

INF = 1 << 60


class SegmentTreeBeats:
    # 区間 a 代入・区間 chmax(b)・区間 (Σa, Σb, Σab, 要素数) 取得
    # 遅延: (aへの代入値, bへのchmax値)。-INF は「なし」
    # chmax が2番目の最小値以上のノードは子に伝播してから再計算(beats)
    n: int
    log: int
    size: int
    sa: list[int]  # Σa
    sb: list[int]  # Σb
    sab: list[int]  # Σab
    sz: list[int]  # 要素数
    mn: list[int]  # bの最小値
    mn2: list[int]  # bの2番目の最小値
    cnt: list[int]  # 最小値の個数
    sam: list[int]  # 最小値位置のaの総和
    lza: list[int]
    lzm: list[int]

    def __init__(self, aa: list[int], bb: list[int]):
        n = len(aa)
        log = 0
        while (1 << log) < n:
            log += 1
        size = 1 << log
        self.n = n
        self.log = log
        self.size = size
        self.sa = [0] * (2 * size)
        self.sb = [0] * (2 * size)
        self.sab = [0] * (2 * size)
        self.sz = [0] * (2 * size)
        self.mn = [INF] * (2 * size)
        self.mn2 = [INF] * (2 * size)
        self.cnt = [0] * (2 * size)
        self.sam = [0] * (2 * size)
        self.lza = [-INF] * size
        self.lzm = [-INF] * size
        for i in range(n):
            a = aa[i]
            b = bb[i]
            k = size + i
            self.sa[k] = a
            self.sb[k] = b
            self.sab[k] = a * b
            self.sz[k] = 1
            self.mn[k] = b
            self.cnt[k] = 1
            self.sam[k] = a
        for k in range(size - 1, 0, -1):
            self._update(k)

    def _update(self, k: int):
        lc = 2 * k
        rc = 2 * k + 1
        self.sa[k] = self.sa[lc] + self.sa[rc]
        self.sb[k] = self.sb[lc] + self.sb[rc]
        self.sab[k] = self.sab[lc] + self.sab[rc]
        self.sz[k] = self.sz[lc] + self.sz[rc]
        if self.mn[lc] < self.mn[rc]:
            self.mn[k] = self.mn[lc]
            self.mn2[k] = min(self.mn2[lc], self.mn[rc])
            self.cnt[k] = self.cnt[lc]
            self.sam[k] = self.sam[lc]
        elif self.mn[lc] > self.mn[rc]:
            self.mn[k] = self.mn[rc]
            self.mn2[k] = min(self.mn[lc], self.mn2[rc])
            self.cnt[k] = self.cnt[rc]
            self.sam[k] = self.sam[rc]
        else:
            self.mn[k] = self.mn[lc]
            self.mn2[k] = min(self.mn2[lc], self.mn2[rc])
            self.cnt[k] = self.cnt[lc] + self.cnt[rc]
            self.sam[k] = self.sam[lc] + self.sam[rc]

    def _all_apply(self, k: int, asg: int, mx: int):
        if asg != -INF:
            self.sa[k] = asg * self.sz[k]
            self.sab[k] = asg * self.sb[k]
            self.sam[k] = asg * self.cnt[k]
        fail = False
        if mx > self.mn[k]:
            if mx < self.mn2[k]:
                self.sb[k] += (mx - self.mn[k]) * self.cnt[k]
                self.sab[k] += (mx - self.mn[k]) * self.sam[k]
                self.mn[k] = mx
            else:
                fail = True
        if k < self.size:
            if asg != -INF:
                self.lza[k] = asg
            if mx > self.lzm[k]:
                self.lzm[k] = mx
            if fail:
                self._push(k)
                self._update(k)

    def _push(self, k: int):
        asg = self.lza[k]
        mx = self.lzm[k]
        if asg != -INF or mx != -INF:
            self._all_apply(2 * k, asg, mx)
            self._all_apply(2 * k + 1, asg, mx)
            self.lza[k] = -INF
            self.lzm[k] = -INF

    def _apply_range(self, l: int, r: int, asg: int, mx: int):
        if l >= r:
            return
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)
        l2 = l
        r2 = r
        while l < r:
            if l & 1:
                self._all_apply(l, asg, mx)
                l += 1
            if r & 1:
                r -= 1
                self._all_apply(r, asg, mx)
            l >>= 1
            r >>= 1
        l = l2
        r = r2
        for i in range(1, self.log + 1):
            if ((l >> i) << i) != l:
                self._update(l >> i)
            if ((r >> i) << i) != r:
                self._update((r - 1) >> i)

    def change_left(self, l: int, r: int, x: int):
        self._apply_range(l, r, x, -INF)

    def chmax_right(self, l: int, r: int, x: int):
        self._apply_range(l, r, -INF, x)

    def prod(self, l: int, r: int):
        sa = sb = sab = sz = 0
        if l >= r:
            return sa, sb, sab, sz
        l += self.size
        r += self.size
        for i in range(self.log, 0, -1):
            if ((l >> i) << i) != l:
                self._push(l >> i)
            if ((r >> i) << i) != r:
                self._push((r - 1) >> i)
        while l < r:
            if l & 1:
                sa += self.sa[l]
                sb += self.sb[l]
                sab += self.sab[l]
                sz += self.sz[l]
                l += 1
            if r & 1:
                r -= 1
                sa += self.sa[r]
                sb += self.sb[r]
                sab += self.sab[r]
                sz += self.sz[r]
            l >>= 1
            r >>= 1
        return sa, sb, sab, sz


def solve(n: int, aaa: list[int]) -> int:
    pos: list[list[int]] = [[] for _ in range(n + 1)]
    for i, a in enumerate(aaa):
        pos[a].append(i)
    for a in range(n + 1):
        pos[a].append(n)

    max_right = [pos[0][0]]
    for a in range(1, n + 1):
        max_right.append(max(max_right[-1], pos[a][0]))

    sgt = SegmentTreeBeats([-1] * (n + 1), max_right)
    pos_idx = [0] * (n + 1)
    ans = 0
    for i in range(n):
        a = aaa[i]
        sa, sb, sab, _ = sgt.prod(a, n + 1)
        ans += i * n * (n + 1 - a) - i * sb - n * sa + sab
        sgt.change_left(a, n + 1, i)
        pos_idx[a] += 1
        nxt = pos[a][pos_idx[a]]
        sgt.chmax_right(a, n + 1, nxt)
    return ans


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

目次

JPRSプログラミングコンテスト2026#2 （AtCoder Beginner Contest 470）E,F,G問題メモ

E - Concentration

問題文

制約

解法

F - Googol Swaps

問題文

制約

解法

G - Σex

問題文

制約

解法

$x$ ごとに考える

$x$ をまとめて考える