TTPC 2023 をupsolveするだけのログ

atcoder.jp

TTPC2023、かなり面白い問題が多い(と思った)ので、コンテスト終了後も結構粘って解くなどしていました(もはやコンテスト5時間とか何も考えずに……　ほぼProject Euler)

一部問題は解説・解法を見てしまいましたが、基本的に解説を見ずに解いています

ネタバレ・解法バレを多分に含むので解きたい人は読まないでください

submissions: atcoder.jp

A - Numerous Elimination

コンテスト中に解いた
頭が回ってなくてOEISで解いたそうです

B - Almost Large

コンテスト中に解けず、解説を読んだ
完全に頭が回ってなくて、解説を読んで悲しい気持ちになりました
- 僕はこの手の経路探索を改札ダイクストラと呼んでいるのですが、完全にそれでした
- 由来はARC061です (当時すごく感動した記憶があります)
- atcoder.jp

C - Yet Another Simple Math Problem

コンテスト中に解いた
頭が回ってなくてパターンを列挙したそうです

D - Spacecraft

コンテスト中に解けず、後で解いた
ハイパー3D幾何
実は無限遠だけ考えれば良いことが分かれば、あとは球面幾何でホイ
- 3D幾何の回転とかが行けるなら割と球面幾何方針もきれいに書けると思う
- 詳細はhackmdに置いた
- hackmd.io

E - R-Connected Components

コンテスト中に解いた
x² + y² = R なるベクトル (x,y) を集めて、その線形和が張る格子の格子定数が答え
格子の縮約にLLL……という気持ちをグッとこらえ、格子のサイズを減らすという操作は
- 2ベクトルのなす平行四辺形の面積は外積
- 外積には線形性が成り立つ
- 使えるのは整数倍と足し算引き算
となり、
- 数の整数倍と引き算で値を非0で最小化する
- といえば…… → GCD(ユークリッドの互除法)
なので、任意の2ベクトルの外積を集めて、そのGCDを取れば答え
あまり厳密な証明はしていないし、そもそも計算量も(任意の2ベクトルの外積が必要なので)結構悪い
公式解説が賢いが、まだ理解していない……

F - N^a (log N)^b

コンテスト中に解いた
構文解析だ～～～
構文解析をバグらせたり、log多重周りでバグらせたりした
- 数式の意味単位のBNF表記が与えられているとBNFどおりに書けば良いので楽 (なんか再帰下降パーサが流布され始めた頃は雰囲気で定義されていた……気がする……)
  - 掛け算と足し算をどっち先に処理しなきゃいけない……みたいなのが良いBNFだとそのまま書くだけで行ける (今回のは良いBNF)
  - <expr> ::= <factor> | <expr> “+” <factor> | <expr> “*” <factor> みたいな定義をされると考えないといけなくなる
- 例: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp
多WA枠として結構面白い問題でした

G - Cola

コンテスト中に解けず、後で解いた
- これは解説を読んでないが、TLで五角数定理が流れてきてしまったのを見ています
前から一個ずつ特定して、当てたら次のを1回だけ0コストでクエリできる、と言い換えると問題がシンプルになる
- Pr[rand(1) + rand(2) + … + rand(N) ≤ M-1] みたいな形になった
あとは(五角数定理カンニングもあり)多項式表現に落として数式をこねると答えが出てくる
- rand(k) を (1/k + 1/k x + … + 1/k x^k-1) = 1/k (1-x^k)/(1-x) と表現して計算
- 分子側で五角数定理の形が出るので変換、分母側は負の二項係数で分子に持っていって、必要な係数の部分だけ畳み込んで終わり
- 五角数定理、今更ながら初めて触ったかもしれない
- あとFPSをこねるのもそこまで慣れてない

H - 404 Chotto Found

コンテスト中に解けず、後で解いた
- 解説を読んでおらず、TLでSAが流れてきてしまったのを見ていますが、そもそもどうせSAだろうな……と思ってコンテスト中に問題をそっ閉じした記憶があります
SAとLCPを丁寧にやってセグ木に乗せると解ける
ACLにSAがあるから書かなくて良いの、いい時代だな……と思います
- 自前ライブラリをちゃんと整備しろという話ではある

I - T Tile Placement Counting

コンテスト中に解けず、後で解いた
これね、すごい
結論から言えば公式解説にもあるように、Tタイル敷き詰めの論文を見つけて、それを実装すればOK
Wがめちゃ長いので、遷移行列を求めて行列累乗する方針になるが……
- 遷移行列の計算に論文知識を入れる必要がある
- 公式解説はchain graphの方でやってるみたいだけど、僕はもっと数式が直接書かれている "Tilings of rectangles with T-tetrominoes" の9章のTutte多項式を使いました
- で、これを数え上げようと思うと連結成分を管理する必要があり……
- 完全にフロンティア法(フカシギの数え方)じゃん！！！！
- となりました
  - (興奮するソース)
