AtCoder Regular Contest 192 (Div. 2) A,B,C,D,E問題メモ

AtCoder Regular Contest 192 (Div. 2)

A - ARC Arc

問題文

正整数 $N$ と、長さ $N$ の $0$ または $1$ からなる数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
長さ $N$ の英大文字のみからなる文字列 $S$ であって、以下の操作を $0$ 回以上好きな回数行うことで $A$ に $0$ が含まれないようにできるものを良い文字列と呼びます。
次のうちどちらかを選び、実行する。
- $1\leq i\leq N$ なる整数 $i$ であって $S_i=$ A、$S_{i+1}=$ R、$S_{i+2}=$ C となるものを選び、$A_i,A_{i+1}$ を $1$ に置き換える。
- $1\leq i\leq N$ なる整数 $i$ であって $S_{i+2}=$ A、$S_{i+1}=$ R、$S_i=$ C となるものを選び、$A_i,A_{i+1}$ を $1$ に置き換える。
ここで、$S_i$ $(1\leq i\leq N)$ で $S$ の $i$ 文字目を表し、$S_{N+1}=S_1,S_{N+2}=S_2,A_{N+1}=A_1$ とします。

良い文字列が存在するか判定してください。

制約

$3\leq N\leq 200000$
$A_i\in \lbrace 0,1 \rbrace$ $(1\leq i\leq N)$
入力はすべて整数

解法

ARCRARCRA… のように“ARC”と“CRA”を重ね合わせつつ繰り返せばほとんどの $A_i$ は“1”に置き換えることができる。

特に、[ARCR…ARCR] のように最後の“A”の手前で切って最初に戻るものは、全て“1”にできる。
このようなことができるのは、$N$ が $4$ の倍数の時である。

4で割ったあまりで場合分けすることを考えると、1か3の場合は、

N%4
  1    ARCR...ARCRA
       1111...11110      ←操作により1にできる位置
  3    ARCR...ARCRARC
       1111...1111110    ←操作により1にできる位置

いずれも最後の位置だけ操作により“1”にすることができない。
逆に言うと、ここが初期状態で“1”だった場合は良い。
indexはループしていて任意の位置に合わせられるため、初期状態に“1”が1つでもあれば良い。

2余る場合が厄介。この場合、2箇所はどうしても“1”にできない。この位置に初期状態で“1”があるなら良い。

N%4
  2    ARCR...ARCRAR
       1111...111100

ただ、2つの“1”は連続している必要は無い。2つの「偶数個の“1”+“0”」に分け、この“0”の両方に初期状態を合わせられればよい。

       ARCR...ARCARCR...ARCRA
       1111...1101111...11110

この時、2つの“0”のindexの偶奇は異なっている。
初期状態で $A_i=$“1” である $i$ を偶奇に分けた時、いずれにも1つ以上あれば良い。

Python3

def solve(n, aaa):
    if n % 4 == 0:
        return True
    if n % 2 == 1:
        return any(a == 1 for a in aaa)
    even = False
    odd = False
    for i, a in enumerate(aaa):
        if a == 1:
            if i % 2 == 0:
                even = True
            else:
                odd = True
    if even and odd:
        return True
    return False


n = int(input())
aaa = list(map(int, input().split()))
if solve(n, aaa):
    print('Yes')
else:
    print('No')

B - Fennec VS. Snuke 2

問題文

フェネックとすぬけくんがボードゲームで遊んでいます。
正整数 $N$ と、長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。また、集合 $S$ があり、はじめ $S$ は空集合です。
フェネックとすぬけくんは、フェネックから順に次の一連の操作を交互に行います。
- $1\leq A_i$ なる $i$ を選ぶ。$A_i$ から $1$ を引き、$i\notin S$ ならば $S$ に $i$ を追加する。
- $S=\lbrace 1,2,\dots,N \rbrace$ となっていたら、最後に操作したプレイヤーを勝者としてゲームを終了する。

フェネックとすぬけくんは、どちらも自身が勝者になることを目指して最適な行動を行います。
どちらが勝者になるか判定してください。

