(最長bitの高さ - 1) + 立っている bitの個数が答えになる。いったん２進数文字列に変換すると楽になった。 public class IncrementAndDoubling { public int getMin(int[] desiredArray) { var a = desiredArray.Select(d => Convert.ToString(d, 2)); retu…

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

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

各行ごとに 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…

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

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]までの和を逐次…

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

public class SpaceWarDiv1 { struct Enemy { public long strength, count; } public long minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, long[] enemyCount) { magicalGirlStrength = magicalGirlStrength.OrderByDescending(e => e).T…

public class TravelOnMars { struct Data { public int pos; public int step; } public int minTimes(int[] range, int startCity, int endCity) { Queue<Data> qu = new Queue<Data>(); qu.Enqueue(new Data() { pos = startCity, step = 0 }); var visited = new boo</data></data>…

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 SurveillanceSystem { public string getContainerInfo(string containers, int[] reports, int L) { int n = containers.Length; var ans = Enumerable.Repeat('-', n).ToArray(); var cand = Enumerable.Range(0, n - L + 1) .Select(i => ne…

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) …

ぐぐってみたら、Egalitarianism = 平等主義 だった。市民同士の所持金の差の最大値は、市民同士の最短距離 * dに等しい。もしそれ以上になってしまうと、最短距離上の辺の「所持金の差」のうちの１つが d を上回ってしまう。よって、市民同士の最短距離の中…

Y の中にある高さについての解の個数を全て調べるだけ……と思ってたけど普通にシステムテストに落ちた。確かに 'N' の字の形状だと、その間を調べないと答えが 2 になってしまう。 座標に全て２倍にして、 Y の中の要素を +1, 0, -1 したものをしたものを調べ…

public class StringPath { const int mod = 1000000009; int n, m; string A, B; int?[,,] memo; int newState(int row, int col, String s, char c, int bit) { if (((1 << col) & bit) != 0) { bit ^= (1 << col); if (s[row + col] == c) { if (col + 1 …

L が 26 以下の場合は、"abc","cz" のような同じ文字が２つ以上含まれない文字列が最小の重さ (= 0) になる。このときの総数は、 順列P(26, L) となる。L が 27 以上の場合は、"a..ab..bc..c..yz..z" のような同じ文字が一箇所にまとまっていて、かつ全ての…

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 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) としてしまって、フィルタ後の添え字を返し…

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

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

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