あとは行列累乗をすれば終わり……ではなく、logWが異常に大きく間に合わないので、Berlekamp-Masseyするか定数倍鬼速行列乗算を持ってくるかしましょう、で終わり
- ……ちなみにBerlekamp-Masseyすると何やらカタラン数より小さい次数が出てくるんですが、そもそも上下対称な構造であることを思い出すとステートを上下ひっくり返して同一視して良くて、それを使って状態圧縮した行列を考えると実は小さくできる (BMの次数と一致する)
- この圧縮版行列を使えば普通の行列累乗でも間に合う
(まだ完全に理解してないけど、行列累乗の高速化といえば Black box linear algebra だと思っていてそれを持ち出したが、ただのBMで良かった)
- yukicoder.me

J - Set Construction

コンテスト中に解けず、後で解いた
パズルか？と思い色々実験してそのまま通した
0、2^N-1 が必ず入ることに気をつけると、ビット排他なパターンを組み合わせて M-1 か M-2 を作る問題になる
- ビット排他なものを組み合わせる場合、それまで使ったビット位置をすべて1で塗りつぶす、をすることでAND/ORに影響が出なくなるので足し算になる
使ったパターンは以下
- 2冪 (2^k - 1 通り)
- n=3,4,5 の全探索
  - n=5 は 2^2ⁿ-2 = 2³⁰ がさすがに間に合わないので最低限の表現力になる 2^{min(2ⁿ-2,17)} とかでやった
- 2冪+α
  - 0~k-1 ビットで2冪パターンを作ったところに、k-b~k+c ビットを1にした値を添加して推移的に得られる集合
  - これは 2^k + 2^k-b - 1 みたいな値が作れる
    - これを繰り返したら純粋な2冪を総和できるかも……？と思ったけど試してないしあまりうまく行く気もしない
  - cは余ったビットを1に使い切るためだけの調整用
- 乱択埋め込み
  - 上記で n=7,m=28 と n=8,m=30 以外はカバーしたので、あとはこのパターンだけ乱択で探して埋め込みました
ソース atcoder.jp

K - Dense Planting

コンテスト中に解けず、後で解いた
- これは解説を読んでいないが、TLに流れてきた天才グラフ形状を見てしまった
天才グラフ形状を頭に入れた状態で探索
- ただこの探索も結構簡単にはできない
- ……と見せかけて、実は普通に上限を丁寧にやる全探索がかなり小さな探索空間になるので、余裕で間に合う
- ソース atcoder.jp

L - Next TTPC 3

コンテスト中に解いた
BもCもわからん……をしていた時にふと Next TTPC 3 が問題リストにいるのを見て、あわよくばFA取れそうと思い着手
- 残念ながら2番手……
問題自体は周期で剰余を取る・二分探索で数え上げに落とす・境界を丁寧にやると比較的素直で教育的な問題という印象、良い
- あのNext TTPCシリーズがこんなつよつよ問題になってしまい、感動しています

M - Sum is Integer

コンテスト中に解いた
ユーザー解説の方の解き方をしていた
この手のハッシュ系乱択問題、すき

N - Bracket Sequestion

コンテスト中に解けず、後で解いた
まず部分点がきつい
- はてなを括弧に一対一対応させる数え上げ典型をすると、O(N²)の経路DPっぽいのが手に入る
- 素直に書くと2べきのかかったbinomial convolutionで、よくわからない
  - NxNグリッドで、左下領域を通らず、ある縦遷移を固定してそこで初めて閉じ括弧確定のはてなを使う、とすると、その縦遷移までのdyck pathと、縦遷移後のdyck path (にはてな使う使わないの2べきが掛かった形)として計算できる
  - 最終的に欲しいのは(combの中身が±1ぐらいする) 2^i+n-j comb(i+j,i) comb(2n-i-j-1,n-j-1) みたいな感じ
- 2べきの項が一致する箇所をまとめた総和の値を眺めると…………
  - k=i-j として k ごとに見てみる
    - この時カタラン数みたいに斜め線ができて反対に折り返すと comb(2n-1,…) みたいな式になりそうだなぁ……という気持ちになっておく
  - n=5, i-j=5: comb(5+0,5)comb(9-5-0,4-0) = 1
  - n=5, i-j=4: comb(4+0,4)comb(9-4-0,4-0) + comb(5+1,5)comb(9-5-1,4-1) = 11
  - n=5, i-j=3: comb(3+0,3)comb(9-3-0,3-0) + comb(4+1,4)comb(9-4-1,4-1) + comb(5+2,5)comb(9-5-2,4-2) = 56
  - n=5, i-j=2: … = 176
- ……パスカルの三角形のある三角形の部分和っぽくないか……？(エスパー)
  - comb(2n-1,…) = comb(9,…) に注目していたので、そこから上を眺めると
    - 11 = (1) + (1+9)
    - 56 = (1) + (1+8) + (1+9+36)
    - 176 = (1) + (1+7) + (1+8+28) + (1+9+36+84)
