Tuple の == は ReferenceEquals BigInteger.Parse(s) の計算量は O(|s|^2) String のデフォルトの比較は重い 空の Queue.Clear() の計算量は O(|Capacity|) (.Net Framework) Tuple の == は ReferenceEquals Tuple.Create(1, 5) == Tuple.Create(1, 5)); /…

オンラインジャッジと C# 対応状況 OnlineJudge C# compiler C# ver source CodeForces .Net Core 3.1 C# 8 Submit page Google Code Jam mono 4.6.2 C# 6 https://code.google.com/codejam/resources/faq AOJ mono 4.6.2 C# 6 http://judge.u-aizu.ac.jp/on…

例として { 1, 5, 3, 4, 7, 6, 2 } から遷移できる配列を列挙する。 1 5 5 5 5 7 2 5 5 3 7 7 6 6 5 5 5 5 7 7 7 1 5 5 7 7 6 2 7 7 7 7 7 7 7 眺めてみると、以下の規則性があることが分かる。 同一の数字は一箇所にかたまっている。1112111のように複数箇…

Practice だと return 0; するだけのプログラムでも StackOverFlow になってシステムテストで正当チェックができなかった。一番出現数が多い名前 f の出現数を x とする。x が全名前の過半数以下の場合は、ペアの最大数 floor(名前の個数 / 2) がそのまま答…

問題文とは逆に (x, y) からスタートして 1, 9, 27 ... の直進移動で (0, 0) に移動できるかどうかを考える。2ステップ以降は、3の倍数分しか移動できないため 1ステップ目で x, y が両方とも 3 の倍数になるように移動しなくてはならない。x と y が両方と…

サンプルが豊富で大きなヒントになっているが、バグ無しの実装が大変な問題。方針としては、微小距離だけ移動しても自分自身と重ならないような方向が存在するかを判定する。 以下、「移動」というのは微小距離だけ移動という意味で用いている。２つの線分だ…

解法は TopCoder SRM614 解説 を参考にしてください。流れは、だいたい以下のとおり。 全てのループを断ち切るように N + M - 1 箇所のマスを変数化 斜めに変数化すれば max(N, M) 箇所でよい すべての箇所の期待値を、DP を使って (N + M - 1) 変数多項式で…

第一段階で、各々の長さの彩色パターンを DP で求めて、 第二段階で、第一段階で求めた彩色パターンを使って、同じような DP を構築する。K 色全てを状態にするのではなく、開始地点と同じ色かそうでないかの２通りだけの状態を考えれば良い。具体的な処理は…

解説は、TopCoder SRM614 解説 を参考にしてください。\(O(N^3)\) 解です。 public class MinimumSquare { struct Point { public long X, Y; } public long minArea(int[] x, int[] y, int K) { var points = x.Zip(y, (X, Y) => new Point { X = X, Y = Y …

解法については、 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); } }

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