使うギターを全探索するだけ。 #include <algorithm> #include <string> #include <vector> #include <set> using namespace std; class GuitarConcert { public: vector<string> comp(vector<string> vs1,vector<string> vs2) { if(vs1.size()==vs2.size()) return (vs1</string></string></string></set></vector></string></algorithm>

分からなかった。 ビットを使って部分集合を求めると結構速いらしい。 このDPの計算量はそれぞれのビットについて (mask:0,sub:0),(mask:1,sub:0),(mask:1,sub:1) の場合があるので3^nなんだって。 2^n*2^nしか思いつかなかった。 #include <vector> using namespace</vector>…

凸な図形＝三角形の集まりなので rec(どの座標を使ったか(=mask)、今どの座標か(=k))は kを含む三角形を(i,j,k)の面積をsとすると s+rec(maskにi,j,kを追加した物,k+1) の内最小化のものを返せば良い。あとはそれをメモ化再帰して終わり。 三角形の面積を求…

最大値の最小化なのでセオリー通りに二分探索。 #include <algorithm> #include <string> #include <vector> #include <sstream> using namespace std; class LogCutter { public: int n; vector<int> canCut; bool check(int L,int C,int mid) { int beforeCut=0; while(mid</int></sstream></vector></string></algorithm>

#include <algorithm> #include <vector> #include <cstdio> #include <cstring> #include <climits> using namespace std; typedef long long LL; int n; LL k; int range[55][55][2][2]; LL cache[55][55][2]; class ContiguousCache { public: LL intersect(int a1,int a2,int b1,int b2) { if(a1<=b1 &</climits></cstring></cstdio></vector></algorithm>…

メモ化再帰。 難しくて解説みた。 #include <string> #include <vector> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL DP[(1<<13)][2][15][15]; class PalindromePhrases { public: int n; vector<string> words; bool isPalindome(string s) { for(int i=0;i</string></cstring></cstdio></vector></string>

満点で予選通過した。 Round1は中間テストの真っ最中だけど、頑張って出るかもしれない。

二部探索＋ダイクストラ。 #include <algorithm> #include <string> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; typedef long long LL; int n; LL limit; LL INF=((LL)1<<LL(50)); LL visited[500]; vector<int> F[500]; vector<int> T[500]; vector<int> P[500]; vector<int> D[…</int></int></int></ll(50));></utility></queue></sstream></vector></string></algorithm>

二部探索＋２SATらしい。 #include <vector> #include <cstdio> #include <cstring> using namespace std; class ColorfulDecoration { public: int n; int len; int dist[110][110]; int G[110][110]; int ABS(int n) { return (n<0)?-n:n; } bool check() { memset(G,0,sizeof(G)); </cstring></cstdio></vector>…

眠い！ どの行とどの列をひっくり返したかと位置を状態としてBFS。 #include <string> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; int mv[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; int dist[(1<<15)][10][10]; class TurningMaze { public: bool can</utility></queue></sstream></vector></string>…

貪欲でOK。 #include <string> #include <vector> using namespace std; class StringInterspersal { public: string minimum(vector <string> W) { string ans; int n=W.size(); int s=0; for(int i=0;i<n;i++) s+=W[i].size(); vector<int> used(n,0); while(ans.size()</n;i++)></string></vector></string>

calc(n)をn以下のjumpyNumを求める関数とする 答えはcalc(high)-calc(low-1) ーーーーーーーーーーーーcalc(n)の説明ーーーーーーーーーーーー 数字を文字列にして考える n=123456789のとき m=12345....なら、mはnにpos=4(0-indexed)までマッチしているとい…

二つの列に一箇所でも共通点があれば片方でしか分かっていない情報も分かるようななる。 行についても同様。 #include <string> #include <vector> using namespace std; class RectangleArea { public: int h,w; vector<string> vs; void check() { for(int i=0;i</string></vector></string>

OXX 1457→1590

自転車で亀岡まで行った。 保津川下りっていうイベント(？)をやっていた。

解けなっかた人が解説しても仕方がないのでぐぐればいいと思うよ。 全探索。 #include <vector> using namespace std; class DrawingLines { public: double countLineCrossings(int n, vector <int> startDot, vector <int> endDot) { vector<int> ceil(n,-1); int m=startDot.size</int></int></int></vector>…

全部一箇所に集めればいい。 マンハッタン距離ではxとyは分離できるので 集める場所のx座標の候補は初期位置のx座標 集める場所のy座標の候補は初期位置のy座標 で全探索。 #include <limits.h> using namespace std; class TournamentPlan { public: int ABS(int n) {</limits.h>…

TopCoder Statistics ↑のテキトー日本語訳 最終的にグラフはそれぞれに一つずつmarkedを含む部分グラフに分けられる。 markedな頂点A,B(AとBの間には他のmarkedな頂点はない)を考える。 AとBを分けるときに使う辺はAとBの間で最もコストの小さい辺である。 #…

map,得点>でメモ化再帰。 どちらの番かという情報は”どの頂点が残っている”から得ることができる。 #include <map> #include <vector> #include <float.h> #include <cmath> using namespace std; int n; double point[(1<<13)]; map<int,double> cache; int popCount(int _mask) { int r=0; for(int i</int,double></cmath></float.h></vector></map>…

一番高いビルから入れていく。 一番左に入れると左から見えるビルが一つ増える。 一番右に入れると右から見えるビルが一つ増える。 それ以外の場所に入れても見えるビルは増えない。 #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL cac</cstring></cstdio>…

何個のサイコロがvを出すかの組み合わせで分ける #include <algorithm> using namespace std; double cache[2500+10][50+10]; class Conditional { public: int v; int maxSide; double C[55][55]; double rec(int sum,int nD) { if(sum<=0) return 1.0; else if(nD==0)</algorithm>…

分からへんかった。 class MagicalSpheres { public: int count(int n,int p) { int r=0; while(n>1) { r+=n/p; n/=p; } return r; } bool check(int s,int f,int g) { for(int i=2;1