air-春合宿2013day1

本選落ちのガチクズなので家でまったりオープンコンテストに出ました。
起床に失敗して絶望。
130点でした。合宿行けててもだめだったなあ
1日目だけを見ると去年より適正な難易度に見える

Bus tour -- バスの経路の交点(交線なら両端)、始点、終点を頂点にしてDijkstraかなあと思ったけどうまく実装できなかった。違うかも

Collecting Images is Fun -- 1辺2^20とかどうするんだ...と思ってとりあえず部分点解を書く。
1行変更してもそんなに状況は変わらないので、前回の結果を使えるところは使うという方法で枝刈り。

#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define fi first
#define se second
#define mp make_pair

#define SZ (1 << 20)
typedef pair<int, int> P;

int n, q;
int col[SZ], row[SZ];
map<P, P> m[SZ + 1];

P calc(int x, int y, int sz, int lx, int ly){
    if(sz == 1) return mp(row[x] ^ col[y], 1);
    if(ly == -1){
	if(!(x <= lx && lx < x + sz)) return m[sz][mp(x, y)];
    }else if(!(y <= ly && ly < y + sz)) return m[sz][mp(x, y)];

    P lu = calc(x, y, sz / 2, lx, ly);
    P ld = calc(x, y + sz / 2, sz / 2, lx, ly);
    P ru = calc(x + sz / 2, y, sz / 2, lx, ly);
    P rd = calc(x + sz / 2, y + sz / 2, sz / 2, lx, ly);
    int colsum = lu.fi + ld.fi + ru.fi + rd.fi;
    int cost = lu.se + ld.se + ru.se + rd.se;
    if(colsum == 0 || colsum == 4) return m[sz][mp(x, y)] = mp(colsum / 4, 1);
    else return m[sz][mp(x, y)] = mp(10, cost + 1);
}

P init(int x, int y, int sz){
    if(sz == 1) return mp(0, 1);
    m[sz][mp(x, y)] = mp(0, 1);
    P lu = init(x, y, sz / 2);
    P ld = init(x, y + sz / 2, sz / 2);
    P ru = init(x + sz / 2, y, sz / 2);
    P rd = init(x + sz / 2, y + sz / 2, sz / 2);
    int colsum = lu.fi + ld.fi + ru.fi + rd.fi;
    int cost = lu.se + ld.se + ru.se + rd.se;
}

int main(){
    scanf("%d %d", &n, &q);
    int si = 1;
    rep(i, n) si *= 2;
    if(n > 10){
	printf("▂▅▇█▓▒░(’ω’)░▒▓█▇▅▂ \n");
	return 0;
    }
    init(0, 0, si);
    rep(i, q){
	int t, x;
	P ret;
	scanf("%d %d", &t, &x);
	--x;
	if(!t){
	    row[x] ^= 1;
	    ret = calc(0, 0, si, x, -1);
	}else{
	    col[x] ^= 1;
	    ret = calc(0, 0, si, -1, x);
	}
	printf("%d\n", ret.se);
    }
    return 0;
}

//30points

Communication Jamming -- 一応問題に目を通したが無理そうなので放置。

JOI Poster -- 制約小さいし愚直にやる。円が接するのはダメ(迫真)と書いてあったのでテキト〜にEPSを使う。

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

int n, w, h, ans;
int x[60], y[60];
int dia, dib;

#define EPS 0.0000001
inline int sqr(int x){ return x * x; }

int main(){
    scanf("%d %d %d", &n, &w, &h);
    rep(i, n) scanf("%d %d", &x[i], &y[i]);
    //A=i, B=j, C=k, D=l
    rep(i, n){
	rep(j, n){
	    if(i == j) continue;
	    dia = sqr(x[i] - x[j]) + sqr(y[i] - y[j]);
	    int mas = min(min(min(sqr(x[i]), sqr(w - x[i])), sqr(y[i])), sqr(h - y[i]));
	    if(mas < dia) continue;
	    rep(k, n){
		if(k == i || k == j) continue;
		rep(l, n){
		    if(l == i || l == j || l == k) continue;
		    dib = sqr(x[k] - x[l]) + sqr(y[k] - y[l]);
		    int mat = min(min(min(sqr(x[k]), sqr(w - x[k])), sqr(y[k])), sqr(h - y[k]));
		    if(mat < dib) continue;
		    if(dia <= dib) continue;
		    int chu = sqr(x[i] - x[k]) + sqr(y[i] - y[k]);	
		    //printf("%d %d %d %d %d %d %d\n", i, j, k, l, dia, dib, chu);    
		    if(sqrt((double)dia) - sqrt(double(dib)) - sqrt((double)chu) > EPS) ans++;
		}
	    }
	}
    }
    printf("%d\n", ans);
    return 0;
}

//O(n^4) solution

まだday1なので参加者のみなさんは気持ちを切り替えて頑張ってください。
自分も来年行きたいです....