Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2012-03-29

Codeforces #114 C (Wizards and Numbers)

| 00:50

解けなかった&解法を見ても理解できなかったので復習。

問題文は

http://codeforces.com/problemset/problem/167/C

下のような思考をできれば解けたのではないかと思われる。


(a, b) (a<=b) で手番が回ってきたとき、勝てるか負けるかを考える。

(b%a, a)は(b-a^k, a)より考えやすいので、まずは(b%a, a)について考え場合分け。

(1) a==0 の場合

既に負け。


(2) (b%a, a) で相手に回して勝てる場合

勝ち。


(3) (b%a, a) で相手に回して負ける場合

どうやっても、どちらかの手番にいずれ(b%a, a)が現れること(※)に注意。

自分に(b%a, a)の手番を回すよう仕向けることが出来れば勝てる。

そうで無い場合、相手に(b%a, a)の手番が回るので、負ける。


(※の証明)

このターンで(b-a^k, a)にして相手に渡したとする。

この時、b-a^k < aならば、b-a^k == b%a。

b-a^k >= a ならb≡b-a^k (mod a) より帰納法で示せる。



(3)の、「自分に(b%a, a)の手番を回すよう仕向けることができる」のは、どんな場合?

(※)より、b-b%a == a^k1 + a^k2 + ... + a^kn となる。

(k1は自分の手、k2は相手の手、k3は自分の手...を表す)

自分がk1を選び、それを見て相手がk2を選び、...を繰り返して、

nを偶数にできるなら自分の勝ち、奇数にしかできないなら相手の勝ち。

(i) aが奇数の時

a^kも奇数。よって b-b%a ≡ a^k1 + a^k2 + ... + a^kn ≡ n (mod 2)

ゆえに、b-b%aが偶数ならば自分の勝ち、奇数ならば相手の勝ち。


(ii) aが偶数の時

b-b%aに、aがいくつ詰められるか、という観点で考える。

x = (b-b%a)/a (== floor(b/a)) について場合分けをして法則性がないか見る。

a <= b より x >= 1。

(あ) x == 1 の時

b-b%a = xa = a, よって相手の勝ち。


(い) x == 2 の時

b-b%a = xa = a+a, よって自分の勝ち。


(う) x == 3 の時

b-b%a = xa = a+a+a, よって相手の勝ち。

...

(わ) x == a の時

b-b%a = xa = a*a, よって自分の勝ち。(aは偶数であることに注意)


(を) x == a+1 の時

b-b%a = xa = a^2 + a, よって偶数にできるので自分の勝ち。


(ん) x == a+2 の時

b-b%a = xa = a + a^2 + a or a^2 + a + a

この時は、k1=1でもk1=2でもk2の選び方によりnを偶数にされてしまい、自分の負け。



(あ) ~ (ん) より、1<=x<=aでは相手勝ち/自分勝ちが交互に現れ、a+1<=x<=a+2では自分勝ち/相手勝ちが交互に現れることがわかる。


ここから、x%(a+1)が奇数ならば自分勝ち、偶数ならば相手勝ち、という仮説が導かれる。

一般の場合に、この仮説が正しいかを検証する。

a^2 - 1 ≡ (a+1)(a-1) ≡ 0 (mod a+1)

よって a^2 ≡ 1 (mod a+1) となることに注意。

よってmod a+1ではa^2≡1, a^3≡a, a^4≡1...となる。(<=この性質は覚えておいたほうがよさげ)


以下xをmod a+1で考える。

(1) x が奇数の時

xから1を引く(=bからaを引く)ことで、xを偶数にできる(xが偶数の状態で相手に手番を回せる)。

よって自分勝ち。


(2) x が偶数の時

xから1を引いても、aを引いても、xは奇数となる。

よって相手勝ち。


以上より、aが偶数の時、x%(a+1)の偶奇で勝敗が決まる、という仮説が証明された。

よって次のような関数を作れる。

bool win(long long a, long long b) {
    if (a == 0) return false;
    else if (!win(b%a, a)) return true;
    else {
        if (a%2) return (b-b%a) % 2 == 0;
        else return (b/a) % (a+1) % 2 == 0;
    }
}

