\((x, y)\) から \((x + y, y)\) または \((x, x + y)\) に変換できる。 ここで \(x + y\) は \(x\) や \(y\) よりも大きいため、要素の大きいほうが、最後に加算された箇所だと分かる。 よって変換後から変換前への状態は一意で決まるため、\((c, d)\) から…

問題文通りにソートする。OrderByは安定ソートのため、ThenBy(p => p.index0) は実は必要ない。 public class CandidatesSelectionEasy { public int[] sort(string[] score, int x) { return score .Select((s, index0) => new { s, index0 }) .OrderBy(p =…

ある１つの頂点 \(X\) に着目したとき、その頂点がサイズ３以下の連結成分に含まれる時のパターンは以下の５つになる。 連結成分が１つの場合 連結成分が２つの場合 連結成分が３つの場合 - \((X, Y), (Y, Z)\) のように枝が伸びている場合 連結成分が３つの…

x が y で割り切れない場合は、y には x より余分な素因数が含むので、最小公倍数に含めてはいけない。 それ以外の場合は、最小公倍数で取り込むデメリットはないので、全て取り込んだ上で x と同じになるかどうかを判定すればよい。 public class LCMSetEas…

xの中に '0' から '9'の文字について 0個か2個しか含まれてない 2個ある場合は、その間にある文字数とその文字が表す数字が等しい。 かどうかをチェックする。 public class InterestingNumber { public string isInteresting(string x) { for (int i = 0; i …

あらかじめ、市松模様上に色を反転させておく。すると後は、黒一色の長方形と白一色の長方形の面積の最大値を求める問題になる。最大の長方形面積を求める問題は \( O(WH) \) の解法があるが、そこまでに頑張らなくても \( O(W^2H^2/4) \) の全探索で十分間…

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

典型的なDP。dp[gumiNum, iaNum, mayuNum] = それぞれの歌手が歌うパターン数で状態を持てば良い。ただし７通りの遷移の部分は手で書きたくなかったのでビットを使ったループ処理に置き換えている。 public class VocaloidsAndSongs { public int count(int …

variety set の個数を固定すると、same set の個数が一意に求められる。 そして variety set の候補は、0 から max(R,G,B) で高々 101 通りなので、それらを全て試す。 public class PackingBallsDiv2 { public int minPacks(int R, int G, int B) { int ans…

左右に分割して、それぞれ文字を反転しなければならない箇所を数える。 public class MagicalStringDiv2 { public int minimalMoves(string S) { int n = S.Length; var left = S.Take(n / 2); var right = S.Skip(n / 2); return left.Count(c => c == '<')…

任意の切れ目で、２つの文字列に分割して、左側の '>' の個数と右側の ' public class MagicalStringDiv1 { public int getLongest(string S) { int n = S.Length; int ans = 0; for (int i = 0; i < n; i++) { var left = S.Take(i).Count(c => c == '>'); …

どういう場合にパターン数が指数関数オーダーになるかというと、それは ある点に対して複数ループが存在する場合 という条件を満たすときになる。ループが１つしかない場合は、線形オーダーでしかパターンが増えないが、２つ以上ある場合はループで戻るたび…

箱の全集合を \( 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…