例として { 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のように複数箇…

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

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

public class TPS { static int[] GetDegrees(string[] linked) { var n = linked.Length; var deg = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (linked[i][j] == 'Y') { deg[j]++; } } } return deg; } String[] Shrink…

public class StringPath { const int mod = 1000000009; int n, m; string A, B; int?[,,] memo; int newState(int row, int col, String s, char c, int bit) { if (((1 << col) & bit) != 0) { bit ^= (1 << col); if (s[row + col] == c) { if (col + 1 …

問題文 解法 ###.### ###.### ###.### ...x... ####### 上のような「最大の深さが３以上の子ノードが３以上あるような地点 x」が存在して、 Bob が Alice より 2ターンか、それ以上早く先にその地点にたどり着くことができれば Bob の勝ち、それ以外は Alice…

問題文 public class FlippingBitsDiv1 { public int getmin(string[] _S, int M) { string S = String.Concat(_S); int N = S.Length; int L = (N - 1) / M + 1; int ans = int.MaxValue; if (M <= 18) { for (int i = 0; i < (1 << M); i++) { var dp = ne…