ここで、a%2==1のとき(b-b%a) % 2 == (b/a)*a % 2 == (b/a) % 2 == (b/a) % (a+1) % 2であることを用いると、少し圧縮できる。

bool win(long long a, long long b) {
    if (a == 0) return false;
    else if (!win(b%a, a)) return true;
    else return (b/a) % (a+1) % 2 == 0;
}

これが答え。

計算量はユークリッドの互除法と同じでO(log(a))。

2011-04-25

Codeforces Beta Round #69

| 11:46

結果

AHeroesAC (00:15)総当り
BFalling AnvilsAC (00:42)受験数学
CBeavermuncher-0xFFAC (01:06)貪欲
DDomino CarpetAC (01:55)2段DP
EMartian Food--

今更ながら。


A Heroes

3^7を総当りするだけ。


B Falling Anvils

テストででそうな問題。

これ日本人有利なんじゃね?とか思いながら解いてだしたけど、

aまたはbが0のときの例外処理を忘れてて3回ぐらい撃墜された。


C Beavermuncher-0xFF

木構造なので、親より子を先に計算するタイプっぽい。


巣がA-B-Cとあって、ビーバーが余っている場合、A・B間の往復を優先しても、B・C間の往復を優先してもスコアは一緒。

なのでビーバーが余った場合、親・子間より子・孫間の方を優先させてよい。

あとは子が複数の場合とか、ビーバーが足りない場合とかに対処する。


D Domino Carpet

横向きのダイスは縦方向にずれて重ならない、という条件があるので、縦に区切ってDPすればよい。


E Martian Food

見てない。


結果

AC/AC/AC/AC/Unopened +0/-0

470 + 682 + 1104 + 1030 + 0 + 0 = 3286 21位 (部屋2位)

2069 -> 2168


ソース

なんか最近ソースが適当すぎ..

A Heroes

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF (1LL<<60)

char heroes[7][16] = {"Anka", "Chapay", "Cleo", "Troll", "Dracul", "Snowy", "Hexadecimal"};
int of(const string& s) {
    rep(i, 7) if(s==heroes[i]) return i;
    return -1;
}

int g[8][8], to[8], cnt[3], ex[3], dx[3];

int main() {
    int n;
    cin >> n;
    rep(i, n) {
        string a, b, _;
        cin >> a >> _ >> b;
        int aix=of(a), bix=of(b);
        g[aix][bix] = 1;
    }
    rep(i, 3) cin >> ex[i];
    int nn = 1;
    rep(i, 7) nn *= 3;
    LOG(nn);
    Int minx=INF, maxy=0;
    rep(b, nn) {
        int p = b;
        rep(i, 7) {
            to[i] = p%3;
            p /= 3;
        }
        rep(i, 3) cnt[i] = 0;
        rep(i, 7) cnt[to[i]]++;
        int ok=1;
        rep(i, 3) if(cnt[i]==0) ok=0;
        if(!ok) continue;
        rep(i, 3) dx[i] = ex[i]/cnt[i];
        sort(dx, dx+3);
        int x=dx[2]-dx[0];
        int y=0;
        rep(i, 7) rep(j, 7) if(g[i][j] && to[i]==to[j]) y++;
        if(minx>x || (minx==x && maxy<y)) {
            minx = x;
            maxy = y;
        }
    }
    cout << minx << " " << maxy << endl;
    return 0;
}

B Falling Anvils

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int main() {
    int T;
    scanf("%d", &T);
    while(T--) {
        double a, b;
        scanf("%lf%lf", &a, &b);
        if(b==0) {
            printf("%.9f\n", 1.0);
            continue;
        }
        if(a==0) {
            printf("%.9f\n", 0.5);
            continue;
        }
        double ans = a*b;
        if(a<=b*4) {
            ans += a*a/8.0;
        }
        else {
            ans += a*b-2*b*b;
        }
        LOG(ans);
        LOG(a*b*2);
        printf("%.9f\n", ans/(a*b*2));
    }
    return 0;
}

C Beavermuncher-0xFF

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY

int n, s[101000], r[101000];
vector<int> g[101000];

