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

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

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

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

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

問題 Problem - C - Codeforcescodeforces.com 解法 について考える。 の時、自分より前に出てきたbの数を記録しておく。 の時、自分より前に出てきたに記録されているbの数の和を記録しておく。 の時、それまでに出てきたbの数に1加える。 コード import ja…

問題 Problem - D - Codeforcescodeforces.com 解法 残ったボードに存在しうる船の数を常に保持するようにする。 コード import java.util.Scanner; import java.util.TreeMap; public class Main { public void solve() { Scanner scanner = new Scanner(Sy…

問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCodertenka1-2015-quala.contest.atcoder.jp 解法 http://tenka1.klab.jp/2015/explain/quala_c.htmltenka1.klab.jp隣り合った2マスが両方Bと違い、かつ、入れ替えればBと一致する場合、…

解法 式を書いてみると、K回目の操作が終わった後、Aの山の方は石の数が となっている。それを計算し、小さい方を返せば良い。 コード import java.math.BigInteger; public class BearPlays { public int pileSize(int A, int B, int K) { long S = A + B; …

問題 Problem - D - Codeforcescodeforces.com 解法 含む範囲のクエリは、重なっている部分だけを取り出していけば、必ず1つだけの範囲になるはず。離れた2つの範囲が出てきた場合、題意に合わないのでcheatである。含まない範囲のクエリは、和集合を取って…