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

hamayanhamayan's blog

HackerRank Week of Code 31 問題と解説

https://www.hackerrank.com/contests/w31/challenges

問題

Beautiful Word

  • 隣り合う文字が同じではない
  • 母音("aeiouy")が隣り合わない

ならば、その文字列は美しい。
文字列wが美しいなら"Yes", そうでないなら"No"を出力せよ

Accurate Sorting

長さNの0~N-1から成る数列Aがある。
隣り合う数の差が1なら隣り同士をスワップできる。
このルールでスワップして、昇順に並べることができるか。

Zero-One Game

長さNの0,1から成る数列がある。
この数列に対して以下のルールでゲームをするとき、先手Aliceと後手Bobのどちらが勝つか

  • 数列から1つ数を消していくが、左右が0で挟まれている数のみ消せる
  • 端の2つの数は消せない
  • 消せなくなったら負け

Spanning Tree Fraction

N頂点M辺の連結無向グラフがある。
辺についているコストA[i],B[i]について、(A[i]の総和)/(B[i]の総和)が最大となるようにこのグラフを全域木にする。
その最大値を既約分数の形で答えよ。

Colliding Circles

N個の数列Rがある。
等確率で数列内の2要素を取り出して消し、足して追加するという操作を行う。
この操作をK回繰り返したときに、最終的な数列Rの要素の二乗の総和*πの期待値を答えよ。

Nominating Group Leaders

N人の人物がいる。
iさんはv[i]さんに票を入れている。
これに対してクエリに答える。
[L,R]の票を集めた時に、丁度X票獲得した人を答えよ。
複数人いる場合は、最もIDが小さい人を答える。

Split Plane

以下のクエリを処理する。
N個の線分があり、線分で区切られた領域の連結成分の個数を答えよ。


以下、解説




















Accurate Sorting

https://www.hackerrank.com/contests/w31/challenges/accurate-sorting/submissions/code/1301284040
(0 1 2 3 4 ... N-1)を与えられた数列の状態にできるかを判定する。
実はある数についてスワップは1度しか出来ないということが分かる。
そのため、最初の状態を先頭から順にスワップすべきかを判定してすべきならスワップを繰り返すことで、与えられた数列の状態を目指していけば良い。

Zero-One Game

https://www.hackerrank.com/contests/w31/challenges/zero-one-game/submissions/code/1301297259
今回は順序はあまり関係なさそう(証明できないけど)。
なので、消せる回数はどう動かしても一定になる(割とこういう問題はある)。
そのため、消せる回数を求めて mod2=1ならAliceの勝ち、そうでないならBobの勝ちである。

消せる回数の求め方を考えてみよう。

010101 -> 00101 -> 0001 -> 001
011000 -> 01100
010000 -> 00000 -> 0000 -> 000 -> 00

雑な実験結果でアレだけれど、「011...110」という部分は一生消えない。
両脇が0でないと消せないという条件から元々離れていた1が操作によってくっつくことはない。
そのため、1が孤立している部分については全て消せて、連続している部分は消えないとして貪欲に消していけば良い。

貪欲に消すには
1. 孤立した1を消す
2. 0が連続している部分に対して3個以上連続しているなら、(連続個数-2)個分消せる
という操作を行っていけばよい。

Spanning Tree Fraction

https://www.hackerrank.com/contests/w31/challenges/spanning-tree-fraction/submissions/code/1301382148
二分探索+プリム法
答えの小数表現Cについて「chk(C) := C <= (A[i]の総和)/(B[i]の総和)とできるかどうか」で二分探索する。
chk関数の中身ではプリム法を用いれば良いのだが、
C <= (A[i]の総和)/(B[i]の総和)
(B[i]の総和)C <= (A[i]の総和)
(B[i] * Cの総和) <= (A[i]の総和)
0 <= (A[i]の総和) - (B[i] * Cの総和)
0 <= (A[i] - B[i] * Cの総和)
と変形できるので、A[i]-B[i]*Cをコストとしてコストが大きい順で全域木を作っていく。
有理数で表現する所は、chk関数内で作ればOK

Colliding Circles

DPっぽいけども分からん。

Nominating Group Leaders

https://www.hackerrank.com/contests/w31/challenges/nominating-group-leaders/submissions/code/1301384315
平方分割とMo's Algorithmが分からないと厳しい。
hamayanhamayan.hatenablog.jp
hamayanhamayan.hatenablog.jp
「freq[i] := iさんが指名された回数」とする。
まず区間クエリなのでMo'sアルゴリズムを使う。これで各クエリについて、O((G+Q)sqrt(G))でfreq配列を更新できる。
更新はいいが、X人投票されていて最小のインデックスを取得するのにO(N)くらいかかる。
これを何とかするために平方分割する。
「freq2[i][j] := i番目のバケット内の人で指名された回数がj回の人が何人いるか」とする。
これを毎回の更新時に同時に更新する。
すると答えを取得するのにO(sqrt(N))で取得できるようになるので、AC