\( |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…

まず、各区間ごとに異なる色で塗り分ける。 最後まで塗り分けたあと、残っている色数を X とすると、 X 個の色それぞれについて独立に白と黒の２色を割り当てられるので、\( 2^X \) が答えになる。色が塗られていない部分を無視しないといけない点にだけ注意…

全ての部分文字列を調べる。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 }; } }

「現在の位置」「買い物をした店のbit表現」 = 最小の時間 で動的計画法を行う。今回は PriorityQueue の実装も兼ねて、動的計画法ではなくダイクストラで解いた。 public class PriorityQueue { private T[] array = new T[100]; private int size = 0; pri…

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 += …

小数点の取り扱い まずハマった点としては、CodeForcesのサーバー上では CultureInfo がロシアになっているため、小数点の表記が "." ではなく "," で使用される。そのため double.Parseに "0.11" を渡すと Runtime Error となり "0,11" のような小数文字列…

namespace Codeforces { public class _352B { static int? getP(IEnumerable<int> array) { if (array.Count() == 1) return 0; var diff = array.Zip(array.Skip(1), (a0, a1) => a1 - a0); if (diff.Distinct().Count() == 1) return diff.First(); return nul</int>…

90の倍数の条件は 各桁の数字の和が、9の倍数 最後の桁が 0 を満たすことである。よって 5 は 「9 の倍数」分使えるだけ使う 0 は 全部使う ただし、使える 5 がない場合は "0000..0" とせず "0" を返し、0 がない場合は強制的に -1 を返す。 namespace Code…

\( 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…

最悪なケースでも 1 2 3 1 2 3 ... 3 1 2 3 1 2 ... 2 3 1 2 3 1 ... を置くことで、色の個数は高々３に抑えられる。したがって２色で交互に深さ優先探索で色分けしていって、失敗したら３を返すようにする。 public class HexagonalBoard { static public i…

最初の '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 …

public class TriangleXor { public int theArea(int W) { double area = 0; // top if (W % 2 == 0) area += W / 4.0; // side double ratio = 0, prevX = 0; for (int i = 1; i <= W; i++) { double x = 1.0 * i * W / (W + i); if (i % 2 == 1) { ratio +…

a1 , .. , an b1 , .. , bn 順列 a,b に対して、N から 1 まで。大きい順に値を配置していくことを考える。 大きい順に配置するため、両方空いている場所に値 i を配置した時点で もう片側に i 以下の値しか入らないので、 magic(A,B) に i が追加される。値…

青赤 青緑 ←← →→ ↑ ↑ 上の図のように、左右のキューのどちらかに追加していく。このときにすでにその色が入ってないキューに入れるようにすればよい。 public class LittleElephantAndBalls { public int getNumber(string S) { var left = new HashSet(); v…

TrafficCongestionDivTwo の treeHeight の上限が 60 から 1000000 になったもの。漸化式自体は、同じ dp[i] = (sum 2*dp[j] where j だけど、これだと O(treeHeight^2) でTLEになる。合計を求めるところがネックなので、dp[0], ... , dp[i-2]までの和を逐次…