HackerRank May World CodeSprint
https://www.hackerrank.com/contests/may-world-codesprint/challenges
Compare the Triplets
言われたとおりに実装。
Richie Rich
とりあえず最小手数で構成。まだ操作回数が余ってるなら上の桁から 9 に変えていく。
Absolute Permutation
よく考えると条件を満たす順列はひとつしかないので、それを実際に構成すればいい。
Beautiful Quadruples
(W,X) を全通り試す。W xor X = Y xor Z となる(Y,Z)のパターン数は配列に入れておけばいい。
Square-Ten Tree
自分は非再帰 segment tree に近い方法で覆うことにした。半開区間の方が慣れているので半開区間で解く。
- X=10 とする。
- L 以上の X の倍数 L' を計算する。
- R 以下の X の倍数 R' を計算する。
- L'≧R' なら [L,R) で覆い操作を終了する。
- [L,L'),[R',R) で覆う。
- L←L', R←R', X←X2 とし操作 2 に戻る。
ループは 20 回以下で終わる。L,R が非常に大きいため多倍長整数で計算する必要あり。Discussion で出力について質問している人がいて助かった。
Div and Span
parenthesis と bracket を独立に並び替えて、それらをマージする。
parenthesis の方は dp[ i 文字使った ][ 開いている括弧の数 ][ まとまりの数 ] として O(n3) の DP をすればいい。bracket の方はカタラン数なので二項係数で計算できる。
マージするときは ( ( ) )+( )+( ) は PPP、[ [ ] ] は BBBB とみなし、PPPBBBB の並び替え総数を求めればいい。このとき () のまとまりの数が活きてくる。括弧に区別があるので最後に X!Y! に掛けて終わり。……簡単すぎない？
Travel in HackerLand
TLE,MLE が怖いけど永続で解けるのは明らかなので殴ったら通った。
辺コスト x 以下のグラフの set 付き unionfind が保持できればいい。もし保持できれば二分探索で答えを見つけることができる。
愚直に unionfind を保持すると O(n2) になるが、unionfind と set を永続化すれば多少現実的な計算量になる。set の永続化には RBST を使った。
座標圧縮しなくても動きはするが、二分探索のループ回数を減らすために座標圧縮は掛けた方がいい？二分探索のループ回数を 30→20 に減らしたら TLE を回避できた。
普通の unionfind なら経路圧縮が有効だけど、永続バージョンの場合は経路圧縮するとノードが増大＋圧縮しても使われない可能性があるから良くないっぽい？経路圧縮切ったら 1sec 未満に収まった。
Unique Colors
部分木に対する距離の総和を求めるのは難しくない。
dp[curr] を curr から部分木への距離の総和とする。curr から next の部分木の頂点にパスを繋ぐことを考えると、もし色の重複がなければ距離の総和は dp[next]+sub[next] になる。 実際には色の重複があるので、囲まれているノードの個数だけ減らす必要がある。これはマージテクで処理可能。
問題なのは親側の総和である。
頂点 v から見たとき途中に同じ色があって隠れてしまう頂点の個数を高速に求めたい。これが思いの外面倒である。
ノード数を増やさず、同じ色同士の隣接関係が保持できる圧縮ができないか考えてみたら、次のような圧縮が思いついた。
- 祖先に同じ色があったら、それの一個下の祖先に辺を結ぶ。
- 親が同じ色だったら、親に直接つなぐ。
これなら頂点数は高々 2n だし、隣接ノードの部分木のサイズの計算も簡単だ。
頑張れば解けそうな気がしたので粘って全完。
