キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) E,F,G,H問題メモ

キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227)

キーエンスのコンテスト、なんか通常回より難しくなりがちな気がするんだよな。

E - Swap

• K,E,Yの3種類の文字のみから成る文字列 $S$ が与えられる
• $S$ の隣接する2文字を入れ替える操作を $K$ 回以下おこなって作ることの出来る文字列は何通り？
• $2 \le |S| \le 30$
• $0 \le K \le 10^9$

数列の転倒数の考え方を使って、DP。

数列を隣接swapによりソートするときの最小操作回数は、 各要素につき「初期状態で自身より左にあって、最終状態で自身より右にある要素の個数」の総和となる。

4 2 5 1 3    2にとって 4    の1個が該当┐  
↓           1にとって 4,2,5の3個が該当┼計6回が最小操作回数
1 2 3 4 5    3にとって 4,5  の2個が該当┘

この時、同じ要素が含まれるなら同じ要素同士は操作する必要が無いので、並ぶ順番は最初と最後で変わらない。

        a       b   c
3 1 4 1 5 9 2 6 5 3 5
↓
            a b c        5に着目すると、
1 1 2 3 3 4 5 5 5 6 9    a,b,cの順序を変える必要は無い

以上を踏まえると、最終状態を先頭から決めていったとき、 「ここまでで部分的にかかる操作回数」というものを計算することができる。

4 2 5 1 3    1を先頭に持ってくるのに 3┐
↓           2を 次 に持ってくるのに 1┴暫定コスト4
1 2

これを今回の問題に当てはめると、以下のようなDP（のふわっとしたイメージ）で計算できそう。

• $DP[i][j][???]=$ 最終状態の $i$ 文字目までを決めたとき、暫定コスト $j$ で、???な文字列の種類数

最終的に、$DP[N][K以下]$ の総和が答えとなる。

???の部分、同じDPにまとめられる途中経過の状態を考える。
「初期状態で自身より左にあって、最終状態で自身より右にある要素」を「swap対象」と呼ぶことにする。

i    1 2 3 4 5 6    3文字目まで決まり、4文字目に置く文字を考える
初期 K E Y K E Y    ・Kの場合、初期で i=1 のKを使う。swap対象は無し
↓                  ・Eの場合、もう既に全て使っている
最終 E Y E ?        ・Yの場合、初期で i=6 のYを使う。swap対象はK,Kの2個

具体例を整理すると、

• 「Kを置けるか、置くなら初期のどの位置のKを使えばよいか」は、ここまでに既に使ったKの個数に依存する
• その時のswap対象は、「初期で自身より左にあったE,Yのうち、最終でまだ置かれていないもの」となるので、前者を事前計算しておけば、後者はここまでに既に使ったE,Yの個数に依存する

よって、「ここまでに既に使ったK,E,Yそれぞれの個数」によって次の1文字を置くコストが計算できる。
逆に言うと、これらが同じ暫定文字列は、次の1文字を置くコストが同じであり、状態をまとめられる。

• $DP[i][j][k][e][y]=$ 最終状態の $i$ 文字目までを決めたとき、暫定コスト $j$ で、K,E,Yを使った回数がそれぞれ $k,e,y$ な文字列の種類数

$j$ の状態数は $O(|S|^2)$、他は $O(|S|)$ で全体で $O(|S|^6)$ となりそうだが、

• $i=k+e+y$ なので、$i,k,e$ が決まれば $y$ は自動的に決まる
• $i$ の小さい内は $j,k,e,y$ ともに小さい

ため、実際にあり得るのはぐっと少なくなると期待できる。

DPの実装上は $(j,k,e,y)$ を1つのキーとして連想配列で持っておくと、 実際にあり得る状態だけを取り出しやすくなる。

Python3

F - Treasure Hunting

• $H \times W$ のマス目にそれぞれ正整数 $A_{i,j}$ が書かれている
• 左上 $(1,1)$ から右下 $(H,W)$ まで、1つ右か1つ下のマスへの移動を繰り返す
• 通った $H+W-1$ マスに書かれた整数のうち、大きい方から $K$ 個の和を移動コストとする
• コストとしてあり得る最小値を求めよ
• $1 \le H,W \le 30$
• $1 \le A_{i,j} \le 10^9$

一見、最短経路っぽく $DP[i][j]=(i,j)$ への最小コスト、とできそうに見えるが、上手くいかない。

$K=4$ で、途中のあるマスへ至るのに通過したマスが $\{1,1,100,100\}$ であるルートと $\{51,51,51,51\}$ であるルートでは、 そこまででは前者の方が低コストだが、その後に通過するマスに $52$ が敷き詰められていたりすると、 前者は $\{52,52,100,100\}$、後者は $\{52,52,52,52\}$ となり、逆転する。

