2009-12-23
SRM456 Hard: FunctionalEquation
寝る前にちょっと考えた
- f(x)=ax+b な形だとa=1,b=(C-1)/2になってしまってCが偶数のときにf(x)がintegerにならなくてアウト
- f(x)=ax^2 + bx + c な形だとa=0で結局同上
- f(x)=Σa_ix^i で考えると... 寝落ち
SRM456 Medium: CutSticks
- なんか最初単峰性の何かを想像してて、どこで最大になるか求めようとしていた
- 既存の棒の長さを順番に試していって、どこまで行けるか（というか求める値がどことどこの間か）という問題に脳内修正
- ということは要は任意の値でどこまで行けるか、に脳内修正
- ま、二分探索さ。最初から分かっていたさｗ
- どこまで「何が」行けるかの計算に悩んでてごにょごにょしてるうちに時間切れ
- Challenge Phase無視
- Practice room
- 最初の棒の本数(N)が多いときに変な値が出る → 二分探索の最小値が小さすぎて、割り算した結果がINT_MAXより大きくなる → 無限大表現に INT_MAX/N を使うか（※素直にlong longにしとけばいいものを）
- 最初の本数が少ないときに小さい値が出る → 大きい棒を切ることで順位が変わるのにstick[K]（※並べ替え済）を返していた。お馬鹿
- Cが大きいときに変な値が出る →そろそろlong longにしないと無理ですか
- 答えが1e8みたいに大きくなる時に二分探索が止まらない → 終了条件がhi-lo>1e-9とか駄目ですってば
- ５度目の正直でpassed
typedef long long ll;
#define rep(var,n) for(int var=0;var<(n);var++)
#define sz(a) int((a).size())
class CutSticks {
ll N, C, K;
vector<double> s;
public:
int f(double x){
ll cutcnt=0,sum=0;
rep(j,N){
double sx = s[j]/x;
ll cut;
if (sx >= (double)INT_MAX) cut = INT_MAX;
else cut=(ll)sx;
if (cut==0) continue;
if (cut>=2) cutcnt+=(cut-1);
if (cut>=1) sum+=cut;
}
if (cutcnt >= C) sum -= cutcnt-C;
if (sum>=K) return 1;
return 0;
}
double md(double l, double h) {
if (!f(l)) return -1;
if (f(h)) return h; //-2;
double m=(l+h)/2;
if ((h-l)/h < 1e-12) return m;
if (f(m)) return md(m,h);
else return md(l,m);
}
double maxKth(vector<int> sticks, int c, int k) {
N=sz(sticks); C=c; K=k;
sort(all(sticks)); reverse(all(sticks));
s.resize(N); rep(i,N) s[i]=(double)sticks[i];
return md(1e-12,s[0]);
}
};
SRM456 Easy: SilverDistance
class SilverDistance {
public:
int minSteps(int sx, int sy, int gx, int gy) {
int dx = gx-sx, dy = gy-sy;
if (dx==0&&dy==0) return 0;
int up=0;
int ex = dx+dy;
int ey = -dx+dy;
if (ex&1) {
up=1; ex--; ey--;
}
int hx = ex/2, hy = ey/2;
return abs(hx)+abs(hy)+up;
}
};
こんな問題で悩むなんて… orz
SRM455 Easy(300): DonutsOnTheGridEasy
過去問 | | 
- 問題激しく読み違えてた...ドーナツが幾つ取れるか数えようとしてた。重箱状の階層の深さの最大を求めるだけだった。
#define sz(a) int((a).size())
#define pb push_back
#define rep(var,n) for(int var=0;var<(n);var++)
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
// memoize..
char z[50][50][51][51], mp[50][50][51][51];
class DonutsOnTheGridEasy {
vector<string> gr;
int R,C;
int isZeroShape(int r,int c,int h,int w){
if (h<3 || w<3) return 0;
if (z[r][c][h][w]>=0) return z[r][c][h][w]; // memo
int re=1;
rep(j,h) { int y=r+j;
if (gr[y][c]=='.') {re=0; goto end;}
if (gr[y][c+(w-1)]=='.') {re=0; goto end;}
}
rep(i,w) { int x=c+i;
if (gr[r][x]=='.') {re=0; goto end;}
if (gr[r+(h-1)][x]=='.') {re=0; goto end;}
}
end:
return z[r][c][h][w] = re;
}
int sub(int r,int c,int h,int w){
if (h<3 || w<3) return 0;
if (mp[r][c][h][w]>=0) return mp[r][c][h][w]; // memo
int ct=0; if (isZeroShape(r,c,h,w)) ct=1+sub(r+1,c+1,h-2,w-2);
FOR(hj,1,h-1) ct = max(ct, max(sub(r,c,hj,w),sub(r+hj,c,h-hj,w)));
FOR(wj,1,w-1) ct = max(ct, max(sub(r,c,h,wj),sub(r,c+wj,h,w-wj)));
mp[r][c][h][w] = ct;
return ct;
}
public:
int calc(vector<string> grid) {
R=sz(grid), C=sz(grid[0]);
gr = grid;
// clean up
memset(z,255,sizeof(z)); memset(mp,255,sizeof(mp));
return sub(0,0,R,C);
}
};
SRM456
| 
12.23.2009
| DIV | level | 問題名 | 競技中 | 後で | System Test | 通過率 | 備考 |
|---|---|---|---|---|---|---|---|
| 1 | 250 | SilverDistance | 諦めたので試合終了 | - | - | ||
| 1 | 450 | CutSticks | 間に合わず | - | - | - | |
| 1 | 1050 | - | 開いてない | - |
250点問題: SilverDistance
- 駒移動系苦手意識++
- mapでバグって悩んで
- 結論から言うと空のpriority_queueからtop()取ろうとしてた
- てか何探索しようとしてるの... うまく行ってもTLEな予感
- 40分使っちゃったので諦めて450点問題へ
450点問題: CutSticks
- なんで小数が出る
- 二分探索とか最急降下とか？
- 求めるのは山の頂点ではなく、長さどこまで行けるかの境界値。だったら二分探索だよな
- 最初、どことどこの間だろうか、とか既存の棒の長さで考えてた
- でも任意の長さでいいわけで
- 時間切れ
- Practice roomにて５度目の正直でpassed
- int -> long long にすれば解決する問題多し
- 数値がでかくなると差分1e-9で終了しないとかよくあるよね
- あとで書く
1050点問題:
- 開いてない
Challenge Time
- 450点問題考えてた
System Test
結果
- 0点, xxx/yyy位
- 1353→1292 (-61)
下落の一途…もうだめぽ
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20091223
f(x) = x + ((x%2 == 0) ? 0 : 1)
とかが条件を満たします
なるほどそういうのもアリですね。頭固かったです。