AtCoder ARC #042 : A - 掲示板、B - アリの高橋くん

ABで時間かけすぎたのが反省ですが、C,Dがまぁまぁの速度で1位を取れたので良かったです。
http://arc042.contest.atcoder.jp/tasks/arc042_a
http://arc042.contest.atcoder.jp/tasks/arc042_b

A - 掲示板

1～N番のスレッドが先頭から順に並んでいくスレッドフロート型掲示板を考える。
ここでM回の書き込みがスレッドA[i]に成された。
書き込みが成されると、そのスレッドはスレッド列の先頭に移動する。
最終的なスレッドの並び順を答えよ。

問題の絵の通りにスレッドを引っこ抜いて先頭に持って行って…とやると大層なデータ構造が必要で難しい。
ここは、スレッドを引っこ抜かず先頭に追加していくだけにしておく。
そして順番を答える際は頭から見ていって、同じスレッドが２回目以降に登場したときは無視してやればよい。

int N,M;
int A[201010];
int vis[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) A[i]=N-i;
	FOR(i,M) cin>>A[N+i];
	
	for(i=N+M-1;i>=0;i--) {
		if(vis[A[i]]==0) _P("%d\n",A[i]),vis[A[i]]=1;
	}
}

B - アリの高橋くん

二次元座標において、凸多角形と内部のある点の座標が与えられる。
その点から凸多角形外部に至る最短距離を求めよ。

点から、多角形の各頂点及び各線分への距離を求めればよい。
自分は幾何のよりライブラリを持ってないのでガリガリ内積とか計算している。

int N;
int X[1010],Y[1010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>x>>y;
	cin>>N;
	double mi=101010;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		X[i]-=x; Y[i]-=y;
		mi=min(mi,sqrt(X[i]*X[i]+Y[i]*Y[i]));
	}
	X[N]=X[0],Y[N]=Y[0];
	
	FOR(i,N) {
		double dx=X[i+1]-X[i];
		double dy=Y[i+1]-Y[i];
		double r=sqrt(dx*dx+dy*dy);
		dx/=r;
		dy/=r;
		double dot=-X[i]*dx-Y[i]*dy;
		double tx=X[i]+dot*dx;
		double ty=Y[i]+dot*dy;
		
		if((tx*Y[i]-ty*X[i])*(tx*Y[i+1]-ty*X[i+1])<0) mi=min(mi,sqrt(tx*tx+ty*ty));
	}
	
	_P("%.12lf\n",mi);
}

まとめ

幾何ライブラリの有無で難易度が大幅に変わる。
Aも一瞬考えるし、今回A,Bが難しめじゃない？