解法については TopCoder SRM614 解説 を参考にしてください。 public class MinimumSquareEasy { public long minArea(int[] x, int[] y) { int n = x.Length; long minSide = long.MaxValue; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) {…

ある２匹の猫が互いに背を向けている場合、両方の猫の向きを直して、向かい合わせることで必ず移動後の位置の差が小さくなる。つまり任意の猫のペアが向かい合っているような初期状態だけを考えればよく、そのような状態は |coordinates|+1 通りしかないので…

「入力済みのEmoticonsの個数」「ClipBoard上のEmoticonsの個数」で動的計画法を構成する。\(O(smiles^2)\) public class EmoticonsDiv2 { static public void UpdateMin<T>(ref T x, T newValue) where T : IComparable<T> { if (x.CompareTo(newValue) > 0) x = </t></t>…

一番小さな箱を２つ選んで、一段階サイズが大きいの箱に入れる。これを箱が１つだけになるまで繰り返す。 public class BoxesDiv2 { int ToPower2(int x) { for (int i = 0; i <= 20; i++) { if (x <= (1 << i)) return i; } return -1; } public int findSi…

古いSlimonade を優先して売るように実装する。 public class SlimeXSlimonadeTycoon { public int sell(int[] morning, int[] customers, int stale_limit) { var n = morning.Length; var stock = new int[n]; int ans = 0; for (int i = 0; i < n; i++) {…

全探索しても間に合う。計算量は、\(O(|word|^4)\) public class LongWordsDiv2 { public string find(string word) { int n = word.Length; for (int p1 = 0; p1 < n - 1; p1++) { if (word[p1] == word[p1 + 1]) return "Dislikes"; } if ((from p1 in E.R…

有名なヨセフスの問題のアレンジ版のため、ヨセフス数を求める再帰アルゴリズムを改造すると \(O(N)\) で解ける。愚直にシミューレートした \(O(N^2)\) 解法でも通る。 public class ChooseTheBestOne { int dfs(int N, int pos, long k = 1) { if (N == 1) …

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

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

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

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…

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

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

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

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

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

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

まず、長方形が幅＜高さになるように回転させる。 あとは、共通部分の領域面積が 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[…

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

\( 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…

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 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 …

public class LittleElephantAndString { public int getNumber(string A, string B) { if (!A.OrderBy(s => s).SequenceEqual(B.OrderBy(s => s))) return -1; int a = A.Length - 1, b = B.Length - 1; while (a >= 0 && b >= 0) { while (a >= 0 && A[a] …

dp[現在の位置] = 最小ステップ数として動的計画法を適用する public class ColorfulRoad { public int getMin(string road) { int n = road.Length; int inf = 1 << 30; var dp = Enumerable.Repeat(inf, n).ToArray(); dp[0] = 0; for (int i = 0; i < n; …

\( |L| = |R| \le 10 \)。よって高々 \( 2^{10} = 1024 \) 通りの塗り分け方を全て試せばよい。想定解法的には LittleElephantAndIntervalsDiv1 のほうが簡単だと思う。 public class LittleElephantAndIntervalsDiv2 { public int getNumber(int M, int[] L…

public class AstronomicalRecordsEasy { public int minimalPlanets(int[] A, int[] B) { return ( from a in A from b in B select A.Length + B.Length - A.Select(v => v * b).Intersect(B.Select(v => v * a)).Count() ).Min(); } }

各行ごとに buffer を使う場合と、undo を使う場合を試して、手数が少ない方を採用する。 public class UndoHistory { int CommonPrefixLength(string a, string b) { return a.Zip(b, (c1, c2) => c1 == c2).TakeWhile(v => v).Count(); } public int minPr…

最初の 'w' の個数を数えて、それに対応する wolf 文字列でちゃんと始まっているかチェックしていけばよい。 "w..w"+"o..o"+"l..l"+"f..f"の文字列生成はSelectManyで。 public class WolfDelaymaster { public string check(string str) { if (str == "") r…

N! のペアを全部試す必要はない。片方の並び順だけを固定したうえでもう片方の順列を全て試して、最後に N! を掛ければ良い。LINQ の Sum を使ったら TLE だった。こういう next_permutation するだけの問題は大抵 8! の上限だったのだけど、今回は何故か制…