HackerRank Week of Code - 19 参加日記
HackerRankのWeek of Code - 19に参加したのでそのメモ。
結果は346位/3176人だった。
4つのノードA,B,C,Dをもつ有向グラフを考える。D→Aのエッジをa、A→Bのエッジをb、B→Cのエッジをc、C→Dのエッジをd、A→Cのエッジをe、B→Dのエッジをfとする。
a~fの重みが与えられたとき、負の閉路をなくすためには、最小でいくら重みを足せばよいか。ただし、1つのエッジにのみ重みを足すことができる。
不可能な場合は-1を返こと。制約:a~fの重みの値は-20から+20
全エッジに対し、足す重み全て(0~80)をチェックするだけでよい。
ちなみに、すべてのループがエッジaを通るため、答えが-1になることはない。
static bool Success(int a, int b, int c, int d, int e, int f, int val, int idx) { switch (idx) { case 0: a += val; break; case 1: b += val; break; case 2: c += val; break; case 3: d += val; break; case 4: e += val; break; case 5: f += val; break; } return (b + f + a >= 0) && (b + c + d + a >= 0) && (e + d + a >= 0); } public static int Solve(int a, int b, int c, int d, int e, int f) { for (int i = 0; i <= 80; i++) { for (int j = 0; j < 6; j++) { if (Success(a, b, c, d, e, f, i, j)) return i; } } return -1; //should not be here since all loops have edge 'a' }
無限個のキャンディーが入ったM個のコンテナが、1列に配置されている。そして2つのロボットがある。ロボットはコンテナ間を移動して、キャンディーを運ぶことができる。
キャンディー運ぶ順番(あるコンテナから別のコンテナへ)が指定されたとき、トータルで最小のロボット移動距離を求めよ(隣り合うコンテナ間の距離を距離1とする)。
キャンディーを運ぶ順番は次のように指定される。
N #運ぶ回数
Ma1 Mb1 #コンテナMa1からMb1に運ぶ。必ず違う値
・・・
Man Mbn
制約:
次のDPを設定し、手順を後ろからループしていく。
DP[現在のロボットAの位置][現在のロボットBの位置] = 以降の移動距離の最小(Aの位置<Bの位置)
単純に実装するとメモリと実行時間が足りなくなるので、(1)DP配列の再利用(2)あり得ない条件は無視して枝刈り、を行った。
public class Solver { public int n = 0; public int m = 0; public Tuple<int, int>[] queries; public int Solve() { int[][,] dp_all = new int[][,] { new int[m + 2, m + 2], new int[m + 2, m + 2] }; int[] minIdx = new int[m + 1]; for (int idx = 0; idx < m + 1; idx++) { minIdx[idx] = Int32.MaxValue; } for (int idx = 0; idx < queries.Length; idx++) { var val = queries[idx].Item2; if (minIdx[val] == Int32.MaxValue || idx < minIdx[val]) { minIdx[val] = idx; } } int dpIdx = 0; for (int idx = queries.Length - 1; idx >= 0; idx--) { var q = queries[idx]; var pos1 = idx == 0 ? 0 : queries[idx-1].Item2; for (int pos2 = 0; pos2 < m + 1; pos2++) { if (pos2 != 0 && idx < minIdx[pos2]) continue; //cannot be var dp = dp_all[dpIdx]; var dp_next = dp_all[dpIdx == 0 ? 1 : 0]; dp[Math.Min(pos1, pos2), Math.Max(pos1, pos2)] = Math.Abs(q.Item1 - q.Item2); var movePos1 = (pos1 == 0 ? 0 : Math.Abs(pos1 - q.Item1)) + ((idx == queries.Length - 1) ? 0 : dp_next[Math.Min(q.Item2, pos2), Math.Max(q.Item2, pos2)]); var movePos2 = (pos2 == 0 ? 0 : Math.Abs(pos2 - q.Item1)) + ((idx == queries.Length - 1) ? 0 : dp_next[Math.Min(q.Item2, pos1), Math.Max(q.Item2, pos1)]); dp[Math.Min(pos1, pos2), Math.Max(pos1, pos2)] += Math.Min(movePos1, movePos2); } dpIdx = dpIdx == 0 ? 1 : 0; } return dp_all[dpIdx == 0 ? 1 : 0][0, 0]; } }
次の数列を考える。
このとき、ベクトルを次のように規定する。
Sをのスカラ積の集合としたとき、Sの剰余の個数をMでModしたものを求めよ。
制約:
で開始するフィボナッチ数列の変種と考えればよい。
フィボナッチ数列の特徴
を利用すると、この数列に対しては
が導き出せる。
よって、の部分を見ていけばよい。
public class Solver { public long Solve(long c, long m, long n) { c %= m; var resultSet = new HashSet<long>(); var prev = c; long prev2 = 0; for (int i = 2; i <= 4 * n - 1; i++) { var val = (prev2 + prev) % m; if (i % 2 == 1 && i >= 7) resultSet.Add((val * c) % m); prev2 = prev; prev = val; } return resultSet.Count() % m; } }
これは解けなかったのが悔しかった。
「フィボナッチ数列」で検索してみるべきだった。
一次元配列A[](長さN、Indexは1から始まる)が与えられたとき、次の疑似コードで得られるansを答えよ。
//f(a, b)はA[a, b]の最小値を返す ans = 0 for a -> [1, N] for b -> [a, N] for c -> [b + 1, N] for d -> [c, N] ans = ans + min(f(a, b), f(c, d)) ans = ans % (10^9 + 1)制約:
まった手が出なかった。
Editorialは理解できるのだが、最後が「これをSegmentTreeを使って解けばよい」で終わっていて困る・・・。このレベルなら自明であるべきなのだろうか。
仕方ないので、SegmentTreeの集中特訓をしてから、後でもう一度解いてみることにする。
Editorialの内容
配列Aにあるすべての数字xについて、になる回数を求めればよい。
これをとすると、最終的な解答はになる。
ここで、
と定義すると、
となる。
を求めるためには、別の配列Bを用意するとよい。
BはAと同じ長さで、なら、それ以外ならのもの。
すると、は
かつ
かつ
になる の組み合わせのうち、
との範囲内すべてが1になるものの数と等しくなる。
はSegmentTreeを使えば解くことができる。