コンテストページ
解法
✔A - ニコニコ文字列判定(100 点)
char で 4 回入力を受け取って、0 文字目と 2 文字目、1 文字目と 3 文字目が等しいかどうかを判定すればよいです。
✔B - 2525文字列分解(300 点)
2 -> '(', 5 -> ')' と書き換えると、正しい括弧列であることが 2525 分解の出来る条件で、ネストの深さが分解の最小数です。
✔C - Kill/Death(500 点)
これが 500 点、本当ですか!?
A のデス数の場合の数を数えます。これは、B のキル数の総和を分配するやり方であって、A のキル数の同じであるもの同士の入れ替えを同一視したものです。これは、自然数の分割が複雑になったものですね。
まずは A をキル数で仲間分けして、メンバーの数の配列を改めて a と置いておきましょう。 そして、初めの i 個のグループのメンバーに j 個を分配する場合の数を crr = dp[i][j] と置きます。 すると遷移は、自然数 n の長さ k 以下の分割の数を p[k][n] と置けば dp[ i + 1 ] [ j + m ] += crr * p[ a[i] ] [ m ] と書けます。
分割数の計算をしましょう。ヤング図形の共役を考えると、長さ k 以下の分割は、最大成分が k 以下である分割と 1 対 1 対応することがわかります。詳細は省略するのですが、これの母関数は と書けることが知られていますから、これを展開した式が漸化式です。
以上、p の計算と dp の計算は、いずれも 3 乗の時間がかかってしまいます。そこで、両方とも FFT で高速化しましょう。p の方はそもそも多項式で書いてしまいましたが、dp の方もよく見ると多項式の掛け算の形になっています。
ツイッターの様子
第4回ドワコン、ばちゃお疲れ様でした...!!
— ねてるくん (@neterukun_cd) January 13, 2020
A: 文字を比べます
B: 括弧列の対応が見えます
C: x + y + z + ...<= n, 0 <= x <= y <= z <= ...を満たす通り数を考えてたら実は分割数でした
D: DFSであれもこれも状態欲しいをやったらdfs1~4まで生えてバグり散らかしました...残念
FFT はいらないという説が出てきました。たしかによく読むと N, M の制約は 100 ですから、100 × 1000 × 1000 で 10 の 8 乗、これならば間に合いそうです。9 乗かと勘違いしてしまいました。たしかに、FFT パートがなければ 500 点くらいかもしれません。
解説 PDF の様子
FFT かと思ったのですが、ただの実行時間が厳しい問題でした……
✔D - ディスクの節約(600 点)
bit DP です。現在メモリに乗っているものではなく、既に処理したものがなんであるのかを管理するのが味噌です。
部分集合 bs の処理を済ませるために、最も節約しながらメモリを使ったときの最大使用量を dp[bs] と置きます。なお bs が部分木でないときには意味不明なのですが、私の実装ではこれらはすべて inf になります。
さて、遷移です。bs が処理済みのとき、次に処理できるもの i を列挙して、それぞれ遷移です。新たに i を処理するにはどれくらいメモリが必要でしょうか。まず、消しても良いものは全て消します。すなわち、親が処理済みなものはメモリから消えています。それ以外のもののメモリ使用量に i のメモリ使用量を足したものが、この瞬間に必要なメモリです。
ただ、これだけではありません。i を処理する瞬間のメモリだけではなく、過去も見つめる必要があります。ですから、先ほどお話した値と dp[bs] との max を取っておいて、それを dp[ bs | 1<<i ] に change min で遷移します。
✔E - ニワンゴくんの家探し(1000 点)
インタラクティブです。
重心を探しましょう。次数が 1 以下なら頂点数が 1 か 2 なので、特別処理です。 次数が 2 以上なら、トップ 2 のブランチの根でクエリしましょう。
どちらかが近かった場合は、その部分木のサイズになるのですが、これはもとの 1 / 2 以下です。また等距離ならばのとりのブランチになるのですが、これはもとのサイズを N として、N - (N - 1) * 2 / 5 以下です。なぜならトップ 2 ブランチがそれぞれ (N - 1) / 5 以上のサイズだからです。
以上より、部分木は常に 3 / 5 倍(+1 くらいはあるかも)以下になります。ここで wolfram alpha さんの登場です。神のお告げを乞いましょう。
どうやら怪しそうですね。とはいえ除算は毎回切り捨てですし、なんだかんだなんとかなるのではないかなと思い、そのまま決行したところ、通ってしまいました(はい!?!?)
結果
121:14 全完、当時の順位表で 19 位相当です。これはかなり良かったのではないでしょうか。
特にインタラクティブが間に合ったのは嬉しいです。インタラクティブはローカルにジャッジを用意するところから始めると決めていますから、確信を持って提出することが出来ます。嬉しいですね。