https://www.hackerrank.com/contests/world-codesprint-10/challenges
問題
Reward Points
1回スワイプすると10ポイント貯まる。
一ヶ月に最大100ポイント貯められる。
三ヶ月間のスワイプ回数が与えられるので、何ポイント貯まったか答えよ。
Zigzag Array
N個の配列Aがある。
この配列をジグザグ配列にする為に、最小何個の要素を消せばよいか。
※ジグザグ配列 : 任意の連続する3要素を取った時に単調増加または単調減少にならない配列
Maximal AND Subsequences
N要素の配列Aがある。
ここからK個取り出してAND計算をした時の最大値とその最大値を作るK個の取り出す組合せを答えよ。
Permutation Happiness
Q個のクエリがある。
各クエリでは、N個の順列の任意の順番に対し、左右どちらかの要素がその要素よりも大きくなる(happyである)要素数が少なくともK個以上ある、順番の組合せを答えよ。
Maximum Disjoint Subtree Product
N頂点の木がある。
頂点にはコストW[i]がついている。
ここから互いに素な連結な頂点の集合を2つ取り、2つの集合それぞれについて総和を取った積の最大値を答えよ。
Node-Point Mappings
N頂点の木とN個の座標がある。
木のノードと座標を1つずつマッピングしていく。
木上でノード間に辺があるなら、xy平面上でノードに対応する座標を端点とする線分が引かれる。
適切にマッピングして、xy平面上で線分が公差しないようにせよ。
Interoffice Travel
N頂点の木がある。
N個の配列Wがある。
全ての頂点iについて、sum{j=0...N-1} W[頂点iと頂点jの距離]を求めよ。
以下、解説
Reward Points
Zigzag Array
https://www.hackerrank.com/contests/world-codesprint-10/challenges/zigzag-array/submissions/code/1301475792
配列Aの部分列で最長のジグザグ配列を見つけて、「N-最長の長さ」を答えとする。
見つける方法は、
1. 大きい->小さい->大きい->小さい->...
2. 小さい->大きい->小さい->大きい->...
のどちらともを試して、頭から貪欲にジグザグを決めていけばよい。
もし、上向きであれば、数が小さくなるまで最大の要素を保持しながら探していく。
Maximal AND Subsequences
https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximal-and-subsequences/submissions/code/1301476466
まず最大値を求める(getmax関数)。
これは上のビットからK個以上1が立っていれば使うという操作を繰り返すが、そのビットを使う場合にそのビットが0である数は今後使えなくなるため、それをフラグとして持っておきながらカウントする。
あとは、最大値がそれに成るためにandで使われるかは「a[i] & ma == ma」という条件を満たせばよいので、使われる数をカウントして、aCb(cnt, K)を取れば個数も取れる。
Permutation Happiness
https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness/submissions/code/1301483886
DPを使って前計算してから解く(makedp関数)。まず2つほど大事なことがあり、これが分からないと解けないのだが、
- unhappyな要素は2つ続かない
- 順列数え上げDPでは1から順番に配置していくようなDPを作る
DPは以下の構成で作る
DP[n][h] := [1,n]の順列でhappyな要素がh個ある組合せ
まず、[1,n]の順列ではn+1を挿入できる場所はn+1通りある。
そのうち、happyな要素が増加する挿入場所はunhappyの隣であり、これは2(n - h)通りある。
これは、unhappyが連続していると違ってくるが、unhappyな要素は続かないので大丈夫。
そして、happyな要素が増加しない挿入場所はn+1-2(n-h)通りあるため、これを遷移先としてDPを更新する。
詳しくはmakedp関数を見ると分かりやすいかもしれない。
各クエリの答えはdp[n][k]+dp[n][k+1]+...+dp[n][n]なのだが、これは累積和を予め取っておき(ruisekiwa関数)、区間和として答えれば良い。
これでAC
Maximum Disjoint Subtree Product
https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximum-disjoint-subtree-product/submissions/code/1301483116
各辺で2つの木に分けた時に、各木の部分木の和の最大値をそれぞれ求めて、かければ答え。
しかし、積の最大値では最小値どおしを掛けることで積を最大化するパターンもある。
なので、dfsをしていくが、以下の情報を伝播させていく
res[0] := その頂点を含んだ部分木の総和の最大
res[1] := その頂点を含まない部分木の総和の最大
res[2] := その頂点を含んだ部分木の総和の最小
res[3] := その頂点を含まない部分木の総和の最小
あとは、これをメモ化再帰させて、辺毎に答えを更新すると答え。
Node-Point Mappings
20%解法(鎖状の木の場合のみ)
https://www.hackerrank.com/contests/world-codesprint-10/challenges/node-point-mappings/submissions/code/1301484405
x座標昇順(同じならy座標昇順)でソートすると、その順で辺を引くと交点無く鎖が作れるので、これを使ってdfsで頂点をマッピングしていく。