制約

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq 10^9$ $(1\leq i\leq N)$
入力はすべて整数

解法

実験したら、証明はともかく、法則性は簡単に推測できる。（また、ゴールが見えた方が証明もしやすい）
ただ、証明は場合分けが多くて大変。

とりあえず小さいケースでは、

$N=1$ の時は明らかに「先手必勝」
$N=2$ の時、$S$ に一方を追加すると相手は即座にもう一方を追加すれば勝つ。「後手必勝」
$N=3$ の時、
- $A$ に2種類目の要素を追加したら、相手は即座に3種類目を追加するので負ける
- → なるべく2種類目の要素の追加を相手に押しつけたい
- → 先手が1種類目に追加した $i$ を、$A_i$ が0になるまで互いに選び続ける
- $A_i=0$ となり2種類目を追加せざるを得ないのは、$A_i$ が奇数なら後手、偶数なら先手
- 先手は奇数の $A_i$ があればそれを1種類目とすることで「先手必勝」。なければ「後手必勝」

$N \ge 4$ 以降は分岐が多くなるので人力での全探索は難しい。（実際はここから実験に転換した）
ただし、小さいケースで分かったこともあって、「$A$ で1以上の要素がラスト2になった状態」が重要そうである。

問題を以下のように言い換える。
一旦 $S$ に追加した後の $A_i$ はどれを選んでも変わらないので、$X$ という1変数にまとめてしまえる。

数列 $A=\{A_1,...,A_N\}$ と、変数 $X=0$ を用意する。
各手番では2種類の操作のいずれかを選んで行う。
- $A$ から1要素 $A_i$ を選び、取り除く。$A_i-1$ を $X$ に加算する。
- $X$ を1減らす。（$X \gt 0$ の場合のみ）
$A$ を空にする操作をした方が勝ち

$A$ に残る要素が2、かつ $X$ が偶数の状態で相手に手番を回せる方が勝つ。
$X$ は、ひいてはその加算元となる各 $A_i$ は、偶奇のみが重要と分かる。

更に以下のように言い換える。

$A$ にある奇数の要素数を $C_o$、偶数の要素数を $C_e$ とする。1bit変数 $X=0$ を用意する。
各手番では3種類の操作のいずれかを選んで行う。
- $C_o$ を1減らす。（$C_o \ge 1$ の時のみ）
- $C_e$ を1減らし、$X$ を反転させる。（$C_e \ge 1$ の時のみ）
- $X$ を1減らす。（$X=1$ の時のみ）
$C_o=C_e=0$ にする操作をした方が勝ち

初期状態を以下で場合分けする。ただし $C_o+C_e \ge 4$ とする。
3つ組の意味を、$(C_oの偶奇,C_eの偶奇,X)$ とする。
また、$偶_4$ のような表記は「4以上の偶数」を意味するとする。

① $(偶,偶,0)$
② $(偶,奇,0)$
- ②a) $(0,奇_5,0)$
- ②b) $(2,奇_3,0)$
- ②c) $(偶_4,奇,0)$
③ $(奇,偶,0)$
④ $(奇,奇,0)$
- ④a) $(1,奇_3,0)$
- ④b) $(奇_3,奇,0)$

①は後手必勝である。後手は、先手と同じ操作をすれば先手に $(偶,偶,0)$ を渡す状態をキープできる。
この状態はいつか $(0,0,0)$ となり、後手を最後の手番として終了する。

また③は、先手が初手で $C_o$ を選べば①を後手に回せるので、先手必勝となる。

②④がややこしい。$C_o,C_e$ が少なくなると行動が変わる。

④は先手必勝となる。

④a) $(1,奇_3,0)$ の時、先手は $C_o$ を減らし、$(0,奇_3,0)$ を相手に渡す。
後手は $C_e$ を操作するしかなく、$(0,偶_2,1)$ が返ってくるので、$(0,偶_2,0)$ を返せば①に帰着して先手必勝。

