通信範囲を１づつ大きくしながらメモ化再帰。 #include <algorithm> #include <vector> using namespace std; class ConnectTheCities { public: int n,dist,range; vector<int> pos; int cache[105][55]; int rec(int bP,int k) { //printf("bP=%d k=%d\n",bP,k); int &r=cache[bP][</int></vector></algorithm>…

問題概要 あるデバイスに送らななければならないデータがその始まりのアドレスと大きさの形で渡される。 データはパケットに分けて送らなければならない。 そのパケットはメインデータとオーバーヘッド部分から成る。 このとき送らなければならない最小のバ…

問題要約 ーーーーーーーーーーーー n人の人が円形に並んでいて、 時計回りの順にボールを任意の他の人に向かって投げる。 ボールがあたった人は円から離脱し、 番号iの人が投げたボールが当たる確率はprobably[i]である。 この時円形に並んでいる人が１人に…

k乗和の公式を使う。 求め方は数学Bの教科書に載っている。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <climits> using namespace std; typedef long long LL; static const LL MOD=10000000…</climits></map></set></cmath></cstring></cstdio></sstream></iostream></vector></string></algorithm>

なにそれオイシーの？

使うギターを全探索するだけ。 #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>

二部探索＋ダイクストラ。 #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>…

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

ステージ１： ４番を爆破したとする。すると１番も開けることができる。 このような連鎖関係で箱を分ける。 このグループの数が爆弾の数より少ないならすべての箱を開けることができる。 そのようになる箱の分け方の場合の数を求めて(箱の数)!で割ればいい。…

rec(直前の色、直前の色は何個続いたか、Aの個数、Bの個数、Cの個数)をメモ化再帰。 場所は全体の長さ-(Aの個数+Bの個数+Cの個数)で求められる。 #include <algorithm> #include <vector> using namespace std; int cache[3][4][50+10][50+10][50+10]; class BoxesArrangement {</vector></algorithm>…

解説見ました。 Login - TopCoder Wiki class PuyoPuyo { public: int theCount(int L, int N) { memset(DP,0,sizeof(DP)); DP[0][0]=1; for(int i=0;i

無理やり感が否めない。基本的にシンボルとパターンを総当りでぶつけていく。 でも、どの電球が生きているのかはパターンすべての中で一回でもついたことのある電球だけ。 パターンiとシンボルjをぶつけるときに、 パターン[i][k]=='1' && シンボル[j][k]=='…

cache[y][x][何個訪れた][最後に訪れた番号]でメモ化再帰。 #include <cstring> #include <vector> #include <cstdio> using namespace std; int field[60][60]; int cache[60][60][60][60]; class CountPaths { public: int rec(int y,int x,int v,int l) { if(y<1 || x<1 || v<0) re</cstdio></vector></cstring>…

めんどくさい。 #include <queue> #include <string> #include <vector> using namespace std; class FixImage { public: int h,w; int image[60][60]; int color() { for(int i=0;i</vector></string></queue>