問題文の読み間違い。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 実はこのコードは間違い。-100 int countProbablePlaces(vector <int> X, vector <int> Y, vector <int> R) { int sz = X.size(); int cnt = 0; for(int i = -100; i <= 100; i++) { for(int j = -100; j <= 100; j++) { bool flag = true; for(int k = 0; k < sz; k++</int></int></int>…

確率 有限個の事象A1,A2, · · · ,An のとき， 一般加法定理 三角関数 から加法定理の公式が簡単に求めることができる。。 逆三角関数 (複素数変換) 和積、積和の公式 極限 微分 n次導関数のライプニッツの公式 テイラー定理 を満たす c が開区間 (a, x) 内に…

medium できなかった。時間かかり過ぎ． 端的に言うと、条件を満たす３点をとってその最小の長さをとるというもの． 距離順にソートしてからだと(0, 0) (0, 1)(1, 0)(0, 2) みたいになってしまいうまくいかない． double getArrangement(string leftRow, str…

自由に選択できるというのと、無作為に選ばれるというのでは全く違う． 自由に選択できるということは、戦略をもって最前の手で選択肢を選べるということ．

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);み…

多い間違い 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 //だけ増えればそれが最…