AtCoder Grand Contest 050 (Good Bye rng_58 Day 1) A,B,C問題メモ

AtCoder Grand Contest 050 (Good Bye rng_58 Day 1)

A - AtCoder Jumper

• $1～N$ の番号が付いた $N$ ページのWebサイトに、以下の条件を満たしてリンクを張る方法を構築せよ
• 条件
  • 1ページあたり2ページにリンクを張る
  • どのページからどのページへも、10回以下クリックする（リンクを辿る）ことでたどり着ける
• $1 \le N \le 1000$

制約が $2^{10} \simeq 1000$ なので、二分木的なアプローチを使いそう。

最大数ができたら全てできるので、$N=1000$ を考える。
ただ、1000は大きすぎて考えづらいので、$1 \le M \le 15$ ページを4回までのクリックで巡ることを考える。

ページ1からだけを考えると、二分木のように $i$ から $2i,2i+1$ に辺を張っていくと3回以内で全てに行ける。

       １
     ／  ＼
   ２      ３
  ／＼    ／＼
 ４  ５  ６  ７
 /\  /\  /\  /\
８９⑩⑪⑫⑬⑭⑮

これをもとに、他の頂点からも上手く行けるようにしたいが……リンクは一方通行なので上へは戻れない。
1～7は全て2リンクを使い果たしているので、葉である8～15を使うしかない。

葉からは全て1にリンクさせてやり直せば？という案が思いつくが、例えば2→15などはほぼ2回分木を辿ることになってしまう。
葉ごとに、ちょうどいい感じの戻り方をしなければならない。

いろいろ試すと、葉からも同様に $2i,2i+1$ に辺を張りつつ $\mod{M}$ を取る（正確には1引いて $M$ で割ったあまりを1足す）と、上手くいく。

               １
         ,----'  `----,
       ２              ３
     ／  ＼          ／  ＼
   ４      ５      ６      ７
  ／＼    ／＼    ／＼    ／＼
 ８  ９  ⑩  ⑪  ⑫  ⑬  ⑭  ⑮
 /\  /\  /\  /\  /\  /\  /\  /\ 
１２３４５６７８９⑩⑪⑫⑬⑭⑮１

二分木のように $i$ から $2i,2i+1$ に辺を張った木は、左上から頂点番号が連番になるが、これは $\mod{M}$ を取った後でも成り立ち、$1～M$ がループする形になる。

すると、1から4回で行ける層は、$2^4$ 個の要素が連番で並ぶ。この中には当然 $M$ 以下の値が全て含まれる。

ここで頂点2を根としてみる。階層間では連番でなくなるが、第 $k$ 階層に、$2^k$ 個の数字が連番で並ぶという性質は変わらない。

               ２
         ,----'  `----,
       ４              ５
     ／  ＼          ／  ＼
   ８      ９      10      11
  ／＼    ／＼    ／＼    ／＼
 １  ２  ３  ４  ５  ６  ７  ８
 /\  /\  /\  /\  /\  /\  /\  /\ 
２３４５６７８９⑩⑪⑫⑬⑭⑮１２

よって二分木のように辺を張れば、第10階層には1024個の数字が連番で並び、その中に $1～N$ が含まれることが保証できる。

Python3

B - Three Coins

• $N$ 個の横一列に並ぶマス、最初は何も置かれていない
• 以下の操作を好きに繰り返す
• 操作
  • 3つ並んだ空きマスを選び、コインを1枚ずつ置く
  • 3つ並んだコインの置かれたマスを選び、コインを全て取り除く
• 最終的に左から $i$ 番目にコインが置かれていると、$a_i$ 点を得る（負もあり得る）
• 得点を最大化せよ
• $3 \le N \le 500$

問題タイトルはショッピングモールで見かける300円均一の雑貨屋さんか。

置くことができるコインの位置を考えると、

..ooo..... → ..oooooo.. → ..oo...o..
                         → ..o...oo.. → ..o...ooooo.. → ..o...o...o..

3個続けて置いたコインの一部を、あたかも距離3ずつ移動させるような操作をすることができる。

コインを取り除く操作は、結局この「移動させる」操作と同一視でき、以下の2操作ができると考えてよい。

• 3個連続した空きマスにコイン置く
• 1コインを距離3単位で移動させる、ただし途中に他のコインのあるマスに入ったり飛び越したりしてはいけない

