解法については、 TopCoder SRM614 解説 を参考にしてください。 public class TorusSailingEasy { int reach(int N, int M, int x, int y) { for (int p = x; p < N * M; p += N) if (p % M == y) return p; return -1; } public double expectedTime(int N…

解法については 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++) {…

初 Writerした回。本問は非担当。再帰できる場合は再帰したほうがかっこいい。 public string makeMicroString(int A, int D) { if (A < 0) return ""; return A + makeMicroString(A - D, D); }

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

'A','C','T'以外の文字を削除した後に、文字列が "CAT" になっているかを判定する。 public class TaroString { public string getAnswer(string S) { S = new String(S.Where(c => "CAT".Contains(c)).ToArray()); return S == "CAT" ? "Possible" : "Impos…

「入力済みの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>…

S に含まれている "RL" を個数をカウントする。 public class LeftAndRightHandedDiv2 { public int count(string S) { return S.Zip(S.Skip(1), (c1, c2) => c1 == 'R' && c2 == 'L' ? 1 : 0).Sum(); } }

ある程度の数までフィボナッチ数を求めてから、差分の最小値を求める。 public class FibonacciDiv2 { public IEnumerable<int> GetFibonacci() { List<int> f = new List<int>(); f.Add(0); f.Add(1); while (true) { var x = f[f.Count - 2] + f[f.Count - 1]; if (x >= 1</int></int></int>…

一番小さな箱を２つ選んで、一段階サイズが大きいの箱に入れる。これを箱が１つだけになるまで繰り返す。 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…

象が水を飲むときは、一番近いものを選ぶ。つまりそれぞれの象について、水を飲む場合はどこまで鼻を伸ばすかは一意に決まっている。上側の象と下側の象が水を飲むかどうかは、\(2^{2n}\) 通り。上下の象が鼻を伸ばすかどうかが決まれば、左右の象がそれぞれ…

全マスへの移動を考えるのではなく、残っている gold がある箇所と同じ行または列に移動することを考える。そうすると、移動箇所はたかだか 50*50 だけになる。あとは、「座標」と「日数」で動的計画法を適用すればよい。 \(O(|event|^4) \) public class Mi…

問題文通り実装するだけだけど、Div2 Easy にしてはやや複雑。 public class DivideByZero { public int CountNumbers(int[] numbers) { var newElements = ( from A in numbers from B in numbers let C = A / B where A > B && !numbers.Contains(C) selec…

古い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++) {…

探索しなくても、 n >= 20 より奇数と偶数で場合分けできる。（コード参照） public class SilverbachConjecture { public int[] solve(int n) { return (n % 2 == 0) ? new[] { 4, n - 4 } : new[] { 9, n - 9 }; } }

全探索しても間に合う。計算量は、\(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…

合計出すだけ。 public class WritingWords { public int write(string word) { return word.Sum(c => c - 'A' + 1); } }

まず、候補者が全員不採用の状態からスタートすることを考える。 この時点の利益は 「earning の全要素の合計」にマイナスを掛けたものになる。候補者 a を不採用から採用へと変更すると value[a] の利益が減る 他の不採用の候補者 b がいる場合 earning[a][…

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

各 department について、重複 した work type がないかどうかを判定すればよい。 Div2 Easy にしては やや複雑な問題。 public class GoodCompanyDivTwo { public int countGood(int[] superior, int[] workType) { int n = superior.Length; int ans = 0; …

\((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) \) の全探索で十分間…

典型的な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 == '<')…

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

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