Practice だと return 0; するだけのプログラムでも StackOverFlow になってシステムテストで正当チェックができなかった。一番出現数が多い名前 f の出現数を x とする。x が全名前の過半数以下の場合は、ペアの最大数 floor(名前の個数 / 2) がそのまま答…

第一段階で、各々の長さの彩色パターンを DP で求めて、 第二段階で、第一段階で求めた彩色パターンを使って、同じような DP を構築する。K 色全てを状態にするのではなく、開始地点と同じ色かそうでないかの２通りだけの状態を考えれば良い。具体的な処理は…

本番では、嘘解法っぽい後ろからの貪欲の全探索で通したけど、合っている証明ができなかった。想定解法は、ミッションをRefuelの大きい順に順番を固定してから、動的計画法が適用する、というものだった。ミッションをRefuel の大きい順に並び替れば上手くい…

久しぶりに本番で通ったMedium。A + C = C + B が成立するときは A は B を巡回シフトさせたものになる。 よって、もし A の文字列の最小周期が x だった場合は、対応するペアの個数は x になる。周期が x の文字列の個数は n % k == 0 のときは \(k^x\) 、…

public class WinterAndSnowmen { const int mod = 1000000007; static public void Add(ref int x, int value) { x += value; x %= mod; } public int getNumber(int N, int M) { const int BitNum = 12; int ans = 0; for (int diffBitPosition = 0; diffB…

回文になる行の集合を全通り試す。回文になる行の箇所が固定されると、(0列とW-1列), (1列とW-2列）... のペアそれぞれについて独立に処理できるため、あとは動的計画法で処理できる。本番だと、i列と(W-1-i)列のペアについて、「i列が回文である / でない」…

public class FoxAndFencing { const string Ciel = "Ciel"; const string Liss = "Liss"; const string Draw = "Draw"; public string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d) { if (mov1 + rng1 >= d) return Ciel; if (mov1 + d <= mo…

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

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

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 TreeUnion { const int inf = 1 << 28; int[,] Convert(string[] tree) { var array = String.Concat(tree).Split().Select(int.Parse).ToArray(); int n = array.Length + 1; int[,] d = new int[n, n]; for (int i = 0; i < n; i++) { for (i…

public class PyramidSequences { static public long Gcd(long s, long t) { return t != 0 ? Gcd(t, s % t) : s; } public long distinctPairs(long N, long M) { long gcd = Gcd(N - 1, M - 1); long ans = 0; long x = (N - 1) / gcd; long y = (M - 1) …

public class XorCards { public long NumberOfSolution(int[,] matrix) { int n = matrix.GetLength(0); int m = matrix.GetLength(1); bool[] used = new bool[n]; for (int i = 0; i < m; i++) { int target = -1; for (int j = 0; j < n; j++) { if (!us…

問題文「ドアの使用状況」×「赤い鍵の個数」×「緑色の鍵の個数」でメモ付き探索で通るけど、「ドアの使用状況」×「赤い鍵の個数」だけでも通る。しかし、前者はたまたまメモリが足りただけ、後者はたまたま上手くいくだけ（証明できない）で想定解法ではない…

問題文 public class GearsDiv1 { public int getmin(string color, string[] graph) { int N = graph.Length; int ans = int.MaxValue; string RGB = "RGB"; foreach (var c in RGB) { foreach (var c2 in RGB) { if (c == c2) continue; BipartiteMatching…