こういう、いくつかの操作を繰り返してできる配置が可能かどうかが重要な問題では、 移動前後の不変量を見つけることで、 逆にそれを満たすような配置は必ず作れる、ということを利用する解法がよくある。

変わらないものを奥華子ばりに探すと、コインが置かれた座標の $\mod{3}$ を見れば 必ず最初に置くのは $(0,1,2), (1,2,0), (2,0,1)$ のいずれかになり、移動させても変わらないことがわかる。

どれだけ移動させても (2,0,1)

0120120120    0120120120    0120120120120
..ooo..... → ..oo...o..
           → ..o...oo.. → ..o...o...o..

逆に、間が全て空きマスで、このいずれかの順に並んだ3つのコインは、必ず作れる。
置く操作で一緒に置いた3枚のコインを「3つ組」と呼ぶことにする。

もう一段階考察を進めると、3つ組を移動させて開いた穴に、 また同様に3つ組を置き、移動させることができる。
そうすると、必ずしも最終配置において3つ組（$(0,1,2)$ など）が繰り返されるわけでは無くなる。

  2            01        2 120        01        2 1   20     01
..o............oo.. → ..o.ooo........oo.. → ..o.o...oo.....oo..

ただし、

• 一番最後に置いた3つ組は、必ず間に他のコインは挟まれない
• そうやって取り除ける3つ組を上手い順に取り除いていくと、最後まで取り除ける方法がある

なら、構成可能であることがわかるし、これが満たされないなら無理。

括弧列のように、先頭から $0 \mod{3}$ の位置を取ったら「あと $1,2$ が1個ずつ必要」みたいに開く数と閉じる数を管理するDP、というのは筋が悪そう。
0,1,2を開いた個数が同じでも順番によって閉じ方が変わってくるので、同一視してまとめられる状態数がそこまで小さくならない。

以下のような区間DPをするとよい。

• $DP[l][r]=$ 区間 $[l,r)$ だけにコインを置いたり移動したりできるとき、得られる最大得点

そうすると、$[l,r)$ 内の3つ組としてあり得る3マス $(i,j,k)$（これは $\mod{3}$ でなく本来の座標で）について、

• 区間 $[l, i)$ から得られる最大得点
• 区間 $[i+1, j)$ から得られる最大得点
• 区間 $[j+1, k)$ から得られる最大得点
• 区間 $[k+1, r)$ から得られる最大得点
• $a_i+a_j+a_k$

の合計が、$(i,j,k)$ が3つ組だった時に $[l,r)$ から得られる得点となる。
全ての $(i,j,k)$ について求めた最大値が $DP[l][r]$ となる。
区間の狭い方から埋めていくことで、計算できそう。

しかし、単純にこれを埋めていこうとすると、$O(N^5)$ のループとなってしまう。

$l \le i \lt j \lt k \lt r$ かつ $\mod{3}$ 上の制約があるにしても、ちょっと無理。

ここで、DPを以下のように更新すると、効率よく計算できる。

• 区間が狭い方から $l,r$ を埋めていく
• 基本的には、2つの区間を統合する
  • 分割点 $m=l+1～r-1$ について、$DP[l][r] = \max(DP[l][m] + DP[m][r])$
• 区間全体が新たな3つ組の両端になり得る時のみ、そのパターンを調べる
  • つまり、3つ組 $(l,j,r-1)$ が存在した場合を調べる
  • $j=l+1～r-2$（3個おき）について、
  • $DP[l][r] ← \max(DP[l+1][j] + DP[j+1][r-1] + a_l + a_j + a_{r-1})$

こうすると、$O(N^3)$ に収まる。

区間全体が新たな3つ組の両端にならないなら、必ず事前に計算した2区間をくっつけた形で表現できる、というのがなるほどポイント。

Python3

C - Block Game

• 無限に横一列に続くマス目上で、刑事と怪盗が以下のゲームを行う
• ルール
  • 怪盗がマスの1つに立つ
  • 手番を示す文字列 $t$ が2人に示される
    • $i$ 文字目が 'B' なら $i$ ターン目は刑事の手番
      • 好きなマスにブロックを置く
    • $i$ 文字目が 'S' なら $i$ ターン目は怪盗の手番
      • 左右に隣接するブロックの無いマスを選んで1マス動くか、何もしない
  • $|t|$ ターンまでに怪盗の両側のマスにブロックを置けたら刑事の勝ち、それ以外なら怪盗の勝ち
