問題 TopCoder Statistics - Problem Statement 解法 配列が環状になっている区間のDP。「first枚目からcount枚の連続した区間の中からmustLeave枚取り除かなければならない場合の最高点」を考える。 コード Petrのコードを参考にした。 import java.util.Ar…

問題 TopCoder Statistics - Problem Statement 解法 貪欲にやれば良い。 コード public class FlipGame { public int minOperations(String[] strings) { int N = strings.length; char[][] board = new char[N][]; for (int i = 0; i < N; i++) { board[i]…

問題 TopCoder Statistics - Problem Statement 解法 100問マラソンはプライドを捨てて AC/Open が高い簡単な問題から解いていくことにした。from->to の移動が可能な時、実際に移動するためには i i の経路を全て潰すことになるので、そのコストを辺 from->…

解法 sigma425.hatenablog.com kmjp.hatenablog.jp求めるべきMSTは一直線になっているので、ある区間がM未満になる場合を考えるとDPになる。 コード public class LineMST { private final long MOD = (long) 1e9 + 7; private long[][] dp; private int L; …

解法 最初のうちは愚直に繰り返すが、ある程度繰り返すと先頭と末尾で常に同じ文字列が生成されるようになるので、あとは足し算を繰り返していくだけで良い。 コード public class AkariDaisukiDiv1 { private final int MOD = 1000000007; public int count…

解法 kmjp.hatenablog.jpやることは、 ワーシャルフロイト + 二部グラフの最大マッチング（最大フロー）ワーシャルフロイトで2点間の距離を出しておくと、最短距離を通る時にその頂点を通過するか確認することが出来る。 for (int x = 0; x < N; x++) { for …

解法 右回転と左回転の中から上手く組み合わせてできるだけ180度に近い角度を作る。最初にできるだけまっすぐ進み、次に180度に出来るだけ近くなるように回転し、そこから反対向きにまっすぐ進み、最後にその場で消費しきれていない回転コマンドを使いきれば…

解法 そもそも、specialの中の整数を互いに素になるように組み合わせてnが作れるのかチェックする。出来るのであればbitDPするだけ。 コード import java.util.ArrayList; import java.util.Map; import java.util.TreeMap; public class EllysNumbers { pub…

解法 topcoder.g.hatena.ne.jp絶対ナップザックだと思ったら二分探索だった。 コード import java.util.ArrayList; import java.util.Collections; public class FoxAndBusiness { public double minimumCost(int K, int W, int[] work, int[] cost) { int N…

解法 各ビットについては独立に考えて動的計画法で解く。 コード public class KingXMagicSpells { public double expectedNumber(int[] ducks, int[] one, int[] two, int D) { int N = ducks.length; int[] from = new int[N]; for (int i = 0; i < N; i++…

解法 平均値付近に山が出来る。 コード import java.util.Arrays; public class RollingDiceDivOne { public long mostLikely(int[] dice) { Arrays.sort(dice); int N = dice.length; long low = 1, high = dice[N - 1]; for (int i = N - 2; i >= 0; i--) …

解法 各列・各行をそれぞれ1つの頂点とみなし，列->行->列->行->...というように全ての頂点を通ることができれば良い． 一筆書きできるかどうかはオイラー閉路の考え方で頂点の次数を調べれば良い． コード public class MagicBoard { boolean[][] graph; bo…

解法 mayokoex.hatenablog.com コード public class CatsOnTheCircle { public double getProb(int N, int K, int p) { if (p == 1e9 / 2) { return 1.0 / (N - 1); } if (p > 1e9 / 2) { K = N - K; p = (int) 1e9 - p; } double pd = p / 1e9; return turn…

解法 bitDP tanzaku先生のコードを参考にした． コード public class DengklekBuildingRoads { private long MOD = (int) 1e9 + 7; private int K; private boolean[][][][] done; private long[][][][] dp; // nowを見た時に，残りedgeの辺が残っていて，st…

解法 そもそも0->1->0のルートが作れなければ無理である．ルートが作れる場合，シミュレーションによって 0->0 のルートの距離をリストアップする．この距離を組み合わせて1を作ることが出来れば，ある数以上で1刻みの距離を作ることができるので，それを調…

コード import java.util.Arrays; public class MonsterFarm { private final int MOD = (int) 1e9 + 7; public int numMonsters(String[] transforms) { int N = transforms.length; int[][] edge = new int[N][N]; int[] out = new int[N]; for (int i = 0…

解法 まずは深さ優先探索でゴールする．1回のプレイで1回新しい行動をとるようにすれば，最大回数違う経路でプレイできる． コード public class GogoXMarisaKirisima { int N; private boolean[][] map; boolean[][] accessible; boolean visited[]; public…

解法 作られる文字列は種類のうち条件を満たすものだけなので大して種類はない． ある文字列maskを作る時，stringを前から見ていき，Xに入れられるか，あるいは，Yに入れられるかというのでdpを遷移させていけばいい． コード public class SPartition { pub…

解法 辞書順最小なので，前の方から0を入れ，ダメなら1に変える，というふうに貪欲に決めていく．ある'?'を0にした時に矛盾がないかどうかは，その都度rowsの各列とcolumnsの各列が矛盾なくマッチングできるかどうかを調べる． 2部マッチングは最大流問題と…

解法 各bitを頂点，各bit間の遷移を辺としてダイクストラする． コード import java.util.Arrays; import java.util.PriorityQueue; public class OrderOfOperations { public int minTime(String[] s) { int N = s.length; int M = s[0].length(); int[] op…

解法 ゲーム木っぽい動的計画法．実はKが十分に大きければ素数が作れない事態になることはなく，2か3を作って爆速で終了に持ち込むことができる． コード import java.util.Arrays; public class PrimeCompositeGame { public int theOutcome(int N, int K) …

コード import java.util.ArrayDeque; public class LongestSequence { private int[] C; private final int MAX_C = 1000; public int maxLength(int[] C) { this.C = C; if (!isLoop(MAX_C * 2)) { // 無限に続く場合 return -1; } // Dの和がループしない…

解法 Aだけ知っているときはAを，Bだけ知っているときはBを自分の仲間全員に伝えたほうが良い．両方知っている場合は先にどちらかを全員に伝えることになるが，どちらを先にするかはbitmaskで管理して全探索する． コード import java.util.Arrays; public c…

解法 メモ化再帰。「あっ！この問題SRMで見たことある！」感がすごい。TopCoder SRM 509 Div1 Medium: PalindromizationDiv1 - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com TopCoder SRM 511 Div1 Medium: FiveHundredEleven - 宇宙ツイッタラーXの憂鬱…

コード public class CorrectMultiplication { public long getMinimum(int a, int b, int c) { if (a > b) { int bb = b; b = a; a = bb; } long ans = Long.MAX_VALUE; for (int A = 1; A < 1000000; A++) { long B = c / A; for (int d = -5; d <= 5; d++…

コード import java.util.Arrays; import java.util.HashSet; public class RangeSquaredSubsets { public long countSubsets(int nlow, int nhigh, int[] x, int[] y) { int N = x.length; int[] sX = Arrays.copyOf(x, N); int[] sY = Arrays.copyOf(y, N)…

解法 SRM520 Div1 Medium(500) SRMIntermissionPhase - 赤コーダーになりたいd.hatena.ne.jpDPする。総和をとるところで式を工夫して、問題数の少ない方から埋めていくとO(MAX_P)で計算することができる。 コード public class SRMIntermissionPhase { priva…

解法 桁DPの強いバージョン。深さ優先探索で1文字ずつ足していった時に、C個の文字列を含む状態になるかどうかをメモ化して調べれば良い。文字列の後ろl文字がとwords[i]の前l文字と一致している時に、文字列に1文字cを追加したら何文字が一致するようになる…

解法 愚直オブザイヤー。お前その解法が通っちゃダメだろ……！！ コード import java.util.Arrays; public class ConvexSequence { public long getMinimum(int[] a) { int N = a.length; int[] b = Arrays.copyOf(a, N); while (true) { boolean end = true;…

解法 SRM 517 div1 med:AdjacentSwaps - mayoko’s diarymayokoex.hatenablog.com個人的にはこれと一緒だと思った。TopCoder SRM 666 Div1 Medium: SumOverPermutations - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com コード import java.util.Arrays; p…