途中までで何が最善かが、後のマスによって変わるため、何を残せばよいのか判断できない。

ここで、やや天啓的だが「最終的にコストに加算される値の下限 $X$」を固定すると現実的な状態数に落とし込める。

隣接マスへの遷移時、$X$ 以上ならコストに加算し、未満なら無視するようにする。

最終的に加算される値が $K$ 個ないといけないのでその個数は管理する必要があるが、 それさえ同じであれば、暫定コストの低い方が正義である。

• $DP[i][j][k]=(i,j)$ までの移動で、$X$ 以上の値を $k$ 個取っている際の暫定最小コスト

コスト最小となる真のルートと真の $X$ が（現時点では不明ながらも）あったとして、

• $X$ を大きく見積もりすぎると、真のルートでは $K$ 個以上通過できない
  • 仮に $K$ 個通過できる他のルートがあったとしてそれは最善ではない
• $X$ を小さく見積もりすぎると、真のルートで無駄な $A_{i,j}$ を加算することになる

いずれにしろ誤った $X$ を仮定するとコストが大きくなるので、$X$ を全て試すことで最善が求まる。

注意点として、$A_{i,j}=X$ となるマスが複数あるとき、 その中の一部だけコストに加算され、残りは捨てられることがある。

これは、「$A_{i,j}=X$ なるマスへの遷移は、それをコストに採用して $k+1$ に遷移してもよいし、 採用しないで $k$ に遷移してもよい」とすることで、表現できる。

計算量は、$X$ としてあり得る値がマスの数 $O(HW)$、それぞれでDPに $O(HWK)$ なので、$O(H^2W^2K)$。

Python3

詳細は解説放送参照

• キーエンスプログラミングコンテスト2021-Nov. (AtCoder Beginner Contest 227) - YouTube

最短経路探索の添字を $DP[i][j]$ だけにできる（個数 $k$ を省ける）。

$X$ に対し、各 $A_{i,j}$ を、$\max(A_{i,j}-X,0)$ とした上で最短経路探索する。

結果に対して $X \times K$ を加算すると、これは $X$ が正しい場合、正しい答えとなる。

さらに $X$ を真の値より大きくしても小さくしても、コストが大きくなってしまうことが示せる。

G - Divisors of Binomial Coefficient

• 二項係数 $\dbinom{N}{K}$ の正の約数の個数を $998244353$ で割ったあまりで求めよ
• $1 \le N \le 10^{12}$
• $1 \le K \le 10^6$

二項係数・約数の個数の公式さえ知っていれば、E,F問題より何をすればいいかはわかりやすかったかも知れない。

正整数 $X$ の約数の個数は、$X$ を素因数分解して $x^ay^bz^c...$ と表せるとき、$(a+1)(b+1)(c+1)...$ となる。

二項係数 $\dbinom{N}{K}$ は、$\dfrac{N(N-1)(N-2)...(N-K+1)}{K(K-1)(K-2)...1}$ で計算できる。
$N(N-1)...(N-K+1)$ に含まれる素因数 $p$ の個数が $x$、$K(K-1)...1$ に含まれる素因数 $p$ の個数が $y$ 個だった場合、 $\dbinom{N}{K}$ に含まれる素因数 $p$ の総和は $x-y$ となる。

素因数毎にこれを求め $x-y+1$ の総積を取れば答え。

$L～R$ の連続した整数を高速に全て素因数分解する方法。
（厳密には、区間篩とだけ言ったときはその中にある素数を列挙するアルゴリズムを指すのが一般的で、 素因数分解はちょっとだけ発展となる）

$R$ が大きく、$R-L$ が線形探索可能な程度の場合に有効。

• エラトステネスの篩に基づく高速な素因数分解 - Qiita

今回は、$L～R$ を全てかけあわせた時の素因数がわかればよいので 各数値を個別に素因数分解する必要は無く、全てまとめた素因数の個数がわかればよい。

今回の問題にあわせて $L=N-K+1,R=N$ とする。

まず、$\sqrt{R}$ までの素数を列挙する。（計算量 $O(\sqrt{R} \log{\log{R}})$）

次に、$L～R$ の値を列挙した配列を作成する。

L=205  R=215
  [ 205  206  207  208  209  210  211  212  213  214  215 ]

p = 2,3,5,7,... から順番に、以下を行う

【p=2】
・範囲内で最初のpの倍数を求める  ceil(L/2) * 2 = 206
・そこからpごとの位置にある数字をpで割れるだけ割っていき、回数を記録する
         206       208       210       212       214
         ↓1回     ↓4回     ↓1回     ↓2回     ↓1回         9回
  [ 205  103  207   13  209  105  211   53  213  107  215 ]