④b) $(奇_3,奇,0)$ の時、先手は $C_e$ を減らし、$(奇_3,偶,1)$ を相手に渡す。
後手は、
- $C_o$ を減らすと $(偶_2,偶,1)$ なので次に先手は $(偶_2,偶,0)$ を渡せば①に帰着して先手必勝
- $X$ を減らすと $(奇_3,偶,0)$ なので次に先手は $(偶_2,偶,0)$ を渡せば①に帰着して先手必勝
- $C_e$ を（あるなら）減らすと $(奇_3,奇,0)$ となり④b)に戻る

後手は $C_e$ を操作するしかないが、それが可能なのも $C_e$ が尽きるまでなので、なくなったら他のいずれかを操作せざるを得ず、すぐに必敗パターンに持ち込まれる。

②は、後手必勝となる。

②abc) 全てにおいて、
- 先手が初手 $C_e$ を減らすと $(偶,偶,1)$ を相手に渡すことになり、$(偶,偶,0)$ が返ってきて負ける
- 先手は $C_o$ を操作するしかない。
②a) の場合、$C_e$ しか操作できない。
②b) の場合、$(1,奇_3,0)$ を渡すことになるので④a)に帰着される。
②c) の場合、$(奇_3,奇,0)$ を渡すことになるので④b)に帰着される。

いずれでも後手必勝となる。

Python3

def naive(n, aaa, s, d=0):
    # print('  ' * d, n, aaa, s)
    for i in range(n):
        if aaa[i] == 0:
            continue
        aaa[i] -= 1
        added = i not in s
        if added:
            s.add(i)
        if len(s) == n:
            aaa[i] += 1
            if added:
                s.remove(i)
            return True
        if naive(n, aaa, s, d + 1) == False:
            aaa[i] += 1
            if added:
                s.remove(i)
            return True
        aaa[i] += 1
        if added:
            s.remove(i)
    return False


def solve(n, aaa):
    if n == 1:
        return True
    if n == 2:
        return False
    odd = sum(a % 2 for a in aaa)
    if n == 3:
        return odd > 0

    if n % 2 == 0:
        if odd % 2 == 1:
            return True
        return False
    else:
        if odd % 2 == 0:
            return False
        return True


n = int(input())
aaa = list(map(int, input().split()))
if solve(n, aaa):
    print('Fennec')
else:
    print('Snuke')

def naive_wrap():
    n = 6
    for i in range(n + 1):
        aaa = [1] * i + [2] * (n - i)
        ta = tuple(aaa)
        ans1 = solve(n, aaa)
        ans2 = naive(n, aaa, set())
        print(f'{ta=} {ans1=} {ans2=} {ans1==ans2=}')


# naive_wrap()

C - Range Sums 2

問題文

この問題はインタラクティブな問題です。
正整数 $N$ が与えられます。
すぬけくんは、$(1,2,\dots,N)$ を並び替えた正整数列 $P=(P_1,P_2,\dots,P_N)$ と、長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ を隠し持っています。ここで、$P_1 \lt P_2$ が保証されます。
あなたは、すぬけくんに $2N$ 回までクエリを送ることができます。クエリは以下のようなものです。
- $1\leq s,t\leq N$ なる相異なる正整数 $s,t$ を指定し、$\displaystyle \sum_{i=\min(P_s,P_t)}^{\max(P_s,P_t)}A_i$ の値を教えてもらう。

$P,A$ を特定してください。

制約

$3\leq N\leq 5000$
$1\leq P_i\leq N$ $(1\leq i\leq N)$
$P_i\ne P_j$ $(i\ne j)$
$P_1 \lt P_2$
$1\leq A_i\leq 10^9$ $(1\leq i\leq N)$
$N,P_i,A_i$ は整数
$P,A$ はジャッジとの対話前に決定される

解法

$A_i$ が正なので、$(1,2),(1,3),...,(1,j),...,(1,N)$ をクエリで聞いたとき、最も大きい値が返る $j$ が $P_j=1$ または $P_j=N$ となる。

i  1 2 3 4 5 6    i  1 2 3  4 5 6
P  2 4 6 5 3 1    A  1 9 2 25 2 9

