public class LittleElephantAndString { public int getNumber(string A, string B) { if (!A.OrderBy(s => s).SequenceEqual(B.OrderBy(s => s))) return -1; int a = A.Length - 1, b = B.Length - 1; while (a >= 0 && b >= 0) { while (a >= 0 && A[a] …

public class FoxAndGo2 { static public int[] dx = { 0, 1, 0, -1 }; static public int[] dy = { 1, 0, -1, 0 }; public struct Point { public int Row, Col; } public class Group { public List<Point> Points = new List<Point>(); } public class WhiteGroup : Gro</point></point>…

public class LittleElephantAndSubset { int mod = 1000000007; void enumeratePattern(int[] pattern, int N, int used = 0, long current = 0) { if (current > N) return; if (current > 0) { pattern[used]++; } for (int d = 0; d <= 9; d++) { if (cu…

それぞれの要素について、２の倍数でなくなるまで２で割って、全ての要素が同じ値になるかどうかを判定する。 ２進数文字列で変換 末尾の 0 を除去 全て同じ文字列になるかの判定 で実装してみた。 public class LittleElephantAndDouble { public string ge…

\(F(n) = n (n - 1^2) (n - 2^2) ... (n - k^2) \) ただし \(k\) は \((n - k^2) > 0\) となる最大の整数とする「\(F(n) \mod m = 0 \)」が成立することと 「\((n - x^2) \mod m = 0\) かつ \( n > x^2 \) となるような自然数 \( x \) が存在すること」は同…

dp[現在の位置] = 最小ステップ数として動的計画法を適用する public class ColorfulRoad { public int getMin(string road) { int n = road.Length; int inf = 1 << 30; var dp = Enumerable.Repeat(inf, n).ToArray(); dp[0] = 0; for (int i = 0; i < n; …

先頭と末尾以外の要素についてスキップを試す。 public class FoxAndSightseeing { public int getMin(int[] position) { int n = position.Length; var candidate = Enumerable.Range(1, n - 2) .Select(i => position.Where((v, index) => index != i)) .T…

\( |L| = |R| \le 10 \)。よって高々 \( 2^{10} = 1024 \) 通りの塗り分け方を全て試せばよい。想定解法的には LittleElephantAndIntervalsDiv1 のほうが簡単だと思う。 public class LittleElephantAndIntervalsDiv2 { public int getNumber(int M, int[] L…

public class LittleElephantAndXor { // dp[着目しているbit][A未満になったか][B未満になったか][C未満になったか] = パターン数 public long getNumber(int A, int B, int C) { int largeBit = new[] { A, B, C }.Select(GetLargeBit).Max(); var dp = ne…

全ての部分文字列を調べる。SubString の代わりに SkipとTakeを使うと配列外参照を気にしないで書ける。 public class LittleElephantAndBallsAgain { public int getNumber(string S) { return (from i in Enumerable.Range(0, S.Length) from j in Enumera…

public class EllysNewNickname { public bool IsVowel(char c) { return "aeiouy".Contains(c); } public int getLength(string nickname) { return nickname.Length - nickname.Zip(nickname.Skip(1), (c1, c2) => IsVowel(c1) && IsVowel(c2) ? 1 : 0) .S…

public class AstronomicalRecordsEasy { public int minimalPlanets(int[] A, int[] B) { return ( from a in A from b in B select A.Length + B.Length - A.Select(v => v * b).Intersect(B.Select(v => v * a)).Count() ).Min(); } }

実際にシミューレーションして判定をする。n と m が互いに素かどうかを判定してもよい。 public class FoxAndClassroom { public string ableTo(int n, int m) { HashSet memo = new HashSet(); int r = 0, c = 0; while (true) { r = (r + 1) % n; c = (c …

public class WolfInZooDivTwo { struct Interval { public int left, right; } int N; Interval[] intervals; int?[,] memo; int dfs(int pos = 0, int last = -1) { if (pos == N) return 1; if (!memo[pos, last + 1].HasValue) { int val = dfs(pos + 1,…

public class GooseInZooDivTwo { public int count(string[] field, int dist) { int w = field[0].Length; int h = field.Length; int mod = 1000000007; var points = from i in Enumerable.Range(0, h) from j in Enumerable.Range(0, w) where field[i]…

public class DeerInZooDivTwo { public int[] getminmax(int N, int K) { return new[]{ Math.Max(0, N-K), N - (K+1) / 2 }; } }

public class MarblePositioning { static public void Swap(ref T a, ref T b) { T t = a; a = b; b = t; } static public bool NextPermutation(T[] array) where T : IComparable { int n = array.Length; for (int i = n - 2; i >= 0; i--) { if (array[…

各行ごとに buffer を使う場合と、undo を使う場合を試して、手数が少ない方を採用する。 public class UndoHistory { int CommonPrefixLength(string a, string b) { return a.Zip(b, (c1, c2) => c1 == c2).TakeWhile(v => v).Count(); } public int minPr…

弱い順に倒していけば良い。 public class PrimalUnlicensedCreatures { public int maxWins(int initialLevel, int[] grezPower) { Array.Sort(grezPower); int ans = 0; foreach (var power in grezPower) { if (initialLevel > power) { initialLevel += …

\( A(S) = \sum_{i \in S} A[i] \) \( A(T) = \sum_{i \in T} A[i] \) \( B(S) = \sum_{i \in S} B[i] \) \( B(T) = \sum_{i \in T} B[i] \)とすると、求めるべき答えは、\( \max(|A(S) - B(T)| , |A(T) - B(S)|) \)になる。\( A(S) + A(T) = \sum A (\equiv…

最初の 'w' の個数を数えて、それに対応する wolf 文字列でちゃんと始まっているかチェックしていけばよい。 "w..w"+"o..o"+"l..l"+"f..f"の文字列生成はSelectManyで。 public class WolfDelaymaster { public string check(string str) { if (str == "") r…

切り分け方を全通り試す。 public class RaiseThisBarn { public int calc(string str) { int ans = 0; for (int i = 1; i < str.Length; i++) { string left = str.Substring(0, i); string right = str.Substring(i); if (left.Replace(".", "") == right.…

public class ThreeColorabilityEasy { int n, m; int ToIndex(int row, int col) { return row * (m + 1) + col; } List[] ConstrustGraph(string[] cells) { int nodeNum = (n + 1) * (m + 1); var graph = Enumerable.Range(0, nodeNum).Select(_ => new …

dp[i][j] = 「(A+i) の部分シーケンスで j 番目に小さい数(以下 A[i][j]) 」に到達するパターン数 とすると dp[0][*] = 1; dp[i+1][j] = sum dp[i][k] where A[i][k] で動的計画法を適用できる。ただし、毎回合計を取っていくと TLE になるので、工夫して合…

N! のペアを全部試す必要はない。片方の並び順だけを固定したうえでもう片方の順列を全て試して、最後に N! を掛ければ良い。LINQ の Sum を使ったら TLE だった。こういう next_permutation するだけの問題は大抵 8! の上限だったのだけど、今回は何故か制…

pages をソートした配列を A とすると、 A[0],...,A[number-2],A[number] が２番目に最小な本の選び方になる。 public class LittleElephantAndBooks { public int getNumber(int[] pages, int number) { return pages .OrderBy(p => p) .Where((p, index) =…

public class Excavations2 { long?[,] choose = new long?[55, 55]; long Choose(int s, int t) { if (!choose[s, t].HasValue) { if (t == 0 || t == s) choose[s, t] = 1; else choose[s, t] = Choose(s - 1, t - 1) + Choose(s - 1, t); } return choose…

壁は水平に並べるだけでよい。そうすると「ウサギ」は「左右にいくつか移動して、下に一歩移動する」のアクションを繰り返すように強制できる。あとは、「ウナギの現在位置」を状態にして動的計画法を使えば良い。 public class WallGameDiv2 { static publi…

うなぎの通過する時間の区間の端点で切った結果が変動する。よって、その端点を２つ選んで全部試せば良い。 端点といっても開始と終了を両方試す必要はなく、片方だけ試しても良い。LINQで集合演算的に処理してみた。 public class EelAndRabbit { public in…

全探索。クエリ式を使うと作業用ローカル変数が減って、幸せな気持ちになれます。 public class ShoutterDiv2 { public int count(int[] s, int[] t) { int n = s.Length; return (from i in Enumerable.Range(0, n) from j in Enumerable.Range(0, n) where…