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; | |
| } |
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をコンテスト中にコンスタントに解けるようになるのが、当面の目標です。