はまやんはまやんはまやん

hamayanhamayan's blog

HackerRank HourRank 20 問題と解説

競技プログラミング

https://www.hackerrank.com/contests/hourrank-20/challenges

Hot and Cold

4人が部屋の温度の条件を言っている。

  • AさんはC[0]度以上がいい
  • BさんはC[1]度以上がいい
  • CさんはC[2]度以下がいい
  • DさんはC[3]度以下がいい

4人の条件を満たす温度にできるか

Counting Perfect Subsequences

abcdからなる文字列がある。
この文字列の部分文字列のうち、aとbの個数が同じでcとdの個数が同じ部分文字列は何通りあるか(mod10^9+7)

Birjik and Nicole's Tree Game

N頂点の根付き木がある。
これに対して、Q個のクエリについて考える。
各クエリではK個の頂点が与えられて、その頂点のみ黒色で他は白色に塗る。
これに対して、「c[i] := その頂点を根とした部分木の黒頂点の数がi個である頂点の数」を求めて答える。

以下、解説

















Hot and Cold

https://www.hackerrank.com/contests/hourrank-20/challenges/hot-and-cold/submissions/code/1301516445
AさんとBさんの条件を満たすには、low = max(C[0], C[1])度以上である必要がある。
CさんとDさんの条件を満たすには、high = min(C[2], C[3])度以下である必要がある。
あとは、「low <= high」であれば全員が納得する温度にできる。

Counting Perfect Subsequences

https://www.hackerrank.com/contests/hourrank-20/challenges/p-string/submissions/code/1301517639
まず、abcdの個数を数えておく。
ここで、作れる部分文字列はabが[0,min(a,b)]個あって、cdが[0,min(c,d)]個ある文字列であるので、これを全列挙する感じで考える。
abをi個、cdをj個使う部分文字列の個数はaCi*bCi*cCj*dCjである。
よって答えは、sum{i=0...min(a,b)}{j=0...min(c,d)}aCi*bCi*cCj*dCjを計算すれば良い。

これを愚直にやるとTLEなので、高速化する。
上記の式はよく見ると、aCi*bCiとcCj*dCjの全ての組合せの積の和をしていることになる。
なので、(aCi*bCiの全通りの和)*(cCj*dCjの全通りの和)と同じであるため、こっちで計算すれば間に合う。
i=0,j=0の時は空の文字列なので、それだけ引いてAC

Birjik and Nicole's Tree Game

https://www.hackerrank.com/contests/hourrank-20/challenges/birjik-and-nicoles-tree-game/submissions/code/1301518293
愚直に書いたら、まあって感じ。

https://www.hackerrank.com/contests/hourrank-20/challenges/birjik-and-nicoles-tree-game/submissions/code/1301519327
ある頂点が更新されたら、答えが変わってくるのはその親ノードだけやん！
と思って高速化をちょっとしたらちょっと上がった。

解説もさっぱり分からんので、以下、プロからの情報だけ載せときます。





pekempey.hatenablog.com