ABC #016参加しました。 メモついでに、(公式のほうがわかりやすいと思いますが)簡易解説もどきと一緒にコードを貼っていきます。
- コンテストページ: https://abc016.contest.atcoder.jp/
- 公式解説スライド: https://www.slideshare.net/chokudai/abc016
- 公式ニコ生解説放送: https://live.nicovideo.jp/watch/lv202514545
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;
}a.cppB - 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;
}b.cppC - 友達の友達
問題概要
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;
}
}c.cppD - 一刀両断
問題概要
多角形を1本の線分が分断する。分断された後の多角形の総数を出力する。
解法
多角形を構成する線分と分断する線分の交差判定を行い、交差する線分2つ毎に1箇所分断、すなわち多角形の総数が1つ増えます。 そのため、(交差する線分数/2)+1(最初の多角形)が答えとなります。
ただ、私は幾何系の問題が苦手でライブラリも現状あまりちゃんと用意してないので、昔ICPC向けに用意していた他の方が公開されているライブラリ(チームメイトに教えてもらったライブラリ)を利用しました。
今回は@fura_2さんが昔公開されたライブラリの幾何部分を利用しました。 https://twitter.com/fura\_2/status/271623570159972352
コード
#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;
}d.cppまとめ
D問題が解法はすぐ方針がたったのですが、実装が他の方のライブラリ頼りだったので、使い方を間違ったり等結構ひどいことに… ICPC参加中に、自分が使えるライブラリをまとめ直したいと思い少しづつやっていましたが、結局やりきれず残ってしまった部分も多くそういったところが今でも弱点なので、できるだけ改善していきたいところです。