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 になるので、工夫して合…

N! のペアを全部試す必要はない。片方の並び順だけを固定したうえでもう片方の順列を全て試して、最後に N! を掛ければ良い。LINQ の Sum を使ったら TLE だった。こういう next_permutation するだけの問題は大抵 8! の上限だったのだけど、今回は何故か制…

pages をソートした配列を A とすると、 A[0],...,A[number-2],A[number] が２番目に最小な本の選び方になる。 public class LittleElephantAndBooks { public int getNumber(int[] pages, int number) { return pages .OrderBy(p => p) .Where((p, index) =…

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…

うなぎの通過する時間の区間の端点で切った結果が変動する。よって、その端点を２つ選んで全部試せば良い。 端点といっても開始と終了を両方試す必要はなく、片方だけ試しても良い。LINQで集合演算的に処理してみた。 public class EelAndRabbit { public in…

全探索。クエリ式を使うと作業用ローカル変数が減って、幸せな気持ちになれます。 public class ShoutterDiv2 { public int count(int[] s, int[] t) { int n = s.Length; return (from i in Enumerable.Range(0, n) from j in Enumerable.Range(0, n) where…

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 SpaceWarDiv2 { public int minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, int[] enemyCount) { int n = magicalGirlStrength.Length; magicalGirlStrength = magicalGirlStrength.OrderByDescending(s => s).ToArray(); va…

public class SpaceWarDiv1 { struct Enemy { public long strength, count; } public long minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, long[] enemyCount) { magicalGirlStrength = magicalGirlStrength.OrderByDescending(e => e).T…

全探索 public class SemiPerfectSquare { public string check(int N) { return (from a in Enumerable.Range(1, N) from b in Enumerable.Range(1, N) where a < b && a * b * b == N select 1).Any() ? "Yes" : "No"; } }

public class TravelOnMars { struct Data { public int pos; public int step; } public int minTimes(int[] range, int startCity, int endCity) { Queue<Data> qu = new Queue<Data>(); qu.Enqueue(new Data() { pos = startCity, step = 0 }); var visited = new boo</data></data>…

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>…

普通の実装問題。yyyy/mm/dd が一般的なカレンダーにおいて Valid かどうかは DateTime.DaysInMonth を使うと楽に書ける。 public class IDNumberVerification { const string Invalid = "Invalid"; public bool ValidBirthday(string birthday) { int year …

総当りするだけ。 クエリ式の let を使ってみた 入力文字は数字だけなので、StringComparer.Ordinalで文字列比較する必要はない。しかし基本的に文字列ソートはこれを使う癖をつけたほうが良さそうなので一応付けてる。 public class SwappingDigits { stati…

public class TreeUnion { const int inf = 1 << 28; int[,] Convert(string[] tree) { var array = String.Concat(tree).Split().Select(int.Parse).ToArray(); int n = array.Length + 1; int[,] d = new int[n, n]; for (int i = 0; i < n; i++) { for (i…

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; …

public class SurveillanceSystem { public string getContainerInfo(string containers, int[] reports, int L) { int n = containers.Length; var ans = Enumerable.Repeat('-', n).ToArray(); var cand = Enumerable.Range(0, n - L + 1) .Select(i => ne…

"BWBW..." と "WBWB..." の２通りとの差分の最小値を出せばよい。 public class BlackAndWhiteSolitaire { public int minimumTurns(string cardFront) { int cost = cardFront.Select((c, index) => (c == 'B' ^ (index % 2 == 0)) ? 1 : 0).Sum(); return …

public class PyramidSequences { static public long Gcd(long s, long t) { return t != 0 ? Gcd(t, s % t) : s; } public long distinctPairs(long N, long M) { long gcd = Gcd(N - 1, M - 1); long ans = 0; long x = (N - 1) / gcd; long y = (M - 1) …

ぐぐってみたら、Egalitarianism = 平等主義 だった。市民同士の所持金の差の最大値は、市民同士の最短距離 * dに等しい。もしそれ以上になってしまうと、最短距離上の辺の「所持金の差」のうちの１つが d を上回ってしまう。よって、市民同士の最短距離の中…

こういうCROSS JOIN系の処理は、クエリ式のほうがメソッド形式より簡単に書ける。 public class TopFox { public IEnumerable<string> cand(string s) { return Enumerable.Range(1, s.Length).Select(i => s.Substring(0, i)); } public int possibleHandles(string</string>…

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

外周を沿うように、大きく「へ」の字に車を移動させると残った部分は、高さ 0 から treeHeight-2 まで完全二分木が２つずつになる。Editorial の図がわかりやすい。 このことから漸化式に帰着できるので、あとは動的計画法で求める。最初 dp = new long[tree…

seq[i] >= seq[i+1] になっている部分が LISNumber の切れ目になるので、その箇所の個数に１足したものが答え。Zip() の段階で 1 か 0 に変換して Sum() すれば短く書けることに気づいた。 public class LISNumberDivTwo { public int calculate(int[] seq) …

Y の中にある高さについての解の個数を全て調べるだけ……と思ってたけど普通にシステムテストに落ちた。確かに 'N' の字の形状だと、その間を調べないと答えが 2 になってしまう。 座標に全て２倍にして、 Y の中の要素を +1, 0, -1 したものをしたものを調べ…

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 …

L が 26 以下の場合は、"abc","cz" のような同じ文字が２つ以上含まれない文字列が最小の重さ (= 0) になる。このときの総数は、 順列P(26, L) となる。L が 27 以上の場合は、"a..ab..bc..c..yz..z" のような同じ文字が一箇所にまとまっていて、かつ全ての…

最小のスキルの固定して、|skill| 分だけ動的計画法すると O(50 * 50 * 50 * 60000) でTLE。スキルが高い順に足していくと、最後に足されたスキルが最小のスキルになる。 そのことを利用して、昇順からナップサップの動的計画法をしていく、いざ足し合わせる…

a, b, c それぞれの変数を変更した場合の差分の最小値を出す。 public class TheArithmeticProgression { public double minimumChange(int a, int b, int c) { return Enumerable.Min(new[]{ Math.Abs(c - (b + b - a)), Math.Abs(a - (b + b - c)), Math.A…