Atcoder beginner contest 168

43919 ワード
数学 自閉場 データ構造
最初の話は消極的すぎて、討論してから削除することにしました.
タイトル番号
練習時間
難易度
状態
A
2 min
入門
AC
B
2 min
入門
AC
C
18 min
普及-
AC
D
28 min
普及/向上-
AC(Penalty=2)
E
31 min
普及する
試合後AC
F
inf
普及する
未送信
A
Solution
小さい模擬問題で、問題の表面をよく見て、コードを慎重にしてください.ミスに注意して処罰します.
#include 
#define int long long
using namespace std;

int k;
string s;

signed main()
{
	cin>>s;
	k=s[s.size()-1]-'0';
	
	if (k==2||k==4||k==5||k==7||k==9)  cout<<"hon"<<endl;
	else if (k==0||k==1||k==6||k==8)  cout<<"pon"<<endl;
	else if (k==3)  cout<<"bon"<<endl;
	
	return 0;
}
B
Solution
簡単な文字列シミュレーション動作.
コード
#include 
#define int long long
using namespace std;

int k;
string s;

signed main()
{
	cin>>k>>s;
	if (s.size()<=k)  cout<<s<<endl;
	else
	{
		for (int i=0;i<=k-1;i++)  cout<<s[i];
		cout<<"..."<<endl;
	}
	return 0;
}
C
Chatting
コサインの定理が必要なフロントチーズは、オーディLSHにチャンスを与えます.
しかし、このコンニャクは試験中にチャットソフトを絶対につけないという趣味があるので、コンニャクは試合中に一人の女学覇によって三角関数の余弦定理を説明しました.
Solution
発見しやすいです.時計の針の長さ、つまり三角形の片側aです.分針の長さb b b、つまり三角形の反対側も知っています.上記の二つの辺の夾角を求めたら、三番目の長さを求めることができます.なぜかと聞かずに見続けてください.
発見しやすくて、時計回りの12時間は360°を回転して、だからそれは1時間で30°回転します.同じ理屈で、分針は60分で360°回転するので、1分で6°回転します.
だから、時計回りの角度は時間の数です.×30;時間数はh+m 60 h+\fram｛60｝h+60 mなので、時計回りに30(h+m 60)°30(h+\fram｛60｝30(h+60 m)°を回しました.
分針は一時間回ると元の位置に戻りますので、分針は全部で6 m°6 m°6 m°回転しました.
回転後の時計回りと分針の挟み方は、30(h＋m 60)−6 m|30(h＋\fram｛60｝)−6 m|30(h＋60 m)−6 mŲで、上記の負の値を絶対値として残すように注意してください.
便利さを表現するために、ここでは夾角度咻30(h＋m 60)−6 m|30(h＋\fraacm｛60｝−6 m|30(h＋60 m)−6 m呷呷−d d eを記しています.すると、答えはa 2｛a^2｝a 2＋b 2｛b 2｝b 2−ab 2 de c o s(ab)です.これは多くの高校生と中学三年生がよく知っている余弦定理ですか?食べてもいいですか
C+++cmashライブラリのc o s cos関数のパラメータはラジアン(このコンニャクは知っています.)ですので、角度のcos値を計算します.
inline double COS(double tmp)//      double 
{
	double k=tmp*(M_PI)/180.00;//      
	return cos(k);//      Cmath  cos     
}
最後に重要なことをいくつか注意します.
①万能ヘッドファイルを使わないオーディエンスは必ずc m a t h cmathヘッダファイルを追加します.
②ラジアンに変換する必要があります.
③余弦式は間違えないようにしてください.
④三角関数の余弦定理を学んでいないなら、それでできていないので、がっかりしないでください.
コードをつける
#include 
#define int long long
using namespace std;

double a,b,n,m,de;

inline double pi()
{
	return M_PI;
}

inline double COS(double tmp)
{
	double k=tmp*pi()/180.00;
	return cos(k);
}

signed main()
{
	cin>>a>>b>>n>>m;
	de=double((30.00*n+(m/60.00)*30.00)-6.00*m);
	if (2*de>360)  de=360-de;
	double now=1.00*a*a+1.00*b*b-2.00*a*b*COS(de);
	cout<<fixed<<setprecision(10)<<sqrt(now)<<endl;
	
	return 0;
}
D
Solution
これは裸のD i j k s t r+H e a p Dijkstraa+Heap Dijkstraa+Heapです.
直接D i j k s t r+H e a Dijkstraa+Heap Dijkstraa+Heapを走ります.たるみの過程で、u u u u号の部屋がv号の部屋にゆるみました.u u u号の部屋にv号の部屋を指す案内板を置いたのと同じです.
このように:
if (dis[y]>dis[x]+e[i].dis)
{
	ans[y]=x;
	dis[y]=dis[x]+e[i].dis;
	if (!visited[y])  q.push((node){dis[y],y});
}
注意、k(2≦k≦n)k(2≦k≦n)k(2≦k≦n)号の部屋が1号の部屋に届かない場合、明らかにNoを出力するべきです.
時間複雑度O(n+m)l o g 2 n)O(n+m)logn 2 n)O(n+m)logn 2 n)
#include 
#define int long long
#define inf 20000000007
using namespace std;