• この問題では、'B','S','?' からなる文字列 $s$ が与えられる
• '?'の文字数を $Q$ として、'?'を'B'か'S'のいずれかに置き換える方法は $2^Q$ 通りある
• この内、$t$ としてゲームを開始したときに両者が最適に行動して刑事が勝てるパターンの数を求めよ
• $1 \le |s| \le 10^6$

刑事は行動可能範囲をなるべく狭めたい。
最初の1個はともかく、あとは、より怪盗のいる方の空きマスが少なくなるように置いていけばよさそう。（ちゃんとした証明はわからん）

■・・・・・・怪・・・・・・・・・■

■・・・・・・怪■・・・・・・・・■  B

■・・・・怪←←■・・・・・・・・■  SS

■・・・■怪・・■・・・・・・・・■  B

■・・・■→怪・■・・・・・・・・■  S

■・・・■・怪■■・・・・・・・・■  B

すると、怪盗の最適な行動は、壁からなるべく離れた位置を保つこととなる。

移動可能範囲のちょうど真ん中までたどり着ける（'S'がそれだけ続く）ならそこへ
■・・・・・・怪■  B

■・・・怪←←←■  SSSSSS

足りなければ'S'が続くだけ壁から離れる
■・・・・・・怪■  B

■・・・・怪←←■  SS

その後、刑事は怪盗の真横へまたブロックを置くので、怪盗の次の移動可能範囲（怪盗のいるマス自身を除く）は、以下の小さい方となる。

• 今の移動可能範囲を $x$ として、$\left \lfloor \dfrac{x}{2} \right \rfloor$
• 前回の'B'と次の'B'の間にある'S'の個数を $y$ として、$y$

これが繰り返され、終了までに移動可能範囲が0になったら刑事の勝ち。

逆に怪盗が勝つには、以下のように'B'に挟まれた'S'の個数が、後ろから $1,2,4,8,16,...$ 以上ならよい。

B SSS...SS B SSS...SS B SSS...SS B SSSS B SS B S B
      32        16         8         4     2   1

どれか1箇所でも、連続する'S'の個数がこれ未満ならアウト。

なので、$s$ から'?'を書き換えたときにこういう条件を満たす文字列がどれだけ作れますか、という問題を解けば、それを $2^Q$ から引けば答えとなる。

上記のようにかなり刑事に有利なルールであり、むしろ怪盗が逃げ切れるケースの方がまれなので、そちらを数える。

前から決めていくと、あと何回'B'が出てくるかによって'S'が直近に連続してほしい数が異なってきてややこしいので、後ろから決めていきたい。

• $DP[i][j]=s$ を後ろから見て $i$ 文字目までで、Bが出てきた回数が $j$ 回で、$i$ 文字目がたとえ'B'であったとしても怪盗がこの先生きのこれるパターン数
  • 後ろから、という点に注意
• 初期化: $DP[0][0]=1$
• 求めるもの: $DP[|s|][0] + DP[|s|][1] + ...$

$j$ の上限は21くらいでよい。
'B'が1回出てきたら $2^1+1$、2回出てきたら $2^2+2$、$k$ 回出てきたら $2^k+k$ 文字が最低必要となるので、$k=20$ で $10^6$ を超える。

遷移を配るDPで考える。後ろから $i$ 文字目（$i=0,1,2,...$）が

• 'S' のとき
  • $i$ 文字目まで生き残れている怪盗が詰むことは無く、$i+1$ 文字目まで生き残れる
  • $DP[i+1][j] += DP[i][j]$
• 'B' のとき
  • 'B' が既に $j$ 個出てきているような状況で生き残るには、この'B'の後、'S'が $2^j$ 個続く必要がある
    • $2^j$ 個の中に他に'B'が出てくるならそもそも不可能
    • それ以外なら、たとえ'?'が出てきていても'S'にするしか無く、1通り
  • $DP[i+1+2^j][j+1] += DP[i][j]$
• '?' のとき
  • 'S'と'B'の両方の遷移をする

'B'が次にどこに出てくるかは、最初に'B'の出てくる位置を求めておけばすぐに求められる。

また、$i+1+2^j$ が $|s|$ を超える場合は、便宜上 $|s|$ に切りそろえる。

これで、計算量は $O(|s| \log{|s|})$ となる。

Python3

怪盗は自分の手番で必ず動かなくてはならない、だったら、偶奇によってちょうど中央で止まることができないことがあるので、もう少しややこしかったかも知れない。