SRM413 div2
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]) { break; } else { used[npos] = true; } npos = board[npos] -1; } maxi = max(count(used, used+sz, true), maxi); } return maxi; }
medium
この程度の問題で3重ループは罪悪感を覚える．
int maxElements(vector <string> words) { int sz = words.size(); for(int i = 0; i < sz; i++) { for(int j = 1; j <= words[i].length(); j++) { string sub = words[i].substr(0, j); for(int k = 0; k < sz; k++) { if(sub == words[k] && i != k) { words[k] = 'X'; } } } } return sz - count(words.begin(), words.end(), "X" ); }
なので、最初にsortして仕込みましょう．
int maxElements(vector <string> words) { int sz = words.size(); sort(words.begin(), words.end() ); for(int i = 0; i < sz; i++) { for(int j = i+1; j < sz; j++) { //実は、words[j].substr(0, 100)とかでもout_of_rangeしないのだ!! if(words[j].substr(0, words[i].length()) == words[i]) { words[i] = 'X'; } } } return sz - count(words.begin(), words.end(), "X" ); }
difficult グラフ問題。
やっぱりダイクストラちゃんとやらないと。
この点を通らないと、先にいけないっていう条件があるけど、どうすればいいか。 とりあえず、条件として、 condでこの点いかないと先にいけないよ 的な変数を格納してみた。 あと、A->B->C->Aみたいなわっかができてしまった場合どうするかでいろいろまよった。 わっかがあるときは絶対に全部のプロセス終わらないじゃん。 隣接リストで書いたので、コード汚い。 良く考えれば、わざわざ隣接リストで書きなおさなくても 直接与えられた2次元配列で処理すればいいかもしれないな。
int minTime(vector <int> time, vector <string> prec) { int sz = time.size(); vector<int> order[sz]; vector<int> cond[sz]; //you have to be finish the task list. vector<int> begin; for(int i = 0; i < sz; i++) { bool indep = true; for(int j = 0; j < sz; j++) { if(prec[i][j] == 'Y') { order[j].push_back(i); indep = false; cond[i].push_back(j); } } if(indep) begin.push_back(i); } int cost[sz]; memset(cost, -1, sizeof cost); priority_queue<pii, vector<pii>, greater<pii> > Q; for(int i = 0; i < begin.size(); i++) { int p = begin[i]; cost[p] = time[p]; Q.push(pii(cost[p], p) ); } while(!Q.empty() ) { pii tmp = Q.top(); Q.pop(); int cur = tmp.first; int pos = tmp.second; bool flag = true; for(int i = 0; i < cond[pos].size(); i++) { if(cost[ cond[pos][i] ] == -1) { flag = false; break; } } if(flag) { vector<int> to = order[pos]; for(int i = 0; i < to.size(); i++) { int n = to[i]; if(cost[n] == -1 || cost[n] < time[n]+cur) { cost[n] = max(cost[n], time[n]+cur); Q.push(pii(cost[n], n)); } } } //end if } //end while int ans = 0; for(int i = 0; i < sz; i++) { ans = max(ans, cost[i]); if(cost[i] == -1) { return -1; } } return ans; }
配列をそのまま用いて。
class ParallelProgramming { public: int minTime(vector <int> time, vector <string> prec) { int sz = time.size(); //pii(time, index) priority_queue<pii, vector<pii>, greater<pii> > Q; int cost[sz]; memset(cost, -1, sizeof cost); //create trigger for(int i = 0; i < sz; i++) { bool flag = true; for(int j = 0; j < sz; j++ ) { if(prec[i][j] == 'Y') { flag = false; break; } } if(flag) { cost[i] = time[i]; Q.push( pii(cost[i], i) ); } } //traverse while( !Q.empty() ) { pii info = Q.top(); Q.pop(); //※ bool flag = true; for(int i = 0; i < sz; i++) { if(prec[info.Y][i] == 'Y' && cost[i] == -1) { flag = false; } } if(flag) { for(int i = 0; i < sz; i++) { if(prec[i][info.Y] == 'Y' && cost[i] < info.X + time[i]) { cost[i] = info.X + time[i]; Q.push( pii(cost[i], i) ); } } } //end if } //end while return (count(cost, cost+sz, -1)) ? -1 : (*max_element(cost, cost+sz) ); }
※はcontinue;で打った方がいいかもね。 for(int i = 0; i < sz; i++) { if(prec[info.Y][i] == 'Y' && cost[i] == -1) { continue; } }
良く考えたら、priority_queue使うのは、memo[v] < p.Xのとき （つまり、最初から値が変更される可能性がないとき） スキップできるから、使うのであって、 今回の場合は、最小の経路を通るとは限らず、むしろ遅れた人を待つ形式なので スキップできないよね。だったら普通のQueueで良さそうな気がする。 ちょっとまてよ。priority_queue使う意味はあるかも知んない。 NYNN NNYN YNNY NNNN こういうときは？ 3->(2-0-1-2) で-1になるはず。 とかんがえると、やっぱり、priority_queueを使わなくていいのかも。 rity
//cost[i]の初期値をINFに変更 //traverse while( !Q.empty() ) { pii info = Q.top(); Q.pop(); //一度通った個所でコストが高い時は更新されることはないので、スルー if(cost[info.Y] < info.X) continue; //この個所はいらないんじゃないか。 for(int i = 0; i < sz; i++) { if(prec[info.Y][i] == 'Y' && cost[i] == INF) { continue; } } for(int i = 0; i < sz; i++) { //ここも変更 if(prec[i][info.Y] == 'Y' && (cost[i] < info.X + time[i] || cost[i] == INF) ) { cost[i] = info.X + time[i]; Q.push( pii(cost[i], i) ); } } //end if } //end while return (count(cost, cost+sz, INF)) ? -1 : (*max_element(cost, cost+sz) ); }
だいぶ洗練されました。
#define X first #define Y second #define INF (1<<30) using namespace std; typedef pair<int, int> pii; class ParallelProgramming { public: int minTime(vector <int> time, vector <string> prec) { int sz = time.size(); //pii(time, index) priority_queue<pii, vector<pii>, greater<pii> > Q; int cost[sz]; fill(cost, cost+sz, INF); //create trigger for(int i = 0; i < sz; i++) { if(count(prec[i].begin(), prec[i].end(), 'Y') != 0) continue; cost[i] = time[i]; Q.push( pii(cost[i], i) ); } //traverse while( !Q.empty() ) { pii info = Q.top(); Q.pop(); if(cost[info.Y] < info.X) continue; bool flag = true; //やっぱりここは必要。 for(int i = 0; i < sz; i++) { if(prec[info.Y][i] == 'Y' && cost[i] == INF) flag = false; } if(!flag) continue; for(int i = 0; i < sz; i++) { if(prec[i][info.Y] == 'Y' && (cost[i] < info.X + time[i] || cost[i] == INF) ) { cost[i] = info.X + time[i]; Q.push( pii(cost[i], i) ); } } } //end while return (count(cost, cost+sz, INF)) ? -1 : (*max_element(cost, cost+sz) ); } };
//indegを付け加えた。InDegree[g, n] 有向グラフ g の頂点 n の入次数 int minTime(vector <int> time, vector <string> prec) { int sz = time.size(); queue<int> Q; int cost[sz]; int indeg[sz]; fill(cost, cost+sz, 0); fill(indeg, indeg+sz, 0); //create trigger for(int i = 0; i < sz; i++) { if((indeg[i]=count(prec[i].begin(), prec[i].end(), 'Y')) != 0) continue; Q.push(i); } //traverse while( !Q.empty() ) { int cur = Q.front(); Q.pop(); cost[cur] += time[cur]; for(int i = 0; i < sz; i++) { if(prec[i][info.Y] == 'Y' && cost[i] < cost[cur]) { cost[i] = info.X + time[i]; if(!indeg[i]) { Q.push(i); indeg[i]--; } } } } //end while return (count(cost, cost+sz, INF)) ? -1 : (*max_element(cost, cost+sz) ); }
