World CodeSprint 5の参加日記
3完＋1部分点で暫定349位/6403人。難易度Moderateを1つ落としたのが悔しい。
https://www.hackerrank.com/contests/world-codesprint-5/challenges
CamelCaseの文字列に、英単語がいくつあるか答えよ。
大文字の数＋１を返せばよい。
Console.WriteLine(str.Count(s => s >= 'A' && s <= 'Z') + 1);
空文字列pに以下の操作を行い、文字列sを作りたい。最小のコストを答えよ。
・p末尾に任意の文字を足す（1ドル）
・p内の部分文字列を、p末尾に足す（0ドル）
2度目以降に使う文字にはコストがかからないので、sから重複を排除した文字数を答えればよい。
Console.WriteLine(s.Distinct().Count());
英小文字のみからなる文字列sが与えられる。このとき、次の条件を満たす部分文字列が、s内にいくつあるか答えよ。
・任意のインデックスa,b,c,d（0 <= a < b < c < d）について、s[a]==s[d]かつs[b]==s[c]
1 <= |s| <= 10^6、解答は10^9+7のModを出力する
動的計画法を次のように定義して解いた。
dp_1[i][j]：0~iの文字jの個数
dp_2[i][l][m]：0~iで、{…,文字l,…,文字m,…}になっているパターン数
→ dp_2[i][l][s[i]] = dp_1[i-1][l] + dp_2[i-1][l][s[i]]
dp_3[i][j][k]：0~iで、{…,文字j,…,文字k,…,文字k,…}になっているパターン数
→ dp_3[i][j][s[i]] = dp_2[i-1][l][s[i]] + dp_3[i-1][j][s[i]]
このまま実装するとメモリが不足するので、配列の再利用を行っている。
const ulong mod = 1000000007; static void Main(string[] args) { var s = Console.ReadLine(); var dp_1 = new ulong[26]; var dp_2 = new ulong[26, 26]; var dp_3 = new ulong[26, 26]; ulong ret = 0; for (int i = 0; i < s.Length; i++) { var c = s[i] - 'a'; for (int x = 0; x < 26; x++) { ret += dp_3[c, x]; ret %= mod; } for (int x = 0; x < 26; x++) { dp_3[x, c] += dp_2[x, c]; dp_3[x, c] %= mod; } for (int x = 0; x < 26; x++) { dp_2[x, c] += dp_1[x]; dp_2[x, c] %= mod; } dp_1[c]++; dp_1[c] %= mod; } Console.WriteLine(ret); }
Editorialよりすっきりした解だと思うのだが、どうだろうか。
Longest Increasing Subsequence Arrays
長さmのInt型の配列を作る。このとき、部分列として、必ず{1,2,3,…n}が含まれるようにしたい。可能なパターン数を答えよ。
1 <= m <= 5x10^5、1 <= n <= 10^5
n <= m
解答は10^9+7のModを出力する
Editorialより。S[n]の位置+1をループすることで求めることができる。
static Int64 Solve(Int64 m, Int64 n) { Int64 ret = 0; Int64 nPowX = 1; var n1PowX = ModPow(n - 1, m - n, mod); var invN1 = ModInv(n - 1, mod); for (Int64 x = 0; x <= m - n; x++) { //これだと大きいケースでTLEになる //var n1PowX = ModPow(n - 1, m - n - x, mod); //Invを掛けていく方法では、最終的に1になってはくれない if (m - n - x == 0) n1PowX = 1; var value = (Nck((int)(m - x - 1), (int)(n - 1)) * nPowX % mod) * n1PowX; value %= mod; ret += value; if (ret >= mod) ret -= mod; nPowX *= n; nPowX %= mod; n1PowX *= invN1; n1PowX %= mod; } return ret; }
(n-1)^(m-n-x)をループ内で直接求めるとTLEになるので、(n-1)^(-1)のModを掛けていくことで算出する。ただし、この方法だと最終的に(n-1)^0のとき解が1になってくれないので、その場合だけ直接1をアサインすることになる。
ModPow()、Nck()、ModInv()は個人ライブラリより。
ノード数nの木があり、各ノードにはc[i]個のコインが付いている。ここで、どれかのノードにコインがcw個付いたノードを足し、n+1ノードの木にする。この木の2つのエッジを切ったとき、出来た3つの木が同じ数のコインを持つようにしたい。cwの最小値を求めよ。不可能な場合は-1とする。
1 <= n <= 5x10^4
1 <= c[i] <= 10^9部分点(30%)
1 <= n <= 100
1 <= c[i] <= 100部分点(50%)
1 <= n <= 2000
1 <= c[i] <= 10^9
本番では50%の部分点だった。エッジでループし、該当エッジをカットしたときの小さいほうが、最終的な3つの木の1つとなり得るかを判定している。そのとき、予め「ノードAからみたノードB以降の木の合計値」を求めることで計算量を削減した。
https://www.hackerrank.com/contests/world-codesprint-5/challenges/balanced-forest/submissions/code/6349361
Editorialによると、ノード1をルートとし、各ノードに子ノードのコイン合計を持つことで、O(n Log(n))で算出できる。これは本番で場合分けがうまくいかず、断念したやり方だった。
Editorialサンプルの変数名やコメントを直したものが以下。
static Int64 Solve() { // Nodeクラスの配列を作成 // 各Nodeについて、サブ木の合計、DFSの到着時間、およびDFSのLeave時間を保持する Dfs(1, 0); // サブ木合計値から、最小の到着時間、最大の到着時間とそれぞれのノードインデックスを保持する辞書を作成する for (int i = 1; i <= n; i++) { if (!minArrivalTime_BySum.ContainsKey(c[i].SumOfSubtree)) { minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i; idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i; } else { if (minArrivalTime_BySum[c[i].SumOfSubtree] > c[i].ArriveTime) { minArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; idxOfMinArrivalTime_BySum[c[i].SumOfSubtree] = i; } if (maxArrivalTime_BySum[c[i].SumOfSubtree] < c[i].ArriveTime) { maxArrivalTime_BySum[c[i].SumOfSubtree] = c[i].ArriveTime; idxOfMaxArrivalTime_BySum[c[i].SumOfSubtree] = i; } } } minCw = (Int64)1e15; // 木のコイン合計が偶数、かつちょうど半分のサブ木合計があったら、その値が解になり得る if (sum % 2 == 0 && maxArrivalTime_BySum.ContainsKey(sum / 2)) minCw = sum / 2; // 全ノードのループ for (int i = 1; i <= n; i++) { if (3 * c[i].SumOfSubtree <= sum) // この時は、該当サブ木にcwを足すことを試す TryAddCw_ToSubTree(i); else if (2 * c[i].SumOfSubtree < sum) // サブ木合計を、最終的な1/3の１つとできるか試す TryAddCw_ToAnotherTree(i); } return minCw == (Int64)1e15 ? -1 : minCw; } static void TryAddCw_ToSubTree(int x) { if ((sum - c[x].SumOfSubtree) % 2 == 0) //サブ木以外が2で割れなければ無理 { Int64 p = (sum - c[x].SumOfSubtree) / 2; //最終的な1/3のコイン数 if (maxArrivalTime_BySum.ContainsKey(p) && (c[idxOfMaxArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime)) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); else if (minArrivalTime_BySum.ContainsKey(p) && (c[idxOfMinArrivalTime_BySum[p]].ArriveTime > c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[p]].LeaveTime < c[x].ArriveTime)) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); else if (minArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) && c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && c[idxOfMinArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); else if (maxArrivalTime_BySum.ContainsKey(p + c[x].SumOfSubtree) && c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].ArriveTime < c[x].ArriveTime && c[idxOfMaxArrivalTime_BySum[p + c[x].SumOfSubtree]].LeaveTime >= c[x].ArriveTime) minCw = Math.Min(minCw, p - c[x].SumOfSubtree); return; } } static void TryAddCw_ToAnotherTree(int x) { Int64 add = 3 * c[x].SumOfSubtree - sum; if (minArrivalTime_BySum[c[x].SumOfSubtree] != maxArrivalTime_BySum[c[x].SumOfSubtree]) minCw = Math.Min(minCw, add); else if (minArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMinArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add); else if (maxArrivalTime_BySum.ContainsKey(c[x].SumOfSubtree - add) && (c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime < c[x].ArriveTime || c[idxOfMaxArrivalTime_BySum[c[x].SumOfSubtree - add]].ArriveTime > c[x].LeaveTime)) minCw = Math.Min(minCw, add); else if (minArrivalTime_BySum.ContainsKey(2 * c[x].SumOfSubtree - add)) minCw = Math.Min(minCw, add); return; } //// 省略 class Node { public Int64 SumOfSubtree; //c[i].s - sum of values in subtree rooted in i public int ArriveTime; //time when dfs arrived in i-th node public int LeaveTime; //time when dfs leave i-th node ( all children are marked) };
TryAddCw_ToSubTree()とTryAddCw_ToAnotherTree()で細かい場合分けをしているが、ノードのコイン数は必ず1以上なのだから、もっと簡略化できそうな気がする。
（あるノードのサブ木合計値が、そのノードの子で発生することは有り得ないため）
