AtCoder Beginner Contest (ABC) #016 参加記

~ ik-fib
このエントリーをはてなブックマークに追加
LINEで送る

ABC #016参加しました。
メモついでに、(公式のほうがわかりやすいと思いますが)簡易解説もどきと一緒にコードを貼っていきます。

A – 12月6日

問題概要

日付が与えられるので月が日で割り切れるかを判定する。

解法

(月÷日)が0か否かを判定して、”YES” or “NO”を出力

コード


#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int m,d;
cin>>m>>d;
if(m%d)
cout<<"NO"<<endl;
else
cout<<"YES"<<endl;
}

view raw

a.cpp

hosted with ❤ by GitHub

B – A±B Problem

問題概要

入力A,B,Cに対してA ± B = C となるかを判定して、どちらの可能性もあるなら ? 、 どちらでもないなら ! を、そうでなければその演算子を出力する。

解法

± 両方満たすか、もしくはどちらかのみ満たすか、どちらも満たさないかの順番で判定して、判定結果を出力する

コード


#include<algorithm>
#include<iostream>
using namespace std;
int main()
{
int a,b,c;
cin>>a>>b>>c;
if(a+b==c && a-b==c)
cout<<"?"<<endl;
else if(a+b==c)
cout<<"+"<<endl;
else if(a-b==c)
cout<<"-"<<endl;
else
cout<<"!"<<endl;
}

view raw

b.cpp

hosted with ❤ by GitHub

C – 友達の友達

問題概要

N人のユーザ間の友達関係が与えられるので、各ユーザの友達の友達の人数(自分と友達は除く)を出力する。

解法

1人ごとに友達か否かを判定、その友達の友達を更に判定して保存、その一覧から自分自身と友達を除いた合計を計算して出力しています。
今回はNが最大10人なので、ループが重くても回るので最初に思いついたこの方式が一番すぐ書けそうだったので実装しましたが、人数が多くなるとこの方法だと重くて厳しいと思います。

コード


#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int a[m],b[m];
for(int i=0;i<m;i++)
{
cin>>a[i]>>b[i];
a[i]–;
b[i]–;
}
for(int i=0;i<n;i++)
{
bool flend[2][n];
memset(flend,false,sizeof(flend));
for(int j=0;j<m;j++)
{
if(a[j]==i||b[j]==i)
flend[0][a[j]]=flend[0][b[j]]=true;
}
for(int j=0;j<m;j++)
{
if(flend[0][a[j]]||flend[0][b[j]])
flend[1][a[j]]=flend[1][b[j]]=true;
}
for(int j=0;j<m;j++)
{
if(a[j]==i||b[j]==i)
flend[1][a[j]]=flend[1][b[j]]=false;
}
int cnt=0;
for(int j=0;j<n;j++)
{
if(flend[1][j])
{
cnt++;
}
}
cout<<cnt<<endl;
}
}

view raw

c.cpp

hosted with ❤ by GitHub

D – 一刀両断

問題概要

多角形を1本の線分が分断する。分断された後の多角形の総数を出力する。

解法

多角形を構成する線分と分断する線分の交差判定を行い、交差する線分2つ毎に1箇所分断、すなわち多角形の総数が1つ増えます。
そのため、(交差する線分数/2)+1(最初の多角形)が答えとなります。

ただ、私は幾何系の問題が苦手でライブラリも現状あまりちゃんと用意してないので、昔ICPC向けに用意していた他の方が公開されているライブラリ(チームメイトに教えてもらったライブラリ)を利用しました。

今回は@fura_2さんが昔公開されたライブラリの幾何部分を利用しました。

コード


#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
template<class T>
struct point{
T x,y;
point &operator+=(const point &a){ x+=a.x; y+=a.y; }
point &operator-=(const point &a){ x-=a.x; y-=a.y; }
point operator+(const point &a)const{ return (point){x+a.x,y+a.y}; }
point operator-(const point &a)const{ return (point){x-a.x,y-a.y}; }
operator point<double>()const{ return (point<double>){x,y}; }
};
template<class T>
struct segment{
point<T> a,b;
operator segment<double>()const{ return (segment<double>){a,b}; }
};
template<class T>
T cross(const point<T> &a,const point<T> &b){ return a.x*b.y-a.y*b.x; }
enum{CCW=1,CW=-1,ON=0};
template<class T>
int ccw(const point<T> &a,const point<T> &b,const point<T> &c){
T rdir=cross(b-a,c-a);
if(rdir>0) return CCW;
if(rdir<0) return CW;
return ON;
}
template<class T>
bool intersect(const segment<T> &S1,const segment<T> &S2){
if(max(S1.a.x,S1.b.x)<min(S2.a.x,S2.b.x)
|| max(S1.a.y,S1.b.y)<min(S2.a.y,S2.b.y)
|| max(S2.a.x,S2.b.x)<min(S1.a.x,S1.b.x)
|| max(S2.a.y,S2.b.y)<min(S1.a.y,S1.b.y)) return false;
return ccw(S1.a,S1.b,S2.a)*ccw(S1.a,S1.b,S2.b)<=0
&& ccw(S2.a,S2.b,S1.a)*ccw(S2.a,S2.b,S1.b)<=0;
}
int main()
{
int ax,ay,bx,by;
cin>>ax>>ay>>bx>>by;
point<int> a={ax,ay};
point<int> b={bx,by};
segment<int> ab={a,b};
int n;
cin>>n;
int cnt=0;
point<int> p[n];
for(int i=0;i<n;i++)
{
int x,y;
cin>>x>>y;
p[i].x=x;
p[i].y=y;
}
for(int i=0;i<n-1;i++)
{
segment<int> tmp={p[i],p[i+1]};
if(intersect(ab,tmp))
{
cnt++;
}
}
segment<int> tmp={p[n-1],p[0]};
if(intersect(ab,tmp))
{
cnt++;
}
cout<<(cnt/2)+1<<endl;
}

view raw

d.cpp

hosted with ❤ by GitHub

まとめ

D問題が解法はすぐ方針がたったのですが、実装が他の方のライブラリ頼りだったので、使い方を間違ったり等結構ひどいことに…
ICPC参加中に、自分が使えるライブラリをまとめ直したいと思い少しづつやっていましたが、結局やりきれず残ってしまった部分も多くそういったところが今でも弱点なので、できるだけ改善していきたいところです。

このエントリーをはてなブックマークに追加
LINEで送る

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。