SRM461 の成績・ソース (要ログイン) : AC/-/- : 泥酔SRM
500開く
- 『二次元平面上に都市がN≦50個あります。ユークリッド距離がmaxDist以下の都市は往き来できます。1番の都市からN番目の都市までmaxTrav以下の距離で行けるように都市を増やすとき、増やす数を最小にしてね。無理なら-1。』
- コーナーケース考えるの面倒だし、ソーステンプレのテストデータ埋める欄などはコメントアウトだ！
- とりあえず、いくらでも都市は置ける（整数座標じゃなくてもよいので本当にいくらでも置ける）ので、始点終点のユークリッド距離がmaxTrav以下なら中継都市を置きまくればいけるし、それ以外なら行けない
- というif文を書く
- ユークリッド距離はhypotという関数があるはずなのだけど、いつものように距離を返すのだったか距離の2乗を返すのだったか思い出せないので調べるのが面倒になって手書きする
- ※こういうの本当やめよう…
- さて
- とりあえず何も都市を増やさず行けるかどうか確かめるコード書くか。
- 普通に最短路。
- 50都市だからウォーシャルフロイドの３重ループで十分間に合う！
- 書けた。
- で？
- 0個増やしで行けるかどうかは、この結果で始点と終点の距離≦maxTravかどうかでわかる。
- 1個増やしていけるかどうかは？
- WFで
- d[i][j] = min(d[i][j], d[i][k]+d[k][j])
- と更新する代わりに
- d[i][j][1] = min(d[i][j][1], d[i][k][0]+d[k][j][1], d[i][k][1]+d[k][j][0])
- すれば良いのではないか。1個増やしで行ける = どっかで左右に割って、片側が1個増やしで片側が0個増やし。
- 初期状態は
- d[i][j][s] = iとjのユークリッド距離がmaxDist*(s+1)以内ならそれ、そうでなければ∞。
- で。
- 2個増やしとかも同様に。
- これ計算量幾つだろう。
- 最大何個増やす必要があるか。
- maxDist, maxTravともに 1～2000 らしい。
- ということは、各都市間を2000回中割する可能性があるから、
- 最悪、edge数×2000？
- いや、都市の座標も2000くらいの範囲しかこないらしい
- でも最悪2000個要るケースは作れるな。
- で、dp[i][j][2000]を求めるための分割は2000通り考えるから…
- 2000×2000×50^3 のオーダ
- 無理だ。どう考えても無理だ
- ううむ。
- 逆に考えよう。
- edge毎に、そこを直線で行くには何個の中継都市が必要か？が独立に決まるので
- ユークリッド距離を使うのじゃなくて、この「何個必要か？」を重みにしたグラフとか考えるとどうだろう
- iとjの距離がDだったら、floor(D/maxDist) を距離としたグラフ
- これの最短パスは
- 始点から終点にたどりつけるために必要な最低限の都市の個数になる！
- これか！？
- いや、でも「maxTrav以内で到達しないといけない」って条件は、いったいどこで考慮すればいいの…
- ううーむ。
- うわー残り30分しかない
- Lv1が300点ということは難しそうだから、ここらで300に向かわないと0点になってしまうかもしれない。
- 500は離脱。無念。
300開く
- 『（15分にらめっこしても問題の意味がよくわからない…）』
- とりあえず、コーナーケース考えるの面倒だし、ソーステンプレのテストデータ埋める欄とかコメントアウトだ！
- 問題文は、他の方のログで書かれてた 1e-5 の部分は単に「精度がきわどいケースは来ないよ」という保証だろーと見てそもそも精読する気すらなく気にならなかったのですが、
- 自分の英語力だと、左に置いたdiskを、右に置いたdiskが「完全に」カバーしなきゃいけないようにしか読めなかった…
- しかしサンプルの１個目は別にそんなことはない
- サンプルの２個目以降は絵がないからよくわからない
- わっからん。
- わからないが最初のサンプルの絵を見るに、
- すぐ左のdiskとちょっとでも重なれば問題ないっぽい？
- 『赤のdiskと青のdiskがそれぞれ何枚かづつ与えられます。width*heightの四角形の、height/2のところの中心線に中心を合わせてdiskを置いていって、四角形をカバーするには最低何枚必要か。ただし赤と青は交互に並べること』
- でいいのかな。
- もう知らんこれで書いちゃえ。
- height/2より半径が小さいdiskは使う意味がないのでフィルタ
- 大きいdiskからgreedyに使えばいいので、逆順にソート
- あとは
- 赤、青、赤、青…の順で使っていって何個目でwidth覆えるか計算
- 青、赤、青、赤…の順で使っていって何個目でwidth覆えるか計算
- 小さい方を答える
- サンプル全部通った
- もうこれでいいや。
- これでいいなら200点でもおかしくない難易度な気がするけど…
500に戻る
- おい
- 始点も終点も固定されているのに、なんで僕はWarshal-Floydしているんだろう
- これは全点間最短路ではないのか。なぜ単一始点最短路では駄目なのか
- さっきの1つづ中継都市を増やしていくアルゴリズム、Dijkstraの拡張で作れば計算量間に合ったり…
- ええと、「s都市増やして都市iに辿り着く最短路」というのを求めればいいから
- 2000*50頂点のDijkstra。10万
- 辺の数は？それぞれの都市から、行ける都市は50個までで、それぞれ何都市増やせば行けるかは一意に決まるから、
- 50*10万 = 500万の辺
- これは行ける
- しかし時間がなかった！
撃墜フェーズ
- あ、int height; を整数の 2 で割っている人がいる
- これは double で演算しないとおかしいはず。
- heightが奇数の場合とそれを偶数に切り捨てた場合で結果が違うようなデータは…
- 6:8:10が直角三角形だから、12*16の四角形を半径10のdiskで覆うのはできるけど
- 13*16を半径10で覆うのはできないはず
- でもheight/2してると12/2も13/2も同じになってしまって間違える
- これだ
- 二人撃墜
感想
- 飲み会の最中にSRM 3時間前を迎えたので、登録だけしておこう…と思ってarenaを開こうとするも、パスワードを何回打っても通らないのでこれは俺はダメだ…と思って、直前に酔いが醒めてたらもう登録しようと思って放置
- と思って次に目が覚めたときにはSRM開始時間
- しまった間に合わなかった…観戦とかできたっけ…
- arena起動。お、一発でパスワード通った。俺凄い。
- あれ？普通にEnterできるし部屋にassignされてるぞ？
- いつのまに…？？？？？？
- しかもredの人が少ない部屋だ。なにか参加しないともったいない気がする。
- Go!
- という酷い状態で始めたのですが、終わってみれば普通の成績でした。
- まあこんなもんでしょう。
- しかし500はもったいないことをした気がする…
Dijkstraで。
class BuildingCities { public:
int findMinimumCities(int maxDirect, int maxTravel, vector <int> cityX, vector <int> cityY)
{
int result = 0x7fffffff;
const int N = cityX.size();
typedef pair<int, int> vert;
typedef pair<double, vert> cedge;
set<vert> V;
priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
Q.push( cedge(0, vert(0,0)) );
while( !Q.empty() )
{
double d = Q.top().first;
vert v = Q.top().second;
int vc = v.first;
int vs = v.second;
Q.pop();
if( V.count(v) )
continue;
V.insert(v);
if( vc==N-1 )
result = min(result, vs);
for(int j=0; j<N; ++j) if( vc != j )
{
double dd = hypot( cityX[vc] -cityX[j], cityY[vc] -cityY[j] );
double dx = hypot( cityX[N-1]-cityX[j], cityY[N-1]-cityY[j] );
vert u(j, vs+int(dd/maxDirect - 1e-10));
if( d+dd+dx<=maxTravel && u.second<result && !V.count(u) )
Q.push( cedge(d+dd, u) );
}
}
return result==0x7fffffff ? -1 : result;
}
};
これ想定解なのかな。変な枝刈り入れないとTLEだったのがイマイチ美しくないので、もっと自然に探索を打ち切れる条件があるような気がするんだけども。
