2015-09-01から1ヶ月間の記事一覧

TopCoder SRM 669 Div1 Medium: LineMST

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

TopCoder SRM 541 Div1 Medium: AkariDaisukiDiv1

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

TopCoder SRM 539 Div1 Medium: SafeReturn

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

TopCoder SRM 538 Div1 Medium: TurtleSpy

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

TopCoder SRM 534 Div1 Medium: EllysNumbers

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

TopCoder SRM 535 Div1 Medium: FoxAndBusiness

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

TopCoder SRM 537 Div1 Medium: KingXMagicSpells

解法 各ビットについては独立に考えて動的計画法で解く。 コード 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++…

TopCoder SRM 536 Div1 Medium: RollingDiceDivOne

解法 平均値付近に山が出来る。 コード 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--) …

TopCoder SRM 533 Div1 Medium: MagicBoard

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

TopCoder SRM 667 Div1 Medium: CatsOnTheCircle

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

TopCoder SRM 532 Div1 Medium: DengklekBuildingRoads

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

TopCoder SRM 668 Div1 Medium: WalkingToSchool

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

TopCoder SRM 531 Div1 Medium: MonsterFarm

コード 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…

TopCoder SRM 530 Div1 Medium: GogoXMarisaKirisima

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

TopCoder SRM 528 Div1 Medium: SPartition

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

TopCoder SRM 526.5 Div1 Medium: MagicBlizzard

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

TopCoder SRM 527 Div1 Medium: P8XMatrixRecovery

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

TopCoder SRM 667 Div1 Easy: OrderOfOperations

解法 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++) { …

TopCoder SRM 667 Div1 Easy: OrderOfOperations

解法 各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 Round #319 Div1 C: Points on Plane

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

Codeforces Round #319 Div1 B: Invariance of Tree

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

TopCoder SRM 526 Div1 Medium: PrimeCompositeGame

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

TopCoder SRM 524 Div1 Medium: LongestSequence

コード 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の和がループしない…

TopCoder SRM 525 Div1 Medium: Rumor

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

初心者が CODE FESTIVAL 予選突破するには

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

Codeforces Round #318 Div1 C: Bear and Drawing

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

TopCoder SRM 523 Div1 Medium: BricksN

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

TopCoder SRM 522 Div1 Medium: CorrectMultiplication

コード 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++…

TopCoder SRM 521 Div1 Medium: RangeSquaredSubsets

コード 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)…

TopCoder SRM 520 Div1 Medium: SRMIntermissionPhase

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