atcoder初め、 ARC #032参加しました。
前回のABCに参加した際には、全問通していたのでそのまま全部簡易解説を書きましたが、
Atcoderのコンテストに関しては、公式に解説、および提出コードや解説コードが公開されているので、基本的には自分のメモとして自分の解法+αとコードを載せるぐらいにしておきます。(後日、追加で解いたらコード等は追記しますが…)
A – ホリドッグ
問題概要
数字、Nが与えられるので、1+2+…Nが素数か否かを判定する。
解法
最初にエラトステネスの篩で1+2+…1000(N>=1000)までの値について、素数のリストを作成します。
次に、入力Nに対しての累積和を求めます。累積和は以下の公式で求められます。
この求めた累積和が素数か否かを判定すればOKです。
ただし実は、N=2のみ素数でそれ以外の時は全て素数ではありません。
これは、上記の累積和の公式を見れば明らかで、nが奇数の時は、(n)((n+1)/2)が整数同士の積となり、明らかに素数ではありません。同じくnが偶数の時は、(n/2)(n+1)が整数同士の積となります。ただしn=2の時は1*2=2となり、2は素数のためこの場合のみ素数となります。(n=1の時は、累積和もそもそも1->1は素数ではない)
コード
2の時のみ素数というのは、公式解説で聞いて初めて知ったので篩版のコードを貼ります。
#include<iostream> | |
#include<cstring> | |
using namespace std; | |
int main() | |
{ | |
const int MAX= 1000*1001/2; | |
bool prime[MAX+1]; | |
memset(prime,true,sizeof(prime)); | |
prime[0]=prime[1]=false; | |
for(int i=2;i<=MAX;i++) | |
{ | |
if(prime[i]) | |
for(int j=i+i;j<=MAX;j+=i) | |
prime[j]=false; | |
} | |
int n; | |
cin>>n; | |
if(prime[n*(n+1)/2]) | |
cout<<"WANWAN"<<endl; | |
else | |
cout<<"BOWWOW"<<endl; | |
} |
B – 道路工事
問題概要
N個の交差点を結ぶ、M本の道路がある。
N個の交差点全てが繋がるにはあと何本道路が必要かを出力する。
解法
N個の交差点をunion-findでグループ分けする。それぞれの交差点をつなぐ道路があった場合、unionする。最終的に全ての道路を追加した時のグループを1つにつなげれば良いので、そのグループ数(union-findのroot数)-1が答えとなる。
コード
union-findでやればいいというのはすぐ思いついたのですが、union-findであまり解いたことがなかったので、その実装で苦戦してました。
最終的な数のカウントにsetを使ってますが、実際はsetを使わなくてもpar[i]=iとなる数を数えるだけでOKでした。
#include<iostream> | |
#include<set> | |
using namespace std; | |
int par[100002]; | |
int find(int x) | |
{ | |
if(par[x]==x) | |
return x; | |
else | |
return par[x]=find(par[x]); | |
} | |
void ufunion(int x,int y) | |
{ | |
x=find(x); | |
y=find(y); | |
if(x==y)return; | |
par[y]=x; | |
} | |
int main() | |
{ | |
int n,m; | |
cin>>n>>m; | |
int cnt=0; | |
for(int i=0;i<n;i++)par[i]=i; | |
for (int i=0; i<m; i++) { | |
int a,b; | |
cin>>a>>b; | |
a–,b–; | |
ufunion(a,b); | |
} | |
set<int> hash; | |
for (int i=0; i<n;i++) | |
hash.insert(find(i)); | |
cout<<hash.size()-1<<endl; | |
} |
C – 仕事計画
問題概要
a_i~b_iまでの時間を使う仕事がN個ある。
最大で受けられる仕事数とその仕事の番号iの一覧を表示する。
ただし、同じ仕事数を受けられる組み合せが複数ある場合は、開始時間、仕事番号の昇順でソートした最も小さい仕事を使う組み合わせを出力する。
解法
解けなかった。
D – アットコーダーモンスターズ
問題概要
M体のモンスターから、K体選んでチームを作る。
この時、チームの不安度を最小にしたい。
チームの不安度は、そのチームのモンスター2体を選んだ時の、攻撃力の差分か防御力の差分の中で一番大きい値となる。
コード
時間内に解法が思いつかなかったため、部分点を狙いに行きました。
部分点の場合は、K体のモンスターを選んだ後、その全てのモンスターの組み合わせについて不安度を計算すればOKです。
モンスターの組み合わせを列挙する部分は、http://www.programming-magic.com/20090123132035/ のnext_combination関数(厳密にはboostのライブラリ)を利用しました。
#include<iostream> | |
#include<vector> | |
#include<algorithm> | |
using namespace std; | |
template < class BidirectionalIterator > | |
bool next_combination ( BidirectionalIterator first1 , | |
BidirectionalIterator last1 , | |
BidirectionalIterator first2 , | |
BidirectionalIterator last2 ) | |
{ | |
if (( first1 == last1 ) || ( first2 == last2 )) { | |
return false ; | |
} | |
BidirectionalIterator m1 = last1 ; | |
BidirectionalIterator m2 = last2 ; –m2; | |
while (–m1 != first1 && !(* m1 < *m2 )){ | |
} | |
bool result = (m1 == first1 ) && !(* first1 < *m2 ); | |
if (! result ) { | |
while ( first2 != m2 && !(* m1 < * first2 )) { | |
++ first2 ; | |
} | |
first1 = m1; | |
std :: iter_swap (first1 , first2 ); | |
++ first1 ; | |
++ first2 ; | |
} | |
if (( first1 != last1 ) && ( first2 != last2 )) { | |
m1 = last1 ; m2 = first2 ; | |
while (( m1 != first1 ) && (m2 != last2 )) { | |
std :: iter_swap (–m1 , m2 ); | |
++ m2; | |
} | |
std :: reverse (first1 , m1 ); | |
std :: reverse (first1 , last1 ); | |
std :: reverse (m2 , last2 ); | |
std :: reverse (first2 , last2 ); | |
} | |
return ! result ; | |
} | |
template < class BidirectionalIterator > | |
bool next_combination ( BidirectionalIterator first , | |
BidirectionalIterator middle , | |
BidirectionalIterator last ) | |
{ | |
return next_combination (first , middle , middle , last ); | |
} | |
int main() | |
{ | |
int n,k; | |
cin>>n>>k; | |
vector<int> data; | |
int ma[n],mb[n]; | |
for(int i=0; i<n; i++){ | |
cin>>ma[i]>>mb[i]; | |
data.push_back(i); | |
} | |
int cnt=0; | |
int mindiff=99999999; | |
do{ | |
int tmp=0; | |
for(int i=0;i<k;i++) | |
for(int j=i+1;j<k;j++) | |
{ | |
tmp=max(tmp,max(abs(ma[data[i]]-ma[data[j]]),abs(mb[data[i]]-mb[data[j]]))); | |
} | |
if(mindiff>tmp) | |
{ | |
mindiff=tmp; | |
cnt=1; | |
} | |
else if(mindiff==tmp) | |
cnt++; | |
}while(next_combination(data.begin(), data.begin()+k, data.end())); | |
cout<<mindiff<<endl<<cnt<<endl; | |
} |
まとめ
最近、ARCの難易度が上がってきているように感じてます。(確か以前chokudaiさんが解説動画かどこかで、ABCもあるのでARCの難易度が上がってきているという話を言っていた気がします)
以前はCが解けるか解けないかぐらいだった気がするのですが、最近は結構解けなくなってしまっているので、
改めてCをコンテスト中にコンスタントに解けるようになるのが、当面の目標です。