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

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

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

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

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