美味しいものから順に食べる。ただし美味しさがマイナスかつ、すでにその種類のものを食べたことがある場合は食べない。この工程での満足度の最大値を求めれば良い。 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] …