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

hamayanhamayan's blog

Week of Code 30 問題と解説

問題

Candy Replenishing Robot

https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot
カップ内のボールの数をb個とする。最初はb=N。
これについて以下の操作をT回する。

1. C[i]個のボールを取り除く。つまり、b=b-C[i](各操作で取り除けることが保証される)
2. 残ったボール数が5個未満(b < 5)ならば、カップ内のボールの数をN個にするように(N-b)個を足す

操作2で足されたボールの総和は?

Find the Minimum Number

https://www.hackerrank.com/contests/w30/challenges/find-the-minimum-number
2つのint,intの最小値 -> min(int, int)
3つのint,int,intの最小値 -> min(int, min(int, int))
4つのint,int,int,intの最小値 -> min(int, min(int, min(int, int)))
となるとき、Nつのintの最小値の文字列は?

Melodious password

https://www.hackerrank.com/contests/w30/challenges/melodious-password
N文字の以下のルールを満たす文字列を全て出力せよ。

  • 小文字の英語だけ使う
  • 子音と母音を交互に置く
  • 'y'は使わない
Poles

https://www.hackerrank.com/contests/w30/challenges/poles
N本の電柱をK本にまとめる。
電柱には重さW[i]と高度X[i]がある。
ある電柱は低い高度へ動かすことしかできず、コストW[i]*dXだけかかる。
コストの総和の最小値は?

Range Modular Queries

https://www.hackerrank.com/contests/w30/challenges/range-modular-queries
N個の数列Aがある。
Q個の「[left, right]の範囲でxを法にした時にyとなる要素数を答える」クエリに答える。

A Graph Program

https://www.hackerrank.com/contests/w30/challenges/a-graph-problem
N頂点の無向グラフGがある。
この点誘導部分グラフG'のうち、(G'の三角数)÷(G'の頂点数)が最大となるグラフの点集合を出力せよ。
三角数とはグラフの点集合のうち、(a,b),(b,c),(c,a)に頂点がある三点(a,b,c)の組となる数のこと。

Substring Queries

https://www.hackerrank.com/contests/w30/challenges/substring-queries
N個の文字列がある。
この文字列に対してQ個のF(S[x], S[y])のクエリに答えよ。
F(s, ss) := 文字列sと文字列ssでそれぞれ連続する部分文字列を取った時の最大の長さ。


以下、解説















解説

Candy Replenishing Robot

https://www.hackerrank.com/contests/w30/challenges/candy-replenishing-robot/submissions/code/1300888823
シミュレートしていって足された数を数え上げるだけ。

Find the Minimum Number

https://www.hackerrank.com/contests/w30/challenges/find-the-minimum-number/submissions/code/1300898524
i+1つの最小値はiつの最小値から、以下のように作れる。
s[1] = "int"
s[i + 1] = "min(int, " + s[i] + ")"
これで作って出力。

Melodious password

https://www.hackerrank.com/contests/w30/challenges/melodious-password/submissions/code/1300927188
幅優先探索みたいにして列挙していく。
キューを2つ用意して処理していくが、swap処理などと組み合わせると列挙しやすくなる。

Poles

https://www.hackerrank.com/contests/w30/challenges/poles/submissions/code/1300943221
以下、TLEするNaive解答
前処理として

  • 同じX[i]の電柱は重さW[i]をまとめて、電柱は高度で昇順ソート
  • C[i][j] := [i,j]番目の電柱をi番目の高度にまとめるための総コスト

を計算しておく(pre関数)

rec(int i, int k) := [i, N-1]の電柱をkグループにまとめるのに必要な最小コスト
とすると、rec(0, K)が答え。
rec(i,k) = min{j=i,...,N-1}(C[i][j] + rec(j+1,k-1))
という漸化式があるので、これを使って計算していく。
この解法だとO(K N^2)となるからTLEする。

以下、AC解答
https://www.hackerrank.com/contests/w30/challenges/poles/submissions/code/1301067791
再帰をDPに変えてより効率よく更新することを考える。

dp[i][k] = min{j=0...i-1}(dp[k-1][j] + j+1以降をiに纏める時のコスト)
となる。これは累積和などを使いながら、式を立てて変形していくとConvexHullTrickで解ける形になる。
CHTが理解できていないと解くのは難しい。

hamayanhamayan.hatenablog.jp

Range Modular Queries

https://www.hackerrank.com/contests/w30/challenges/range-modular-queries/submissions/code/1301076611
クエリのxの値によって処理を変えることで平均的な計算量を減らし、ACとする問題。
コドフォでも同じような方針の問題を見たことがある(誰か教えて)。
平方分割という手法を用いるが、一般的な平方分割(Mo's Algorithmみたいな)とはちょっと違う。
N=40000なのでK=200を境界として、2種類の手法を用いる。

x<Kのときは手法1
pos[x][y] := xで割った余りがyとなる要素番号の配列
を事前に用意しておき、二分探索で[L,R]の範囲の個数を数えるとそれがクエリの答えとなる
こっちは各クエリO(logN)で計算可能

K≦xのときは手法2
pos2[x] := 要素の中身がxである要素番号の配列
を事前に用意しておき、それを使ってy, y+x, y+2x, y+3x, ...となる個数を愚直に数え上げる手法
K≦xなのでO(400logN)で計算可能

全てのクエリが手法2であっても計算量的に間に合うのでAC

A Graph Program
Substring Queries