SRM
解法 操作Aと操作Bは完全に対称な操作であることが分かる。操作Aをしまくって1箇所に集め、操作Bをしまくって復元すれば良い。 コード import java.util.ArrayList; import java.util.Collections; public class ReverseMancala { private int N; private Ar…
問題 "()" は良い文字列です。 S を良い文字列としたとき、"(SSS...S)" は良い文字列です。 文字列 S が与えられるので、文字列 S の部分列、かつ、良い文字列のうち、辞書順で k 番目の文字列を返してください。 解法 括弧列に対する様々な先入観から良い文…
問題 N 匹の狼が 0〜2^30-1 の中の数字から 1 つずつ数字を選んでそれぞれ持っています。各狼は「黙秘する」か「自分以外の全ての狼の数字のXOR」かのどちらかを教えてくれます。教えてもらった情報から、全狼の数字の合計の最小値を求めてください。 解法 30…
問題 N 個の頂点があり、各頂点に 1 から N の番号が振られています。各 a[i] と b[i] について、 a[i] の倍数の全ての頂点から b[i] の倍数の全ての頂点へ距離 1 の有向辺を張ります。S から T への距離を求めてください。 解法 条件より 距離が 500 以上に…
問題 自然数の集合 S1 と S2 がある。S1 に含まれる全ての数について、その数の自然数倍の数が S2 に含まれるとき、S2 は S1 の multiple であるということにする。S に含まれる自然数 x は A素数はいくつか。 解法 まず A A = Math.max(A, B / 2 + 1); C = …
問題 ある大きさの長方形を水平方向に切って N 行に分割する。この時、各行の高さは必ずしも同じではない。次に垂直方向に切って M 列に分割する、この時、各列の幅は必ずしも同じではない。この操作によって、N 行 M 列の小さい長方形の集合になる。元の長…
解法 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>…
もうだめ コード 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…
解法 最小費用流そのものやんけ!!!! コード 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 =…
解法 二分探索+全探索+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>…
解法 dp[sum][m] := m個の相異なる非負整数からなる合計がsumとなる増加数列の個数。 この並び方は m! 通りある。 さらにこの数列の上に blocks 個の M の倍数を積んでいく時、重複組合せより通りある。逆元から組み合わせを求めるテクを使うと大きい数字に…
解法 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>
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>
解法 NをYにするのは意味が無いので、YをNにすることだけ考える。各spellを覚えたかどうかをビットマスクで管理し、新しくスペルを覚えるのに潰さなければならないYの個数をコストとしてダイクストラする。 コード #include <bits/stdc++.h> using namespace std; typedef p</bits/stdc++.h>…
コード #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>
問題 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>…
解法 当たりそうなところだけを持っていればお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>
解法 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>…
解法 すぎむさんのコードを参考にしました。木DP。 dp[u][x]:= 頂点uから生えるの最大の辺の長さがxとなる確率を保存しながらDFSして、作りうる辺の最大値がmax_lを超えないように計算していく。すると、確率の合計が「辺がmax_l以下になる確率」になる。こ…
解法 全探索 コード #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>
解法 二分探索 + 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>
解法 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>…
解法 上の桁から貪欲に埋めていく。できるだけ小さい数字を入れてみて、残りの数字が条件を満たす最大のものだった時にN以上になるなら大丈夫。 コード public class FavouriteDigits { public long findNext(long lN, int dSmall, int cSmall, int dBig, in…
コード 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[][…
解法 Med、a/b=c/dという変形は考えたのにそれを使って単に舐めるだけでシンプルに解く方法に至らなかったのは酷い・・・それにしてもみんな早く解きすぎじゃないですかね— SKY/sky58 (@skyaozora) 2015, 10月 14 コード import java.util.HashMap; public c…
解法 ワーシャルフロイトで2点間の距離を出しておく。Aの各コマa_iについて、以下の操作によってゲームを終わらせるのに必要なターン数を出す。 必要なターン数movesを固定する。 a_i からmoves以内で行けて、かつ、Bの全ての駒がmoves以内で行けない頂点を…
解法 1文字取り出して別のところに挿入するとLCSが最大の文字列が生成される。数は大して大きくないので、全探索でいける。 コード import java.util.HashSet; public class Bracket107 { public int yetanother(String s) { int N = s.length(); HashSet<String> an</string>…
問題 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 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 Statistics - Problem Statement 解法 bitDP。intersectするかどうかはfromとtoの間(内回りと外回り)にある点について訪問済みかどうか考えるだけで良い。 コード import java.util.Arrays; public class PolygonTraversal { private long[]…