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

本番では、嘘解法っぽい後ろからの貪欲の全探索で通したけど、合っている証明ができなかった。想定解法は、ミッションをRefuelの大きい順に順番を固定してから、動的計画法が適用する、というものだった。ミッションをRefuel の大きい順に並び替れば上手くい…

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

variety set の個数を固定すると、same set の個数が一意に求められる。 そして variety set の候補は、0 から max(R,G,B) で高々 101 通りなので、それらを全て試す。 public class PackingBallsDiv2 { public int minPacks(int R, int G, int B) { int ans…

左右に分割して、それぞれ文字を反転しなければならない箇所を数える。 public class MagicalStringDiv2 { public int minimalMoves(string S) { int n = S.Length; var left = S.Take(n / 2); var right = S.Skip(n / 2); return left.Count(c => c == '<')…

任意の切れ目で、２つの文字列に分割して、左側の '>' の個数と右側の ' 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 == '>'); …

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

箱の全集合を \( S \) 、選んだ箱の集合を \( A \)とする。選んだ箱の集合に含まれるキャンディが最小となる場合というのは、選ばれなかった箱に可能な限りキャンディが入っている場合と同等になる。よって \(A\) に含まれるキャンディの最小値は、\(C - \su…

単純な実装問題。 public class OneDimensionalRobotEasy { public int finalPosition(string commands, int A, int B) { int pos = 0; foreach (var c in commands) { pos += (c == 'R') ? 1 : -1; if (pos < -A) pos = -A; if (pos > B) pos = B; } return…

C# とは関係ないけど、一応ここに貼っておく。 素数 3 5 7 83 89 97 983 991 997 9949 9967 9973 99971 99989 99991 999961 999979 999983 9999971 9999973 9999991 99999959 99999971 99999989 999999893 999999929 999999937 ------2^31--------- 99999999…

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

愚直に全部分文字列が回文であるかどうかを判定すると \(O(N^3)\) になる。Sのi番目からj番目の範囲の部分文字列を S[i,j] とすると、S[i,j] が回文である条件は、S[i] == S[j] かつ S[i+1,j-1] が回文になることである。これを理由して動的計画法を適用する…

問題クラス名通り、Bounding Boxの面積を出せばよい。 public class BoundingBox { public int smallestArea(int[] X, int[] Y) { return (X.Max() - X.Min()) * (Y.Max() - Y.Min()); } }