JOI2013春合宿day3 山岳救助隊
問題
日本語なので本文参照(http://imoz.jp/data/joi/2013-sp-d3-mountain.pdf)
マップから、高さがxであるような点を求める。
マップのそれぞれのマスの高さは異なる。
山の頂点のマスがある。
マップのそれぞれのマスから、頂点から遠くなるほうの隣接するマスは、必ず高さが低い。
制約条件
マップの広さは200x200
マスの高さを調べられる回数は1000回まで。
方針
解説スライドに賢い方法が載ってた。
(http://japl.pl/slides/joi/mountain_rescue_team.pdf)
自分は、適当に頂点から4方向に二分探索して、ゴールの高さに近いマスを4つ求め、
そこから、ゴールとの差分をペナルティとしてダイクストラした。
こんな感じの嘘解法でも通ってしまった。
ソースコード
bool v[1010][1010]; int dp[1010][1010], cnt; int ty, tx, goal; priority_queue<pi> q; int get(int y, int x){ int &res = dp[y][x]; if(res > 0) return res; if(++cnt > 1000){ while(1); Pinpoint(y + 1, x + 1); } res = Measure(y + 1, x + 1); if(res == goal) Pinpoint(y + 1, x + 1); return res; } void push(int y, int x){ if(!v[y][x]) q.push(mp(-abs(goal - get(y, x)), y * 1000 + x)); } void Rescue(int h, int w, int ty, int tx, int goal){ ty--; tx--; ::goal = goal; ::ty = ty; ::tx = tx; int lo = tx, hi = w, mid; while(lo + 1 < hi){ mid = (lo + hi) / 2; if(get(ty, mid) >= goal) lo = mid; else hi = mid; } push(ty, lo); lo = ty, hi = h, mid; while(lo + 1 < hi){ mid = (lo + hi) / 2; if(get(mid, tx) >= goal) lo = mid; else hi = mid; } push(lo, tx); lo = 0, hi = tx + 1, mid; while(lo + 1 < hi){ mid = (lo + hi) / 2; assert(0 <= mid && mid < w); if(get(ty, mid) < goal) lo = mid; else hi = mid; } push(ty, lo); lo = 0, hi = ty + 1, mid; while(lo + 1 < hi){ mid = (lo + hi) / 2; assert(0 <= mid && mid < h); if(get(mid, tx) < goal) lo = mid; else hi = mid; } push(lo, tx); while(!q.empty()){ int y = q.top().second / 1000, x = q.top().second % 1000; q.pop(); if(v[y][x]) continue; v[y][x] = 1; if(get(y, x) == goal){ Pinpoint(y + 1, x + 1); } rep(d, 4){ const int dy[] = {-1, 0, 1, 0}, dx[] = {0, -1, 0, 1}; int ny = y + dy[d], nx = x + dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue; if(v[ny][nx]) continue; if((get(y, x) > goal) == (abs(ny - ty) + abs(nx - tx) < abs(y - ty) + abs(x - tx))) continue; q.push(mp(-abs(goal - get(ny, nx)), ny * 1000 + nx)); } } while(1); rep(i, h) rep(j, w) if(!v[i][j]) Pinpoint(i + 1, j + 1); }