単純な実装問題。 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…

愚直に全部分文字列が回文であるかどうかを判定すると \(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()); } }

任意の行は、自由に全体反転することができる。このことから、内部のそれぞれの行にはたかだか一色しか含まれていない正方形のうち、最大のサイズのものを求めれば良いことになる。以下のコードでは、最大正方形を 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 …

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…

問題文にかかれている通りに実装するだけ。 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] …

正面から見えるブロック数を N、横から見えるブロック数を Mとすると N × M の長方形の全列全行にブロックが少なくとも１つあるような配置のパターン数が答えになる。以下では、「すでにブロックが配置されている行の個数」×「着目している列」を状態にした…

色が変わる節目の個数を数える。 public class TypoCoderDiv2 { public int count(int[] rating) { int ans = 0; int current = 500; foreach (var r in rating) { if (current >= 1200 ^ r >= 1200) ans++; current = r; } return ans; } }

まず、長方形が幅＜高さになるように回転させる。 あとは、共通部分の領域面積が limit 以下であるような２つの長方形のペアを全通り選ぶ。 それぞれのペアについて、共通部分の短形を完全に内包する他の長方形の個数 m としたとき、 m + 2 の最大値を求めれ…

DP[n] = 「初期値が n のとき先手必勝」とすると DP[n] = n - 「nの1とn以外の約数」のときについて、先手必勝ではないものあれば、True。あとはこの漸化式を計算する。 public class TheNumberGameDivTwo { public string find(int n) { var dp = new bool[…

スワップの全パターンを試す。String.Join に String 以外の配列をそのまま渡しても問題ないようだ。 public class TheSwapsDivTwo { static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; } public int find(int[] sequence) { int n = seq</t>…

文字列 A、B から文字列 C を内包する最小限の区間を全て列挙する。 A : [A1] [C を内包する区間] [A2] B : [B1] [C を内包する区間] [B2]としたとき、 [A1][B1]の LCS の長さ + C の長さ + [A2]と[B2]の LCSの長さ の最大値が答えになる。(LCS: 最長共通部…

ヒストグラムを取って、 １の個数 １の個数 * ２の個数 ... １の個数 * ２の個数 * ３の個数 * ... * |type| の個数 の合計を出すだけ。よく見てみると O(|type|) に落とせますね。 public class WinterAndCandies { public int getNumber(int[] type) { var…

bags をソートして、連続区間を全て試せば良い。 public class WinterAndMandarins { public int getNumber(int[] bags, int K) { if (bags.Length < K) return int.MaxValue; Array.Sort(bags); return Math.Min(bags.Take(K).Max() - bags.Take(K).Min(), …

public class SimilarNames2 { int mod = 1000000007; int?[,] memo; int dfs(string[] names, int pos, int L) { if (L == 0) return 1; if (!memo[pos, L].HasValue) { int val = 0; for (int i = 0; i < names.Length; i++) { if (i == pos) continue; if…

\( A = 2^{a1} \times 3^{a2} \times ... \times p_n^{an} \) \( C = 2^{c1} \times 3^{c2} \times ... \times p_n^{cn} \) より \( A^B = 2^{a1*B} \times 3^{a2*B} \times ... \times {p_n}^{an*B} \) \( C^D = 2^{c1*D} \times 3^{c2*D} \times ... \time…

体重 5kg を超えないように、みかんを軽い順に食べていきます。 public class MiniatureDachshund { public int maxMikan(int[] mikan, int weight) { Array.Sort(mikan); int cnt = 0; foreach (int m in mikan) { weight += m; if (weight <= 5000) cnt++;…

N,M は 2 以上 8 以下のため、「回文になる列の集合」と「回文になる行の集合」について全探索できる。回文になる行と列がはっきりしていると、{ A[y][x] , A[H-1-y][x] , A[y][W-1-x] , A[H-1-y][W-1-x] } について、同じ値にしないといけないペア情報が確…

シャトルの座席数で全探索。 public class TheShuttles { public int getLeastCost(int[] cnt, int baseCost, int seatCost) { int ans = int.MaxValue; for (int seat = 1; seat <= 100; seat++) { int need = 0; foreach (var c in cnt) { need += (c - 1)…

Div1Easy の ORSolitaire とは違って、|numbers| public class ORSolitaireDiv2 { public int getMinimum(int[] numbers, int goal) { int n = numbers.Length; int ans = int.MaxValue; for (int i = 0; i < (1 << n); i++) { int or = 0, cnt = 0; for (in…

public class FoxAndFencingEasy { const string Ciel = "Ciel"; const string Liss = "Liss"; const string Draw = "Draw"; public string WhoCanWin(int mov1, int mov2, int d) { if (mov1 >= d) return Ciel; if (mov1 > mov2 * 2) return Ciel; if (mov…

public class BinPackingEasy { public int minBins(int[] item) { Array.Sort(item); int ans = 0; int n = item.Length; bool[] used = new bool[n]; for (int i = n - 1; i >= 0; i--) { if (used[i]) continue; int target = -1; for (int j = i - 1; j …

s.Substring(0, i)+s.Substring(i + 2) とするより Remove 使ったほうが楽でした。 public class ErasingCharacters { public string simulate(string s) { for (int i = 0; i < s.Length - 1; i++) { if (s[i] == s[i + 1]) { return simulate(s.Remove(i, …