//はじめに再帰で解いた． 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>…

まぁ、簡単だけど、一応．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>…

0 --> 0, 1 1 --> 2 2 --> 0, 1 みたいになっている場合、Kの深さになったときのすべての場合の数を求める． //ちなみに重複は認める．自分自身がはいっていても問題ない． #include <iostream> #include <vector> using namespace std; const int sz = 3; const int K = 4; in</vector></iostream>…

TIMESが4になっているので、無駄はあるが、殆ど速度に影響しないと思う． string whatHappens(vector <string> commands) { const int TIMES = 4; //right rotate int step[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; int x = 0; int y = 0; int dir = 0; for(i</string>…

まえできなかった臭いので。 int feedMost(vector <int> hunger, vector <int> greed, int totalFood) { int sz = hunger.size(); for(int i = sz; i >= 1; i--) { vector<int> eat(sz, 0); for(int j = 0; j < sz; j++) { eat[j] = hunger[j] + greed[j]* (i-1); } sort(ea</int></int></int>…

新しく習うべきことはなし． vector determineWebsite(vector address, vector keyword, vector dangerous, int threshold) { int sz = address.size(); set word; for(int i = 0, len = dangerous.size(); i vector res; bool flag[sz]; memset(flag, false…

printfとか、sprintfとかをがんばって駆使していく問題．まぁさ、anticipationで別に制限加えなくても、計算量的には余裕だけど、ループ大幅に減らせるからさ． string findFraction(int maxDen, string number) { double dicimal; sscanf(number.c_str(), "…

100 -->4*5*5みたいにdigitを細小にする問題．実は簡単で、 int cnt = 0; for(int i = 9; i >= 2; i++) { while(n % i == 0) { cnt++; n /= i; } //いちいち素因数分解して、ということはやらなくていいのだ．

貪欲法& 文字列操作 int findMax(int n, int K) { //1~9までは数字が1個しかないので、returnする． if(n < 10) return -1; stringstream ss; ss << n; string number = ss.str(); int sz = number.length(); //9000とかは swapむり。 if(number.substr(1) =…

friends[i][j]--friends[j][k] ---> i -->kは友達になり、数が一つ増える．

int count(vector S, int K) { int sz = S.size(); int order[sz]; for(int i = 0; i strmap; int res = 0; do { string str = ""; for(int i = 0; i string rotate = str + str; int len = str.length(); for(int i = 0; i ポイントはrotateするときに、二…

cnt["0001"] = 2; cnt["0010"] = 3; みたいに、集積． int mostLit(vector <string> initial, int K) { map<string, int> cnt; for(int i = 0; i < initial.size(); ++i) { cnt[initial[i]]++; } int res = 0; map<string, int>::iterator it; for(it = cnt.begin(); it != cnt.end(); it++) { </string,></string,></string>…

物理の重力計る問題。 ここでのポイントは、角度の求め方(atan2)と二分法 double gravitationalAcceleration(vector x, vector y, int T) { int sz = x.size(); vector angle(sz-1, 0); vector distance(sz-1, 0); for(int i = 1; i atan2(y[i-1]-y[i], x[i]…

とりあえずどうなるのかを列挙してみる。 00000 - 00001 - 00011 00010 - 00110 00100 00101 00111 - 01111 01000 01001 たとえば、n = 5, k = 11のときどうなるか調べたいときは、 10001 --> 00001 --> 00000とたどっていけば良さげだということが分かる。 …

立方体を展開すると、 RBRRBRRBR BGBBGBBGB RBRRBRRBR みたいになる。最初の出発点を(0, 0)とすると、 BRR BRR GBB になる。これが基本形．このタイルの繰り返し．最終的にstandしている座標がわかれば、どの色かが分かる． それをふまえて． string finalPo…

多角形の成立条件は三角形のやつを拡張したものでOK! a+b vector gl_seg; int sz; LL sumplus(int cur, int sum, int cnt) { LL ans = 0; if(cnt == 0) { for(int i = cur; i ans += sumplus(cur+1, sum+gl_seg[cur], cnt-1); ans += sumplus(cur+1, sum, cn…

2~100000までの範囲． 100000 = pow(100*√10, 2) 素数をしらべればよい。 素因数分解すると、 2^17 > 100000になるので、個数はせいぜい17個． set getprime(int num) { set prime; //ans set::iterator it; for(int i = 2; i prime = getprime(up); set::it…

交差点を何回曲がったかを答える問題． class MazeWanderingEasy { public: int decisions(vector maze) { int row = maze.size(); int col = maze[0].length(); pii start, goal; //search start and goal point for(int i = 0; i Q; int dir[4][2] ={ {-1,…

もう発想勝負な問題。頭柔らかくね。 1 2 3 4 5 6 7 8 9 10 -->1 3 5 7 9::25 1 2 3 4 5 -->1 3 5 ::9 1 2 -->1 ::1 1 -->1 ::1 //ということで再帰で終わり。奇数の和が二乗になることさえ分かれば解ける。 //というか、再帰使う必要性すら感じない。分かっ…

計算機は小数点とか扱うの苦手なので、あまり÷(/)を使わない． できるだけ×をつかうと、int型のみで済む．doubleに変換しなくても良くなる． とくに、座標計算とか、角度もとめるとかはもろにそうで、 int x, y; ならば、 arg = atan2(y, x) とかとやるより…

SRM458 div2 medium ボールを衝突させるとき、 for(int i = 0; i

SRM453.5 div2 medium int longestPath(vector maze, int startRow, int startCol, vector moveRow, vector moveCol) { int row = maze.size(); int col = maze[0].length(); int step[row][col]; //初期化 for(int i = 0; i > que; step[startRow][startCol…