→L～Rを全て掛け合わせた数に含まれる素因数2の個数は 9 個

【p=3】
・範囲内で最初のpの倍数を求める  ceil(L/3) * 3 = 207
・そこからpごとの位置にある数字をpで割れるだけ割っていき、回数を記録する
              207            105            213
              ↓2回          ↓1回          ↓1回              4回
  [ 205  103   23   13  209   35  211   53   71  107  215 ]

→L～Rを全て掛け合わせた数に含まれる素因数3の個数は 4 個

これを列挙した全素数で繰り返す。

結果がこうなる
  [  41  103   23    1   19    1  211   53   71  107   43 ]

残っている2以上の数は素数である。
素数でないとしたら $\sqrt{R}$ 以上の数の合成数ということになるが、必ず $R$ を超過してしまい矛盾する。

この中で要素毎にカウントを取れば、残りの素因数とその個数もわかる。
$K \gt \sqrt{R}$ の場合は同じ素数が残る場合がある点に注意。
または、最初に素数列挙する段階で上限を $\max(K,\sqrt{R})$ としておけば、残る素数は必ず重複しなくなる。

$1～K$ の区間にも同じことをやれば答えが求まる。

この部分の計算量は評価が難しいが、$M=\max(K,\sqrt{R})$ として、$M \log{\log{M}}$ となるらしい。

Python3

H - Eat Them All

• $3 \times 3$ の各マス $(i,j)$ に、猫缶がそれぞれ $A_{i,j}$ 個置かれている
• 1匹の猫が左上 $(1,1)$ にいて、以下の要領で移動を繰り返す
  • 今いるマスの猫缶を1つ食べてから、上下左右の隣接マスへ移動する
  • 今いるマスに猫缶が残っていなければ移動を終了する
• 猫が全ての猫缶を食べ終えて $(1,1)$ で移動を終了するような移動経路を1つ構築せよ
• $1 \le A_{i,j} \le 100$

フロー+オイラー閉路構築。

マスを $(i,j)$ の2つの数字で表すのは冗長なので、説明上は以下のように番号を振りなおす。

⓪①②
③④⑤
⑥⑦⑧

あるマスに入ってきて出る、という操作で猫缶を1つ消費するので、 「マスを頂点とし、全ての頂点 $i$ に $A_i$ 本の辺が入り $A_i$ 本の辺が出る有向連結グラフ」を作り、 その全辺を一筆書きでなぞれるルート（オイラー閉路）を構築すればよい。

ルート構築は、そのようなグラフが作れたなら必ず出来る。
有向オイラー閉路の条件が、「頂点の入次数＝出次数」が全頂点について満たされるかなので。

• 競プロにおけるオイラー路とその応用について - Learning Algorithms

①から出た $A_1$ 本の辺が、隣接マスの⓪、②、④にそれぞれ何本ずつ向かうか、というのを各マスについて決めたい。

これは最大流で解ける。

     in   out        S→各マスin、各マスout→T には、容量＝Ai の辺を張る
  ,- ⓪    ⓪ -,     
  |- ①    ① -|     各マスin→各マスout へは、隣接頂点間に容量INFの辺を張る
S-|- ：    ： -|-T   （図では表現しきれないので省略）
  |- ⑦    ⑦ -|
  `- ⑧    ⑧ -'

  ,- ⓪    ① -,     S→偶数頂点、奇数頂点→T には、容量＝2Ai の辺を張る
  |- ②    ③ -|  
S-|- ④    ⑤ -|-T   偶数頂点→奇数頂点 へは、隣接頂点間に容量INFの辺を張る
  |- ⑥    ⑦ -'    （図では表現しきれないので省略）
  `- ⑧

$S→T$ へ最大流を流して、$A_i$ の総和分流せなければ不可能。

流せたら、流し終わった後のネットワークに、どの辺にどれだけ流したかの情報が残っている。
⓪→①に流量5を流していれば、目標の連結グラフでは⓪を出て①に入る辺を5本作ればよいことになる。

ただし最大流に任せると連結性が保証されない。

⓪→①⇄②    こんなんでも解となり得てしまう
↑  ↓
③←④  ⑤
        ⇅
⑥⇄⑦⇄⑧

あらかじめ、外周をぐるっと1回だけループさせると決めうてばよい。
（$A_4$ を除く $A_i$ を1ずつ減らしてフローを解き、グラフに反映させる段階で戻す）

⓪→①→②
↑      ↓
③  ④  ⑤
↑      ↓
⑥←⑦←⑧

各辺をこの向きに最低1回使うというのが重要で、実際に通る順番はバラバラでよい。