クエリ  (Pi,Pj)                    返値
(1,2) → (2,4)         [----]        36
(1,3) → (2,6)         [--------]    47  ← j=3 の時最大
(1,4) → (2,5)         [------]      38     ⇒P3 が1,Nのどちらか
(1,5) → (2,3)         [-]           11     （この例では N だが、
(1,6) → (2,1)       [-]             10       この時点では回答側にとっては不明）

今度は $j$ を主軸として $(j,2),(j,3),...,(j,N)$ をクエリで聞くと、返値の昇順が $j$ から近い順となる。
また、差分を取っていけば、最初の2つ以外の $A_i$ は分かる。

クエリ  (Pi,Pj)                    返値
(3,1) → (6,2)         [--------]    47（←実際は上で聞いているので聞かなくていい）
(3,2) → (6,4)              [---]    36
(3,4) → (6,5)                [-]    11
(3,5) → (6,3)           [------]    38
(3,6) → (6,1)       [----------]    48

  i   3  4  2  5  1  6
  P   1  2  3  4  5  6  （または 6 5 4 3 2 1）
返値    11 36 38 47 48

  i   1  2  3  4  5  6
  A   [11] 25  2  9  1  ←返値の差分から計算

$A_1,A_2$ に関しては和しか分からないが、ここまでわかれば1回の追加クエリで判別できる。
ここまでで $2N-2$ 回のクエリなので間に合う。

最後に $P$ を復元し、$P_1 \gt P_2$ となっていたら反転すれば良い。

Python3

def solve(n):
    try1 = [(0, 1)]
    for i in range(2, n + 1):
        print(f'? 1 {i}')
        try1.append((int(input()), i))
    try1.sort(reverse=True)
    edge = try1[0][1]
    try2 = [(try1[0][0], 1)]
    for i in range(2, n + 1):
        if i != edge:
            print(f'? {edge} {i}')
            try2.append((int(input()), i))
        else:
            try2.append((0, edge))
    try2.sort()
    # print(f'{try2=}')
    ppp = [0] * n
    aaa = []
    prev = 0
    for j, (s, i) in enumerate(try2):
        ppp[i - 1] = j + 1
        aaa.append(s - prev)
        prev = s
    # print(ppp)
    # print(aaa)
    total = try2[-1][0]
    i1 = try2[-1][1]
    i2 = try2[1][1]
    print(f'? {i1} {i2}')
    s = int(input())
    aaa[0] = total - s
    aaa[1] -= aaa[0]
    # print(ppp)
    # print(aaa)
    if ppp[0] > ppp[1]:
        ppp = [n + 1 - p for p in ppp]
        aaa.reverse()
    print(f'! {" ".join(map(str, ppp))} {" ".join(map(str, aaa))}')


n = int(input())
solve(n)

D - Fraction Line

問題文

正の有理数 $x$ に対し、$f(x)$ を以下のように定義します。
- $x$ を互いに素な正整数 $P,Q$ を用いて $\dfrac{P}{Q}$ と表したときの $P\times Q$ の値

正整数 $N$ と、長さ $N-1$ の正整数列 $A=(A_1,A_2,\dots,A_{N-1})$ が与えられます。
以下の条件をすべて満たす長さ $N$ の正整数列 $S=(S_1,S_2,\dots,S_N)$ を良い数列と呼ぶことにします。
- $1\leq i\leq N-1$ なるすべての整数 $i$ について、$f\left(\dfrac{S_i}{S_{i+1}}\right)=A_i$ が成り立つ。
- $\gcd(S_1,S_2,\dots,S_N)=1$

数列のスコアを、その数列に含まれる要素の総積と定義します。
良い数列の個数は有限個であることが証明できます。良い数列すべてに対するスコアの総和を $998244353$ で割った余りを求めてください。

制約

$2\leq N\leq 1000$
$1\leq A_i\leq 1000$ $(1\leq i\leq N-1)$
入力はすべて整数

解法

