AtCoder Beginner Contest 036 D : 塗り絵

abc036.contest.atcoder.jp

当初の方針

  • DPだろうなあ・・・(定義が分かるとは言っていない2回目)
  • 木だから、木の嬉しい性質を利用するのかな
  • まず全探索。白か黒で遷移してチェック。これは2^10^5なのでダメ
  • 両端が黒になるものを列挙して、残りの組み合わせを足していくのは?

f:id:arukuka:20161014164756j:plain

  • 重複がある。それを除く方法も分からない(たぶんない)
  • 諦めて解説を見る

解説を読んで

木DPというらしい。DP好きとしてはマスターしておきたいところ。

解説の通りに実装したらACしそうだけど、なぜそのように立式できるか
分からない。

サンプルケース1でテストしてみる。

f:id:arukuka:20161014164838j:plain

やべえなんだこれ天才か

いざ実装

DPって書いてあるけど、木だからループはないし、
根から探索するので大丈夫でしょう → 大嘘
debugを見てみると同じ探索をしている。フィボナッチ数列みたいな感じ。

メモ化再帰で解いてみる → TLE

Submission #924250 - AtCoder Beginner Contest 036 | AtCoder


やっぱりDPしないとダメなので、PriorityQueueに突っ込んで
深さの大きいところから計算しておく。
こうすれば前に書いたメモ化再帰もDPっぽい動きをしてくれる。
(今思えばソートで十分なのだけれど、イメージとして
PriorityQueueのほうがしっくりきた)
AC。

Submission #924259 - AtCoder Beginner Contest 036 | AtCoder

ちょっと待てよ?

なんでメモ化再帰しているのにTLEするのだろう。

考えられること

  • 関数呼び出しのオーバーヘッドがかかる

(木に対してDFSするとよくあることで
最悪スタック領域が足りなくなりREになる)

  • debug文を残していたのが悪かった。

debug文を消して提出してみる。 → AC

Submission #924303 - AtCoder Beginner Contest 036 | AtCoder


まじかい。しかもlog(N)がない分だけか、早くなってる。

次からは消してから提出しよう・・・。