Int rec(int at, int pre) {
    vector<Int> v;
    rep(i, g[at].size()) if(g[at][i]!=pre && r[g[at][i]]>0) {
        r[g[at][i]]--;
        v.push_back(rec(g[at][i], at));
    }
    Int cur = 0;
    if(r[at] < (int)v.size()) {
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        rep(i, r[at]) cur+=v[i]+2;
        r[at] = 0;
    }
    else {
        rep(i, v.size()) cur+=v[i]+2;
        r[at] -= v.size();
        rep(i, g[at].size()) if(g[at][i]!=pre) {
            Int df = min(r[at], r[g[at][i]]);
            r[at] -= df;
            cur += df*2;
        }
    }
    return cur;
}

int main() {
    scanf("%d", &n);
    rep(i, n) scanf("%d", s+i);
    rep(i, n) r[i] = s[i];
    rep(i, n-1) {
        int a, b;
        scanf("%d%d", &a, &b);
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int st;
    scanf("%d", &st);
    cout << rec(st-1, -1) << endl;
    return 0;
}

D Domino Carpet

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
typedef long long Int;
#define INF MY_INFINITY
#define MOD (1000000007LL)

char vonly[][3][4] = {
    {"..O","...","O.."},
    {"..O",".O.","O.."},
    {"O.O","O.O","O.O"},
};
char honly[][3][4] = {
    {"O..","...","..O"},
    {"O..",".O.","..O"},
    {"OOO","...","OOO"},
};

int n, m;
char fie[1020][1020];
int of[250][250];
Int dp[300], dp2[300];
bool canv[300];

int main() {
    scanf("%d%d", &n, &m);
    rep(i, 4*n+1) rep(j, 4*m+1) scanf(" %c", fie[i]+j);
    rep(i, n) rep(j, m) {
        int v=2, h=1;
        rep(k, 3) {
            int ma=1;
            rep(x, 3) rep(y, 3) if(vonly[k][x][y]!=fie[4*i+1+x][4*j+1+y]) ma=0;
            if(ma) h=0;
        }
        rep(k, 3) {
            int ma=1;
            rep(x, 3) rep(y, 3) if(honly[k][x][y]!=fie[4*i+1+x][4*j+1+y]) ma=0;
            if(ma) v=0;
        }
        of[i][j] = v|h;
    }
    /*
    rep(i, n) {
        rep(j, m) printf("%d", of[i][j]);
        puts("");
    }
    */
    dp[0] = 1;
    rep(i, m) {
        dp[i+1] = 0;
        canv[i] = n%2==0;
        rep(j, n) if(of[j][i]==1) canv[i]=false;
        if(i==0) {
            if(canv[i]) dp[i+1] = dp[i];
        }
        else {
            dp2[0] = 1;
            rep(j, n) {
                dp2[j+1] = 0;
                if((of[j][i]&1) && (of[j][i-1]&1)) dp2[j+1] = dp2[j];
                if(j>0) {
                    if((of[j][i]&2) && (of[j][i-1]&2)
                        && (of[j-1][i]&2) && (of[j-1][i-1]&2)) {
                        dp2[j+1] = (dp2[j+1]+dp2[j-1])%MOD;
                    }
                }
            }
            LOG(dp2[n]);
            dp[i+1] = (dp2[n]*dp[i-1])%MOD;
            if(canv[i]) {
                dp[i+1] = (dp[i+1]+dp[i])%MOD;
                if(canv[i-1]) {
                    dp[i+1] = (dp[i+1]-dp[i-1]+MOD)%MOD;
                }
            }
        }
        LOG(dp[i+1]);
    }
    cout << dp[m] << endl;
    return 0;
}

2011-03-29

Codeforces Beta Round #64

| 09:54

結果

ACookiesAC (00:10)倍々
BText MessagingAC (00:32)文分割
CLucky TicketsAC (01:29)数理
DProfessors task-幾何
EInformation Reform-1??


A Cookies

問題文分かりにくい...図を見たほうが分かりやすい。


図を見ればわかるように、辺の長さが2倍になると空白の数は3倍になる。

n=0のときだけ特殊なことに気をつける。


B Text Messaging

.!?で文を分割してDP.


C Lucky Tickets

とっかかりづらい...

maxx*maxy=10^10なので、シミュレーションはムリ。

実はx*y==rev(x)*rev(y)を満たすものは少ないのか?

->書いてみると、どうも100万ちょっとしかないみたい。

ならば、x*y==rev(x)*rev(y)を満たすものを効率的に列挙出来ればよさそう。


x*y==rev(x)*rev(y)で、xを固定し、g=gcd(x, rev(x))とすると、

y = a*rev(x)/g

rev(y) = a*x/g

となる。(aは任意の自然数)

なので逆に、rev(x)/gの倍数のうち、そのrevがa*x/gとなるようなものを探せばよい。


それを全てのxについて試す。

あるyまでの合計を計算するのにBITを使い、

wを越えるyを探すのには二分探索を使う。


D Professors task

幾何?

やってません。


E Information Reform

とりあえず書いたけどWA.


結果

AC/AC/AC/-/- 0/0

480 + 872 + 966 + 0 + 0 + 0 = 2318 51位

1986 -> 2069


復習

Cは、本番は混乱して無駄なコード書いたりしてた。

考えを整理すればもうちょっと速く書けるはずなので、頑張る。

また、wの条件を満たすyは単調減少なので、いちいち二分探索する必要はなく、しゃくとり法を使ったほうが速い。(LayCurseさんのを参照。)


Bは貪欲で良かったらしい。

貪欲で良いものにDPを持ち出すことが多いので、DPと貪欲を見分けられるようにしないと...


D,Eは手が出なかった。

まだまだ...

2011-03-10

Codeforces Beta Round #60

| 15:29

AHarry Potter and Three SpellsWA場合分け
BHarry Potter and the History of MagicAC (0:30)貪欲
CHarry Potter and the Golden SnitchAC (1:27)半幾何
DHarry Potter and the Sorting HatAC (1:57)難易度詐欺
EHarry Potter and the Moving Staircases- 


A Harry Potter and Three Spells

やるだけ...にみえる。

しかし、0が入るところのサンプルが合わない。

0から何か生み出せるとき十分大きな数を生成することにするとサンプル合う。提出。

->後でHacked. 適当に直して再提出。


B Harry Potter and the History of Magic

年号は、選べる中で一番小さいのを使えばいい。だけ。


C Harry Potter and the Golden Snitch

幾何っぽいけど、vs<vpなので、ある時間tで追いつけたなら、t'>tでも絶対追いつける。

なので、時間に対して二分探索をすればよい。

ある時間tで追いつけるかどうかの判定は、スニッチの時刻tでの位置を求め、そこにハリーが時刻tまでにたどり着けるかどうかチェックするだけ。

書く...サンプル合う。提出。->Wrong answer on pretest 4.

ソースを見直しても落ちる要素が見当たらないので、doubleの比較にEPSを入れてみて再提出。

そしたら通った。いいのか..?


D Harry Potter and the Sorting Hat

?の人が続くと、一番人数の少ない寮から順に埋まっていく。なので、一番人数の少ない寮が複数あるときは一旦保留しておいて、?の人が溜まったら一気に入れればいい?

...とか考えたけど、?と?の間に他の寮が入ると崩れてしまう。


よくよく考えると、?の分岐数は4->3->2->1みたいに?がくるごとに小さくなるので、全状態を調べても大した量にならなくない?

書く。最大ケース(?を10000個)を突っ込んでも、手元で0.5秒ぐらいで終わる。

提出。->Wrong answer on pretest 3. えぇー?


見直してみると、Gryffindor, Ravenclaw, Hufflepuff, Slytherinの順に出力してて、「アルファベット順に」というのを見落としてた。なんか罠っぽい。

直して提出。


E Harry Potter and the Moving Staircases

見てません。


結果

WA/AC/AC/AC/- Hack:0

0 + 880 + 928 + 1014 + 0 + 0 = 2822 43位(部屋3位)

1822 -> 1986


反省

Aみたいな、場合分けをして全てを網羅する、的な問題が苦手っぽい。

それと、全体的に書くのが遅いですね。


提出ソース

A Harry Potter and Three Spells

※Wrong Answer (0 0 823 740 0 806とかで)

int main() {
    int a, b, c, d, e, f;
    scanf("%d%d%d%d%d%d", &a, &b, &c, &d, &e, &f);
    double t=1;
    t = a==0 ? b*1e100 : t*b/a;
    LOG(t);
    t = c==0 ? d*1e100 : t*d/c;
    LOG(t);
    t = e==0 ? f*1e100 : t*f/e;
    LOG(t);
    if(a==0 && b!=0 && d!=0) t=1e100;
    if(c==0 && d!=0) t=1e100;
    puts(t>1&&d>0 ? "Ron" : "Hermione");
    return 0;
}

B Harry Potter and the History of Magic

定数倍無視。

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)

