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…

正面から見えるブロック数を N、横から見えるブロック数を Mとすると N × M の長方形の全列全行にブロックが少なくとも１つあるような配置のパターン数が答えになる。以下では、「すでにブロックが配置されている行の個数」×「着目している列」を状態にした…

色が変わる節目の個数を数える。 public class TypoCoderDiv2 { public int count(int[] rating) { int ans = 0; int current = 500; foreach (var r in rating) { if (current >= 1200 ^ r >= 1200) ans++; current = r; } return ans; } }

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

まず、長方形が幅＜高さになるように回転させる。 あとは、共通部分の領域面積が limit 以下であるような２つの長方形のペアを全通り選ぶ。 それぞれのペアについて、共通部分の短形を完全に内包する他の長方形の個数 m としたとき、 m + 2 の最大値を求めれ…

DP[n] = 「初期値が n のとき先手必勝」とすると DP[n] = n - 「nの1とn以外の約数」のときについて、先手必勝ではないものあれば、True。あとはこの漸化式を計算する。 public class TheNumberGameDivTwo { public string find(int n) { var dp = new bool[…

スワップの全パターンを試す。String.Join に String 以外の配列をそのまま渡しても問題ないようだ。 public class TheSwapsDivTwo { static public void Swap<T>(ref T a, ref T b) { T t = a; a = b; b = t; } public int find(int[] sequence) { int n = seq</t>…

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

文字列 A、B から文字列 C を内包する最小限の区間を全て列挙する。 A : [A1] [C を内包する区間] [A2] B : [B1] [C を内包する区間] [B2]としたとき、 [A1][B1]の LCS の長さ + C の長さ + [A2]と[B2]の LCSの長さ の最大値が答えになる。(LCS: 最長共通部…

ヒストグラムを取って、 １の個数 １の個数 * ２の個数 ... １の個数 * ２の個数 * ３の個数 * ... * |type| の個数 の合計を出すだけ。よく見てみると O(|type|) に落とせますね。 public class WinterAndCandies { public int getNumber(int[] type) { var…

bags をソートして、連続区間を全て試せば良い。 public class WinterAndMandarins { public int getNumber(int[] bags, int K) { if (bags.Length < K) return int.MaxValue; Array.Sort(bags); return Math.Min(bags.Take(K).Max() - bags.Take(K).Min(), …

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

public class SimilarNames2 { int mod = 1000000007; int?[,] memo; int dfs(string[] names, int pos, int L) { if (L == 0) return 1; if (!memo[pos, L].HasValue) { int val = 0; for (int i = 0; i < names.Length; i++) { if (i == pos) continue; if…

\( A = 2^{a1} \times 3^{a2} \times ... \times p_n^{an} \) \( C = 2^{c1} \times 3^{c2} \times ... \times p_n^{cn} \) より \( A^B = 2^{a1*B} \times 3^{a2*B} \times ... \times {p_n}^{an*B} \) \( C^D = 2^{c1*D} \times 3^{c2*D} \times ... \time…

体重 5kg を超えないように、みかんを軽い順に食べていきます。 public class MiniatureDachshund { public int maxMikan(int[] mikan, int weight) { Array.Sort(mikan); int cnt = 0; foreach (int m in mikan) { weight += m; if (weight <= 5000) cnt++;…

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

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

N,M は 2 以上 8 以下のため、「回文になる列の集合」と「回文になる行の集合」について全探索できる。回文になる行と列がはっきりしていると、{ A[y][x] , A[H-1-y][x] , A[y][W-1-x] , A[H-1-y][W-1-x] } について、同じ値にしないといけないペア情報が確…

シャトルの座席数で全探索。 public class TheShuttles { public int getLeastCost(int[] cnt, int baseCost, int seatCost) { int ans = int.MaxValue; for (int seat = 1; seat <= 100; seat++) { int need = 0; foreach (var c in cnt) { need += (c - 1)…

Div1Easy の ORSolitaire とは違って、|numbers| public class ORSolitaireDiv2 { public int getMinimum(int[] numbers, int goal) { int n = numbers.Length; int ans = int.MaxValue; for (int i = 0; i < (1 << n); i++) { int or = 0, cnt = 0; for (in…

この記事は、Competitive Programming Advent Calendar Div2013 - PARTAKE の10日目の記事です。 はじめに 長い年月を経て、ついにTopCoderの C# 環境が、.NET Framework 2.0 から .NET Framework 4.0 へとアップグレードされました。そこでさっそく TopCode…

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…

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…

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 FoxAndFencingEasy { const string Ciel = "Ciel"; const string Liss = "Liss"; const string Draw = "Draw"; public string WhoCanWin(int mov1, int mov2, int d) { if (mov1 >= d) return Ciel; if (mov1 > mov2 * 2) return Ciel; if (mov…

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

s.Substring(0, i)+s.Substring(i + 2) とするより Remove 使ったほうが楽でした。 public class ErasingCharacters { public string simulate(string s) { for (int i = 0; i < s.Length - 1; i++) { if (s[i] == s[i + 1]) { return simulate(s.Remove(i, …