SRM716 div1

前回初参加した結果おかしなレーティングになったためdiv1に放り込まれました。

結果は一完。かなしい

easy

bc>=ab>=caと仮定します。

このときA='1..1'(max(ab,ca)個)、B='1...1'(ab個),C='1...1'(ca個)とすると、AとB,BとCについては条件が満たされています。あとはBとCの条件を満たすようにすればよいのですが、この状態からBとCの末尾に0を追加してもＡとＢ、ＡとＣのLCSは変わらないことがわかります。したがってBの末尾にbc-ab個の0,Ｃの末尾にbc-ca個の0を追加することで、ＢとＣのLCSは1..10..0(min(ab,bc)個の1,bc-min(ab,ca)個の0)となり、この長さはbcです。以上の操作によって得られた文字列が答えです。あとはab,bc,caの大小について場合分けをして頑張ると通ります。

medium

時間内には通せませんでした。

まず根からＳに含まれる距離の移動のみを行ってたどり着ける頂点を列挙できたとします。この頂点がたどり着ける頂点のすべてであり、逆にこの頂点集合内での任意の2頂点間での移動は全てＳに含まれる距離の移動のみで可能であることがわかります。したがってこの頂点集合内で2重ループを回して2頂点間の距離を列挙し、その集合にＳが含まれればPossible、そうでなければImpossibleです。

根からたどり着ける頂点の列挙ですが、僕は深さに関する(01でない)ナップサック問題のようにして実装しましたが、何か別の方法はないですかね。

また2頂点間の距離を予め計算しておく必要がありますが、これは単純にn回bfsをする方法と、LCAを用いる方法があります。前者では計算にO(n^2),クエリにO(1)かかり、後者では実装によりますが僕の場合は計算にO(nlogn),クエリにO(logn)かかります。今回はO(n^2)回2頂点間の距離を取得するので、前者であれば全体の計算量はO(n^2),後者はO(n^2logn)となります。僕のLCAライブラリが貧弱なため、後者ではTLEが発生しました。

hard

わからん(´・ω・`)

あとがき

レーティングは1765から1741に下がりました。下がるのは当然ですが全然下がってませんね・・topcoderのレーティングはよくわかりません。