int n,m,s=1,cnt=0;
int head[200005],dis[100005],visited[100005],ans[100005];

struct edgde
{
	int next;
	int to;
	int dis;
}e[500005];

struct node
{
	int dis;
	int pos;
	bool operator < (const node x) const
	{
		return x.dis<dis;
	}
};

std::priority_queue<node> q;

inline void add_edge(int u,int v,int w)
{
	cnt++;
	e[cnt].to=v;
	e[cnt].dis=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}

inline void dijkstra()
{
	dis[s]=0;
	q.push((node){0,s});
	
	while (!q.empty())
	{
		node tmp=q.top();
		q.pop();
		
		int x=tmp.pos;
		if (visited[x])  continue;
		visited[x]=1;
		
		for (int i=head[x];i;i=e[i].next)
		{
			int y=e[i].to;
			if (dis[y]>dis[x]+e[i].dis)
			{
				ans[y]=x;
				dis[y]=dis[x]+e[i].dis;
				if (!visited[y])  q.push((node){dis[y],y});
			}
		}
	}
}

signed main()
{
	cin>>n>>m;
	for (int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v,1);
		add_edge(v,u,1);
	}
	for (int i=1;i<=n;i++)  dis[i]=inf;
	
	dijkstra();
	
	for (int i=2;i<=n;i++)
	{
		if (ans[i]==0)  return cout<<"No"<<endl,0;
	}
	cout<<"Yes"<<endl;
	for (int i=2;i<=n;i++)  cout<<ans[i]<<endl;
	return 0;
}
E
えっと、私は弱すぎます.
試合の時は緊張して、問題が分からなくて、第二の例が分かりませんでした.考え始めませんでした.
もちろん、説明が始まる前に、まずB 6 e 0 b 6 e 0 b 6 e 0 b 6 e 0オーケーのE問題に対する説明に感謝します.そうしないと、この問題は永遠に解けません.
Solution
この可愛い式を詳しく調べてみます.a i× a j+b i× b j=0 a_i×a_j+b_i×b_j=0 ai×aj+bi×bj=0です
アイテムを移す× a j=−b i× b j a_i×a_j=-b_i×b_j ai×aj=−bi×bj更に項目を移動して、a i b i=−b j b＿i\fraac{auui}=-\fraac{buj}{buui}bi=−bi bjを得る.
今はもっとよさそうな表現が得られました.そこで、私たちはどうやってこの問題を解くかを考え始めました.まず、すべてのa i b i\frac{auui}{buui}bi aiを前処理し、その中からいくつかの選択されたものとして、もちろん選択されたものの中には-1の積が二つあってはならない.ソリューション数を出力すればいいです.
そして、今の難点はこれらをどうやって行うかです.まず、入力する時に(a i,b i)(aui,bui)(ai,bi)ごとに約分します.そして、各グループの出現した(a i,b i)(auui,bui)(ai,bi)の回数をm a p mapで記録します.
現在(x,y)(x,y)(x,y)が見られたと仮定すると、k個が存在し、x 2,y 2(x 2,y 2)(x 2,y 2)が存在しない(x 2,y 2)(x 2,y 2)がx yとなる.× x 2 y 2=−1\frac{x}{y}×\fraac{x 2}{y 2}=-1 yx×y 2 x 2=−1では、2 k 2^k 2 kのスキームが明らかに存在する(それぞれがこのクラスに属するサーモンについては選択しないか).
x 2,y 2)(x 2,y 2)(x 2,y 2)(x 2,y 2)が存在すればx y× x 2 y 2=−1\frac{x}{y}×\fraac{x 2}{y 2}=-1 yx×y 2 x 2=−1は?k 2 k 2 k 2ペア(x 2,y 2)(x 2,y 2)(x 2,y 2)(x 2,y 2)が存在すると仮定する.
明らかに、私たちは二つの中の一つしか選択できません.答えは2 k 2 k+2 k 2^2 k 2 k 2^2 k 2 k 2です.しかし、実際には両方とも選択しない案がもう一回計算されました.だから、この時の方案数は2 k 2^k 2 k+2 k 2−1 2−2 k 2−1です.
以上より、答えは全ての方案数の積です.
気をつけて
①すべて選択しない場合を差し引きます.
②i i iがあればa i=b i=0 a_i=b_i=0 ai=bi=0なら、これを選ぶだけで他のものは選べません.だから最初はこの状況を無視しますが、最後に追加してください.
注意点②に穴が空いたら、コードの29行目と56行目をよく読んでください.
③型取りと減法＋型取りの仕方を忘れないでください.
コードをつける
#include 
#define int long long
using namespace std;
const int mod=1e9+7;