④は必ず①③⑤⑦のどれかと接続されるため、これで連結性は保証される。

「いやいや、⓪→①の辺を張ったら破綻するけど、使わなければ上手く流せるケースがあるんじゃないの？」と思うが、 どのような成立状態でも上手く辺の結び方と方向を変えることで、外周一周を使う成立状態に変換可能である。

証明

    →    →      これ以降の図で、対応する位置に
 ⓪ ← ① ← ②   ・矢印が書かれている: 使うことが確定した辺
↑↓  ↑↓  ↑↓  ・×印が書かれている: 使わないことが確定した辺
 ③ → ④ → ⑤   ・何も書かれていない: 未決定の辺
    ←    ←      とする。

    ×      
 ⓪    ①    ②     ⓪→①を使わないとした場合、
  ↓                Ai >= 1より⓪から1本は辺が出るので、
 ③    ④    ⑤     ⓪→③の辺を使うことが確定する

【①→⓪を使う場合】
    ×
 ⓪ ← ①(←)②     現在の状態は条件を満たす（オイラー路を構築できる）ので、
  ↓       (↑)     ①→⓪を通って①に戻る、交差しない閉路が必ず存在する。
 ③(→)④(→)⑤     （図は一例）
 
    →    →
 ⓪    ①    ②     それを全て反転させることで⓪→①の辺を作れる。
↑          ↓      反時計回りを時計回りに変換するので、他の外周辺を失うことはない。
 ③    ④    ⑤
    ←    ←

よって、①→⓪の辺も使えないことがわかる。そして③→⓪の辺を使うことが確定する。
    ×      
 ⓪ × ①    ②     
↑↓                
 ③    ④    ⑤     

【④→①を使う場合】
    ×      
 ⓪ × ①    ②     
↑↓  ↑            ⓪→③ と ④→①のように互い違いの関係にある平行な2辺は、
 ③    ④    ⑤     

    →      
 ⓪ × ①    ②     こう繋ぎ替えられる。
↑                  つなぎ替えることで連結で無くなる可能性を考慮しなければならないが、
 ③    ④    ⑤     ③→⓪を使うことが確定しているため、連結は保たれる。
    ←

【①→④を使う場合】
    ×      
 ⓪ ← ①    ②     同様に、こう繋ぎ替えられる。
  ↓                更に先ほどの、閉路の辺反転を使うことで、⓪→①の辺を作れる。
 ③ → ④    ⑤     一時的に外周辺③→⓪を失うが、これを含めて辺反転させればよい。

よって、①→④、④→①の辺も使えないとなる。
すると、①を他と連結にするためには、②、⑤と連結するしか無くなる。
    ×    →
 ⓪ × ① ← ②     
↑↓  ××  ↑↓    
 ③    ④    ⑤     

以下、同様の議論が④⇄⑤にも適用され、これらの辺も使えないとなる。
すると⑤は連結を保つため、⑧、⑦と連結になる。
    ×    →
 ⓪ × ① ← ②     
↑↓  ××  ↑↓    
 ③    ④ × ⑤     
            ↑↓
       ⑦ → ⑧
          ←
これを繰り返すと、④⇄⑦、③⇄⑦ の辺も使えなくなり、④が孤立する。
よって矛盾する。

証明はそれなりに煩雑な場合分けが必要なため、公式Editorialの通り、 必ず流すと決める全域木を全探索したり、ランダムでフローの流し方を何通りか試す方が考察は速そう。

各頂点間の辺数が決まったら、あとはオイラー閉路の構築となる。

これは、DFSの帰りがけ順で通過頂点を記録するとよい。

• オイラー(閉)路についてまとめた - perogram

同じ頂点間に辺が複数本あり、頂点ではなく辺について網羅しないといけないため、よくあるDFSとは若干コードが異なる点に注意。

複数本無ければ点と辺を逆転させて考える手もありだが、複数本ある場合は辺の数が大量にできてしまう。

   10本    10本       このようなグラフで点と辺を逆転させた場合、
⓪ --→ ① --→ ②    ① にどの辺から入ってどの辺から出るか、10 x 10 通りの辺を張らないといけない？

答えの1つには外周を一周するものが必ず存在するとわかったので、それをベースとしてもよい。

• 外周を一周する過程で、必要に応じて隣接マスとの往復を繰り返す
• ①③⑤⑦は、適宜④とも往復する

⓪１①３②
12  ２  ４    数字の順に、往復しながら移動する
③11④５⑤
10  ８  ６
⑥９⑦７⑧

各頂点が周囲の隣接マスとそれぞれ何回往復するか（合計で、外周マスは $A_i-1$ 回、④は $A_i$ 回）は最大流で求められる。

こうすると、オイラー閉路の構築が楽になる。

Python3