AtCoder ARC #076(C,D,E)

所感

1完のみで惨敗です。D,Eは本番中途中までいっていたので解説を読んで解き直してみました。

 

C: Reconciled? - AtCoder Regular Contest 076 | AtCoder

犬N匹と猿M匹を、犬と猿が隣り合わないように並べる時の並べ方の総数。

 

差が

・2以上なら0

・1なら種類の場所が一意に決まるのでN!M!

・0なら先頭が犬か猿かの2種類あるのでN!M!*2

で余りを出しながら計算。

 

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;
long long INF = 1000000007;

int main() {
long long N,M;
cin>>N>>M;
if(abs(N-M)>1){
cout<<0<<endl;
}else{
long long ans=1;
REP(i,N){
ans*=(i+1);
ans%=INF;
}
REP(i,M){
ans*=(i+1);
ans%=INF;
}
if(N==M){
ans*=2;
ans%=INF;
}
cout<<ans<<endl;
}

return 0;
}

 

D: Built? - AtCoder Regular Contest 076 | AtCoder

街(x1,y1)と(x2,y2)を結ぶコストがmin(|x1-x2|,|y1-y2|)である時の、全ての街を繋ぐ最低コスト。

 

最初に最小全域木かな?と思いましたが、辺を張るのにN^2かかるじゃん...と思って延々と別の解法を考えてしまいました。

解説にもありますが、(i,j,k)について x_i<=x_j<=x_k の時、i-k間を結ぶくらいなら i-j, j-k間を繋ぐよねっていう話。なので、x,yについてソートして隣同士の街の辺だけ張る。これだとO(N log N)なので後は最小全域木クラスカル法で解きました。構造体のソートはもうちょっといい方法があると思います...

 

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()
using namespace std;

struct Edge{
int u,v,cost;
};
struct Node{
int x,y,id;
};

bool compx(Node& x,Node& y){ return x.x<y.x ;}
bool compy(Node& x,Node& y){ return x.y<y.y; }
bool compc(Edge& x,Edge& y){ return x.cost<y.cost;}

//////////////////UnionFind木の実装/////////////////
int pare[100000];
int trank[100000];

int find(int u){
if(u==pare[u]){ return u
; }
return pare[u]=find(pare[u]);
}

void unite(int u,int v){
u=find(u)
; v=find(v);
if(u==v){ return; }
if(trank[u]<trank[v]){
pare[u]=v
;
}else{
pare[v]=u
;
if(trank[u]==trank[v]){
trank[u]++
;
}
}
return;
}
//////////////////UnionFind木実装終わり//////////////////

int main() {
int N;
cin>>N;
vector<Edge> edge;
vector<Node> node;
REP(i,N){
int x,y;
cin>>x>>y;
Node n;
n.x=x; n.y=y; n.id=i;
node.push_back(n);
pare[i]=i;
trank[i]=0;
}


//x,yについて隣同士の辺を貼る
sort(node.begin(),node.end(),compx);
REP(i,N-1){
Edge e;
e.u=node[i].id;
e.v=node[i+1].id;
e.cost=node[i+1].x-node[i].x;
edge.push_back(e);
}

sort(node.begin()
,node.end(),compy);
REP(i,N-1){
Edge e;
e.u=node[i].id;
e.v=node[i+1].id;
e.cost=node[i+1].y-node[i].y;
edge.push_back(e);
}

//クラスカル法、コストの小さい辺から見て行って、
//閉路を作らなければ(無駄な辺を張らない)辺を張る。UnionFind木
sort(ALL(edge),compc);
long long ans =0;
REP(i,edge.size()){
Edge e =edge[i];
if(find(e.u)!=find(e.v)){
ans+=e.
cost;
unite(e.u,e.v);
}
}
cout
<<ans<<endl;

return 0;
}

 

E: Connected? - AtCoder Regular Contest 076 | AtCoder

R*Cマスの格子点で、井戸-家接続パズル。

解説みた後にも一番苦しめられた(知識が浅かっただけ)。

5分くらい考えて、ある組み合わせ(x1,y1),(x2,y2)について、両点が周上にある時だけを考えれば良さそうだなと思った。しかし、これらの点についての条件判定が思いつかなかった(ある点の組み合わせについて、他の全ての点の組み合わせが衝突しないかどうか判定しようとしてた)。

解説を読んで、stackとか使えばめっちゃ楽じゃんと納得。なるほど。

しかし幾度も提出してもRE...これは点の組み合わせを保存するのに、周上の格子点上の配列(2*(R+C))を用意してたので(四角形の左上を0として、時計回りで進んだ時の距離)、メモリが足りなかったらしい。4byte*4*10^8=1.6GB。mapとかunordered_mapも試してみたけど、(R+C)が10^8あるので間に合わない(検索がO(1)を超える)。pairを使って距離順でソートして解決した。

2時間くらい格闘してた...。

 

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;
int R,C,N;

/////長方形の辺上の点を始点からの距離に直す関数//////
int length(int x,int y){
if(y==0){ return x; }
if(x==0){ return 2*(R+C)-y; }
if(x==R){ return R+y; }
return 2*R+C-x;
}
//////////////////////////////////////////////

bool comp(pair<int,int>& p1,pair<int,int>& p2){
return p1.first - p2.first;
}

int main() {
cin>>R>>C>>N;
vector<pair<int,int>> border;

REP(i,N){
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
if ((x1%R==0||y1%C==0)&&(x2%R==0||y2%C==0)){
//pair(始点からの距離、id)
border.push_back(pair<int,int>(length(x1,y1),i+1));
border.push_back(pair<int,int>(length(x2,y2),i+1));
}
}

sort(border.begin(),border.end());
stack<int> pos;
pos.push(-1);

//次の点とスタックのidが等しければ両方削除、違うならばスタックに重ねる
REP(i,border.size()) {
if(pos.top()!=border[i].second){
pos.push(border[i].second);
}else{
pos.pop();
}
}

if(pos.size()==1){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
return 0;
}