問題 D: マーブル - AtCoder Beginner Contest #004 | AtCoderabc004.contest.atcoder.jp 解法 AtCoder Beginner Contest 004 解説 from chokudai www.slideshare.netスタートと赤・緑・青のノードを結び、赤・緑・青と座標-500~500のノードを結び、これらの…

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

問題 D: Big Bang - AtCoder Beginner Contest 022 | AtCoderabc022.contest.atcoder.jp 解法 AtCoder Beginner Contest 022 解説 from chokudai www.slideshare.net外側の点を結んで、全ての点が内部か線上にあるような多角形を作る。（凸包というらしい）…

問題 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;…

問題 C: 億マス計算 - AtCoder Regular Contest 037 | AtCoder 解法 各a[i]の段のmid以下のa*bの数をカウントし、それがKとなるようにmidを二分探索する。 コード import java.util.Arrays; import java.util.Scanner; public class Main { public static vo…

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

問題 D: トランプ挿入ソート - AtCoder Beginner Contest #006 | AtCoder 解法 AtCoder Beginner Contest 006 解説 コード import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws Excep…

問題 D: おいしいたこ焼きの焼き方 - AtCoder Beginner Contest #005 | AtCoder 解法 たこ焼き器について、二次元の累積和を求めておく。クエリに対して作れる長方形を全列挙し、その長方形を(x,y)だけ平行移動した時に、長方形内部の美味しさの合計を計算す…

問題 D: AtCoder社の冬 - AtCoder Beginner Contest #003 | AtCoder 解法 ステップとしては、 R*C内のX*Yの取りうるパターンを調べる。 X*Y内のD+Lの取りうるパターンを調べる。 D+L内のDとLのパターンを調べる。 の3つをこなす必要がある。R*C内のX*Yの取り…

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

問題 D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder 解法 1からnの中から重複を許してk個選ぶという問題に帰着できる。 を求めたいが、割り算をすると計算に時間がかかりすぎる。そこでモジュラ逆数を使う。モジュラ逆数 - Wikipedia コード impo…

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

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

問題 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder 解法 ある頂点vに注目した時に、「vに入ってくる最大のパス」と「vから出て行く最大のパス」を計算する。この2つが同じパスにならないように、頂点はそれぞれ1度ずつしか注目しない。め…

問題 C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder 解法 dp[pos][diff0][diff1]:= pos文字目まで見た時に、(0の文字数)-(1の文字数)の最大値がdiff0であり、(1の文字数)-(0の文字数)の最大値がdiff1である組み合わせの数とする。S[pos]='0'…

問題 E: Page Rank - Indeedなう（オープンコンテスト） | AtCoder 解法 最初に全社員のPage Rank を1.0としておき、定義にしたがって1000回ほど計算すると収束する。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Scanne…

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