全て要素が１の場合は、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)\) から…