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となり、２は素数のためこの場合のみ素数となります。(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;
}a.cppB - 道路工事
問題概要
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;
}b.cppC - 仕事計画
問題概要
a_i~b_iまでの時間を使う仕事がN個ある。 最大で受けられる仕事数とその仕事の番号iの一覧を表示する。 ただし、同じ仕事数を受けられる組み合せが複数ある場合は、開始時間、仕事番号の昇順でソートした最も小さい仕事を使う組み合わせを出力する。
解法
解けなかった。
D - アットコーダーモンスターズ
問題概要
M体のモンスターから、K体選んでチームを作る。 この時、チームの不安度を最小にしたい。 チームの不安度は、そのチームのモンスター2体を選んだ時の、攻撃力の差分か防御力の差分の中で一番大きい値となる。
コード
時間内に解法が思いつかなかったため、部分点を狙いに行きました。
部分点の場合は、K体のモンスターを選んだ後、その全てのモンスターの組み合わせについて不安度を計算すればOKです。
モンスターの組み合わせを列挙する部分は、https://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;
}d.cppまとめ
最近、ARCの難易度が上がってきているように感じてます。(確か以前chokudaiさんが解説動画かどこかで、ABCもあるのでARCの難易度が上がってきているという話を言っていた気がします)
以前はCが解けるか解けないかぐらいだった気がするのですが、最近は結構解けなくなってしまっているので、 改めてCをコンテスト中にコンスタントに解けるようになるのが、当面の目標です。