B,C問題と同じ配点とは思えない難度だが、得意な人は得意なのかも。

まず、サンプル1から良い数列の例を見る。
$S_i,S_{i+1}$ で隣り合う数の比が、$A_i$ になっていればよさそう……?

A     1   9   2   2   9

S   2   2  18   9  18   2
         x9  /2  x2  /9      ← Si から Si+1 にするための計算

S  18  18   2   1   2  18
         /9  /2  x2  x9

ただ、これは $A$ がいずれも単一の素因数しか持たないからで、合成数ならもう少し違ってくる。

A     6  15  20
S   2   3   5  100
     /2      x4
     x3  /3
         x5  x5

全体として比が $A_i$ になっていなくても、素因数毎の比の積が $A_i$ になっていればよい。
実際、$f(x)$ の定義を考えると、$S_i \times a / b = S_{i+1}$ の時、$f(\frac{S_i}{S_{i+1}})=ab$ となる。
ただし、$a$ と $b$ は互いに素でないといけないので、たとえば $A_i=2^2$ の時、2を $a$ にも $b$ にも分けるということはできない。

要は $A_i$ の素因数の種類毎に、1つ前の数に「かける」「わる」の2通りの選択肢があり、それ毎に異なる $S$ ができる。
上例では、$6,15,20$ はいずれも $2^13^1,3^15^1,2^25^1$ と2種類ずつの素因数を持ち、計6個あるので、$2^6$ の $S$ が存在する。

素因数毎に分解してスコアを考える。

$B(p):=A$ から素因数 $p$ のみを取り出した数列。
- 例) $A=(6,15,20)$ → $B(2)=(2,1,4)$
$T_p:=T_{p,i}$ と $T_{p,i+1}$ の比が $B(p)_i$ となるようにした数列（の1つ）

元のA:  6  15  20

B(2): 2   1   4    Scr    B(3): 3   3   1    Scr    B(5): 1   5   5     Scr
┌( 1   2   2   8 ) 32┐  ┌( 1   3   9   9 )243┐  ┌( 1   1   5  25 ) 125┐
│( 2   4   4   1 ) 32│×│( 1   3   1   1 )  3│×│( 1   1   5   1 )   5│
│( 2   1   1   4 )  8│  │( 3   1   3   3 ) 27│  │( 5   5   1   5 ) 125│
└( 8   4   4   1 )128┘  └( 9   3   1   1 ) 27┘  └(25  25   5   1 )3125┘
                   ---                       ---                       ----
                   200                       300                       3380

この時、各素因数の $T_p$ としてたとえば $(2,4,4,1),(1,3,1,1),(5,5,1,5)$ を選んだとすると、実際の最終的な $S$ はこれを各項毎に掛け合わせた $(10,60,4,5)$ となる。

$S$ のスコアは各 $T_p$ ごとのスコア（$(2,4,4,1)$ などの各項の総積）を掛け合わせたものと一致する。

$S$ のスコア（各項の総積）: $10 \times 60 \times 4 \times 5 = 12000$
$T_p$ ごとのスコアの積: $32 \times 3 \times 125 = 12000$

さらに、ありえる全ての $S$ を考えた時の総和は、以下にまとめられることが分かる。

（全ての $T_2$ のスコアの和）×（全ての $T_3$ のスコアの和）×（全ての $T_5$ のスコアの和）

つまり、上例の $A=(6,15,20)$ に対する答えは、$200 \times 300 \times 3380 = 202800000$ となる。

素因数 $p$ 毎に「全ての $T_p$ のスコアの和」を求めれば良い。
以下のDPを考える。

$\mathrm{DP}[i,k]:=T_p[i]$ までを決めて、
- 以下の条件をともに満たすような
  - $T_p[i]$ までの最小値が $1$ である
  - $T_p[i+1]=p^k$ となる
- 全ての $T_p[:i]$ の総積の和

$T_p[i]$ までは最小値が1であることを保証するが、次に置く予定である $k$ は負であってもよいとし、遷移時に調整する。

