問題文とは逆に (x, y) からスタートして 1, 9, 27 ... の直進移動で (0, 0) に移動できるかどうかを考える。2ステップ以降は、3の倍数分しか移動できないため 1ステップ目で x, y が両方とも 3 の倍数になるように移動しなくてはならない。x と y が両方と…

解説は、TopCoder SRM614 解説 を参考にしてください。\(O(N^3)\) 解です。 public class MinimumSquare { struct Point { public long X, Y; } public long minArea(int[] x, int[] y, int K) { var points = x.Zip(y, (X, Y) => new Point { X = X, Y = Y …

ある２匹の猫が互いに背を向けている場合、両方の猫の向きを直して、向かい合わせることで必ず移動後の位置の差が小さくなる。つまり任意の猫のペアが向かい合っているような初期状態だけを考えればよく、そのような状態は |coordinates|+1 通りしかないので…

全て要素が１の場合は、LOSE 。 要素数が２つ以下の場合も、LOSE 。 ３つ以上要素がある場合は、次のステップで２箇所に加算するため、２より大きい要素が少なくとも２つできる。よって要素が全て１になることはなく、要素数が２以下になるまで勝負がつかな…

Div2Medium の派生版。\((a,b)\)と\((c,d)\) それぞれから逆方向に変換していって、それらの共通部分での最大値を返せば良い。 public class PairGame { public IEnumerable<Tuple<int, int>> Get(int a, int b) { var set = new List<Tuple<int, int>>(); while (a > 0 && b > 0) { set.Add(</tuple<int,></tuple<int,>…

あらかじめ、市松模様上に色を反転させておく。すると後は、黒一色の長方形と白一色の長方形の面積の最大値を求める問題になる。最大の長方形面積を求める問題は \( O(WH) \) の解法があるが、そこまでに頑張らなくても \( O(W^2H^2/4) \) の全探索で十分間…

任意の切れ目で、２つの文字列に分割して、左側の '>' の個数と右側の ' public class MagicalStringDiv1 { public int getLongest(string S) { int n = S.Length; int ans = 0; for (int i = 0; i < n; i++) { var left = S.Take(i).Count(c => c == '>'); …

PalindromicSubstringsDiv2 と要領は同じ。Sのi番目からj番目までの部分文字列をS[i,j]と表記する。「S に含まれている回文の個数の期待値」＝「S の部分文字列の回文の個数の期待値」。期待値の線形性よりこれは「Sのそれぞれの部分文字列について回文にな…

美味しいものから順に食べる。ただし美味しさがマイナスかつ、すでにその種類のものを食べたことがある場合は食べない。この工程での満足度の最大値を求めれば良い。 public class AlienAndHamburgers { public int getNumber(int[] types, int[] tastes) { …

それぞれの guess, answer について guess + answer、 guess - answer のどちらかが必ず答えになる。よってこの２要素となる候補の集合積を取ることで、答えの候補が導出できる。 また、答えは必ず 1 以上 1,000,000,000 以下でないといけないのでその条件で…

動的計画法。rating が 2200 を超えた場合だけ特別処理することで、保持するべき「現在のrating」の状態数を 0～2199 までに落とせる。 public class TypoCoderDiv1 { int?[,] memo = new int?[51, 2200]; public int dfs(int pos, int[] D, int rating) { i…

与えられるグラフは木のため、少なくとも２つは葉がある。先行は、最初のターンで葉だけを残すことができるため、葉の最大コストのスコアを保証することができる。 後攻は、先行が即ゲーム終了しなかった場合だけ、ターンが回ってくる。初期状態の葉のうちの…

x が小さい場合について、TheNumberGameDivTwo の方法で調べると x が偶数かつ x が \( 2^{2*k+1} \) ではない場合だけ先手必勝となることが分かる。 public class TheNumberGameDivOne { public string find(long n) { return Solve(n) ? "John" : "Brus"; …

それぞれのバッグから採るフルーツの個数 X を固定したとき、apple を取った個数が決まれば、orange を取った個数は自動的に決まる。よって、それぞれの X について、appleを取る個数のパターンを調べれば良い。以下のプログラムでは、取れる apple の最大値…

\( A = {p_1}^{q1} \times {p_2}^{q2} \times ... \times {p_n}^{qn} \) \( A^B = {p_1}^{q1 * B} \times {p_2}^{q2 * B} \times ... \times {p_n}^{qn * B} \) とする。まず、X にAの素因数分をそれぞれ掛けて、 \( X = p_1 \times p_2 \times ... \times p…

goal の使っている各bitについて、その bit を立てられないように、numbers から削除すればよい。ただしこのとき numbers のうち、goal が使っていない bit を含むものは無視する。 public class ORSolitaire { public int getMinimum(int[] numbers, int go…

public class BinPacking { public int minBins(int[] item) { Array.Sort(item); int n = item.Length; bool[] used = new bool[n]; int ans = 0; for (int i = n - 1; i >= 0; i--) { if (used[i]) continue; int target = -1; for (int j = i - 1; j >= 0…

public class LittleElephantAndString { public int getNumber(string A, string B) { if (!A.OrderBy(s => s).SequenceEqual(B.OrderBy(s => s))) return -1; int a = A.Length - 1, b = B.Length - 1; while (a >= 0 && b >= 0) { while (a >= 0 && A[a] …

public class AstronomicalRecords { int LCS(long[] A, long[] B) { int n = A.Length; int m = B.Length; var dp = new int[n + 1, m + 1]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (A[i] == B[j]) { dp[i + 1, j + 1] = Math.Ma…

(最長bitの高さ - 1) + 立っている bitの個数が答えになる。いったん２進数文字列に変換すると楽になった。 public class IncrementAndDoubling { public int getMin(int[] desiredArray) { var a = desiredArray.Select(d => Convert.ToString(d, 2)); retu…

まず、各区間ごとに異なる色で塗り分ける。 最後まで塗り分けたあと、残っている色数を X とすると、 X 個の色それぞれについて独立に白と黒の２色を割り当てられるので、\( 2^X \) が答えになる。色が塗られていない部分を無視しないといけない点にだけ注意…

各行ごとに buffer を使う場合と、undo を使う場合を試して、手数が少ない方を採用する。 public class UndoHistory { int CommonPrefixLength(string a, string b) { return a.Zip(b, (c1, c2) => c1 == c2).TakeWhile(v => v).Count(); } public int minPr…

最悪なケースでも 1 2 3 1 2 3 ... 3 1 2 3 1 2 ... 2 3 1 2 3 1 ... を置くことで、色の個数は高々３に抑えられる。したがって２色で交互に深さ優先探索で色分けしていって、失敗したら３を返すようにする。 public class HexagonalBoard { static public 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]までの和を逐次…

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

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 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 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 を上回ってしまう。よって、市民同士の最短距離の中…