AtCoder Grand Contest 051 (Good Bye rng_58 Day 2) A,B,C,D問題メモ

AtCoder Grand Contest 051 (Good Bye rng_58 Day 2)

コンテスト前におさけをのむとひらめきりょくがあがります。（代わりにその他の全能力が下がります）

A - Dodecagon

• 1辺が1の、正三角形と正方形のタイルがたくさんある
• タイルを隙間無く敷き詰めて、1辺の長さが $d$ の正十二角形を作る並べ方が何通りあるか $\mod{ 998244353 }$ で求めよ
• $1 \le d \le 10^6$

こういうのは制約のある部分＝外周から埋めていくのがセオリー。
フリーハンドで図を書いて試すのが難しいが、がんばる。CAD使えたら強そう。

直線部分は、正方形を置いたら隣に正三角形は並べられず、逆も然りなので、片方だけをずっと敷いていくしかない。
逆に角は、正十二角形の1つの内角が150°なので、正方形と正三角形を置いたらちょうど埋められる。

【下辺が直線になるように敷き詰めたい】

     ↓この30度の隙間は埋められない
×: □△

○: □□□  or  △▽△▽△  しかない

【角を埋めたい】

□▷
 ↑ここが150°となり、ちょうど正十二角形と合う

どこか1個の角に正方形と正三角形を置き、埋められない角が出来ないように外周を連鎖的に決めていくと、 辺ごとに正三角形と正方形を交互に敷き詰めると綺麗に埋まり、逆にこれしかないことがわかる。

その時、内側にはまた十二角形が出来るのだが、正三角形を敷き詰めた辺のみ $d-1$、正方形を敷き詰めた方は $d$ のままという形になっている。

内側の十二角形は同じ理屈で外周を交互に敷き詰めることで埋められて、さらに内側には同じように、正三角形を敷き詰めた辺のみ長さの1減った十二角形ができる。

$(d,d)→(d-1,d)→(d-2,d)→(d-2,d-1)→...→(0,0)$ というように、どちらかを1減らしながら $(0,0)$ になるまでの経路数と考えられ、二項係数 ${}_{2d}C_{d}$ と一致する。

回転させての重複を除いて、この半分が答え。

Python3 小さいサンプルでの実験コード

Python3 解答コード

寄木細工の職人さんとか、経験的に知ってたりするのかな。

B - Bowling

• 広い空間に、ボウリングのピンを置く
• $A,B,C,D$ の4人が、それぞれ →,↗,↑,↖ 方向からこれを見る
• 重なっている後ろのピンは見えない（厳密には問題ページ参照）
• それぞれから見える本数を $a,b,c,d$ とすると、$d \ge 10 \max(a,b,c)$ となるような配置を1つ構築せよ
• 置ける本数は $10^5$ 本まで

ボウリングで1-5や2-8など縦に2つ並ぶように残った形は真正面から狙いたくなるが、その場合本当に真正面から当てないと前のピンに弾かれて後ろが残りやすい。 なるべくナナメから狙った方が許容範囲が広い。

$A$ と $D$ だけ考えると、少なくとも10本は必要。

A→  ○○○○○○○○○○
                         ↖D

$C$ を考慮に加えると、$A$ から重なって見えている2本が $C$ からも重なって見えることはないので、10行に増やして対処する。
その際、$D$ からは増やした行を含めて全て重ならないように、行の間を十分空ける。

     ○○○○○○○○○○
     ↕10行
     ○○○○○○○○○○
     ↕10行
A→  ...
     ↕10行
     ○○○○○○○○○○
              ↑C        ↖D

更にこの大きな塊を10回 ↗ 方向に繰り返すと、それが答え。 使うピンの本数は1000本。

Python3

どうも、⊿ の形が強いらしい。$A,B,C$ からは2本、$D$ からは3本見える。

これをフラクタルのように（重ならないように多少ずらしつつ）繰り返すと、

  ⊿      A,B,C: 4本
⊿⊿      D    : 9本

      ⊿
    ⊿⊿  A,B,C: 8本
  ⊿  ⊿  D    : 27本
⊿⊿⊿⊿

と、$A,B,C$ は2倍、$D$ は3倍になっていく。よって6段階目に64 vs 729 となり、比が10倍を超える。

C - Flipper

