解法 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…

解法 まずrangeでソートする．ソートすると，前のrangeは後ろのrangeで完全に覆われるので，前のamountはそのまま全て後ろに引き継がれる． コード import java.util.ArrayList; import java.util.Collections; public class MagicBlizzard { public double …

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

解法 DP．クソ．kenkoooo.hatenablog.com コード import java.util.Arrays; public class OrderOfOperations { public int minTime(String[] s) { int N = s.length; int M = s[0].length(); int[] operations = new int[N]; for (int i = 0; i < N; i++) { …

解法 各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…

問題 codeforces.com 解法 縦，横1000の長方形に切る．長方形内で点をyの値でソートする．ひとつの長方形内では，そこに含まれる点の数をPとすると，x軸方向に1000*P，y軸方向にの長さが最大で必要になる．長方形間ではx軸方向に最大で2000必要になり，これ…

問題 codeforces.com 解法 codeforces.com1つだけでループしている頂点があれば，その頂点から他の頂点に辺を出せば良い．2つだけでループしている頂点があれば，その2点を中心にし，そこから他の頂点に辺を出していく．この2点間の間は1本の辺だけで条件を…

解法 ゲーム木っぽい動的計画法．実は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…

はじめに この記事は，競技プログラミング初心者が CODE FESTIVAL 2015 の予選を突破して本選に出場するためには，どのような準備をしたら良いのかということを，僕が考えた個人的な記事です．これを読んで行動して酷い目にあっても怒らないでください． COD…

問題 Problem - C - Codeforcescodeforces.com 解法 頂点iに接続している頂点vについて考える。 vが葉に接続している一本道の途中にある頂点であれば、葉の一部と考えれば良い。 i以外にvが持っている葉が2枚以下であれば、vはiの対岸の行に収めることができ…

解法 メモ化再帰。「あっ！この問題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…