int n, y[2000], r[2000], k, c[2000];

int main() {
    scanf("%d", &n);
    rep(i, n) scanf("%d", y+i);
    rep(i, n) {
        int p=i==0?1000:r[i-1];
        k=0;
        rep(j, 10) c[k++] = y[i]%1000 + j*1000;
        rep(j, 10) c[k++] = y[i]-y[i]%1000+y[i]%100 + j*100;
        rep(j, 10) c[k++] = y[i]-y[i]%100+y[i]%10 + j*10;
        rep(j, 10) c[k++] = y[i]-y[i]%10 + j;
        sort(c, c+k);
        rep(j, k) {
            if(c[j]>=p) {
                r[i] = c[j];
                goto fixed;
            }
        }
        puts("No solution");
        return 0;
fixed:;
      LOG(r[i]);
    }
    rep(i, n) if(r[i]>2011) {
        puts("No solution");
        return 0;
    }
    rep(i, n) printf("%d\n", r[i]);
    return 0;
}

C Harry Potter and the Golden Snitch

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)

inline double sq(double a) { return a*a; }
struct pos {
    double x, y, z;
    pos(double x, double y, double z) : x(x), y(y), z(z) {};
};

int n, x[11111], y[11111], z[11111], vp, vs, px, py, pz;
double sp[11111];

