pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

HackerRank Week of Code 22

ダメダメでした。最後の問題は解けてないので書いてません。

Cookie Party

m 以上の最小の n の倍数が欲しいクッキーの数なので  \lfloor (m+n-1)/n \rfloor n - m が答え。

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 を使ってパターンマッチングオートマトンを作る作業と同じことをしてますね)

EF は解説を読んで解いた。文字列系の問題は言われれば分かるんだけど、直感的理解みたいなのが中々得られない。慣れれば何とかなるんだろうか。