2009-09-05
Jumper
SRM 158, Div1, Div1 Level-3, Search, Algorithm Tutorials, cheated, 30% |
How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。
一番上までいくのに何ステップかかるか。BFSで解ける。問題を理解するのに1時間。そして、解法が浮かばなくてEditorialを見ながら解くのに2時間ぐらいかかった。
304.01/1000 (cheated)
struct State { int x, y, t; State() {} State(const int x, const int y, const int t) : x(x), y(y), t(t) {} }; bool operator< (const State& a, const State& b) { if (a.t < b.t) { return true; } else if (a.t > b.t) { return false; } else { if (a.y > b.y) { return true; } else if (a.y < b.y) { return false; } else { return a.x < b.x; } } } class Jumper { public: int minTime(vector <string> patterns, vector <int> speeds, string rows) { const int HEIGHT = rows.size()+1; const int WIDTH = 20; vector<string> grid(HEIGHT+1); grid[0] = grid[HEIGHT] = string(WIDTH, '#'); for (int i = 0; i < rows.size(); i++) for (int j = 0; j < 4; j++) grid[i+1] += patterns[rows[i]-'0']; queue<State> Q; Q.push(State(0,0,0)); set<State> checked; while (!Q.empty()) { State s = Q.front(); Q.pop(); if (s.t > 2100) break; if (s.y >= HEIGHT) return s.t; const static int MOVE_KINDS = 5; const static int d[MOVE_KINDS][2] = { {0,0},{1,0},{-1,0},{0,1},{0,-1} }; for (int i = 0; i < MOVE_KINDS; i++) { const int dx = s.x + d[i][0]; const int dy = s.y + d[i][1]; if (0<=dx&&dx<WIDTH && 0<=dy) { int offset = (dy==0||dy==HEIGHT) ? 0 : (((-s.t*speeds[rows[dy-1]-'0'])%5)+5)%5; if (grid[dy][(dx+offset)%WIDTH] == '#') { const int ddx = dx + ((dy==0||dy==HEIGHT)? 0 : speeds[rows[dy-1]-'0']); if (0<=ddx && ddx<WIDTH) { State next(ddx, dy, s.t+1); if (checked.find(next) == checked.end()) { checked.insert(next); Q.push(next); } } } } } } return -1; } };
2009-08-15
HillHike
SRM 145, Div1, Div1 Level-3, Dynamic Programming, cheated, 45% |
採りえる山の形の数を求める。問題は理解できたが、解法が全然思いつかなかった。
470.68/1000
class HillHike { public: long long numPaths(int distance, int maxHeight, vector <int> landmarks) { long long memory[2][52][51]; memset(memory, 0, sizeof(memory)); memory[0][0][0] = 1; landmarks.push_back(-1); for (int i = 1; i < distance; i++) { long long cache[2][52][51]; memset(cache, 0, sizeof(memory)); for (int h = 1; h <= maxHeight; h++) { int mh = (h == maxHeight) ? 1 : 0; for (int j = 0; j < landmarks.size(); j++) for (int d = -1; d <= 1; d++) { int lm = (h == landmarks[j]) ? j+1 : j; cache[mh][h][lm] += memory[0][h+d][j]; cache[ 1][h][lm] += memory[1][h+d][j]; } } memcpy(memory, cache, sizeof(memory)); } return memory[1][1][landmarks.size()-1]; } };
Trevon2011/07/22 14:31What a joy to find such clear thikinng. Thanks for posting!
jknzrlrno2011/07/22 23:00AjjYSE <a href="http://ixlymfbzzugw.com/">ixlymfbzzugw</a>
yvzbbd2011/07/23 22:15ye8QTD , [url=http://uxgtugxylomn.com/]uxgtugxylomn[/url], [link=http://kqcpcalkwsod.com/]kqcpcalkwsod[/link], http://qqpqjszskcfr.com/
zjjbnlaeddz2011/07/24 22:34EkvlNg <a href="http://ziovfuvshgpt.com/">ziovfuvshgpt</a>
kredwos2011/07/26 01:32v3mrNH , [url=http://zmgqozacpuiq.com/]zmgqozacpuiq[/url], [link=http://vvwzqzdemmen.com/]vvwzqzdemmen[/link], http://hmhrbmsipkkf.com/
Camilo2012/11/16 17:32It's wondeurfl to have you on our side, haha!
amnquhs2012/11/16 22:35OOQfVh <a href="http://wykjstupxxmy.com/">wykjstupxxmy</a>