https://www.hackerrank.com/contests/w32/challenges
Duplication
以下のルールで文字列を作る
- 最初は"0"から始める
- 現在の文字列がsであるとき、その0と1を逆転させた文字列をtとする
- 現在の文字列がsであるとき、次の文字列をs+tとして文字列を伸ばしていく
Q個のクエリに対して、X[i]番目の文字を答えよ(0-indexed)
Fight the Monster!
N匹のモンスターがいて、それぞれ体力がH[i]である。
1秒間でHIT分だけ体力を減らせる銃がある(1秒間同じモンスターにしか当てられない)。
T秒間で最大何匹のモンスターを倒せるか。
Circular Walk
円があり、円周上にN点等間隔で並んでいる。
R[i] = (R[i - 1] * G + SEED) mod P
という関数がある。
i番目の場所では[i-R[i],i+R[i]]の場所へ1秒でジャンプできるとき、S番目からT番目まで最短何秒で移動できるか。
Geometric Trick
N文字の文字列Sがあり、
- S[i] == 'a', S[j] == 'b', S[k] == 'c'
- (j + 1)^2 = (i + 1)(k + 1)
- i,j,kは0-indexed
を満たす(i,j,k)の組は何通りあるか
Balls and Boxes
N色のボールがあり、i番目の色のボールはA[i]個ある。
M個の箱があり、j番目の箱にはC[j]個入れられる。
以下のルールで箱にボールを入れる
- 各箱には、各色のボールを多くとも1つだけ入れられる
- i番目のボールをj番目の箱に入れるとB[i][j]個のキャンディーが得られる
- j番目の箱の最大個数をx個超えていた場合は、x^2個のキャンディを支払う
- 全てのボールを入れる必要は無いし、全ての箱を埋める必要も無い
得られるキャンディの個数の最大値は？
以下、解説
Duplication
https://www.hackerrank.com/contests/w32/challenges/duplication/submissions/code/1301611195
シミュレーションして文字列を作った後、指定された要素を出力する。
Fight the Monster!
https://www.hackerrank.com/contests/w32/challenges/fight-the-monsters/submissions/code/1301638238
貪欲に体力が低いモンスターから順に倒していく。
倒せなくなったら、終わり。
Circular Walk
https://www.hackerrank.com/contests/w32/challenges/circular-walk/submissions/code/1301639885
幅優先で解く。
この考察を出すのが難しいのだが、
「時間が立つにつれて到達できる範囲というのは必ず連続範囲となる」
という所が重要。
あとは、t秒からt+1秒で到達できる範囲が増えれば、その増えた部分に対してのみ、範囲が次の時間で更に増えるかを判定することで、各頂点についてその判定を1回しかやらないため、O(N)で間に合う。
具体的な例はこのような感じ
t秒後 ----=====---- ↓ t+1秒後 --=========-- であることが分かった場合、t+2秒後の到達判定をすべき頂点は --@@=====@@-- の@の頂点。これをチェックして範囲が増えるか判定する
Geometric Trick
https://www.hackerrank.com/contests/w32/challenges/geometric-trick/submissions/code/1301687530
まず、Sの先頭に番兵を加えて1-indexedとしておく。
'b'の位置を全探索するが、この時のi,kはj^2の約数になっている。
j^2の約数の個数は実はそんなに無い。
これを高速に列挙できれば、あとは全パターン試すだけ。
これは、
1. jを素因数分解する(O(sqrt(j)))
2. 各素因数の個数を2倍する(これでj^2の素因数分解が得られる)
3. この素因数分解を使って、約数列挙する(計算は10^5いかないくらいだと思う)
で実現できる。
あとは、TLEしないように祈りながら出すと通る
