//ふつうに、0~100000000でループしてたらおそらく間に合わない． //なので、123 4 321みたいになるはずだから、 //m = ss.str(); reverse(m.begin(), m.end() ); と仕込みしておいて、 // string tmp = (i != 10) ? (ss.str() + c + m) : (ss.str() + m);み…

多い間違い are を aに間違える 逆も然り t --> l p --> b とかの変化。 アクセントの位置を把握し切れていないので、違う意味の単語と捉えてしまう． e.g)metropolis あいまい母音はuとか聞こえるので、何の単語か勘違いしてしまう。 rely //r[u]ly 助動詞…

TopCoderではときどき頭混乱させるような木のデータが与えられるので、まとめ。 //consider to be i = 0-based {-1, 0, 0, 2, 2, 4, 4} //i = 3ばんめの2は、2番目に親があるよってことを示してる． int start = 0; for(int i = 0; i < sz; i++) { if(heap[i…

easy 簡単すぎて申し訳ない． string getMessage(string text) { string ans = ""; istringstream iss(text); string tmp; while(iss >> tmp) { ans += tmp[0]; } return ans; } medium 問題把握に時間かかり過ぎ． int fewestClicks(string messages, int l…

easy, mediumは簡単なので、割愛。 //n <= 500000なので、再帰関数は使えない。 //なんか拍子抜けだけど、普通に描く。 1 2 3 4 5 (k = 3) 1 3 5 --> 1 2 3 (k = 2) 1 2 3 (k = 2) //と同値。 class KidsGame { public: int kthKid(int n, int m, int k) { i…

TopCoderではvector一辺倒でなにかと使わないlistですが、カードシャッフル等の操作をするときとかはかなり便利です． explicit list( size_type 長さ, const T& 値 = T() ); //イテレータでの初期化ももちろん可能． list& operator=(const list& c2); bool…

easy //計算量を下げるなら、vector<pii>とかで格納しておくのがよい。普通にやると、4じゅうるーぷとかなった、 int dissatisfaction(vector <string> farmland) { int row = farmland.size(); int col = farmland[0].length(); vector<pii> dots; for(int i = 0; i < row; i+</pii></string></pii>…

easy こんがらがるな。以上．良くありそうな問題です． int maxCycle(vector <int> board) { int sz = board.size(); int maxi = 0; for(int i = 0; i < sz; i++) { bool used[sz]; memset(used, false, sizeof used); int npos = i; while(1) { if(used[npos]) {</int>…

ぶちゃいくコードや．死にたい．boost使いたい． set unitcube; とか構造使っても、ヒープのほうで大小の区別ができないので、別のデータ構造を使った方が良い． //がんばって最適化しようと思えば。 int getVolume(vector <string> parallelepipeds) { set<vector<int> > unitCu</vector<int></string>…

全く同じ領域を二度もflipさせることはなさそうだ、ということに気付けば、どん欲法でやっていけば良さそうということが分かる．flipする順序は関係ないので、[0, 0]から順番にtraverseしていけばよさそう． っていうのがぱって浮かんだらな〜。複雑そうだっ…

変則的な動的計画法の問題．問題の趣向から、iを逆順に回して最大値を簡単に取得できるようにしている． また、j++とすることで、暗に数字を複数回使ってよいことを表している． もし、 for(int j = n; j >= matches[i]; j--) { ... } としてみると、数字は…

とりあえず、２点が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 みたいにする。 あとは与えられた数を当てはめていくだけ． あるいは、…

聞けなかったところを聞き取れるようにするというより、どうして聞き取れなかったか、何か理由があるはずだから、それを探って次にいかす． Section1 1: will of the //of theが意味のある単語に聞こえる willがうぅるとかにきこえる 2:can assure you//きゃ…

再帰、メモ再帰、動的計画法とは？ 有名な？？階乗計算を例に取る。 //純粋な再帰。同じ引数を持つ関数を何度も何度も呼び出している。→むだやん。 #include <iostream> #include <cstdio> using namespace std; int fib(int n) { if(n<=1) return n; return fib(n-1)+ fib(n-2</cstdio></iostream>…

#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 …

\documentclass{jarticle} \begin{document} //ここに処理を書く \end{document} $~~$の$は入れないっぽい。 \begin{eqnarray} \Delta y=\frac{1}{1-b} \end{eqnarray} $\delta$ \begin{eqnarray} y=\frac{1}{1-b} \end{eqnarray} //これではエラーになる。 …

大したことない問題だけど。 //気分的に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…