$i-1$ から $i$ の遷移へは、$C(p)=\log_p{B(p)}$ として、基本的には $T_{p,i}$ に $p^k$ を置いて

$\mathrm{DP}[i,k+C(p)_{i}] += \mathrm{DP}[i-1,k] \times p^k$
$\mathrm{DP}[i,k-C(p)_{i}] += \mathrm{DP}[i-1,k] \times p^k$（$C(p)_i \neq 0$ の場合）

とするが、$k$ が負の場合は最小値が1未満にならないよう、これまでの $i$ 個全体を底上げしてから遷移する。

また、$B(p)$ が1の場合は同じ値が続くため、$1$ 以外になるindexだけ遷移を考えるなどで高速化できる。

$A_{\max}$ 以下の整数が持つ相異なる素因数の最大数を $\omega$ とすると、$O(N^2 \omega \log{A_{\max}})$ で全体を求められる。

Python3

from collections import defaultdict
from math import gcd


def get_spf(n):
    """ nまでの各数を割り切る一番小さな素数 """
    spf = list(range(n + 1))
    for i in range(2, n + 1, 2):
        spf[i] = 2
    for p in range(3, int(n ** 0.5) + 1, 2):
        if spf[p] == p:
            for m in range(p * p, n + 1, 2 * p):
                if spf[m] == m:
                    spf[m] = p
    return spf


def prime_factorize(x, spf):
    """ xを素因数分解、(素数, 個数)の配列で返す """
    factors = []
    prev = -1
    cnt = 0
    while x > 1:
        if spf[x] == prev:
            cnt += 1
        else:
            if prev != -1:
                factors.append((prev, cnt))
                # factors.append(pow(prev, cnt))
            prev = spf[x]
            cnt = 1
        x //= spf[x]
    if prev != -1:
        factors.append((prev, cnt))
        # factors.append(pow(prev, cnt))
    return factors


def calc_dp(n, pos, p, MOD):
    # 素因数 p だけを考える。
    #   A =   1   1   2   2   1
    #   S = 1   1   1   2   4   4
    #       1   1   1   2   1   1
    #       2   2   2   1   2   2
    #       4   4   4   2   1  1
    #
    # 上のように、Si と Si+1 の比が Ai になるような全ての S を考え、総積の和を得る。
    #
    # pos: [(i,c),...]    Ai に p の素因数が c 個含まれる、と言う情報
    # dp[j, follow] :=
    #     pos[j] = (i,c) まで考えて、S[:i] までの最小値は 1 に揃え、S[i+1] の値が p^follow であるような
    #     全ての S[:i] の総積の和

    dp = {0: 1}
    prev = 0
    for i, c in pos:
        ndp = defaultdict(int)
        w = i - prev
        for follow, score in dp.items():
            if follow >= 0:
                score *= pow(p, follow * w, MOD)
            else:
                score *= pow(p, -follow * (prev + 1), MOD)
                follow = 0
            ndp[follow + c] += score
            ndp[follow + c] %= MOD
            ndp[follow - c] += score
            ndp[follow - c] %= MOD
        prev = i
        dp = ndp
    w = n - 1 - prev
    result = 0
    for follow, score in dp.items():
        if follow >= 0:
            score *= pow(p, follow * w, MOD)
        else:
            score *= pow(p, -follow * (prev + 1), MOD)
        result += score % MOD
        result %= MOD
    return result


def solve(n, aaa):
    spf = get_spf(1000)
    MOD = 998244353
    prime_positions = defaultdict(list)
    for i, a in enumerate(aaa):
        pf = prime_factorize(a, spf)
        # print(f'{i=} {a=} {pf=}')
        for p, c in pf:
            prime_positions[p].append((i, c))

    ans = 1
    for p, pos in prime_positions.items():
        result = calc_dp(n, pos, p, MOD)
        ans *= result
        ans %= MOD

    return ans


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

E - Snuke's Kyoto Trip

問題文

