HackerRank Week of Code 22
ダメダメでした。最後の問題は解けてないので書いてません。
Cookie Party
m 以上の最小の n の倍数が欲しいクッキーの数なので が答え。
Making Polygons
多角形の成立条件は(最大の辺の長さ)<(他の辺の長さの総和)である。もし最初から条件を満たしているなら答えは 0 で、満たしていないなら最大の辺を 1 回折れば構成できるので答えは 1 になる。
ただし n=1,2 のときは注意が必要。n=1 のときは 2 回折ればいい。n=2 のときは a[1]!=a[2] なら 1 回折れば作れて、a[1]=a[2] のときは 2 回折れば作れる。
Matching Sets
x[n], y[n] を昇順に並べた時、x[i] と y[i] を対応させるのが最小手数になるだろう。
x[i]>y[i] のとき over+=x[i]-y[i] して、x[i]<y[i] のとき less+=y[i]-x[i] する。答えは over==less なら over(またはless)で、そうでないなら -1 となる。
こうなる理由は次のように説明できる。オーバーしているものを 2 つ持ってきて +1, -1 しても over の量は不変。less も同様に不変。つまり over--, less-- を繰り返す以外の操作は実質存在しない。よって、この操作を繰り返して over==less==0 にならなければ構成できない。
Number of Sequences
i=1→n の順番に値を決めていくことを考える。i=pq と素因数分解できるとき a[p],a[q] の値はすでに定まっているので、中国剰余定理により a[pq] の値も自動的に定まる。つまり決定に自由度があるのは素数冪番目の要素だけとなる。
a[i]!=-1 であるとき a[d] (d は i の約数)も決まるので、こういうのは予め約数番目に伝搬させておこう。もし a[pe]=-1 だったら p 通りで、そうでないなら 1 通り。これを全て掛けあわせたものが答えになる。
Submask Queries
各クエリの集合を上位8ビットと下位8ビットに区切ることで、各クエリ 256 回程度のループで処理できる。
upd→xor→xor→upd→xor→xor→xor のような更新を受けていた場合、最後のupdから先だけが有効である。そこで最後の upd がどこにあったのかを調べたい。
集合を HL と分解する。update_time[H][sub] に更新時間、update_val[H][sub] に更新した値を入れておく(sub は L の部分集合)。このような配列があれば、最後の更新時間は update_time[sup][L] の最大値になる(sup は H の superset)。
次に xor の影響を調べよう。最後の upd から現在時刻までの sup⊕L が受けた xor の和を求めればいい。これは vector 配列 xor[H][L] に(時刻、値)を入れておけば lower_bound で取れる。
Sequential Prefix Function
s[0..i) における prefix function の値をすべての i に対して保持したい。s[0..i) から s[0..i+1) の prefix function は構成できるだろうか。これだけでは不十分である。
そこで s[0..i) ++ x の prefix function の値 d(i, x) も用意する。これが求まっていれば p(s[0..i+1))=d(p(i),s[i]) で取れる。では d(i,x),p(i) があれば d(i+1,x) は分かるだろうか。
x=s[i] ならすべて一致するため d(i,s[i])=i である。 x≠s[i] ならd(i,x)=d(p(i),x) である(このあたりが KMP に似ているのだろうか)。
p はただの配列で管理すればいいが、d は 1..106 までの値を持っているので愚直に持つのは厳しい。更新箇所が少ないので永続配列を使おう。
(よく考えたら KMP とか Aho-Corasick を使ってパターンマッチングオートマトンを作る作業と同じことをしてますね)