キーエンスプログラミングコンテスト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

$O(H^2W^2)$ 解法

詳細は解説放送参照

最短経路探索の添字を $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$ が線形探索可能な程度の場合に有効。

今回は、$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$ 本の辺が出る有向連結グラフ」を作り、 その全辺を一筆書きでなぞれるルート(オイラー閉路)を構築すればよい。

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

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

これは最大流で解ける。

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

ここで、構築するグラフは向きを無くして「各頂点から $2A_i$ 本の辺が出た、無向連結グラフ」でもよい。

「各頂点から偶数本の辺が出た無向グラフ」でも必ずオイラー閉路を作れるし、その一例の構築方法も大きく変わらない。

その場合、グリッドが二部グラフであることを利用し、もう少し最大流を解くグラフを簡潔にできる。 (元から大して複雑でもないが)

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

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

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

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

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

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

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

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

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

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

証明

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

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

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

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

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

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

解法2

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

  • 外周を一周する過程で、必要に応じて隣接マスとの往復を繰り返す
  • ①③⑤⑦は、適宜④とも往復する
⓪1①3②
12  2  4    数字の順に、往復しながら移動する
③11④5⑤
10  8  6
⑥9⑦7⑧

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

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

Python3

programming_algorithm/contest_history/atcoder/2021/1113_abc227.txt · 最終更新: 2021/11/18 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0