整数 $W,H,L,R,D,U$ が与えられます。
$2$ 次元平面上に京都の町があります。
京都の町には、以下の条件をすべて満たす格子点 $(x,y)$ に $1$ つずつ区画が存在します。それ以外の点に区画はありません。
- $0\leq x\leq W$
- $0\leq y\leq H$
- $x\lt L$ または $R\lt x$ または $y\lt D$ または $U\lt y$

すぬけくんは、以下のように京都の町を旅しました。
- まず、区画を $1$ つ選んでそこに立つ。
- その後、$0$ 回以上好きな回数以下の操作を行う。
  - $x$ 軸正方向または $y$ 軸正方向に $1$ 移動する。ただし、移動後の点にも区画がなくてはならない。

すぬけくんが通った経路としてあり得るものの個数を $998244353$ で割った余りを求めてください。

制約

$0\leq L\leq R\leq W\leq 10^6$
$0\leq D\leq U\leq H\leq 10^6$
区画が $1$ つ以上存在する
入力はすべて整数

解法

矩形のグリッドの中に矩形の穴が空いたようなマス目において、始点終点が自由で、右と上だけの移動で到達できるような経路数を数える。

穴が空いていない場合

$(0,0)～(w,h)$ の穴が空いていないグリッドでの答えの求め方を確認しておく。

右と上の移動回数をそれぞれ $i,j$（$0 \le i \le w,0 \le j \le h$）と固定すると、

経路数は $\binom{i+j}{i}$
始点の選び方は $(w-i+1)(h-j+1)$

よって、これらの総和を取って以下になる。

$\displaystyle \sum_{i=0}^{w} \sum_{j=0}^{h} \binom{i+j}{i} (w-i+1)(h-j+1)$

これをWolfram Alphaさんに投げると、Σを除去して（階乗の事前計算の元で）$O(1)$ で算出可能な形にしてくれる。

$f(w,h):=\dbinom{w+h+4}{w+2}-(w+2)(h+2)-1$

また、後で必要になるので以下も計算しておく。
これは、「始点は $(0,0)$ 固定で」終点のみ好きな位置で移動を終える場合の経路数となる。

$g(w,h):=\dbinom{w+h+2}{w+1}-1$

なおこれらの式変形は、ホッケースティック恒等式から導ける。

二項係数の有名公式一覧と2つの証明方針 | 高校数学の美しい物語

穴が空いている場合

穴の境界に沿って、格子点を8つに分類する。

＋＋＋＋＋＋＋      ⑥  |⑦  |⑧
＋＋＋＋＋＋＋      ____|____|______
＋＋    ＋＋＋  →  ④  |    |⑤
＋＋    ＋＋＋      ____|____|______
＋＋＋＋＋＋＋      ①  |②  |③
＋＋＋＋＋＋＋          |    |

まず、穴に関係ない（始点と終点を対角線とする矩形が穴に被らない）答えを求める。重複に注意しつつ、以下で求められる。

①②③を連結した矩形の $f(w,h)$
+ ①④⑥を連結した矩形の $f(w,h)$
+ ③⑤⑧を連結した矩形の $f(w,h)$
+ ⑥⑦⑧を連結した矩形の $f(w,h)$
- ①の矩形の $f(w,h)$
- ③の矩形の $f(w,h)$
- ⑥の矩形の $f(w,h)$
- ⑧の矩形の $f(w,h)$

次に、始点と終点を対角線とする矩形が穴に被るような経路を求める。
穴の左上・右下から45度の斜め線を伸ばした上にある格子点を1つ固定する。影響を受ける経路は、必ずこのどれかを1つだけ通過する。

○＋＋＋＋＋＋
＋○＋＋＋＋＋    ○: 斜め線を延ばした上にある格子点
＋＋    ＋＋＋    ◎: 今回の例で着目する格子点
＋＋    ＋＋＋
＋＋＋＋◎＋＋
＋＋＋＋＋○＋

$g(w,h)$ を使って、◎の左下・右上に広がる2つの矩形の経路数を求め掛け合わせると、◎を通過する経路数となる。

        ＋＋＋
        ＋＋＋
        ＋＋＋
        ＋＋＋
