問題 読解問題は無理なので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 - 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; } // パスカルの三角…

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

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

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

解法 動的計画法（メモ化再帰）するだけ。（独力で解けたのでメッチャ嬉しい） コード 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…

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

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

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

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

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

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

解法 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個を出来るだけ平たく詰めば条件を…

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

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

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

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

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

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

解法 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の木で、…

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

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

解法 前からフルーツを見ていって、そのフルーツから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 - 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++) {…

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