- → hockey stick identity が成り立つのであるラインのbinomialの総和！
  - つまりcomb(2n,…) = comb(10,…) を見れば
    - 11 = 1 + 10
    - 56 = 1 + 10 + 45
    - 176 = 1 + 10 + 45 + 120
  - (ここのエスパー、結局なんで成り立つのかまだ理解できてないが……)
- binomial を累積すればいいので $O(N\log p)$ とかそれぐらいになった
で、満点を探す
- 上記は本当は dyck path で (binomial - binomial) * (binomial - binomial) みたいな形をしていたので、諸々展開して各二項係数を整理すると $\displaystyle\mathrm{Catalan}(n) + \sum_{i=0}^{n-1} 2^{\max(2n-2-i,n)} \binom{2n}{i}$ になる
- とりあえずカタラン数を求めたい
- そもそもでで計算できるのかな？ → できない……(コードテストで確認)
  - 階乗だけなら埋め込みで高速化できるらしい……というのは後で知った
- 高速に計算する手段があるはず…… → P-recursive sequenceに出会う
- カタラン数が高速に計算できるのは分かったけど、2冪×二項係数の総和も P-recursive ってやつなのか……？ → そうっぽい
- で、
- r-th.hatenablog.com
- こうです。
この問題が一番時間かかった
- 5時間コンテストとは……？
- ちなみに「これP-recursiveだな、あとはどうやって実装するか……」を調べる際に “P-recursive AtCoder” で検索したらTTPC2023の解説がトップヒットしてしまい、半分ネタバレをくらいました(結局P-recursiveなんだな……という情報しか得られてないのでセーフ)

O - 2D Parentheses

コンテスト中に解けず、後で解いた
包含関係を考えるとタイブレークできて、同じ座標の点を無くすことができる
端の方から閉じ括弧を見ていくことを考えると、一番近い開き括弧を選ぶとしてよい
- 近いのを選ばず遠いのを選ぶと、後々その近い開き括弧を他の閉じ括弧が選ぼうとした時に邪魔になる可能性がある
あとはこれが判定できればOK
- 二次元包含クエリで、長方形の四隅にxorが0になるような4つの乱数を振っておけば、長方形領域のxor総和が0か？で半端な包含を判定できる
- ……が、どうやらこれはオーバーキルらしい

P - Bridge Elimination

コンテスト中に解けず、後で解いた
対称性がすごい
- $i$ 個の値を乗算した項の総和は $(1+A_ix)$ の乗算結果(ほぼDP)でOK
あとは「個の二重辺連結成分になるようなグラフの数(厳密には対称式の寄与)」を数え上げればOK
- これは寄与典型
二重辺連結成分はOEISに転がってる
- A095983
- なんかMathematicaでFPSいじれば行けるって書いてあるのでやると、なんか求まる
あとは個の二重辺連結成分に分割されたグラフを一成分ずつ決めていくDPで求めていく
- ただ最終的な $k$ 成分の木の繋ぎ方がCayleyの公式でうまくいかない(各成分の次数に応じてどの頂点と繋ぐかが累乗される)のでなんとか数えたい
- “count tree fixed degree” とか調べると
- math.stackexchange.com
- $\displaystyle\frac{(k-2)!}{\prod_i(d_i-1)!}$ らしいです
各成分の木としての次数の総和を管理しながらやれば行けそうですね。
- dp[k][v][d] := k成分をv頂点で木次数総和dで作る数え上げ
- 状態数O(N³) 遷移O(N²) でTLE……
- 2次元FFTすれば O(N³ logN) も見えそうだけど N=400 はきつい……
各成分の構成頂点数がで固定の場合に、次数制約とか気にせず数え上げられれば良さそう
- もう一回考える
- として、dp[i][e] := 成分まで見ての総和が
  - 最終的に欲しいのは dp[k][k-2]
- 使う次数を f として dp[i+1][e+(f-1)] ← dp[i][e] * $m_i^f\cdot\frac{1}{(f-1)!}$
- 多項式にすれば
  - $\displaystyle g_i(x):=\sum_{e=0}m_i^e\frac{x^e}{e!}$ としましょう
  - 最終的に欲しいのは $\left(\prod_{i=1}^k m_i\right)[x^{k-2}]\prod_{i=1}^k g_i(x)$ ですね
これ指数型母関数ってやつですよね？入門しちゃいましょう
- 37zigen.com
- 集合と関連付けられるとすると $m_i^e$ なので $e$ 個要素を選んで $m_i$ 色に塗り分ける……と考えられそう
- つまりこれは「 $k-2$ 個のボールがあって、 $e_i$ 個ずつ $k$ 個のグループに分けて、グループごとに決まった $m_i$ 色の内の色で各ボールを塗り分ける」という通り数……？
- もはやグループごとに色種類を分ける必要はなくてどのグループであっても $\sum_{i=1}^k m_i$ 色から1色選ぶ……として重複なく合算できるので、結局これは $N^{k-2}$
- ほしかった値がになったので、次数制約をDPから省いてトータル
  - ちなみに $O(\log p)$ がつくとTLE(1敗)