int n,tot=1,cnt_all_zero=0,ans=1;

map<pair<int,int>,int> m;
map<pair<int,int>,int>::iterator it;

int quick_power(int a,int b)
{
	int res=1ll;
	for (;b;b=b>>1,a=(a*a)%mod)
	{
		if (b&1)  res=(res*a)%mod; 
	}
	return res;
}

signed main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		int u,v,now;
		cin>>u>>v;
		
		if (u==0&&v==0)
		{
			cnt_all_zero++;
			continue;
		}
		now=__gcd(u,v);
		u/=now,v/=now;
		
		if (u<0)  u=-u,v=-v;
		m[make_pair(u,v)]++;
	}
	for (it=m.begin();it!=m.end();it++)
	{
		if (it->second==0)  continue;
		int x=it->first.first,y=it->first.second;
		int p=quick_power(2,m[make_pair(x,y)])%mod;
		
		y=-y;
		if (y<0)  x=-x,y=-y;
		
		if (m.count(make_pair(y,x)))
		{
			p=(p+quick_power(2,m[make_pair(y,x)])-1)%mod;
			m[make_pair(y,x)]=0;
		}
		ans=(ans*p)%mod;
	}
	cout<<((ans+cnt_all_zero-1)%mod+mod)%mod<<endl;
	
	return 0;
}
F
Solution
まず、大部分の非複雑計算幾何学問題に対しては、2つの方法があります.
①数学の作り方②離散化後d f s dfsまたはb f s bfs.
数学のやり方は明らかに難しいと思います.まず、離散化の役割はすべての線を一つにくっつけさせることです.そうすると、私たちはb f s bfs bfsではなく、d f s dfs dfs(原因は以下で言います.)O(n m)O(nm)O(nm)の代価の中で乳牛たちの最大移動できる面積を求めます.
d f s dfs dfsができないのは、本題の中では、d f s dfs dfsが超高い時間複雑度を示すからです.
コード
細かいところが多すぎて、ひそひそしています.
締め括りをつける
まだ弱すぎて、C、Dの問題に時間がかかりすぎて、後の問題をする時間が緊張しすぎて、震えてしまいました.最後に問題を読み間違えて、第五の問題の正解を考え始めませんでした.
反省する
①自信を持って提出します.初めてD D問題を提出した時、意外にも洛谷の上のD i j k s t a+H e a p Dijkstraa+Heap Dijkstraa+Heapのテンプレートをそのまま渡しました.何を考えているのか分かりません.
②読解力に問題があります.D問題の読み間違いはやっと分かりました.E問題は読み間違えで500点を無駄に失いました.料理がなくなった
③緊張しないで!自分が何をするかを30分以上で解決するとは思わないでください.上五箇記録を奉納する:
(1)CF模擬試合で、32分でDiv.3のベスト5を切りました.
(2)AT模擬試合において、17分間のAKのあるABC;
自信が大切です.
QT QHashの使用方法の例