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の時のみ素数というのは、公式解説で聞いて初めて知ったので篩版のコードを貼ります。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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でした。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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のライブラリ)を利用しました。
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #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をコンテスト中にコンスタントに解けるようになるのが、当面の目標です。