https://twitter.com/kinaba のログ (twilog の方が便利です。)
| 帰宅早々、近年まれに見るくらい http://twitter.com/Cryolite/status/14666633659 がツボに入っている）））））） | |
| 「幅優先ないしは深さ優先でにノードの色を列挙すると "黒赤黒黒黒黒赤赤赤黒黒黒赤黒黒……" となるような、赤黒木条件を満たすような木の総数を mod 1000000007 で求めよ。」 (Div1 500点) | |
| @tsukuno なにも詳細考えてなかったのだけが、行きがけ順と帰りがけ順は問題として真っ当になりそうな気がする。inorderと幅優先は考える気おきないでござる | |
| あれ、Balance the Tree http://www.kmonos.net/wlog/59.php#_2336060309 みたくやれば一意に復元できたりするかな？ | |
| よし、どのノードも子供の数が 2 or 0 である (= http://ja.wikipedia.org/wiki/%E8%B5%A4%E9%BB%92%E6%9C%A8 で言うNILの色まで並べてくれる) なら、行きがけ順/帰りがけ順から一意に復元できることが証明できた気がする | |
| パス上の黒の数を固定すれば幅優先でもuniqueに定まるからせいぜい O(n^2) で数え上げられるな。もっと制約かけられそうかも。残るは通りがけ順… |