箱の全集合を \( S \) 、選んだ箱の集合を \( A \)とする。選んだ箱の集合に含まれるキャンディが最小となる場合というのは、選ばれなかった箱に可能な限りキャンディが入っている場合と同等になる。よって \(A\) に含まれるキャンディの最小値は、\(C - \su…

単純な実装問題。 public class OneDimensionalRobotEasy { public int finalPosition(string commands, int A, int B) { int pos = 0; foreach (var c in commands) { pos += (c == 'R') ? 1 : -1; if (pos < -A) pos = -A; if (pos > B) pos = B; } return…

C# とは関係ないけど、一応ここに貼っておく。 素数 3 5 7 83 89 97 983 991 997 9949 9967 9973 99971 99989 99991 999961 999979 999983 9999971 9999973 9999991 99999959 99999971 99999989 999999893 999999929 999999937 ------2^31--------- 99999999…

PalindromicSubstringsDiv2 と要領は同じ。Sのi番目からj番目までの部分文字列をS[i,j]と表記する。「S に含まれている回文の個数の期待値」＝「S の部分文字列の回文の個数の期待値」。期待値の線形性よりこれは「Sのそれぞれの部分文字列について回文にな…

愚直に全部分文字列が回文であるかどうかを判定すると \(O(N^3)\) になる。Sのi番目からj番目の範囲の部分文字列を S[i,j] とすると、S[i,j] が回文である条件は、S[i] == S[j] かつ S[i+1,j-1] が回文になることである。これを理由して動的計画法を適用する…

問題クラス名通り、Bounding Boxの面積を出せばよい。 public class BoundingBox { public int smallestArea(int[] X, int[] Y) { return (X.Max() - X.Min()) * (Y.Max() - Y.Min()); } }

美味しいものから順に食べる。ただし美味しさがマイナスかつ、すでにその種類のものを食べたことがある場合は食べない。この工程での満足度の最大値を求めれば良い。 public class AlienAndHamburgers { public int getNumber(int[] types, int[] tastes) { …

任意の行は、自由に全体反転することができる。このことから、内部のそれぞれの行にはたかだか一色しか含まれていない正方形のうち、最大のサイズのものを求めれば良いことになる。以下のコードでは、最大正方形を O(WH) で求める動的計画法のアルゴリズムを…

全通り試すだけ。 using E = System.Linq.Enumerable; public class AlienAndPassword { public int getNumber(string S) { return E.Range(0, S.Length).Select(i => S.Remove(i, 1)).Distinct().Count(); } }

dp[ビット表現] = {-1,0,1} でメモ付き探索できそうに見えるが、取る順番によって盤面の状態が変わるので実はできない。よく考えると、キャンディの個数は 10 個以下 で、わざわざメモらなくても高々 10! の計算量になるため、ただのゲーム木上の全探索で十…

それぞれの guess, answer について guess + answer、 guess - answer のどちらかが必ず答えになる。よってこの２要素となる候補の集合積を取ることで、答えの候補が導出できる。 また、答えは必ず 1 以上 1,000,000,000 以下でないといけないのでその条件で…

候補となる区間でのソートを全て試す。 public class EllysSubstringSorter { public string getMin(string S, int L) { int n = S.Length; string ans = ""; for (int i = 0; i + L - 1 < n; i++) { var array = S.ToCharArray(); Array.Sort(array, i, L);…

行動パターンとしては、初期位置からある位置 X に移動してから勝利するまでずっとそこに留まるのがベストになる。すでに X にいるとして 勝利するまで留まるときの勝率を E[X] とすると\( E[X] = (winprob[X] + (100 - looseprob[X] - win[X]) E[X]) / 100 …

動的計画法。rating が 2200 を超えた場合だけ特別処理することで、保持するべき「現在のrating」の状態数を 0～2199 までに落とせる。 public class TypoCoderDiv1 { int?[,] memo = new int?[51, 2200]; public int dfs(int pos, int[] D, int rating) { i…

1ステップ後は、３倍数分の移動しかできないので、x, yともに３の倍数になるように必要がある。このことを利用して再帰的に処理できる。 public class PowerOfThreeEasy { public string ableToGet(int x, int y) { while (x != 0 || y != 0) { if (x % 3 ==…

全探索。 public class FoxAndWord { public int howManyPairs(string[] words) { int n = words.Length; int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { for (int k = 0; k < words[i].Length; k++) { if (words[i].Substring(…

与えられるグラフは木のため、少なくとも２つは葉がある。先行は、最初のターンで葉だけを残すことができるため、葉の最大コストのスコアを保証することができる。 後攻は、先行が即ゲーム終了しなかった場合だけ、ターンが回ってくる。初期状態の葉のうちの…

\(X Aを負の数のグループと、非負の数のグループに分ける。 同じグループ同士でペアを作ると積は必ず 0 以上になり、それぞれのグループは高々１つだけあまる。 もし両方のグループで１つずつ余った場合は、それらでペアを組むようにすればよい。 public cla…

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

問題文にかかれている通りに実装するだけ。 public class MiddleCode { public string encode(string s) { if (s.Length == 0) return ""; int removePosition; if (s.Length % 2 == 1) { removePosition = s.Length / 2; } else { if (s[s.Length / 2 - 1] …