2015-08-07から1日間の記事一覧

TopCoder SRM 505 Div1 Medium: SetMultiples

解法 TopCoder SRM 505 Div1 Medium SetMultiples - simezi_tanの日記d.hatena.ne.jp[C, D]の中でC*2 コード public class SetMultiples { public long smallestSubset(long A, long B, long C, long D) { C = Math.max(C, D / 2 + 1); A = Math.max(A, B / …

TopCoder SRM 504 Div1 Medium: AlgridTwo

解法 SRM 504 div1 med:AlgridTwo - mayoko’s diarymayokoex.hatenablog.comh+1行目はh行目から生成される上に、h行目は与えられているので、そのh+1行目を作る時だけ考えれば良い。 h行目から生成したh+1行目がoutputのh+1と矛盾する場合、答は0である。 矛…

TopCoder SRM 503 Div1 Medium: KingdomXCitiesandVillages

解法 村vについて考える。 村vが最初に選ばれる確率は1/M 村vからj番目に近い村wに道路を敷く時、 村wは接続済みでなければならない 村wよりも村vに近い村は接続されていてはならない それ以外の村が接続されているかどうかは答に影響しないので、「それ以外…

TopCoder SRM 502 Div1 Medium: TheProgrammingContestDivOne

解法 動的計画法で解く、いわゆる典型DP。requiredTime/pointsPerMinが小さい方から解いていく方が有利なので、問題をこの値でソートし、DPすれば良い。 コード import java.util.Arrays; public class TheProgrammingContestDivOne { public int find(int T…

TopCoder SRM 501 Div1 Medium: FoxAverageSequence

解法 Div2 Hard = Div1 Medium FoxAverageSequence (Dynamic Programming) - Wrong Answer -- japljtopcoder.g.hatena.ne.jpdp[pos][sum][last][flag]の配列を作ると時間もメモリも間に合わないのが、posはpos->pos+1の遷移しか起きないので、dp[sum][last][…

TopCoder SRM 500 Div1 Medium: FractalPicture

解法 500回フラクタルを成長させるが、長方形の各頂点は格子点なので、6回め以降に生成された線分についてはまとめて考えることができる。 コード import java.util.ArrayDeque; import java.util.ArrayList; public class FractalPicture { public double g…