Codeforces #172

コンテストでの更新面倒でさぼってたけど今回のCodeforcesは特に面白かった&特にいい順位がとれたのでかきます。気まぐれ。

朝(昼)は12:00くらいにおきたので眠気は全くなくて、万全の態勢で臨むことができたと思っている。

  • 問題を開く。Aを見る。面倒くさそう。とばす。
  • Bを見る。わからない。Xorとったものの大小の性質なにかいいのあったっけ...
  • わからないのでCを見る。simpleでおもしろそう。ちょっと考える。最初木DPかなとか思ったけど各頂点ごとに取り除かれる確率を求めればいいと思いついたら一瞬だった。一瞬で実装してPretest passed.こういう弱実装発想ゲーすき
  • この時点でstandingsみたら8位とかになっててやばい
  • BはわからなかったのでDを見る。どう見てもsegtreeでDP列を保管するゲーム。実装を始める。
  • 実装重いけどコンテスト終わるまでには通せると自分に言い聞かせて実装を続ける。
  • 途中まで実装してオーダーを再確認したところupdateクエリですでにO(k^2log n)くらいの時間がかかることに気付きさすがにやばいのであきらめる。
  • この時点で1時間くらい。
  • かといってEを解くのはさすがに無理だと思ったのでBに戻る。
  • O(n^2)の自明解しか思いつかないなぁ
  • 候補の数の最悪ケースを考えてみる。
  • 各要素に対し、その隣がちいさくてそこから数列が単調増加してるような場合が最悪。
  • このとき単調増加してる部分は全部候補数O(1)だなぁ
  • O(n^2)の候補数になるようなケースはぱっと見少なそう
  • ということは全通り試せるのでは?
  • priority_queueとか使って適当に実装してPretest passed.
  • Aにもどる
  • 紙に適当に計算する
  • doubleっぽい問題だけど誤差が出て分岐に影響したとしても最終的に出力する面積で全部消えるから誤差とかどうでもいい
  • ゼロ除算は気をつけなければと思う(Linesの教訓)
  • 適当に実装してバグとってPretest passed.
  • もう時間がないので適当にLockして落ちるコード探す
  • そもそも落ちそうなケースが見当たらないのでhackはしなかった
  • 終了
  • 現在33位。全部通れば余裕で過去最高。
  • Systestはじまらない
  • 就寝を決意したらsystestはじまったので決意を撤回した
  • 全部通る
  • 24位。rating:1981 -> 2106(+125)
  • わーい

以下ソース
A

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
	double za,zb,zc;
	scanf("%lf%lf%lf",&za,&zb,&zc);
	if(zc>90.0)
	{
		zc=180.0-zc;
	}
	if(za<zb)
	{
		swap(za,zb);
	}
	if(zc==90.0)
	{
		printf("%lf\n",zb*zb);
		return 0;
	}
	zc/=180.0;
	zc*=3.14159265358979323846264338327950288;
	if((1.0+cos(zc))/za<(sin(zc))/zb)
	{
		printf("%lf\n",zb*zb*(1.0/sin(zc)));
	}
	else
	{
		double pl=(za+zb)*sin(zc)/(1.0+cos(zc)+sin(zc));
		double x=(za-pl)/(1+cos(zc)-sin(zc));
		double y=(zb-pl)/(1+cos(zc)-sin(zc));
		printf("%lf\n",za*zb-(x*x+y*y)*cos(zc)*sin(zc));
	}
}

B

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>pii;
int left[100002];
int right[100002];
int main()
{
	int num;
	scanf("%d",&num);
	vector<int>vec;
	vec.push_back(2000000000);
	for(int i=0;i<num;i++)
	{
		int zan;
		scanf("%d",&zan);
		vec.push_back(zan);
	}
	vec.push_back(2000000000);
	priority_queue<pii>que;
	for(int i=0;i<vec.size();i++)
	{
		que.push(make_pair(-vec[i],i));
		for(;;)
		{
			if(que.empty())
			{
				break;
			}
			pii zan=que.top();
			zan.first=-zan.first;
			if(zan.first>=vec[i])
			{
				break;
			}
			else
			{
				que.pop();
				right[zan.second]=vec[i];
			}
		}
	}
	for(int i=vec.size()-1;i>=0;i--)
	{
		que.push(make_pair(-vec[i],i));
		for(;;)
		{
			if(que.empty())
			{
				break;
			}
			pii zan=que.top();
			zan.first=-zan.first;
			if(zan.first>=vec[i])
			{
				break;
			}
			else
			{
				que.pop();
				left[zan.second]=vec[i];
			}
		}
	}
	int maxi=0;
	for(int i=1;i<=num;i++)
	{
		if(left[i]!=2000000000)
		{
			maxi=max(maxi,vec[i]^left[i]);
		}
		if(right[i]!=2000000000)
		{
			maxi=max(maxi,vec[i]^right[i]);
		}
	}
	printf("%d\n",maxi);
}

C

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
vector<int>pat[100000];
bool flag[100000];
double ans=0.0;
void dfs(int node,int d)
{
	if(flag[node])
	{
		return;
	}
	flag[node]=true;
	ans+=1.0/double(d);
	for(int i=0;i<pat[node].size();i++)
	{
		if(!flag[pat[node][i]])
		{
			dfs(pat[node][i],d+1);
		}
	}
}
int main()
{
	int node;
	scanf("%d",&node);
	for(int i=0;i<node-1;i++)
	{
		int za,zb;
		scanf("%d%d",&za,&zb);
		za--;
		zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	dfs(0,1);
	printf("%lf\n",ans);
}