public class TriangleXor { public int theArea(int W) { double area = 0; // top if (W % 2 == 0) area += W / 4.0; // side double ratio = 0, prevX = 0; for (int i = 1; i <= W; i++) { double x = 1.0 * i * W / (W + i); if (i % 2 == 1) { ratio +…

a1 , .. , an b1 , .. , bn 順列 a,b に対して、N から 1 まで。大きい順に値を配置していくことを考える。 大きい順に配置するため、両方空いている場所に値 i を配置した時点で もう片側に i 以下の値しか入らないので、 magic(A,B) に i が追加される。値…

青赤 青緑 ←← →→ ↑ ↑ 上の図のように、左右のキューのどちらかに追加していく。このときにすでにその色が入ってないキューに入れるようにすればよい。 public class LittleElephantAndBalls { public int getNumber(string S) { var left = new HashSet(); v…

TrafficCongestionDivTwo の treeHeight の上限が 60 から 1000000 になったもの。漸化式自体は、同じ dp[i] = (sum 2*dp[j] where j だけど、これだと O(treeHeight^2) でTLEになる。合計を求めるところがネックなので、dp[0], ... , dp[i-2]までの和を逐次…

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 したものをしたものを調べ…