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

象が水を飲むときは、一番近いものを選ぶ。つまりそれぞれの象について、水を飲む場合はどこまで鼻を伸ばすかは一意に決まっている。上側の象と下側の象が水を飲むかどうかは、\(2^{2n}\) 通り。上下の象が鼻を伸ばすかどうかが決まれば、左右の象がそれぞれ…

全マスへの移動を考えるのではなく、残っている gold がある箇所と同じ行または列に移動することを考える。そうすると、移動箇所はたかだか 50*50 だけになる。あとは、「座標」と「日数」で動的計画法を適用すればよい。 \(O(|event|^4) \) public class Mi…

まず、候補者が全員不採用の状態からスタートすることを考える。 この時点の利益は 「earning の全要素の合計」にマイナスを掛けたものになる。候補者 a を不採用から採用へと変更すると value[a] の利益が減る 他の不採用の候補者 b がいる場合 earning[a][…

ある１つの頂点 \(X\) に着目したとき、その頂点がサイズ３以下の連結成分に含まれる時のパターンは以下の５つになる。 連結成分が１つの場合 連結成分が２つの場合 連結成分が３つの場合 - \((X, Y), (Y, Z)\) のように枝が伸びている場合 連結成分が３つの…

典型的なDP。dp[gumiNum, iaNum, mayuNum] = それぞれの歌手が歌うパターン数で状態を持てば良い。ただし７通りの遷移の部分は手で書きたくなかったのでビットを使ったループ処理に置き換えている。 public class VocaloidsAndSongs { public int count(int …

どういう場合にパターン数が指数関数オーダーになるかというと、それは ある点に対して複数ループが存在する場合 という条件を満たすときになる。ループが１つしかない場合は、線形オーダーでしかパターンが増えないが、２つ以上ある場合はループで戻るたび…

dp[ビット表現] = {-1,0,1} でメモ付き探索できそうに見えるが、取る順番によって盤面の状態が変わるので実はできない。よく考えると、キャンディの個数は 10 個以下 で、わざわざメモらなくても高々 10! の計算量になるため、ただのゲーム木上の全探索で十…

行動パターンとしては、初期位置からある位置 X に移動してから勝利するまでずっとそこに留まるのがベストになる。すでに X にいるとして 勝利するまで留まるときの勝率を E[X] とすると\( E[X] = (winprob[X] + (100 - looseprob[X] - win[X]) E[X]) / 100 …

正面から見えるブロック数を N、横から見えるブロック数を Mとすると N × M の長方形の全列全行にブロックが少なくとも１つあるような配置のパターン数が答えになる。以下では、「すでにブロックが配置されている行の個数」×「着目している列」を状態にした…

文字列 A、B から文字列 C を内包する最小限の区間を全て列挙する。 A : [A1] [C を内包する区間] [A2] B : [B1] [C を内包する区間] [B2]としたとき、 [A1][B1]の LCS の長さ + C の長さ + [A2]と[B2]の LCSの長さ の最大値が答えになる。(LCS: 最長共通部…

public class SimilarNames2 { int mod = 1000000007; int?[,] memo; int dfs(string[] names, int pos, int L) { if (L == 0) return 1; if (!memo[pos, L].HasValue) { int val = 0; for (int i = 0; i < names.Length; i++) { if (i == pos) continue; if…

N,M は 2 以上 8 以下のため、「回文になる列の集合」と「回文になる行の集合」について全探索できる。回文になる行と列がはっきりしていると、{ A[y][x] , A[H-1-y][x] , A[y][W-1-x] , A[H-1-y][W-1-x] } について、同じ値にしないといけないペア情報が確…

public class FoxAndFencingEasy { const string Ciel = "Ciel"; const string Liss = "Liss"; const string Draw = "Draw"; public string WhoCanWin(int mov1, int mov2, int d) { if (mov1 >= d) return Ciel; if (mov1 > mov2 * 2) return Ciel; if (mov…

public class FoxAndGo2 { static public int[] dx = { 0, 1, 0, -1 }; static public int[] dy = { 1, 0, -1, 0 }; public struct Point { public int Row, Col; } public class Group { public List<Point> Points = new List<Point>(); } public class WhiteGroup : Gro</point></point>…

public class LittleElephantAndSubset { int mod = 1000000007; void enumeratePattern(int[] pattern, int N, int used = 0, long current = 0) { if (current > N) return; if (current > 0) { pattern[used]++; } for (int d = 0; d <= 9; d++) { if (cu…

\(F(n) = n (n - 1^2) (n - 2^2) ... (n - k^2) \) ただし \(k\) は \((n - k^2) > 0\) となる最大の整数とする「\(F(n) \mod m = 0 \)」が成立することと 「\((n - x^2) \mod m = 0\) かつ \( n > x^2 \) となるような自然数 \( x \) が存在すること」は同…

public class LittleElephantAndXor { // dp[着目しているbit][A未満になったか][B未満になったか][C未満になったか] = パターン数 public long getNumber(int A, int B, int C) { int largeBit = new[] { A, B, C }.Select(GetLargeBit).Max(); var dp = ne…

public class WolfInZooDivTwo { struct Interval { public int left, right; } int N; Interval[] intervals; int?[,] memo; int dfs(int pos = 0, int last = -1) { if (pos == N) return 1; if (!memo[pos, last + 1].HasValue) { int val = dfs(pos + 1,…

public class GooseInZooDivTwo { public int count(string[] field, int dist) { int w = field[0].Length; int h = field.Length; int mod = 1000000007; var points = from i in Enumerable.Range(0, h) from j in Enumerable.Range(0, w) where field[i]…

public class MarblePositioning { static public void Swap(ref T a, ref T b) { T t = a; a = b; b = t; } static public bool NextPermutation(T[] array) where T : IComparable { int n = array.Length; for (int i = n - 2; i >= 0; i--) { if (array[…

\( A(S) = \sum_{i \in S} A[i] \) \( A(T) = \sum_{i \in T} A[i] \) \( B(S) = \sum_{i \in S} B[i] \) \( B(T) = \sum_{i \in T} B[i] \)とすると、求めるべき答えは、\( \max(|A(S) - B(T)| , |A(T) - B(S)|) \)になる。\( A(S) + A(T) = \sum A (\equiv…

public class ThreeColorabilityEasy { int n, m; int ToIndex(int row, int col) { return row * (m + 1) + col; } List[] ConstrustGraph(string[] cells) { int nodeNum = (n + 1) * (m + 1); var graph = Enumerable.Range(0, nodeNum).Select(_ => new …

dp[i][j] = 「(A+i) の部分シーケンスで j 番目に小さい数(以下 A[i][j]) 」に到達するパターン数 とすると dp[0][*] = 1; dp[i+1][j] = sum dp[i][k] where A[i][k] で動的計画法を適用できる。ただし、毎回合計を取っていくと TLE になるので、工夫して合…

public class Excavations2 { long?[,] choose = new long?[55, 55]; long Choose(int s, int t) { if (!choose[s, t].HasValue) { if (t == 0 || t == s) choose[s, t] = 1; else choose[s, t] = Choose(s - 1, t - 1) + Choose(s - 1, t); } return choose…

壁は水平に並べるだけでよい。そうすると「ウサギ」は「左右にいくつか移動して、下に一歩移動する」のアクションを繰り返すように強制できる。あとは、「ウナギの現在位置」を状態にして動的計画法を使えば良い。 public class WallGameDiv2 { static publi…

public class ColorTheCells { public int Dfs(int[] dryingTime, int[] paintTime, int pos = 0, int used = 0, int currentTime = 0) { int n = dryingTime.Length; if (used == (1 << n) - 1) return currentTime; int minTime = int.MaxValue; for (int …

public class GameOnABoard { static public int[] dx = { 0, 1, 0, -1 }; static public int[] dy = { 1, 0, -1, 0 }; static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; } struct Point { public int row, col, step;} public int Solv</t>…

public class TreeUnionDiv2 { int[,] warshallFloyd(string[] tree) { int n = tree.Length; var d = new int[n, n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d[i, j] = tree[i][j] == 'X' ? 1 : 1<<28; } } for (int i = 0; i < n; …

まず青い点、黄色い点、緑の点を結んた三角形について考える。まず左側の黄色い点と右側の緑色の点を選択する。 このとき結んだ直線より下に黒点が存在する場合は、どの青い点を選んでも三角形の外側になるため、該当する三角形は存在しない。そして２点を選…