解法 TopCoder SRM 658 Div1 Easy: OddEvenTree - roiti46's blogroiti46.hatenablog.com誤読で撃墜…… 1363 -> 1293 つらい…… コード import java.util.ArrayList; public class OddEvenTree { public int[] getTree(String[] x) { int N = x.length; int[] …

解法 SRM 633 Div1 Easy, PeriodicJumping - na_o_ysのブログna-o-s.hateblo.jp幾何だ！難しそう！ってなってしまうの良くないなぁ…… コード public class PeriodicJumping { public int minimalTime(int x, int[] jumpLengths) { x = Math.abs(x); if (x ==…

解法 例えばs="2014"の時、 となる。 素因数に2を含む個数は、x=4の時、P(4)は5個、P(5)なら4個、P(6)なら4個、P(7)なら8個、P(8)なら……と増えていくが、正の個数で最小の個数は4個であることが分かる。このように各素数ごとに素因数の最小個数を求めると、"…

解法 二分探索するだけ。（なぜかできなかった） コード public class ProblemSets { public long maxSets(long E, long EM, long M, long MH, long H) { long low = 0; long high = Long.MAX_VALUE; while (high - low > 1) { long mid = (high + low) / 2;…

解法 TopCoder SRM 634 Div1 Easy ShoppingSurveyDiv1、Div2 Medium ShoppingSurveyDiv2 - kmjp's blogkmjp.hatenablog.jp コード import java.util.Arrays; public class ShoppingSurveyDiv1 { public int minValue(int N, int K, int[] s) { for (int p = …

解法 Nが400以下なので、N-1個の区間の長さと傾きを計算しておき、傾きが等しく、長さの倍率が等しい区間を出せば良い……がっ……ダメっ……！！誤差ゲーなので値が小さくなり過ぎないように気をつけなければならない。 コード import java.util.ArrayList; impor…

解法 SRM 640 Div1 Easy, ChristmasTreeDecoration - na_o_ysのブログna-o-s.hateblo.jp コード public class ChristmasTreeDecoration { public int solve(int[] col, int[] x, int[] y) { int N = col.length; UnionFind uf = new UnionFind(N); for (int …

解法 TopCoder SRM 641 Div1 Easy TrianglesContainOrigin、Div2 Medium TrianglesContainOriginEasy - kmjp's blogkmjp.hatenablog.jp各点の仰角を求めてargsに入れておく。0以下になる場合には2*PIを足しておく。atan2を使うと仰角を簡単に求めることが出…

解法 動的計画法（渡すDP）。dp[t]:= 時刻tに出発できる確率を計算しておく。 コード public class WaitingForBus { private final int MAX_TIME = 200001; public double whenWillBusArrive(int[] time, int[] prob, int s) { int N = time.length; double[…

問題 TopCoder Statistics - Problem Statement 解法 上のような整数を素因数分解する場合、ヒントを駆使しても10の8乗ループをすることになるが、primes[i] 素数で、primes[i]とprimes[i+1]の間にあるので、ループする必要がなくなる。 コード import java.…

解法 osizeをソートする。osize[i]が最小となる組み合わせを考える。この時osize[i+M-1]がosize[i]+Kより大きかったら、osize[i]が最小となる組み合わせは0通りである。osize[i]との差がK以内となる最大のosize[last]を考えると、osize[i]は必ず入れることに…

問題 TopCoder Statistics - Problem Statement 解法 TopCoder SRM 645 Div1 Easy JanuszTheBusinessman - kmjp's blog蟻本に載ってた気がする。酷いバグを埋め込んで大変苦労した。 コード import java.util.ArrayList; import java.util.Collections; publ…

問題 TopCoder Statistics - Problem Statement 解法 残っている数から引くことの出来る最大の奇数を引く。これを繰り返す。ただし。残りの数字が2になるようなパターンは避ける。 コード public class AliceGame { public long findMinimumValue(long x, lo…

問題 TopCoder Statistics - Problem Statement 解法 昇順にソートし、スタート位置、操作しない数字、増加か減少か、というのを全探索してシミュレーションする。やるだけ。 コード import java.util.Arrays; public class TheConsecutiveIntegersDivOne { …

問題 TopCoder Statistics - Problem Statement 解法 2015-04-11topcoder.g.hatena.ne.jp最初に全てのマスにトークンを置いておき、収束するまで回す。 min(K, 50) 回だけ回せば良い。収束したら、マスにあるトークンの数+1を各マスについてかけ合わせる。（…

問題 TopCoder Statistics - Problem Statement 解法 TopCoder SRM 656 Div1 Medium PermutationCounts、Div2 Hard PermutationCountsDiv2 - kmjp's blogkmjp.hatenablog.jp神様仏様kmjp様 コード import java.math.BigInteger; import java.util.ArrayList;…

解法 dp[i][j]:= i番目にjのパンケーキが置かれる確率を3重ループを回して求めておき、最後に各パンケーキの美味しさを期待値を出す。1310 -> 1473 (+163) コード import java.util.Arrays; public class RandomPancakeStack { public double expectedDelici…

コード import java.util.PriorityQueue; public class BuildingTowersEasy { public int maxHeight(int N, int[] x, int[] t) { for (int i = 0; i < x.length; i++) { for (int j = 0; j < x.length; j++) { t[i] = Math.min(t[i], t[j] + Math.abs(x[i] -…

解法 X-Ray Screening System | Aizu Online Judge解法はAOJ 2002と同じ。必ず1番上に隠れていない正方形があるはずなので、それを取り除く。するとまた一番上に正方形が出てくるはずなので取り除く… というのを繰り返し、取り除ける正方形が無くなった時に…

嘘解法 左端から順番に見て、お手本に合うように塗っていき、最終形がお手本と同じになっていれば良いと思った（違った）。 誤答コード public class BichromePainting { public String isThatPossible(String[] board, int k) { String YES = "Possible"; S…

問題 TopCoder Statistics - Problem Statement 解法 条件に反さないように立方体を置き、とりあえず立体を作る。 全ての立方体が接続されているとは限らないので、接続されている立体ごとに分け、その中に条件を満たすものが存在するかどうか確かめる。 コ…

解法 SRM 636 Div. 1 Easy: ChocolateDividingEasy - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com以前全探索で解いた問題を2次元の累積和で解き直してみた。実行時間が 1979 ms から 468 ms になった。 コード import java.util.Arrays; public class C…

問題 TopCoder Statistics - Problem Statementsnukeさん 解法 見えている部分については、勝てるカードがあればできるだけ小さいカードで勝ち、勝てない時は小さいカードで負けるようにする。見えていない部分はどうしようもないので期待値を出す。 コード …

問題 TopCoder Statistics - Problem Statement 解法 どう見ても累積和の問題なんだけど、愚直な全探索で通った（通った）。 コード public class ChocolateDividingEasy { public int findBest(String[] choco) { int H = choco.length; int W = choco[0].l…

問題 TopCoder Statistics - Problem Statement 解法 点0から始めて、曲がり角が最も大きくなるように貪欲に点を取っていくと上手くいく。 コード public class NoRightTurnDiv2 { double[] direction(int[] X, int[] Y, int from, int to) { // fromからto…

問題 TopCoder Statistics - Problem Statement 解法 動的計画法を使う。アリスが最後に歌った曲とボブが最後に歌った曲に対応する難易度の最小値をメモしておく。 コード public class SingingEasy { public int solve(int[] pitch) { int N = pitch.length…

問題 TopCoder Statistics - Problem Statement 解法 どのように括弧を挿入しても、a[0]は必ず正、a[1]は必ず負になる。 a[2]からa[i]までの合計値をとる。 ただしa[2]からa[j]までの合計値が負になるとき、-a[2]から-a[j]までの合計値は正になるので、a[2]…

解法 4方向いずれかを連打して壁に当たるなら、-1である。どれを連打しても壁に当たらない時は、連打できる最大数を求めておく。この最大数の範囲内であればどのように部分文字列を取られても死ぬことはない。 コード public class RobotOnMoon { public int…

問題 TopCoder Statistics - Problem Statement 解法 偶数個間が空いている時、例えば2個空いている時、A__Bのようになっている時はABABしかあり得ないが、A__Aのようになっている時はAABAかABAAかABBAのように3通り考えられる。一般化すると、間が2k個空い…

問題 TopCoder Statistics - Problem Statementtozangezanさん 解法 SRM 649 div1 easy: Decipherability - mayoko’s diary コード import java.util.Arrays; public class Decipherability { public String check(String s, int K) { if (s.length() == K) …