＋＋＋＋◎＋＋
＋＋＋＋＋

ただし、この中には「穴に関係ない」で数えた経路も重複して数えられているので、包除原理で除く。

        ＋＋＋             ・・・             ＋＋＋             ・・・
        ＋＋＋             ・・・             ＋＋＋             ・・・
        ＋＋＋  -          ・・・  -          ＋＋＋  +          ・・・
        ＋＋＋             ・・・             ＋＋＋             ・・・
＋＋＋＋◎＋＋     ＋＋＋＋◎＋＋     ・・・・◎＋＋     ・・・・◎＋＋
＋＋＋＋＋         ＋＋＋＋＋         ・・・・＋         ・・・・＋

これで、穴を迂回しつつ◎を通過する経路数が求められる。斜め線上の格子点それぞれについて求めればよい。

Python3

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(w, h, l, r, d, u):
    MOD = 998244353
    facts, finvs = precompute_factorials(w + h + 2, MOD)

    def free_start_free_end(w, h):
        """ Σ_{i=0,w}Σ_{j=0,h} Binom{i+j}{i} * (w-i+1) * (h-j+1) """
        result = facts[w + h + 2] * finvs[w + 1] * finvs[h + 1] % MOD
        result *= ((h + w) ** 2 + 7 * (h + w) + 12)
        result %= MOD
        result *= pow((w + 2) * (h + 2), -1, MOD) % MOD
        result -= h * w + 2 * (h + w) + 5
        result %= MOD
        # print(f'free {w=} {h=} {result=}')
        return result

    def fixed_start_free_end(w, h):
        """ Σ_{i=0,w}Σ_{j=0,h} Binom{i+j}{i} """
        result = facts[w + h + 2] * finvs[w + 1] * finvs[h + 1] - 1
        result %= MOD
        # print(f'fixd {w=} {h=} {result=}')
        return result

    ans = 0
    if l > 0:
        ans += free_start_free_end(l - 1, h)
    if r < w:
        ans += free_start_free_end(w - r - 1, h)
    if d > 0:
        ans += free_start_free_end(w, d - 1)
    if u < h:
        ans += free_start_free_end(w, h - u - 1)
    if l > 0 and d > 0:
        ans -= free_start_free_end(l - 1, d - 1)
    if l > 0 and u < h:
        ans -= free_start_free_end(l - 1, h - u - 1)
        i = l - 1
        j = u + 1
        while i >= 0 and j <= h:
            pre_full = fixed_start_free_end(i, j)
            post_full = fixed_start_free_end(w - i, h - j)
            pre_short = fixed_start_free_end(i, j - u - 1)
            post_short = fixed_start_free_end(l - i - 1, h - j)
            ans += pre_full * post_full
            ans -= pre_full * post_short
            ans -= pre_short * post_full
            ans += pre_short * post_short
            i -= 1
            j += 1
    if r < w and d > 0:
        ans -= free_start_free_end(w - r - 1, d - 1)
        i = r + 1
        j = d - 1
        while i <= w and j >= 0:
            pre_full = fixed_start_free_end(i, j)
            post_full = fixed_start_free_end(w - i, h - j)
            pre_short = fixed_start_free_end(i - r - 1, j)
            post_short = fixed_start_free_end(w - i, d - j - 1)
            ans += pre_full * post_full
            ans -= pre_full * post_short
            ans -= pre_short * post_full
            ans += pre_short * post_short
            i += 1
            j -= 1
    if r < w and u < h:
        ans -= free_start_free_end(w - r - 1, h - u - 1)
    ans %= MOD
    return ans


ans = solve(*map(int, input().split()))
print(ans)

目次

AtCoder Regular Contest 192 (Div. 2) A,B,C,D,E問題メモ

A - ARC Arc

問題文

制約

解法

B - Fennec VS. Snuke 2

問題文

制約

解法

C - Range Sums 2

問題文

制約

解法

D - Fraction Line

問題文

制約

解法

E - Snuke's Kyoto Trip

問題文

制約

解法

穴が空いていない場合

穴が空いている場合