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

public class SpaceWarDiv2 { public int minimalFatigue(int[] magicalGirlStrength, int[] enemyStrength, int[] enemyCount) { int n = magicalGirlStrength.Length; magicalGirlStrength = magicalGirlStrength.OrderByDescending(s => s).ToArray(); va…

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

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…

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

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

文字の種類は 'A'... 'I' の９種類しかない。 となると ('A'...'I') -> ('A'...'I') の割り当ての仕方は 9! になるため、全部試しても間に合う。それぞれの割り当てについて、割り当て通りではない (A[i], B[i]) を削除すればよい。next_permution は C♯ に…

問題文一歩進む、二歩進む、と続けていって、もし障害物にあたったら「一歩進む」をなかったことにする。 その直後のターンでは少なくとも「二歩以上進む」ことになるので必ず障害物は飛び越される。 public class JumpFurther { public int furthest(int N,…

問題文線形な区間ごとに解があるかを判定する。重解に注意。 public class PiecewiseLinearFunctionDiv2 { public int numberOfSolution(int[] Y, int y) { int n = Y.Length; int ans = Y[0] == y ? 1 : 0; for (int i = 0; i < n - 1; i++) { if (Y[i] < y…

問題文全探索。 public class FoxAndGo { static public int[] dx = { 0, 1, 0, -1 }; static public int[] dy = { 1, 0, -1, 0 }; public int FloodFill(char[][] board, int x, int y, ref bool existEmpty){ if(board[y][x] != 'o') return 0; board[y][x…

問題文Div1 とは違って、|songs| が 15以下なので全探索で通る。無理にLINQを使うとより複雑になる一例。 public class GUMIAndSongsDiv2 { IEnumerable<int> GetBitIndice(long n) { int index = 0; var list = new List<int>(); while (n > 0) { if ((n & 1) != 0) l</int></int>…

問題文 「一番最初に削除する場所を固定してから貪欲」を全箇所で試す 答えが 0 の場合は別処理 LINQ だと solve 関数のような一個前の値を見る系の処理が扱いづらいのが残念 public class GearsDiv2 { public int solve(String s) { int ans = 1; for (int …