文字の種類は 'A'... 'I' の９種類しかない。 となると ('A'...'I') -> ('A'...'I') の割り当ての仕方は 9! になるため、全部試しても間に合う。それぞれの割り当てについて、割り当て通りではない (A[i], B[i]) を削除すればよい。next_permution は C♯ に…

public class TheTree { public int maximumDiameter(int[] cnt) { int D = cnt.Length; int ans = D; for (int s = 0; s < D; s++) { int len = cnt.Skip(s).TakeWhile(c => c >= 2).Count(); ans = Math.Max(ans, len + D - s); } return ans; } }

問題文一歩進む、二歩進む、と続けていって、もし障害物にあたったら「一歩進む」をなかったことにする。 その直後のターンでは少なくとも「二歩以上進む」ことになるので必ず障害物は飛び越される。 public class JumpFurther { public int furthest(int N,…

問題文線形な区間ごとに解があるかを判定する。重解に注意。 public class PiecewiseLinearFunctionDiv2 { public int numberOfSolution(int[] Y, int y) { int n = Y.Length; int ans = Y[0] == y ? 1 : 0; for (int i = 0; i < n - 1; i++) { if (Y[i] < y…

問題文交互に最も preference が高い選手を選んでいく。 public class TeamsSelection { public string simulate(int[] preference1, int[] preference2) { int n = preference1.Length; var result = Enumerable.Repeat(' ', n).ToArray(); for (int i = 0;…

問題文やるだけ。 goal から 'z' を除いたものが init と等しいかどうかを判定する。 public class InsertZ { public string canTransform(string init, string goal) { return goal.Replace("z", "") == init ? "Yes" : "No"; } }

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…

問題文 解法 ###.### ###.### ###.### ...x... ####### 上のような「最大の深さが３以上の子ノードが３以上あるような地点 x」が存在して、 Bob が Alice より 2ターンか、それ以上早く先にその地点にたどり着くことができれば Bob の勝ち、それ以外は Alice…

begin, target の '.' 以外の文字（LR)を左から突き合わせる 文字や長さが一致しなかったら、"Impossible" あとは移動前後の位置関係が矛盾しているかを判定する 本番だと Where(...).Select((c, index) => index) としてしまって、フィルタ後の添え字を返し…

問題文各列の状態はそれぞれ独立しているので、各列ごとに状態数を求めてそれらを掛け合わせる。 列ごとの状態数については、上からコマを置いていって、「何番目のコマか」と「コマを置ける一番上の場所」で DP する。 public class FoxAndShogi { const in…

問題文全探索。 public class FoxAndGo { static public int[] dx = { 0, 1, 0, -1 }; static public int[] dy = { 1, 0, -1, 0 }; public int FloodFill(char[][] board, int x, int y, ref bool existEmpty){ if(board[y][x] != 'o') return 0; board[y][x…

問題文全探索 public class FoxAndGomoku { static public bool Between(long a, long x, long b) { return a <= x && x < b; } static public int[] dx = { 0, 1, 1, -1}; static public int[] dy = { 1, 0, 1, 1 }; public string win(string[] board) { i…

問題文アリスが移動できなくなるまで幅優先探索すればよい。 DP してもいいけれど、やっていることは結局同じになる。 public class GameInDarknessDiv2 { int[] dx = { 0, 1, 0, -1 }; int[] dy = { 1, 0, -1, 0 }; string ds = "DRUL"; struct Point { pub…

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

問題文tone が最大の歌と最小の歌を固定して、あとはその範囲内の歌の中から duration が低いものを貪欲に選んでいけばよい。 このとき、「tone が最大の歌と最小の歌」を絶対選ぶようにしなくても、選ばれなかった時点で内側の範囲のほうがよりよい解が得ら…

問題文Div1 とは違って、|songs| が 15以下なので全探索で通る。無理にLINQを使うとより複雑になる一例。 public class GUMIAndSongsDiv2 { IEnumerable<int> GetBitIndice(long n) { int index = 0; var list = new List<int>(); while (n > 0) { if ((n & 1) != 0) l</int></int>…

問題文Count() を使うだけ public class KeyDungeonDiv2 { public int countDoors(int[] doorR, int[] doorG, int[] keys) { return Enumerable.Range(0, doorR.Length) .Count(index => Math.Max(doorR[index] - keys[0], 0) + Math.Max(doorG[index] - key…

問題文 public class FlippingBitsDiv1 { public int getmin(string[] _S, int M) { string S = String.Concat(_S); int N = S.Length; int L = (N - 1) / M + 1; int ans = int.MaxValue; if (M <= 18) { for (int i = 0; i < (1 << M); i++) { var dp = ne…

問題文 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…

問題文ToLookup() が使えないことから微妙なプログラムになってしまった。 public class GooseTattarrattatDiv1 { public int getmin(string S) { int n = S.Length; DisjointSet ds = new DisjointSet(26); for (int i = 0; i < n; i++) { ds.unionSet(S[i]…

問題文メモ付き探索する場合は、Nullableの配列を使うと初期化する必要がなくなるので楽メモ配列へのアクセスに Array.SetValue/GetValue を使うようにすると、メモ化に使うパラメタに破壊的代入してもバグらなくなる。追記：ただし、非常に速度が遅いので取…

問題文 「一番最初に削除する場所を固定してから貪欲」を全箇所で試す 答えが 0 の場合は別処理 LINQ だと solve 関数のような一個前の値を見る系の処理が扱いづらいのが残念 public class GearsDiv2 { public int solve(String s) { int ans = 1; for (int …

問題文最も使用されている文字に寄せればいいので、文字列の長さからそれぞれの文字の使用回数を引けばよい。 public class GooseTattarrattatDiv2 { public int getmin(string S) { return S.Length - Enumerable.Range('a', 26) .Select(c => S.Where(c2 =…

以下は使用するとコンパイルでエラーが出る System.Linq.AsParallel() System.Linq.GroupBy() System.Linq.ToLookup() System.Tuple yield return/break 構文 検証に使ったソースコード public IEnumerable<int> YieldTest() { yield return 0; } public void Lin</int>…