読者です 読者をやめる 読者になる 読者になる

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…

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…

TopCoder SRM 519 Div1 Medium: RequiredSubstrings

解法 桁DPの強いバージョン。深さ優先探索で1文字ずつ足していった時に、C個の文字列を含む状態になるかどうかをメモ化して調べれば良い。文字列の後ろl文字がとwords[i]の前l文字と一致している時に、文字列に1文字cを追加したら何文字が一致するようになる…

TopCoder SRM 518 Div1 Medium: ConvexSequence

解法 愚直オブザイヤー。お前その解法が通っちゃダメだろ……!! コード import java.util.Arrays; public class ConvexSequence { public long getMinimum(int[] a) { int N = a.length; int[] b = Arrays.copyOf(a, N); while (true) { boolean end = true;…

TopCoder SRM 517 Div1 Medium: AdjacentSwaps

解法 SRM 517 div1 med:AdjacentSwaps - mayoko’s diarymayokoex.hatenablog.com個人的にはこれと一緒だと思った。TopCoder SRM 666 Div1 Medium: SumOverPermutations - 宇宙ツイッタラーXの憂鬱kenkoooo.hatenablog.com コード import java.util.Arrays; p…

TopCoder SRM 516 Div1 Medium: RowsOrdering

問題 読解問題は無理なのでkmjp先生の訳を見た。TopCoder SRM 516 Div1 Medium RowsOrdering - kmjp's blogkmjp.hatenablog.jp コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; public class RowsOrdering { pr…

TopCoder SRM 666 Div1 Medium: SumOverPermutations

解法 TopCoder SRM 666 Div1 Medium SumOverPermutations - kmjp's blogkmjp.hatenablog.jp コード public class SumOverPermutations { private final int MOD = (int) 1e9 + 7; public int findSum(int n) { if (n == 1) { return 1; } // パスカルの三角…

TopCoder SRM 515 Div1 Medium: NewItemShop

解法 動的計画法(メモ化再帰)する。2回以上来る顧客をbitで管理しておく。 各タイミングの各bitにおいて、「来ない時」「来たから売る時」「来たけど売らない時」をそれぞれの計算して期待値を出せばいい。重要な式はこんな感じ。 double sell = dfs(time …

TopCoder SRM 514 Div1 Medium: MagicalGirlLevelTwoDivOne

解法 左上のN*Mの長方形内の遇奇を考えれば良い。 i行目の和が奇数になるパターンを組み合わせて、i行目までの各列の和が最終的に奇数になるようにビットDPすれば良い。 コード import java.util.Arrays; public class MagicalGirlLevelTwoDivOne { private …

TopCoder SRM 666 Div1 Easy: WalkOverATree

コード public class WalkOverATree { public int maxNodesVisited(int[] parent, int L) { int N = parent.length + 1; int[] dist = new int[N]; int max = 0; for (int i = 1; i < N; i++) { dist[i] = dist[parent[i - 1]] + 1; max = Math.max(max, dis…

TopCoder SRM 513 Div1 Medium: PerfectMemory

解法 動的計画法(メモ化再帰)するだけ。(独力で解けたのでメッチャ嬉しい) コード public class PerfectMemory { private double[][] dp; public double getExpectation(int N, int M) { int C = N * M; dp = new double[C + 1][C + 1]; double ans = dp…

TopCoder SRM 512 Div1 Medium: SubFibonacci

解法 SRM 512 Div1 Medium SubFibonacci - simezi_tanの日記d.hatena.ne.jp コード import java.util.Arrays; public class SubFibonacci { private final int MAX_F = 46; public int maxElements(int[] S) { long[] fib = new long[MAX_F]; fib[0] = 1; fi…

TopCoder SRM 511 Div1 Medium: FiveHundredEleven

解法 ゲーム木的な考え方で深さ優先探索する。実は今までどのカードを取ったかを記録しておく必要はない。現状のビットを維持できる(現状のビットに影響のないカードを取ることができる)なら511を作って負けることはないので、ビットを増やしてしまうカー…

TopCoder SRM 510 Div1 Medium: TheLuckyGameDivOne

解法 lucky number の総数は大したことないので全列挙しておく。あとは全ての lucky number についてそれぞれの戦略を考えれば良い。 コード import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; public class TheLuck…

TopCoder SRM 509 Div1 Medium: PalindromizationDiv1

解法 文字列の長さ伸びたり縮んだりする気がするが、例えば右端にaddする場合は左端と同じ文字をaddするので、操作を重ねるごとに考えるべき文字列は縮んでいく。メモ化再帰で求めれば良い。 コード import java.util.Arrays; public class Palindromization…

TopCoder SRM 508 Div1 Medium: YetAnotherORProblem

解法 SRM 508 div1 med:YetAnotherORProblem - mayoko’s diarymayokoex.hatenablog.com無理ゲー臭がすごい。 コード public class YetAnotherORProblem { private final long MOD = 1000000009; private final int MAX_D = 61; public int countSequences(lo…

TopCoder SRM 564 Div1 Medium: AlternateColors2

解法 SRM564 Div1 Medium "AlternateColors2" - WARushekaing.hatenablog.comこのページの別解がすごすぎた。 コード public class AlternateColors2 { public long countWays(int n, int k) { long ans = 0; for (int red = 1; red <= k; red++) { int notr…

TopCoder SRM 507 Div1 Medium: CubePacking

解法 SRM 507 Medium CubePacking - simezi_tanの日記d.hatena.ne.jp SRM 507 div1 med:CubePacking - mayoko’s diarymayokoex.hatenablog.com最低でもNs+Nb*L*L*Lは必要だが、L*L*Lを1列にNb個積み上げて、そこに1*1*1のNs個を出来るだけ平たく詰めば条件を…

TopCoder SRM 506 Div1 Medium: SlimeXGrandSlimeAuto

解法 SRM 506 div1 med:SlimeXGrandSlimeAuto - mayoko’s diarymayokoex.hatenablog.com街aから街bに移動する時、街cにある車を使うと、a->cを歩き、c->bを車で移動する。 コード import java.util.ArrayList; import java.util.Arrays; import java.util.Pr…

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…

TopCoder SRM 664 Div1 Easy: BearPlays

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

TopCoder SRM 663 Div1 Medium: ChangingChange

解法 SRM 663 div1 easy:ChangingChange - mayoko’s diarymayokoex.hatenablog.comD円を作る方法のうち、消えるものをDPして求めると、答えを導き出すことができるが時間がかかりすぎてしまう。 for (int q = 0; q < Q; q++) { int v = valueRemoved[q];// …

TopCoder SRM 663 Div1 Easy: ABBADiv1

解法 targetの文字列のうち、initialあるいはinitialの反転部分を見つけ、その前後のBの数が条件にあっているかどうか確かめる。1回以上Bによる反転操作がある場合、絶対に先頭にAは来ない(これで落ちた)。 コード public class ABBADiv1 { public String …

TCO15 Algorithm Round 2C Easy: YetAnotherCardGame

解法 dp(nターン目の時に)(山札の一番上にある数)の最大値を取るようにdpした。実は山札の一番上の数字さえ覚えておけば、一番上のカード以下のカードは出せないため、どのカードを出したかということを覚えておく必要はない。毎ターン「カードを出す」か「…

TopCoder SRM 662 Div1 Medium: ExactTree

解法 TopCoder SRM 662 Div1 Medium ExactTree - kmjp's blogkmjp.hatenablog.jp コード import java.util.Arrays; public class ExactTree { private final int INF = 1 << 25; public int getTree(int N, int MOD, int R) { // dp[n][r]:= 頂点数nの木で、…

TopCoder SRM 662 Div1 Easy: FoxesOfTheRoundTable

解法 高さでソートして、1番目を末尾、2番目を先頭、3番目を末尾、4番目を先頭、 ... とリストに挿入し、それを返せば良い。 コード import java.util.ArrayList; import java.util.Arrays; public class FoxesOfTheRoundTable { public int[] minimalDiffer…

TopCoder SRM 661 Div1 Easy: MissingLCM(素因数分解)

解法 ならばが成り立つ。が成り立つ時、Mを除いて、が成り立つのはどういう時かを考える。Mのある約数Pについて、Pの倍数がの中に含まれているにもかかわらず、の中にPの倍数が含まれていなかった場合、はPの倍数になるが、はPの倍数にならない場合があり、…

TopCoder SRM 659 Div1 Easy: ApplesAndOrangesEasy(貪欲法)

解法 前からフルーツを見ていって、そのフルーツからKの範囲内にリンゴがK/2個以内なら、そのフルーツをリンゴにしても良い。 コード public class ApplesAndOrangesEasy { public int maximumApples(int N, int K, int[] info) { boolean[] isApple = new b…

TopCoder SRM 631 Div1 Easy: TaroJiroGrid

解法 TopCoder SRM 631 Div1 Easy TaroJiroGrid - kmjp's blogkmjp.hatenablog.jp コード public class TaroJiroGrid { public int getNumber(String[] grid) { int N = grid.length; char[][] map = new char[N][]; for (int i = 0; i < map.length; i++) {…

TopCoder SRM 630 Div1 Easy: Egalitarianism3 (グラフ)

解法 ワーシャルフロイトで2点間の最短距離を出しておく。2点を選び、その2点を含む集合を求め、その最大値を返せば良い。 コード import java.util.ArrayList; public class Egalitarianism3 { public int maxCities(int n, int[] a, int[] b, int[] len) {…

TopCoder SRM 658 Div1 Easy: OddEvenTree (グラフ)

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

TopCoder SRM 633 Div1 Easy: PeriodicJumping (幾何)

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

TopCoder SRM 657 Div1 Medium: PolynomialGCD

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

TopCoder SRM 657 Div1 Easy: ProblemSets

解法 二分探索するだけ。(なぜかできなかった) コード 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

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

TopCoder SRM 635 Div1 Easy: SimilarRatingGraph

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

TopCoder SRM 640 Div1 Easy: ChristmasTreeDecoration

解法 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 (幾何)

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

TopCoder SRM 642 Div1 Easy: WaitingForBus (DP・期待値)

解法 動的計画法(渡す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 SRM 643 Div1 Easy: TheKingsFactorization (素因数分解)

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