2017-12-22

Codechef Nomvember Cook-Off 2017 - Adjacent leaves

問題

問題概要

根付き木の美しさを、good subsets of leavesの個数で定義する。

どういうものがgood subsets of leavesになるかというと、根からdfsをしていき、訪れた順番に、そのノードが葉であればその頂点番号をリストに追加する。こうすると、訪れる順番が何通りか考えられるので、その分のリストが得られる(dfs sequenceと呼ぶことにする)。そしてどのようなsubsetがgoodになるかというと、要素が1つ以上であり、そのsubsetがリストのどれかの連続部分列として現れてくれば良い。

頂点数 $n$ の木が与えられるので、各 $i (1 \le i \le n)$ をに対して、頂点 $i$ を根にした場合の根付き木の美しさを $10^9+7$ で割った余りを答えよ。

$2 \le n \le 300000$

例えば以下のような木がある：

f:id:imulan:20171222204241p:plain

1が根であるとすると、葉のノードは6個あるので、subsetの候補は $2^6-1 = 63$ 通りあるが、そのうちのsubsetでgoodでないものは以下の8通り:

{5,7,9}, {5,7,10}, {5,8,9} {5,8,10}, {6,7,9}, {6,7,10}, {6,8,9}, {6,8,10}

この3つの頂点をdfsで訪問順でみた時に連続で訪れることは有り得ない。good subsetの一例を挙げると、{5,7,9,10}などが挙げられる。これはdfsで出来る訪問リストが[6,5,9,10,7,8]となる時の真ん中の4つがこれに該当するのでgoodであると言える。

よって、上の木において根が1の場合は63-8 = 55通りになる。

アイデア

single root

問題では各頂点について根を仮定した場合の答えを要求されるが、とりあえずは1つの根に対して答えを求めることを考えよう(ここでは根を1で固定する)。

以下のdpを考える：

dp[i][0] := iを根とする部分木に対するgood subsetの個数(ただし空のsubsetと、その部分木内にある全ての葉を含むようなsubsetは除く)
dp[i][1] := iを根とする部分木に対するgood subsetの中で、dfs sequenceのprefixとして現れるもの("good prefix subset"と呼ぶことにする)の個数(ただし空のsubsetと、その部分木内にある全ての葉を含むようなsubsetは除く)

今、頂点 $i$ のdpの値の更新を考える。

まず、good subsetの中で、そのsubsetの全てのLCAを取った時にそれが $i$ の子孫になっているようなsubsetはそのLCAの位置で数え上げられているはずなので、それを持ち上げてくるだけで良い。なので、LCAが $i$ に一致するようなsubsetの個数を数えることを考える。

ここで、意識しなければならないのは、ある頂点 $i$ にいる時、dfs sequenceを作る時に、どの子に行くかを自由に選ぶことが出来るが、一度行く子を決めてしまうと、その子の部分木の頂点を全て訪問しきるまで次の $i$ の子に行くということが出来ないということである。つまり、選んでくるsubsetをgoodなものにするためには、 $i$ の子の部分木内で中途半端に選んできて良いのはたかだか2種類までであり(それがprefixとsuffixになる)、それ以外の部分木に対しては全部の葉を取ってくるか1つも選ばないといけないことが分かる。

このことを踏まえて、dpの更新を考える。 $i$ の子のノードの個数を $C$ とする。3パターンに分けて考える：

1つ目は、 $i$ の子の頂点集合の(空ではない)部分集合 $S$ に対して、 $x \in S$ の部分木に含まれる葉を全て取ってきたらそれはgood subsetになり得る。また、それはgood prefix subsetにもなり得るので、dp[i][0]とdp[i][1]の両方に加算される。具体的に加算される値は、(各部分木をまるまる選ぶか選ばないかなので) $2^C$ 通りあるが、dpの定義的に何も選ばないのと全部選ぶのは引いとく必要があるので $2^C - 2$ となる。(このパートで、dpの定義で「その部分木内にある全ての葉を含むようなsubsetは除く」と書いたのが効いてくる。重複して数え上げてしまわないように出来ている。)

2つ目は、 $i$ の子の頂点 $u$ を1つ選び、 $u$ 以外の $i$ の子の部分集合 $S$ を考える。 $x \in S$ の部分木に含まれる葉を全て取り、 $u$ 以下の部分木については全てを選ぶことはせずにgood prefix subsetとなるような葉の選び方(=dp[u][1])をすることを考える(すると、2つを組み合わせたsubsetもgood prefix subsetになる)。この場合の $S$ の妥当な選び方は $2^{C-1}-1$ 通りになる(何も選ばないのは、LCAが $i$ の子孫になってしまい重複するのでダメ)。よって、これにdp[u][1]を掛け合わせたものをdp[i][0]とdp[i][1]の両方に加算すると良い。

