象が水を飲むときは、一番近いものを選ぶ。つまりそれぞれの象について、水を飲む場合はどこまで鼻を伸ばすかは一意に決まっている。上側の象と下側の象が水を飲むかどうかは、\(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); } }

全て要素が１の場合は、LOSE 。 要素数が２つ以下の場合も、LOSE 。 ３つ以上要素がある場合は、次のステップで２箇所に加算するため、２より大きい要素が少なくとも２つできる。よって要素が全て１になることはなく、要素数が２以下になるまで勝負がつかな…

まず、候補者が全員不採用の状態からスタートすることを考える。 この時点の利益は 「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; …

Div2Medium の派生版。\((a,b)\)と\((c,d)\) それぞれから逆方向に変換していって、それらの共通部分での最大値を返せば良い。 public class PairGame { public IEnumerable<Tuple<int, int>> Get(int a, int b) { var set = new List<Tuple<int, int>>(); while (a > 0 && b > 0) { set.Add(</tuple<int,></tuple<int,>…

\((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)\) のように枝が伸びている場合 連結成分が３つの…