C♯の勉強

C♯4.0 で TopCoder の過去問を解きます。

Div1

TopCoder SRM 605: AlienAndPermutation

例として { 1, 5, 3, 4, 7, 6, 2 } から遷移できる配列を列挙する。 1 5 5 5 5 7 2 5 5 3 7 7 6 6 5 5 5 5 7 7 7 1 5 5 7 7 6 2 7 7 7 7 7 7 7 眺めてみると、以下の規則性があることが分かる。 同一の数字は一箇所にかたまっている。1112111のように複数箇…

TopCoder SRM606: EllysPairing

Practice だと return 0; するだけのプログラムでも StackOverFlow になってシステムテストで正当チェックができなかった。一番出現数が多い名前 f の出現数を x とする。x が全名前の過半数以下の場合は、ペアの最大数 floor(名前の個数 / 2) がそのまま答…

TopCoder SRM 604: TorusSailing

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

TopCoder SRM 604: FamilyCrest

サンプルが豊富で大きなヒントになっているが、バグ無しの実装が大変な問題。方針としては、微小距離だけ移動しても自分自身と重ならないような方向が存在するかを判定する。 以下、「移動」というのは微小距離だけ移動という意味で用いている。2つの線分だ…

TopCoder SRM 614: TorusSailing

解法は TopCoder SRM614 解説 を参考にしてください。流れは、だいたい以下のとおり。 全てのループを断ち切るように N + M - 1 箇所のマスを変数化 斜めに変数化すれば max(N, M) 箇所でよい すべての箇所の期待値を、DP を使って (N + M - 1) 変数多項式で…

TopCoder SRM 614: CycleColoring

第一段階で、各々の長さの彩色パターンを DP で求めて、 第二段階で、第一段階で求めた彩色パターンを使って、同じような DP を構築する。K 色全てを状態にするのではなく、開始地点と同じ色かそうでないかの2通りだけの状態を考えれば良い。具体的な処理は…

TopCoder SRM 614: MinimumSquare

解説は、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 …

TopCoder SRM613: TaroFriends

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

TopCoder SRM619: SplitStoneGame

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

TopCoder SRM620: PairGame

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

TopCoder SRM610: TheMatrix

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

TopCoder SRM610: AlbertoTheAviator

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

TopCoder SRM609: MagicalStringDiv1

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

TopCoder SRM607: PalindromicSubstringsDiv1

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

TopCoder SRM605: AlienAndHamburgers

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

TopCoder SRM606: EllysNumberGuessing

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

TopCoder SRM602: TypoCoderDiv1

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

TopCoder SRM603: MaxMinTreeGame

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

TopCoder SRM603: PairsOfStrings

久しぶりに本番で通ったMedium。A + C = C + B が成立するときは A は B を巡回シフトさせたものになる。 よって、もし A の文字列の最小周期が x だった場合は、対応するペアの個数は x になる。周期が x の文字列の個数は n % k == 0 のときは \(k^x\) 、…

TopCoder SRM601: WinterAndSnowmen

public class WinterAndSnowmen { const int mod = 1000000007; static public void Add(ref int x, int value) { x += value; x %= mod; } public int getNumber(int N, int M) { const int BitNum = 12; int ans = 0; for (int diffBitPosition = 0; diffB…

TopCoder SRM575: TheNumberGameDivOne

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

TopCoder SRM601: WinterAndPresents

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

TopCoder SRM599: BigFatInteger

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

TopCoder SRM600: PalindromeMatrix

回文になる行の集合を全通り試す。回文になる行の箇所が固定されると、(0列とW-1列), (1列とW-2列)... のペアそれぞれについて独立に処理できるため、あとは動的計画法で処理できる。本番だと、i列と(W-1-i)列のペアについて、「i列が回文である / でない」…

TopCoder SRM600: ORSolitaire

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

TopCoder SRM598: TPS

public class TPS { static int[] GetDegrees(string[] linked) { var n = linked.Length; var deg = new int[n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (linked[i][j] == 'Y') { deg[j]++; } } } return deg; } String[] Shrink…

TopCoder SRM598: FoxAndFencing

public class FoxAndFencing { const string Ciel = "Ciel"; const string Liss = "Liss"; const string Draw = "Draw"; public string WhoCanWin(int mov1, int mov2, int rng1, int rng2, int d) { if (mov1 + rng1 >= d) return Ciel; if (mov1 + d <= mo…

TopCoder SRM598: BinPacking

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…

TopCoder SRM597: LittleElephantAndString

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

TopCoder SRM594: AstronomicalRecords

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…