線形代数と固有値問題 ひととおり線形代数を学んだ後によむといいかもしれない。できれば、関数解析をちょっとやった後で。スペクトル分解とかの所は結構細かいところまで乗ってるので便利。へぇ、こんな方法でとけるのか、と。でも説明丁寧かといわれるとそ…

単語 rank3::1~~4 --> http://d.hatena.ne.jp/kenta11626918/20111012/1318401749 rank2 --> http://d.hatena.ne.jp/kenta11626918/20111006/1317882668 rank1 -->http://d.hatena.ne.jp/kenta11626918/20111017/1318821771 C34CAFDF85FFCEB9929CD40BD14E730…

問題文の読み間違い。k-double stringsの個数を求める．0-strings ~ k-stringsまでの個数を求めるのではない． 問いの文はi-double stringsはk-double strings(i easy int howMuch(vector <string> str, int k) { string s; for(int i = 0, len = str.size(); i < le</string>…

easy //やるだけ． //きわめて簡単なコード { int len = s.length(); s += '0'; //番兵．a-zとはちがう要素なので、最後に必ず条件分岐が真になる． int div = 0; //sumはかならずszに等しい．ならば分割数だけを調べればいいじゃないか． for(int i = 0; i …

easy //やるだけ。 int findArea(int N) { int aplb = N/2; int a = (aplb&1) ? aplb/2+1 : aplb/2; int b = aplb-a; return a*b; } medium //3種類のゴールの仕方がある． //1:(jump+)walk_forward //2:jump+walk_backward //3:寄り道jump min(1, 2, 3) 三…

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

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…

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

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