pos calc(double t) {
    int ix=lower_bound(sp, sp+n, t)-sp-1;
    if(ix<0) ix=0;
    LOG(t);
    LOG(ix);
    if(ix==n) return pos(-1, -1, -1);
    double dx=x[ix+1]-x[ix], dy=y[ix+1]-y[ix], dz=z[ix+1]-z[ix];
    double dt=t-sp[ix];
    LOG(dx);
    LOG(dy);
    LOG(dz);
    double r=sqrt(sq(dx)+sq(dy)+sq(dz));
    return pos(x[ix]+dx/r*vs*dt, y[ix]+dy/r*vs*dt, z[ix]+dz/r*vs*dt);
}

bool can(double t) {
    pos p(calc(t));
    LOG(t);
    LOG(p.x);
    LOG(p.y);
    LOG(p.z);
    double r=sqrt(sq(p.x-px)+sq(p.y-py)+sq(p.z-pz));
    return r<=t*vp+1e-9;
}

int main() {
    scanf("%d", &n);
    rep(i, n+1) scanf("%d%d%d", x+i, y+i, z+i);
    scanf("%d%d%d%d%d", &vp, &vs, &px, &py, &pz);
    sp[0] = 0;
    rep(i, n) {
        double len = sqrt(sq(x[i+1]-x[i])+sq(y[i+1]-y[i])+sq(z[i+1]-z[i]));
        sp[i+1] = sp[i] + len/vs;
        LOG(sp[i+1]);
    }
    double l=0, r=sp[n];
    if(!can(r)){
        puts("NO");
        return 0;
    }
    rep(i, 100) {
        double mid=(l+r)/2;
        if(can(mid)) r=mid;
        else l=mid;
    }
    puts("YES");
    printf("%.9f\n", l);
    pos p(calc(l));
    printf("%.9f %.9f %.9f\n", p.x, p.y, p.z);
    return 0;
}

D Harry Potter and the Sorting Hat

#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define mp make_pair
#define foreach(it, c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)

int n, f, r[4];
char names[4][16] = { "Gryffindor", "Hufflepuff", "Ravenclaw", "Slytherin"};

