それぞれのバッグから採るフルーツの個数 X を固定したとき、apple を取った個数が決まれば、orange を取った個数は自動的に決まる。よって、それぞれの X について、appleを取る個数のパターンを調べれば良い。以下のプログラムでは、取れる apple の最大値…

文字列 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(), …