3つ目は、 $i$ の子の頂点 $u$ と $v$ (ただし、 $u \neq v$ )とそれら以外の $i$ の子の部分集合 $S$ を考える。 $x \in S$ の部分木に含まれる葉を全て取り、 $u$ 以下の部分木と $v$ 以下の部分木については全てを選ぶことはせずにgood prefix subsetとなるような葉の選び方(dp[u][1],dp[v][1]通り)をすることを考えると、これらを先頭と末尾に配置することで、全体で(good prefix subsetにはならないが)good subsetを得ることができる。よって、これをdp[i][0]に加算していく。具体的に加算される値は、 $u \neq v$ に対して、dp[u][1]*dp[v][1]の和を計算したもの(全体から余計な部分を引くことを考えれば、 $O(n)$ で計算できる)に対し、 $2^{C-2}$ をかけたものになる。

すると、根を1にしたものに対しては、答えをdp[1][0] + 1で得ることが出来る(+1は、全ての葉を含んだものを数えている)。

all roots

全方位木dpの2回目のdfsで、全ての頂点に対してこの頂点を根にした時の答えを求めることを考えよう。今、根を1にした時の部分木の性質が得られている。dfsをしながら、今1ではない頂点にいる状況を考えて、根付き木上で子のノードの個数が $C$ 個で、親側の方にも子が1つあり、合計で $C+1$ 個の部分木があると見ることが出来る。子側の $C$ 個に対してはもう $dp_0 , dp_1$ の値は得られていて、親側からもこの2値を伝播しながらdfsしていき、その結果を統合してそのノードに対する答えを得ることを考えたい。それは、親に対しても子と同じように $dp_0 , dp_1$ の値を持ちながら、子に渡す時にこの2つの値を更新していくことで答えを求めることができる。この時に考えるべきことは、上で考えたことと同じことを考えれば良いが、遷移させる先の分まで数えてしまわないように注意。

実装(C++)

2017-12-17

ACM-ICPC 2017 Asia Tsukuba Regional に参加しました

programming

ACM-ICPC 2017 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2017アジア地区つくば大会

ACM-ICPCというプログラミングコンテストの国内予選を通過したので、アジア予選に参加してきました。私はSyntaxSatoというチームのメンバーとして参加しました。また、自分の大学からはもう1チーム(Up to you)が参加しました。アジア予選に参加するのは初めてだったので、色々と不安な部分もありましたが、特に困る事無く、大会期間を過ごすことが出来ました。

1日目

1日目は、エクスカーション、リハーサル、歓迎会が行われました。エクスカーションはJAXAへ。

JAXAでの思い出

熱いメッセージ pic.twitter.com/vdCIR0clVx
— 鍋食べたいbot (@__imulan__) 2017年12月16日

ハードウェアを制御するようなプログラムを書くみたいな経験が無いのですが、バグった時に実害で出る可能性があるということを考えただけで恐ろしいことだなと思うなどした

リハーサルではうちのチームは次のようなことをしていました：

geditの設定
TLE、MLEがどんな感じで出るか(MLEはなく、RUNTIME ERROR扱いですが)
sample inputをwgetで一気に持ってくるやつを書いてみる
C++だけじゃなくてpythonも書いてみる*1

普段括弧の補完がある環境をつかっていたため、geditは辛かった(話によるとEclipseは括弧の補完あるらしい、それだけでも使う価値ある)

歓迎会ではチーム紹介などが行われ、うちのチームは早く終わらせることを意識しすぎた結果、どこの大学から来たかという情報が完全に欠落した(スライドにも書き忘れた)

2日目

2日目は、コンテスト本番でした。

解いた順番としては、BACIGの5完で、12位でした。

チーム方針として、1問に対して2人が触るような形になっていて、コーディングも問題によって結構分散していた(自分はAとCとGを書いた)。 D以降の難易度がランダムということもあり、ABCまでが終わった段階で次にどれに手を付けるかの見当をつけるために、幾何っぽいの以外をとりあえず見て、どれがいけそうかを考えた。自分の実力がアレなのもあって、まず問題を読んだ時に適切に難易度を推定するのはかなり実力がないと厳しいという感じで、なかなかそこも難しいなと感じたりしました。

GでWAを出さなかったので、それが通った時はかなりいい気分になった(逆にWAが出てたら、絶対にデバッグが闇になるのが見えてたので、考えたくない)。

感想

国内予選の順位からして、12位はかなり健闘だったと思います。 5時間セットを何回か練習していったのはかなりいい練習だったのではないかなと思います。これからも、学内でああいう練習会をコンスタントにやっていけるといいですね。というかやりましょう...

筧先生と少し話した時も仰ってましたが、やはり継続的に参加者が出て来ることはかなり重要に見えるので、後輩が続いていくといいなあという気持ちです。*2

いかにも引退しそうな雰囲気ですが、個人としては来年も参加権があるので、参加していきたい(ただ、このチームとして出るのはもう不可能なので、残念です... )。

来年もこの参加記を書けることを願って、今年の参加記はおわりです。

*1:方針として、計算量に余裕があるときかつ多倍長を使いたい/文字列処理を楽にしたい...などのときに書きやすいので選択肢として十分にありえました( 実際、本番のA問題で使用しました(WAを出しました、ごめんなさい) )

*2:アルゴリズムとデータ構造の授業が面白くなれば、人を誘うのは簡単になりそうですが、現状は------。

裏紙

ほぼ競プロ、たまに日記