ブログ名

競技プログラミングやお歌のお話をする高菜です。

第4回 ドワンゴからの挑戦状 予選 (virtual) 解法

コンテストページ

第4回 ドワンゴからの挑戦状 予選 - AtCoder

解法

✔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 対応することがわかります。詳細は省略するのですが、これの母関数は  \prod_{i=1}^k (1 - q ^ k)  ^ {-1} と書けることが知られていますから、これを展開した式が漸化式です。

以上、p の計算と dp の計算は、いずれも 3 乗の時間がかかってしまいます。そこで、両方とも FFT で高速化しましょう。p の方はそもそも多項式で書いてしまいましたが、dp の方もよく見ると多項式の掛け算の形になっています。

ツイッターの様子

FFT はいらないという説が出てきました。たしかによく読むと N, M の制約は 100 ですから、100 × 1000 × 1000 で 10 の 8 乗、これならば間に合いそうです。9 乗かと勘違いしてしまいました。たしかに、FFT パートがなければ 500 点くらいかもしれません。

解説 PDF の様子

f:id:ngtkana:20200114004525p:plain

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 さんの登場です。神のお告げを乞いましょう。

f:id:ngtkana:20200114002429p:plain

どうやら怪しそうですね。とはいえ除算は毎回切り捨てですし、なんだかんだなんとかなるのではないかなと思い、そのまま決行したところ、通ってしまいました(はい!?!?)

結果

f:id:ngtkana:20200114002628p:plain

121:14 全完、当時の順位表で 19 位相当です。これはかなり良かったのではないでしょうか。

特にインタラクティブが間に合ったのは嬉しいです。インタラクティブはローカルにジャッジを用意するところから始めると決めていますから、確信を持って提出することが出来ます。嬉しいですね。