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