SRM464 の成績・ソース (要ログイン) : AC/AC/TLE : とても教育的な感じのセット
550開く
- 550か。怖いなあ。
- 『N枚の正方形の紙を(xy軸に平行に)2次元平面におきます。i個目の紙は、中心を(xa[i],ya[i])か(xb[i],yb[i])のどっちかに置けます。N枚を互いに重ならないように置くとき、一番小さい紙の辺の長さを最大にするにはどうすればいいでしょう』
- 2≦N≦50
- 座標は 0 ～ 10億
- 重ならないように置けないときは 0 を返してね
- 置けるときは答えは自然数になることが証明できます
- テストケース作る
- 最小例: N=2の場合…
- {0,0},{0,0},{0,0},{0,0}。あー、これが「重ならないようには置けない」パターンか。なるほど。
- {0,0},{0,0},{1,1},{1,1}。じゃあ置けるパターンも入れとこう。
- 最大例: N=50の場合を適当に追加
- さて
- (xa,ya)と(xb,yb)の選び方と、各正方形のサイズと、可変なものが色々あってややこしいな
- 仮に、それぞれ(xa,ya)と(xb,yb)のどっちに置くかを固定したら、最大最小サイズはわかるだろうか。
- a,bへの割り振り方は2^50通りあるから全探索は無理だけど、まあとりあえず…
- ええと、(x,y)にあるサイズsの正方形と(X,Y)にあるサイズSの正方形が重ならないためには…
- abs(x-X) や abs(y-Y) よりも (s+S)/2 が小さくないといけない
- 違う、どっちか一方より小さければいいのか。x軸方向にすごい離れてたらy軸方向にどんな近くても構わない。
- max(abs(x-X), abs(y-Y)) ≧ (s+S)/2
- これを全ての正方形のサイズsに関して50変数の連立方程式として解を求め…
- min≧ならともかくmax≧とか入ってると普通の一次連立方程式になってなくないですか
- 解けんぞ
- しかも解けたとして、可能な解の中から最小値が最大のものを求めねば…線形計画…？
- そんなものは書きたくないぞ…
- うむむ。
- あ
- 正方形のサイズ s[0], s[1], ..., s[N-1] で重ならないとしたら
- サイズを小さくしても重ならないわけだから、最小値をms=min(s[0],...,s[N-1]) として
- 全部の正方形のサイズを揃えて ms,ms,ms,...,msとしても重ならないよね。
- しかもこの時最小値はさっきと同じms
- ということは、全部の正方形のサイズが同じ場合だけ考えればよい。
- するとさっきの式は
- になる。これを満たす最大値が解だ！
- これは 50C2 の組み合わせを全部試して max(abs(x-X), abs(y-Y)) の最小値をとるだけ。
- しかしこれは、「仮に、それぞれ(xa,ya)と(xb,yb)のどっちに置くかを固定したら」の場合だったので、2^50 回これを繰り返さねばいけない…無理…
- むう。
- この前wataさんが"最悪ケース最小化→二分探索！！！"と書いてらしたのを思い出す。
- 今回の問題も同じじゃないか？
- 「正方形のサイズ s で重ならないように（上手く(xa,ya),(xb,yb)を選ぶと）置けますか？」っていうのを二分探索していけば！
- s=0 なら絶対置ける。
- s=10億+1 なら絶対重なる
- ので、解は「L=0 ≦ s ＜ R=10億+1」の範囲に必ずある
- というところから初めて、s=(LとRの中央値)の時にうまく置けるかどうか判定して範囲を狭めていく。
int L=0, R=1000000001;
while( R-L>=2 )
{
int C = (L+R)/2;
(canPlace(C, xa, ya, xb, yb)?L:R) = C;
}
return L;
- こう。
- ところで二分探索のコードを書くときの気持ちなんですが、
- 自分は『「解は区間 {x | L≦x＜R} に存在する」（左が≦で右が＜！）という不変条件を壊さないようにひたすらループ回す』
- ということだけを念頭に置いて他の雑念はすべて忘れて書くようにしています。
- 「C が ok だったとき L と R のどっちを更新すればいいのか」とか
- 「整数で二分探索するとき最後に区間の幅が1で止まって0にならなかったりするけどそういうときLとRのどっちを返すのか」とか
- が、いや、すごく当たり前のことではあるんですけど、
- けっこう混乱してしまいがちなんですが、
- 「二・分・探・索」と考えずに「L≦x＜R」とだけ考えてるとなんだか混乱しにくい気がする
- 閑話休題
- しかしまだ問題は解けていない
- 今度は、正方形のサイズsが固定された状態で「正方形のサイズ s で重ならないように（上手く(xa,ya),(xb,yb)を選ぶと）置けますか？」というyes/no問題を解かねば。
- これは…
- さっきのmaxとabsの式を使うと、
- 「(xa[i],ya[i]) と (xb[j],yb[j]) を同時に使うとかさなっちゃう」
- みたいな制約が全ての i, j, a, b の組み合わせに対してわかる。
- あとは、この制約を満たすように選べるかどうか判定
- これは知識問題として解いてしまいました。
- まんま2-SATですね。
- さっきの制約をつかって、
- 「(xa[i],ya[i]) を選んだら (xb[j],yb[j])とは重なるので(xa[j],ya[j])の方を選ばなければいけない」
- みたいな条件から (xa[i],ya[i]) → (xa[j],ya[j]) というグラフのエッジを作ります。
- このグラフ上で (xa[i],ya[i]) → (略) → (xb[i],yb[i])
- と、最初の選択の逆に戻ってくるループのようなものがあると、
- 「(xa[i],ya[i]) を選んだら (xb[i],yb[i]) を選ばなきゃいけない」という矛盾が起きるので(xa[i],ya[i])を選べないことがわかる
- さらに (xb[i],yb[i]) → (略) → (xa[i],ya[i]) というループのようなものがあると、同じように(xb[i],yb[i])も選べない。
- というわけで、こういう両方向にループのようなものがあると、i番目の紙はどうにも選べないので、これは無理とわかる。noを返す。
- 逆に、こういうループが一個もなければ、さっきの矛盾になってない方を全部選んで置いていけば置ける。yesを返す。
- というわけでできた。二分探索 + 2-SAT。
- サンプル通った。submit。
- 二分探索でなくても、ギリギリサイズの正方形の取り方って50C2*4通りしかないから、この回数2-SATでもよかったかもしれない。
- けどまあlog 10億で終わる二分探索の方が速い
250開く
- 部屋のスコア表を見ると、軒並み200点数前後とみなさま苦戦している。結構難しいのか
- 『10進表記された数字がカラフルであるとは、"連続する桁の数字の掛算"が全部異なること。263は例えば、2,6,3,2*6,6*3,2*6*3が全部違うのでカラフル。n桁の数で辞書順にk番目のカラフルな数を求めてね』
- テストケース作成
- n=1,k=1: 最小ケース
- n=50,k=10億: 最大ケース
- ちょっと待て
- n=50ってそんなに長いの作れるかな？
- 桁の数字って10通りしかないわけだから、11桁あるとどっかはかぶる
- ということはそこのみの掛け算は必ず同じ値
- つまりカラフルでない
- n=10,k=10億 を最大ケースにしよう
- つまり、10桁しかなくて全部違う数字なわけだから、
- 10! 通り "0123456789" の next_permutation を求めて、カラフルかどうか判定して順番に数えればいいんじゃ。
- カラフル判定ってどのくらいで書けるかな。
- ナイーブにやって、始点終点の選び方O(n^2)でその区間の全部掛け算でO(n)、合計O(n^3)。
- おっと、O(n^3 n!) はn=10にはちょっと厳しいぞ
- あと、n＜10 のとき、"0123456789" からn個取り出した順列の列挙しなきゃいけないんだけど
- どうすれば楽に書けるか。
- まあ "0123456789" を next_permutation して上n桁見ればいいか。n=10のケースが通ればこれも通るはずだからタイムは問題ない。
- あー
- 0と何かが並んでいると掛け算も0になる。
- てことは、0単独と、0x の掛け算は等しいから、0があって2桁以上だとカラフルではない
- n≧2 なら "123456789" のpermutationだけ考えればいい
- 10倍の高速化！
- まだ遅い
- あー
- 1と何かxが並んでいると掛け算もxになる。
- てことは2桁以上だと1も使えない
- n≧2 なら "23456789" のpermutationだけ考えればいい
- 9倍の高速化！
- 最悪ケース n=8, k=10億 通った！
- submit!
1000開く
- 『迷路にA-Gの7種類のトラップが仕掛けられてて、それぞれダメージ食らう確率が設定されてます。２回ダメージ食らうと死にます。生きてゴールにたどりつける確率を最大化してね』
- ※ サンプル読まずに、複数 A があったとき、それぞれ独立にダメージ食らう確率があると勘違い
- ※ 実際は、あるAがトラップでなかったら他のAも全部そうでない、みたいな条件
- おお？
- なんかわりと簡単じゃないだろうか。
- 各マスについて「0回ダメージで行ける確率、1回ダメージで行ける確率」を最大にするように歩けば
- 普通のダイクストラで求まる気がする。
- sampleの説明読む。
- おお
- 「あるAがトラップでなかったら他のAも全部そうでない、トラップだったら他も全部そう」
- なのか！
- ひいー勘違いしてた。時間ない！
First, go left one cell, and then down one cell into the 'A'. One of two things might happen with equal probability:
- You get damaged. This means all cells with color 'A' are dangerous, so you should go back and try going through the 'B' zone instead (which might also be dangerous).
- You do not get damaged. This means all cells with color 'A' are safe, so you can continue through the 'A' zone and get to the exit.
The probability of reaching the exit is 0.5 * 0.6 (the first case) + 0.5 (the second case) = 0.8. The probability is the same if you try 'B' first.
- これ、ここに書いてあるのをそのまま実装すればいいんじゃない？
- 「スタートからいけるトラップマスに行ってみる、そこがトラップだった場合とそうでなかった場合にわけて再帰的に探索、答えを確率で重みづけて足し算」
- 7個しかトラップの種類ないから、7!通りの踏む順序 * 2500セルの到達可能性検査
- 5040*2500……いける……かな？？？？いやでも時間ないしこれしかない
- 書いた
- sample通った！
- submitしちゃえー！
撃墜タイム
- 1000は、でもやっぱり5040*2500は無理だろうなあ…とドキドキしてたら結局撃墜されてなんか安心
- 250は、「1桁の場合も0と1を使わない」というミスがあり得ることをまったく予測していなかった。出遅れた…。
- ひとつ、if(a.size()<k){...}else{...a[k]...} みたいなコードを見つけたので撃墜</li>
提出したバージョンはTLEなだけでなく間違ってたけど、多少の修正で直せたみたい。タイムはとりあえず「THE・GORIOSHI」で通した。
class ColorfulMaze { public:
double getProbability(vector <string> maze, vector <int> trap)
{
return solve(maze, trap, 0);
}
typedef int vert;
double solve(const vector<string>& maze, const vector<int>& trap, int damage)
{
const int H = maze.size();
const int W = maze[0].size();
vector<vert> R[7];
{
stack<vert> Q;
vector<bool> V(H*W);
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
if( maze[y][x] == '$' )
{Q.push(y*W+x); V[y*W+x]=1;}
while( !Q.empty() ) {
vert v=Q.top(); Q.pop();
int y=v/W, x=v%W;
int dy[]={-1,+1,0,0}, dx[]={0,0,-1,+1};
for(int i=0; i<4; ++i) {
int yy=y+dy[i], xx=x+dx[i],u=yy*W+xx;
if( 0<=yy && yy<H && 0<=xx && xx<W && maze[yy][xx]!='#' && !V[u] ) {
if( maze[yy][xx]=='!' )
return 1.0;
V[u]=1;
if( maze[yy][xx] == '.' )
Q.push(u);
else
R[maze[yy][xx]-'A'].push_back(u);
}
}
}
}
double pMax = 0.0;
for(int k=0; k<7; ++k) if(!R[k].empty()) {
double p = 0;
vector<string> m = maze;
{
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
if(maze[y][x]=='A'+k) m[y][x] = '.';
else if(maze[y][x]=='$') m[y][x] = ".#"[damage];
for(int i=0; i<R[k].size(); ++i)
m[R[k][i]/W][R[k][i]%W] = '$';
p = (1-trap[k]/100.0) * solve(m, trap, damage);
}
if( damage == 0 ) {
for(int y=0; y<H; ++y)
for(int x=0; x<W; ++x)
if(maze[y][x]=='A'+k && m[y][x]!='$') m[y][x] = '#';
p += (trap[k]/100.0) * solve(m, trap, damage+1);
}
pMax = max(pMax, p);
}
return pMax;
}
};
- サーバで1.9secくらい。トラップ床を踏む順番7!通りを全部試す感じで。
- 想定解はなんかこれメモ化するのかなあと思ったのだけど、7! も 3^7 (踏んでない/踏んで罠だった/罠じゃなかった、の3通りずつ)もそこまで大差ないよなー。ううむ
cafelier2010/03/17 23:17tsukunoさんのアドバイスを参考にdamage==0の時だけ2^7をキーにメモ化してみたら900msecになった。
