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

SRM

TopCoder SRM 710 Div 1 Easy: ReverseMancala

解法 操作Aと操作Bは完全に対称な操作であることが分かる。操作Aをしまくって1箇所に集め、操作Bをしまくって復元すれば良い。 コード import java.util.ArrayList; import java.util.Collections; public class ReverseMancala { private int N; private Ar…

TopCoder SRM 702 Div1 Medium: RepeatedStrings

問題 "()" は良い文字列です。 S を良い文字列としたとき、"(SSS...S)" は良い文字列です。 文字列 S が与えられるので、文字列 S の部分列、かつ、良い文字列のうち、辞書順で k 番目の文字列を返してください。 解法 括弧列に対する様々な先入観から良い文…

TopCoder SRM 699 Div1 Easy: OthersXor

問題 N 匹の狼が 0〜2^30-1 の中の数字から 1 つずつ数字を選んでそれぞれ持っています。各狼は「黙秘する」か「自分以外の全ての狼の数字のXOR」かのどちらかを教えてくれます。教えてもらった情報から、全狼の数字の合計の最小値を求めてください。 解法 30…

TopCoder SRM 699 Div2 Hard: FromToDivisibleDiv2

問題 N 個の頂点があり、各頂点に 1 から N の番号が振られています。各 a[i] と b[i] について、 a[i] の倍数の全ての頂点から b[i] の倍数の全ての頂点へ距離 1 の有向辺を張ります。S から T への距離を求めてください。 解法 条件より 距離が 500 以上に…

TopCoder SRM 505 Div1 Medium: SetMultiples

問題 自然数の集合 S1 と S2 がある。S1 に含まれる全ての数について、その数の自然数倍の数が S2 に含まれるとき、S2 は S1 の multiple であるということにする。S に含まれる自然数 x は A素数はいくつか。 解法 まず A A = Math.max(A, B / 2 + 1); C = …

TopCoder SRM 505 Div1 Easy: RectangleArea

問題 ある大きさの長方形を水平方向に切って N 行に分割する。この時、各行の高さは必ずしも同じではない。次に垂直方向に切って M 列に分割する、この時、各列の幅は必ずしも同じではない。この操作によって、N 行 M 列の小さい長方形の集合になる。元の長…

TopCoder SRM 695 Div1 Medium: BearKRoads

解法 happy が最大となる辺の、大きい方の端は必ず選択される。 コード import java.util.ArrayList; public class BearKRoads { private int N; ArrayList<Integer>[] graph; int[] a, b; int dfs(int[] x, int k) { if (k == 0) return 0; ArrayList<int[]> ab = new Array</int[]></integer>…

TopCoder SRM 695 Div1 Easy: BearPasswordLexic

もうだめ コード import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; public class BearPasswordLexic { private String gen(int lenght, int isa) { String s = ""; for (int i = 0; i < lenght; i++) { if (isa % 2…

TopCoder SRM 693 Div1 Easy: BiconnectedDiv1

解法 最小費用流そのものやんけ!!!! コード import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; public class BiconnectedDiv1 { public int minimize(int[] w1, int[] w2) { int V =…

TopCoder SRM 692 Div1 Easy: OrderOfTheHats

解法 二分探索+全探索+BFS コード #include <bits/stdc++.h> using namespace std; class HardProof { int N; bool check(const vector<int> &D, int minCost, int maxCost) { vector<vector<bool>> g(N, vector<bool>(N, false)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { g[i</bool></vector<bool></int></bits/stdc++.h>…

TopCoder SRM 572 Div2 Hard: DistinctRemainders

解法 dp[sum][m] := m個の相異なる非負整数からなる合計がsumとなる増加数列の個数。 この並び方は m! 通りある。 さらにこの数列の上に blocks 個の M の倍数を積んでいく時、重複組合せより通りある。逆元から組み合わせを求めるテクを使うと大きい数字に…

TCO16 Round 1C Medium: ThreeProgrammers

解法 DP + 筋肉 コード #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; string dp[51][51][51][7], tmp[51][51][51][7]; const int AA = …</vector></typeinfo></sstream></set></iostream></fstream></ctime></cstring></cstdio></cmath></algorithm>

TopCoder SRM 588 Div2

Easy: KeyDungeonDiv2 #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; class KeyDungeonDiv2 { public: int countDoors(vector</vector></typeinfo></sstream></set></iostream></fstream></ctime></cstring></cstdio></cmath></algorithm>

TopCoder SRM 549 Div2 Hard: OrderOfTheHats

解法 NをYにするのは意味が無いので、YをNにすることだけ考える。各spellを覚えたかどうかをビットマスクで管理し、新しくスペルを覚えるのに潰さなければならないYの個数をコストとしてダイクストラする。 コード #include <bits/stdc++.h> using namespace std; typedef p</bits/stdc++.h>…

TopCoder SRM 573 Div2 Hard: WolfPackDivTwo

コード #include <algorithm> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace std; typedef long long ll; class WolfPackDivTwo { int dist…</vector></typeinfo></sstream></set></iostream></fstream></ctime></cstring></cstdio></cmath></cassert></algorithm>

TopCoder SRM 687 Div1 Medium: AllGraphCuts

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14214 解法 Gomory-Hu 木が作れることからGomory-Hu 木が作れることは明らか。 kyuridenamida先生のコードを写経した。 コード #include <bits/stdc++.h> using namespace std; struct UnionFind { vector<int></int></bits/stdc++.h>…

TopCoder SRM 687 Div1 Easy: AlmostFibonacciKnapsack

解法 当たりそうなところだけを持っていればおk コード #include <algorithm> #include <cassert> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <set> #include <sstream> #include <typeinfo> #include <vector> using namespace…</vector></typeinfo></sstream></set></map></iterator></iostream></fstream></ctime></cstring></cstdio></cmath></cassert></algorithm>

TopCoder SRM 681 Div1 Easy: FleetFunding

解法 n=50, m=100000, k=1000000 なので O(nm log(k)) が間に合う。2分探索 -> 貪欲はよく見る気がする。類題: D: 壊れた電車 - CODE FESTIVAL 2015 予選A | AtCoder コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #includ</set></algorithm></iostream></ctime></cstring></cmath></cstdio>…

TopCoder SRM 677 Div1 Medium: DiameterOfRandomTree

解法 すぎむさんのコードを参考にしました。木DP。 dp[u][x]:= 頂点uから生えるの最大の辺の長さがxとなる確率を保存しながらDFSして、作りうる辺の最大値がmax_lを超えないように計算していく。すると、確率の合計が「辺がmax_l以下になる確率」になる。こ…

TopCoder SRM 677 Div1 Easy: DoubleOrOneEasy

解法 全探索 コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> using namespace std; typedef long long ll; class DoubleOrOneEasy { public: int minimal…</fstream></typeinfo></sstream></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>

TopCoder SRM 576 Div1 Easy: ArcadeManao

解法 二分探索 + UnionFind コード #include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <typeinfo> #include <fstream> using namespace std; class UnionFind { public: UnionFind(const int &x) { …</fstream></typeinfo></sstream></vector></set></algorithm></iostream></ctime></cstring></cmath></cstdio>

TopCoder SRM 672 Div1 Easy: Procrastination

解法 n-200からn+200までの数の約数を全列挙して殴る。 コード import java.util.Arrays; import java.util.HashSet; public class Procrastination { public long findFinalAssignee(long n) { HashSet<Long> divisers = new HashSet<>(); long min = Math.max(2,</long>…

TopCoder SRM 546 Div1 Medium: FavouriteDigits

解法 上の桁から貪欲に埋めていく。できるだけ小さい数字を入れてみて、残りの数字が条件を満たす最大のものだった時にN以上になるなら大丈夫。 コード public class FavouriteDigits { public long findNext(long lN, int dSmall, int cSmall, int dBig, in…

TopCoder SRM 545 Div1 Medium: Spacetsk

コード public class Spacetsk { private final int MOD = (int) 1e9 + 7; public int countsets(int L, int H, int K) { if (K == 1) { return ((L + 1) * (H + 1)) % MOD; } // パスカルの三角形 int N = Math.max(Math.max(L + 2, H + 2), K + 2); int[][…

TopCoder SRM 671 Div1 Medium: BearDarts

解法 Med、a/b=c/dという変形は考えたのにそれを使って単に舐めるだけでシンプルに解く方法に至らなかったのは酷い・・・それにしてもみんな早く解きすぎじゃないですかね— SKY/sky58 (@skyaozora) 2015, 10月 14 コード import java.util.HashMap; public c…

TopCoder SRM 670 Div1 Medium: Treestrat

解法 ワーシャルフロイトで2点間の距離を出しておく。Aの各コマa_iについて、以下の操作によってゲームを終わらせるのに必要なターン数を出す。 必要なターン数movesを固定する。 a_i からmoves以内で行けて、かつ、Bの全ての駒がmoves以内で行けない頂点を…

TopCoder SRM 670 Div1 Easy: Bracket107

解法 1文字取り出して別のところに挿入するとLCSが最大の文字列が生成される。数は大して大きくないので、全探索でいける。 コード import java.util.HashSet; public class Bracket107 { public int yetanother(String s) { int N = s.length(); HashSet<String> an</string>…

TopCoder SRM 564 Div1 Medium: AlternateColors2

問題 TopCoder Statistics - Problem Statement コード public class AlternateColors2 { public long countWays(int n, int k) { long ans = 0; for (int red = 1; red <= k; red++) { int notred = k - red;// k番目の赤ボールが破壊される前に破壊される…

TopCoder SRM 555 Div1 Medium: XorBoard

問題 TopCoder Statistics - Problem Statement コード public class XorBoard { private final int MOD = 555555555; public int count(int H, int W, int Rcount, int Ccount, int S) { // パスカルの三角形 int N = Math.max(W, H) * 2; int[][] nCm = ne…

TopCoder SRM 574 Div1 Medium: PolygonTraversal

問題 TopCoder Statistics - Problem Statement 解法 bitDP。intersectするかどうかはfromとtoの間(内回りと外回り)にある点について訪問済みかどうか考えるだけで良い。 コード import java.util.Arrays; public class PolygonTraversal { private long[]…

TopCoder SRM 563 Div1 Medium: SpellCards

問題 TopCoder Statistics - Problem Statement 解法 配列が環状になっている区間のDP。「first枚目からcount枚の連続した区間の中からmustLeave枚取り除かなければならない場合の最高点」を考える。 コード Petrのコードを参考にした。 import java.util.Ar…

TopCoder SRM 544 Div1 Medium: FlipGame

問題 TopCoder Statistics - Problem Statement 解法 貪欲にやれば良い。 コード public class FlipGame { public int minOperations(String[] strings) { int N = strings.length; char[][] board = new char[N][]; for (int i = 0; i < N; i++) { board[i]…

TopCoder SRM 551 Div1 Medium: ColorfulWolves

問題 TopCoder Statistics - Problem Statement 解法 100問マラソンはプライドを捨てて AC/Open が高い簡単な問題から解いていくことにした。from->to の移動が可能な時、実際に移動するためには i i の経路を全て潰すことになるので、そのコストを辺 from->…

TopCoder SRM 669 Div1 Medium: LineMST

解法 sigma425.hatenablog.com kmjp.hatenablog.jp求めるべきMSTは一直線になっているので、ある区間がM未満になる場合を考えるとDPになる。 コード public class LineMST { private final long MOD = (long) 1e9 + 7; private long[][] dp; private int L; …

TopCoder SRM 541 Div1 Medium: AkariDaisukiDiv1

解法 最初のうちは愚直に繰り返すが、ある程度繰り返すと先頭と末尾で常に同じ文字列が生成されるようになるので、あとは足し算を繰り返していくだけで良い。 コード public class AkariDaisukiDiv1 { private final int MOD = 1000000007; public int count…

TopCoder SRM 539 Div1 Medium: SafeReturn

解法 kmjp.hatenablog.jpやることは、 ワーシャルフロイト + 二部グラフの最大マッチング(最大フロー)ワーシャルフロイトで2点間の距離を出しておくと、最短距離を通る時にその頂点を通過するか確認することが出来る。 for (int x = 0; x < N; x++) { for …

TopCoder SRM 538 Div1 Medium: TurtleSpy

解法 右回転と左回転の中から上手く組み合わせてできるだけ180度に近い角度を作る。最初にできるだけまっすぐ進み、次に180度に出来るだけ近くなるように回転し、そこから反対向きにまっすぐ進み、最後にその場で消費しきれていない回転コマンドを使いきれば…

TopCoder SRM 534 Div1 Medium: EllysNumbers

解法 そもそも、specialの中の整数を互いに素になるように組み合わせてnが作れるのかチェックする。出来るのであればbitDPするだけ。 コード import java.util.ArrayList; import java.util.Map; import java.util.TreeMap; public class EllysNumbers { pub…

TopCoder SRM 535 Div1 Medium: FoxAndBusiness

解法 topcoder.g.hatena.ne.jp絶対ナップザックだと思ったら二分探索だった。 コード import java.util.ArrayList; import java.util.Collections; public class FoxAndBusiness { public double minimumCost(int K, int W, int[] work, int[] cost) { int N…

TopCoder SRM 537 Div1 Medium: KingXMagicSpells

解法 各ビットについては独立に考えて動的計画法で解く。 コード public class KingXMagicSpells { public double expectedNumber(int[] ducks, int[] one, int[] two, int D) { int N = ducks.length; int[] from = new int[N]; for (int i = 0; i < N; i++…

TopCoder SRM 536 Div1 Medium: RollingDiceDivOne

解法 平均値付近に山が出来る。 コード import java.util.Arrays; public class RollingDiceDivOne { public long mostLikely(int[] dice) { Arrays.sort(dice); int N = dice.length; long low = 1, high = dice[N - 1]; for (int i = N - 2; i >= 0; i--) …

TopCoder SRM 533 Div1 Medium: MagicBoard

解法 各列・各行をそれぞれ1つの頂点とみなし,列->行->列->行->...というように全ての頂点を通ることができれば良い. 一筆書きできるかどうかはオイラー閉路の考え方で頂点の次数を調べれば良い. コード public class MagicBoard { boolean[][] graph; bo…

TopCoder SRM 667 Div1 Medium: CatsOnTheCircle

解法 mayokoex.hatenablog.com コード public class CatsOnTheCircle { public double getProb(int N, int K, int p) { if (p == 1e9 / 2) { return 1.0 / (N - 1); } if (p > 1e9 / 2) { K = N - K; p = (int) 1e9 - p; } double pd = p / 1e9; return turn…

TopCoder SRM 532 Div1 Medium: DengklekBuildingRoads

解法 bitDP tanzaku先生のコードを参考にした. コード public class DengklekBuildingRoads { private long MOD = (int) 1e9 + 7; private int K; private boolean[][][][] done; private long[][][][] dp; // nowを見た時に,残りedgeの辺が残っていて,st…

TopCoder SRM 668 Div1 Medium: WalkingToSchool

解法 そもそも0->1->0のルートが作れなければ無理である.ルートが作れる場合,シミュレーションによって 0->0 のルートの距離をリストアップする.この距離を組み合わせて1を作ることが出来れば,ある数以上で1刻みの距離を作ることができるので,それを調…

TopCoder SRM 531 Div1 Medium: MonsterFarm

コード import java.util.Arrays; public class MonsterFarm { private final int MOD = (int) 1e9 + 7; public int numMonsters(String[] transforms) { int N = transforms.length; int[][] edge = new int[N][N]; int[] out = new int[N]; for (int i = 0…

TopCoder SRM 530 Div1 Medium: GogoXMarisaKirisima

解法 まずは深さ優先探索でゴールする.1回のプレイで1回新しい行動をとるようにすれば,最大回数違う経路でプレイできる. コード public class GogoXMarisaKirisima { int N; private boolean[][] map; boolean[][] accessible; boolean visited[]; public…

TopCoder SRM 528 Div1 Medium: SPartition

解法 作られる文字列は種類のうち条件を満たすものだけなので大して種類はない. ある文字列maskを作る時,stringを前から見ていき,Xに入れられるか,あるいは,Yに入れられるかというのでdpを遷移させていけばいい. コード public class SPartition { pub…

TopCoder SRM 527 Div1 Medium: P8XMatrixRecovery

解法 辞書順最小なので,前の方から0を入れ,ダメなら1に変える,というふうに貪欲に決めていく.ある'?'を0にした時に矛盾がないかどうかは,その都度rowsの各列とcolumnsの各列が矛盾なくマッチングできるかどうかを調べる. 2部マッチングは最大流問題と…

TopCoder SRM 667 Div1 Easy: OrderOfOperations

解法 各bitを頂点,各bit間の遷移を辺としてダイクストラする. コード import java.util.Arrays; import java.util.PriorityQueue; public class OrderOfOperations { public int minTime(String[] s) { int N = s.length; int M = s[0].length(); int[] op…