• 無限に広がるグリッドがある
• $N$ マス $(x_1,y_1),(x_2,y_2),...,(x_N,y_N)$ が黒く、他が白く塗られている
• 以下の操作を好きなだけ行える
• 操作
  • 連続した縦2マス、横3マスの長方形を選び、6マスそれぞれの白黒を反転させる
• 操作後の黒マスの個数の最小値を求めよ
• $1 \le N \le 10^5$
• $1 \le x_i,y_i \le 10^9$

操作を上手く言い換えたいが、3マスを同時に反転というのがなかなか見たことない操作なので、悩ましい。

黒を1、白を0とする。

ドミノや畳のように2×1のマスを同時に反転させるとき、その列のXORが不変量として挙げられる。

       #        #
      [.]      [#]
      [#]  →  [.]
       .        .
XOR =  0        0

この問題でも同様に、縦方向に関しては同時に反転させる個数は2マスなので、列ごとのXORは何回操作しても変わらない。

初期状態でXOR=1の列（黒マスが奇数個ある列）があったら、その列はどうやっても0個にはできない。

少し観察する。なるべく上の、同じ行なら左の黒マスを消すようにしてみると、

..#..#..  →  ...###..  →  ........
........      ..###...      ..#..#..

..#.##..#..  →  ...#.#..#..  →  ....#...#..  →  .....##.#..  →  .......##..
...........      ..###......      ..#..#.....      ..#.#.#....      ..#.##.#...

1つの行だけのことを考え、他の行に及ぼす影響はひとまず無視すると、

• 1つの黒マスは、$\mod{3}$ が同じ列になら好きに移動させられる
• 2個飛ばしの、つまり列の $\mod{3}$ が等しい2つの黒マスは互いに打ち消し合える

ことがわかる。

よって、行ごと・列の $\mod{3}$ ごとにXORをとると、各行の $\mod{3}$ が $0,1,2$ となる列で、黒マスを消せるか、残ってしまうかがわかる。

j%3  01201201201      j%3   0 1 2    列番号を3で割ったあまりが1と2の列のどこかには、
     ..#.##..#..  →  xor  (0,1,1)   少なくとも1個ずつ、黒マスが残る

                           (1,0,0)   操作して反転させ、あまりが0の列のどこかで
                                     黒マスが残る、という状態にすることもできる
残り方の例
     01201201201    01201201201
     ..#....#...    ...#.......

3列中2列で残ってしまうなら、反転させて1列でしか残らない方が基本的にはいい。
これは、$(1,1,1)$ となってしまったときも同様で、反転させて $(0,0,0)$ にした方がよい。

ただし、どこか1行だけを反転させることはできず、他の行とニコイチになる。全ての行での延べ反転回数は偶数回でないといけない。

012          012
.##  →×→  #..    個別に反転させることはできない  
#..          #..

.##          #..    2行セットなら反転できる。
#..  →○→  #..    縦に連続してなくてもよい。
##.          ..#    （1行ずつずらしながら操作すると、波及させていけるので）

この条件の元で、「列のXORから残ってしまう黒マス」と、「行のXORから残ってしまう黒マス」をなるべく多くマッチングさせる問題となる。
どうせ残すなら、1個の黒マスを「行でも列でも残ってしまう位置」に配置した方がよい。

行ごとのXORは、反転を適宜おこなうと $\mod{3}$ で「どの行もXOR=0」「0の列だけがXOR=1」「1の列だけがXOR=1」「2の列だけがXOR=1」に分類される。 分類毎に行数をカウントしておく。

列ごとのXORも、列番号の $\mod{3}$ ごとにカウントしておく。

    0  1  2
行  3  3  8    ←行ごとのXORで「mod3が0/1/2の列だけがXOR=1」となる行の数
列  5  7  2    ←列ごとのXORで、mod3が0/1/2ごとに、XOR=1となった列の数

貪欲にマッチングさせる。どちらか一方がいくらか余る。

    0  1  2
行  0  0  6
列  2  4  0

ここで、行に関しては $(1,0,0)→(0,1,1)$ に反転させなおすことが可能である。
行単独で見れば黒マスの個数は増えてしまうが、もうその列で打ち消せる黒マスが無く、かつ他の列には黒マスが余っている場合のみ、有効な手立てとなる。

    0  1  2          0  1  2          0  1  2
行  0  0  6  →  行  2  2  4  →  行  0  0  4
列  2  4  0      列  2  4  0      列  0  2  0

また、ここまでで行を反転させた回数が奇数回の場合は、どれでもいいのでどれか1個元に戻さないといけない。

    0  1  2          0  1  2          0  1  2
行  0  0  4  →  行  1  1  3  →  行  1  0  3
列  0  2  0      列  0  2  0      列  0  1  0

このようにして、マッチングで相殺した黒マス $13$ 個に、マッチングできずに余っている $1+1+3=5$ 個を加えた $18$ 個が、この場合の答えとなる。

注意点として、反転が奇数回だった場合の戻し方で、$(1,0,0), (0,1,1)$ など0と1が混ざった行が1個でもあればそこを戻せばよいが、 もし全て $(0,0,0),(1,1,1)$ の行だった場合、元に戻せるのは $(0,0,0)→(1,1,1)$ しかないので戻し方が異なる。
しかしその場合、行のXORは全て0、列のXORは0以上の同じ値になっているはずなので、単に列のXORの合計が答えとなり、結果的に無視しても問題ない。

Python3

D - C4

       d
   Ｓ-----Ｖ
 a ｜     ｜ c
   Ｔ-----Ｕ
       b

• 頂点 $S,T,U,V$ を上図のようにつないだ無向グラフがある
• $S$ からスタートして $S$ で終わるようなウォークのうち、$ST,TU,UV,VS$ の辺をそれぞれ $a,b,c,d$ 回通るものの個数を $\mod{998244353}$ で求めよ
• $1 \le a,b,c,d \le 5 \times 10^5$

数え上げの立式・式変形＋たたみ込み演算。

不可能な場合を先に除外しておく。
$S$ を出発して $S$ に戻ってくるにあたって、ぐるっと1周すると各辺を1回ずつ消費し、そうで無い場合は通った辺について往復で2回ずつ消費する。 そのため、ウォークが構成可能であるためには「$a,b,c,d$ の偶奇が全て一致している」必要がある。
偶奇が異なれば0通りを出力して終了。

偶奇が同じなら、規定の回数になるまで各辺で往復しまくれば、個数はともかくウォークが構成可能なことは示せる。

2回の移動を1セットとして考えると、移動終了後の位置は $S$ または $U$ に限られてパターンが考えやすくなる。

• ① $S→T→U$: $a,b$ を1回ずつ消費
• ② $U→T→S$: $a,b$ を1回ずつ消費
• ③ $S→V→U$: $c,d$ を1回ずつ消費
• ④ $U→V→S$: $c,d$ を1回ずつ消費
• ⑤ $S→T→S$: $a$ を2回消費
• ⑥ $U→T→U$: $b$ を2回消費
• ⑦ $U→V→U$: $c$ を2回消費
• ⑧ $S→V→S$: $d$ を2回消費

①～④の使いどころを先に決めた後、⑤～⑧を適当な位置に挟み込むことでウォークを構成することを考える。

①と②を計 $i$ 回、③と④を計 $j$ 回行ったと決め打つと、$i+j$ 回の $S→U→S→...$ の切り替わりが発生する。

i=2, j=4 としたときの一例

S----U----S----U----S----U----S
  ①   ④   ③   ②   ③   ④    （ここで①～④の並べ方によるパターンが発生する）

$a,b$ はそれぞれ $i$ 回、$c,d$ はそれぞれ $j$ 回消費されている。
よって残りを消費しきるためには、⑤⑥⑦⑧ をそれぞれ $\dfrac{a-i}{2},\dfrac{b-i}{2},\dfrac{c-j}{2},\dfrac{d-j}{2}$ 回行う必要がある。
（$i,j$ は、$a～d$ が全て偶数回残るように決める必要がある）

• ⑤⑧については、$S$ にいる4箇所のどこかに入れ込む
  • ここで⑤⑧の並べ方によるパターンが発生
• ⑥⑦については、$U$ にいる3箇所のどこかに入れ込む
  • ここで⑥⑦の並べ方によるパターンが発生

S------U--------S----------U------S--------U------S----|
  ⑤①   ⑥⑦④   ⑧⑤⑧③   ⑥②   ⑧⑧③   ⑦④   ⑧
  ~~     ~~~~     ~~~~~~     ~~     ~~~~     ~~     ~~

これでウォークが完成する。

$i,j$ の制約は以下の通り。

• $0 \le i \le \min(a,b)$
• $0 \le j \le \min(c,d)$
• $a～d$ が全て奇数なら $i,j$ はいずれも奇数、偶数ならいずれも偶数（残りを偶数にする）
• 1回は $U$ に行かないといけないので $i+j \ge 1$

具体的に、数え上げの式を考える。

①③と②④は交互に現れると決まっているので、$i+j$ 回のうちどれを①②にしてどれを③④にするか決めれば、並べ方は一意に決まる。

i=2 j=2    ⑫＝①または②、㉞＝③または④を意味するとする

⑫⑫㉞㉞ → ①②③④
⑫㉞㉞⑫ → ①④③②

よって、${}_{i+j}C_{i} = \dfrac{(i+j)!}{i!j!}$ 通り。

先ほどの図から、$S$ を出発点としたものだけを抜き出すと

S------U-S----------U-S--------U-S----|
  ⑤①     ⑧⑤⑧③     ⑧⑧③     ⑧

これは、以下のボールを一列に並べる場合の数と一致する。

• 赤いボール: 既定の①③の位置を示す。$\dfrac{i+j}{2}$ 個
• 青いボール: ⑤の挟み込み位置を示す。$\dfrac{a-i}{2}$ 個
• 緑のボール: ⑧の挟み込み位置を示す。$\dfrac{d-j}{2}$ 個

つまり、$\dfrac{\frac{a+d}{2}!}{\frac{i+j}{2}! \frac{a-i}{2}! \frac{d-j}{2}!}$ となる。

同様に $U$ を出発点としたものだけを抜き出すと

S-U--------S-U------S-U------S-|
    ⑥⑦④     ⑥②     ⑦④

以下のボールを一列に並べる場合の数と一致する。

• 赤いボール: 既定の②④の位置を示す。ただし末尾は必ず②④固定なので $\dfrac{i+j}{2}-1$ 個
• 青いボール: ⑥の挟み込み位置を示す。$\dfrac{b-i}{2}$ 個
• 緑のボール: ⑦の挟み込み位置を示す。$\dfrac{c-j}{2}$ 個

つまり、$\dfrac{(\frac{b+c}{2}-1)!}{(\frac{i+j}{2}-1)! \frac{b-i}{2}! \frac{c-j}{2}!}$ となる。

$i,j$ ごとに以上を掛け合わせて合計したものが答えとなる。うげぇとなりそうな式である。

$\displaystyle \sum_{i,j} \left ( \frac{(i+j)!}{i!j!} \times \frac{\frac{a+d}{2}!}{\frac{i+j}{2}! \frac{a-i}{2}! \frac{d-j}{2}!} \times \frac{(\frac{b+c}{2}-1)!}{(\frac{i+j}{2}-1)! \frac{b-i}{2}! \frac{c-j}{2}!} \right )$

上記を全ての $i,j$ について求めて合計すればよいのだが、$i,j$ はそれぞれ $5 \times 10^5$ までの値を取り得るので、愚直には無理。

ここで、上記の式を「定数項」「$i+j$ に依存する項」「$i$ に依存する項」「$j$ に依存する項」に分けてやる。

$\displaystyle \frac{a+d}{2}! (\frac{b+c}{2}-1)! \sum_{i,j} \left ( \frac{(i+j)!}{\frac{i+j}{2}! (\frac{i+j}{2}-1)!} \times \frac{1}{i! \frac{a-i}{2}! \frac{b-i}{2}!} \times \frac{1}{j! \frac{c-j}{2}! \frac{d-j}{2}!} \right )$

すると、「$i$ に依存する項」と「$j$ に依存する項」は、あらかじめ独立に $i=0,1,2,...$ と $j=0,1,2,...$ の場合を計算しておき、 FFTによるたたみ込みを使えば $O(N \log{N})$ で「$i+j$ に依存する項」に変換できる。

そして、$i+j$ ごとに「元々の $i+j$ に依存する項」×「たたみ込みによる $i+j$ の項」を合計してやれば、Σの中身が高速に計算可能になる。

Python3