int main() {
    scanf("%d", &n);
    vector<vector<int> > v;
    v.push_back(vector<int>(4));
    rep(k, n) {
        char op;
        scanf(" %c", &op);
        LOG(op);
        if(op!='?') {
            rep(i, 4) if(op==names[i][0]) {
                rep(j, v.size()) v[j][i]++;
            }
        }
        else {
            vector<vector<int> > nv;
            rep(j, v.size()) {
                int mx=1<<30;
                rep(i, 4) mx=min(mx, v[j][i]);
                rep(i, 4) if(v[j][i]==mx) {
                    nv.push_back(v[j]);
                    nv.back()[i]++;
                }
            }
            sort(nv.begin(), nv.end());
            nv.erase(unique(nv.begin(), nv.end()), nv.end());
            v = nv;
        }
    }
    rep(i, v.size()) {
        int mx=1<<30;
        rep(j, 4) mx=min(mx, v[i][j]);
        rep(j, 4) if(v[i][j]==mx) r[j]=1;
    }
    rep(i, 4) if(r[i]) puts(names[i]);
    return 0;
}

2010-12-23

Codeforces #47 復習

| 18:26

きれいに書き直し+改良したソース。


A

floor(面積/2)は必ず敷き詰めれる。

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    printf("%d\n", m*n/2);
    return 0;
}

B

それぞれの文字について、i番目までに出てきた数をcに記録

#include <iostream>
#include <string>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int c[128];

int main() {
    string s;
    cin >> s;
    long long ans=s.size();
    rep(i, s.size()) ans+=2*c[s[i]]++;
    cout << ans << endl;
    return 0;
}

C

ななめ45度に傾いた長方形で囲ってやればよい。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int n, x, y;
int INF = 1<<30;

int main() {
    scanf("%d", &n);
    int mink=INF, maxk=-INF, minl=INF, maxl=-INF;
    rep(i, n) {
        scanf("%d%d", &x, &y);
        mink = min(mink, x+y);
        maxk = max(maxk, x+y);
        minl = min(minl, -x+y);
        maxl = max(maxl, -x+y);
    }
    printf("%d\n", maxk-mink+maxl-minl+4);
    return 0;
}

D

半径について2分探索+確率についてDP.

#include <stdio.h>
#include <math.h>
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int N, K, eps, xo, yo, x, y;
double d[200], f[200], dp[200][200];

double p(double r) {
    rep(i, N) f[i] = d[i]<=r ? 1 : exp(1-d[i]*d[i]/r/r);
    rep(i, 200) rep(j, 200) dp[i][j]=0;
    dp[0][0] = 1;
    rep(i, N) rep(j, i+1) {
        dp[i+1][j+1] += dp[i][j] * f[i];
        dp[i+1][j] += dp[i][j] * (1-f[i]);
    }
    double s=0;
    rep(i, K) s+=dp[N][i];
    return s;
}

int main() {
    scanf("%d%d%d%d%d", &N, &K, &eps, &xo, &yo);
    rep(i, N) {
        scanf("%d%d", &x, &y);
        d[i] = hypot(x-xo, y-yo);
    }
    double l=0, r=1e10, m;
    rep(q, 100) {
        m = (l+r)/2;
        if(p(m)*1000<eps) r=m;
        else l=m;
    }
    printf("%.9f\n", l);
    return 0;
}

E

解説は参加記の方を参照。結構すっきりしたコードになる。

前半のループ内で範囲を列挙しvに突っ込み、次のソート+ループ部分で範囲をマージしている。

#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int main() {
    long long n, m, k, ans=0;
    cin >> n >> m;
    vector<pair<int, int> > v;
    for(long long b=1; b<=n; b++) {
        ans += min(m, b*b)*2;
        k = b*b>m ? b-sqrt(b*b-m) : b;
        if(k>0) {
            ans -= k*2;
            v.push_back(make_pair(1, k));
            v.push_back(make_pair((int)b*2-k, (int)b*2-1));
        }
    }
    sort(v.begin(), v.end());
    int z=0;
    rep(i, v.size()) {
        if(z>0 && v[z-1].second>=v[i].first) v[z-1].second=v[i].second;
        else v[z++] = v[i];
    }
    rep(i, z) ans += (v[i].second-v[i].first+1);
    cout << ans << endl;
    return 0;
}