とりあえず、２点がA,BがLにたいして線対称のときの条件としては、 ABの中点CがL上にある。 ABとLが直行する。 一番目の条件から、直線を導き、２番目が成り立てば、求めたい直線が得られるというわけ。 注意したいこと。 C(0, 0)になるとき -->AorBを90度回…

1 4 9 16 25 で正方形が増えていくけど、K=15とか14では一段目さえもまともに組み立てられない。 とりあえず、それに注意する。後は裏面の面積もたすこととか。こんがらなければ簡単に解ける問題。 じぶんはこんがらがってたｗｗ class PyramidOfCubes { pub…

わりとむずい。 わかれば、あぁ、そういうことか、となる。 604 10200 なら、 lo:6 60 604 hi:1 10 102 1020 10200みたいにしたあと、 適当な処理をして、 lo:6 60 604 hi:10 102 10200 みたいにする。 あとは与えられた数を当てはめていくだけ． あるいは、…

#define TR_MAX 50 class TreasuresPacking { private: typedef struct _things { int weight; int cost; bool flex; } Things; public: double maximizeCost(vector treasures, int W) { int sz = treasures.size(); vector tr(sz); for(int i = 0; i flex …

実践では1000000のときの数が分からないので、MAX = 5200000とかいうことはできないと思ってもよい。 #define MAX 12924368 //これを超えたらbad_allocがでた。最大値でも1.90sくらいで間に合う。 int preprime[MAX] = {0}; //エラトステネスを改良。 class …

大したことない問題だけど。 //気分的にmapを使いました。多分こうする方が計算量をがくっと落とせる。 int leastAmount(vector <int> left, vector <int> right) { int sz = left.size(); map<int, int> table; for(int i = 0; i < sz; i++) { table[left[i] ]++; table[ right[</int,></int></int>…

貪欲法で解けそうだけど、 oldText:aaaa newText:abacacaaaa とかのときはだめになる． //貪欲法:4 a[b]a[c]a[c]a[aaa] 本当の答え:1 a[bacacacaa]aaa 典型的な動的計画法。 int minDist(vector oldText, vector newText) { string oldT = ""; string newT =…

headにもtailにも移動できる時． a: 8 12 25 7 15 19 sorted :7 8 12 15 19 25 動かす回数を少なくしたいわけだから、どうしても動かさなければならない数字をカウントする． たとえば、aの部分列[12 15 19]は既にソートされているので、8, 12, 7を動かさな…

難しそうだが分かれば簡単。 要するに、ある一点を動かす時、面積最大にするには、その１点Bの両隣の点A,Cの線分と直角に動けばいいことになる。今回は最大の面積だけを問題にしているので、 (点Bが動ける最大量1)*(線分ACの長さ)/2 //だけ増えればそれが最…

座標変換でこんがらがる string getPosition(int N) { int dir[4][2] = { {0, -1}, {-1, 0}, {0, 1}, {1, 0} }; int index = ((int)sqrt(N)-1)/2; int num = (index*2+1)*(index*2+1); int start = index+1; int x = start; int y = start; for(int i = 0; i…

とりあえずキューで実装してみたが、2s以内ではできない． int countOperations(int N, int M) { int flag[M+1]; memset(flag, -1, sizeof flag); queue Q; Q.push(N); flag[N] = 0; while( !Q.empty() ) { int n = Q.front(); Q.pop(); if(n > M) continue;…

mapを使うと効率がよい。 あとは、placeboardを変形してそのままreturnにしたいので、あまり関係のない処理はしたくない。例えば、John-PBとかになったときに、-をどうして処理するかとか。 >||-|| そこで部分文字列を使ってみた。 class XBallGame { public…

string getMinProgram(vector actions) { string instr = ""; map bar; //まとめて格納． char tabC[5] = "N-/|"; char tabR[5] = "SLFR"; for(int i = 0; i instr += tabR[diff]; } instr = '.' + instr; string ans = ""; cout = 1; i--) { if(instr[i] ==…

再帰 double expected(vector cards) { char rank[6] = "AKQJT"; rem = 52; //Init for(int i = 2; i = '2' && ch = 21) return prob*cnt; for(int i = 2; i table[i]--; rem--; ans += go(cnt+1, newsum, prob*(cardnum*1.0/(rem+1) ) ); table[i]++; rem++…

nが奇数のとき、 1 2 3 4 5 2 4 1 3 5 (1+1)%5 4 3 2 1 5 (2+2)%5 3 1 4 2 5 (4+4)%5 1 2 3 4 5 (3+8)%5 nが偶数のとき 1 2 3 4 2 4 1 3 4 3 2 1 3 1 4 2 1 2 3 4 奇数と偶数で状況が変わることが分かる。2のべき乗とかは関係しない。 一応、m class TheCard…

こーどが余りきれいではないけれど、とりあえず、誤差に注意する． X*X = a*a + b*bのとき、 aの値がわかれば、 b = sqrt(X*X - b*b)でわかる。 #define INF (1 << 30) #define eps (1e-9) #define X first #define Y second using namespace std; typedef p…

二次元座標を簡潔に書くのによさそう．コンストラクタ public member function complex (const T& re = T(), const T& im = T()); complex (const complex& cmplx); template complex (const complex& cmplx); // complex first (2.0,2.0); http://na-inet.j…

1234 1234 1234 136974 みたいに足していく．これらは11とか、111とかで割り切れると気づいたら簡単．

for使わなくても解ける． 80 84 88 88 = 8 * 11; 66 = 6 * 11; //なので、88-2*t = nが0<=t<=11で成り立つ時ans = 11になる。 |< >| int minCartons(int n) { int pack = n/8; if(n%8 == 0) return pack; if( n%2 == 0 && (pack+1)*6 <= n) return pack+1; r…

//はじめに再帰で解いた． int TheBasketballDivOne::go(int num, int rem) { int cnt = 0; if(rem = 0; i--) { m_upper = i; cnt += go(num-1, rem-i); } m_upper = prev; return cnt; } できた(キリッ とか思ってたけど、 3)では、 (6, 3, 2, 1) (6, 4, 2,…

E000 1000 1000 1000 のとき、 1 0 0 0 0 1 1 1 >1/(1+1+1) = 0.33333 double getProbability(vector <string> landings, int startLanding, int K) { int sz = landings.size(); double dp[K+1][sz]; //dp[cnt][the-number-of-landings] memset(dp, 0, sizeof dp); </string>…

なんか迷路っぽい問題なので、深さ優先検索すれば良さげな感じだが、下の場合とかになるばあい、実装面でかなり難しくなる．どういう条件で曲がるかが不明瞭で、やたらめったら曲がると、n = 50のとき耐えられなくなってしまう． 000000000 0...0.0.0 0...0.…

はじめてまともに、動的計画法組めたような気がした。 めちゃくちゃ時間かかったけど。 今回メモするのは、 dp[入力したい文字の数+1][辞書順の順番] = 移動距離 2500*2500くらいなので、一応なんとかなるはず。 vectorは取り扱いがめんどくさくなるので、st…

ダイクストラ法を使って．とりあえず、最短経路を探ってみる．今回の問題は２番目に近い最短経路を求めれば良い． int messenger(int n, vector <string> highways) { Node node[n+1]; /*-----Input------*/ for(int i = 0; i < n+1; i++) { node[i].done = false; n</string>…

[1.2 1.3 1.5 1.8 2.1 2.9]とかのとき、 priority_queue, greater > que; ...でやればいいかなとおもったけど、それだと、[1.5 1.5 1.6 .1.7] -->9,9となる。 原因は、 3.3 * 3.0 = 9.9; //priority_queue (1.5+1.5)*(1.6+1.7) 3.2 * 3.1 = 9.92; //この違い…

mapの使い方。 int numPairs(vector <int> numbers) { map<int, int> cnt; for(int i = 0, sz = numbers.size(); i < sz; i++) { stringstream ss; ss << numbers[i]; string str = ss.str(); sort(str.begin(), str.end()); int num; sscanf(str.c_str(), "%d", &num); cnt</int,></int>…

#define ALL(x) (x).begin(), (x),end() #define SZ(x) *1 cout #include #include #include #include #include #include #include #include #include #include #include #define INF (1 pii; typedef pair dot; typedef long long LL; class DonutsOnTheGri…

まぁ、簡単だけど、一応．accumulateは別にSTLとかじゃなくても使えるよ． int calculate(int k, int n) { int dp[k+1][n+1]; for(int i = 0; i < n+1; i++) { dp[0][i] = i; } for(int i = 1; i < k+1; i++) { for(int j = 0; j < n+1; j++) { dp[i][j] = a…

div2 mediumにしてはかなり骨のある問題． {"", "", "", "", ..} -->{"223", "223", "334", ...}に変換してやるのが一番簡単かな． string message(vector part, vector dict, vector keystr) { char ch[26]; for(int i = 0; i //create table lexicographic…

この問題はn, mがおおきいので、可能な場合の数から削っていく方針でやればいいわけですが． long long find(int n, int m, vector <int> row, vector <int> seat) { if(m == 1) return 0; int sz = row.size(); vector<pii> dot(sz); for(int i = 0; i < sz; i++) { dot[i]</pii></int></int>…