例として { 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); }