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の時のみ素数というのは、公式解説で聞いて初めて知ったので篩版のコードを貼ります。
B – 道路工事
問題概要
N個の交差点を結ぶ、M本の道路がある。
N個の交差点全てが繋がるにはあと何本道路が必要かを出力する。
解法
N個の交差点をunion-findでグループ分けする。それぞれの交差点をつなぐ道路があった場合、unionする。最終的に全ての道路を追加した時のグループを1つにつなげれば良いので、そのグループ数(union-findのroot数)-1が答えとなる。
コード
union-findでやればいいというのはすぐ思いついたのですが、union-findであまり解いたことがなかったので、その実装で苦戦してました。
最終的な数のカウントにsetを使ってますが、実際はsetを使わなくてもpar[i]=iとなる数を数えるだけでOKでした。
C – 仕事計画
問題概要
a_i~b_iまでの時間を使う仕事がN個ある。
最大で受けられる仕事数とその仕事の番号iの一覧を表示する。
ただし、同じ仕事数を受けられる組み合せが複数ある場合は、開始時間、仕事番号の昇順でソートした最も小さい仕事を使う組み合わせを出力する。
解法
解けなかった。
D – アットコーダーモンスターズ
問題概要
M体のモンスターから、K体選んでチームを作る。
この時、チームの不安度を最小にしたい。
チームの不安度は、そのチームのモンスター2体を選んだ時の、攻撃力の差分か防御力の差分の中で一番大きい値となる。
コード
時間内に解法が思いつかなかったため、部分点を狙いに行きました。
部分点の場合は、K体のモンスターを選んだ後、その全てのモンスターの組み合わせについて不安度を計算すればOKです。
モンスターの組み合わせを列挙する部分は、http://www.programming-magic.com/20090123132035/ のnext_combination関数(厳密にはboostのライブラリ)を利用しました。
まとめ
最近、ARCの難易度が上がってきているように感じてます。(確か以前chokudaiさんが解説動画かどこかで、ABCもあるのでARCの難易度が上がってきているという話を言っていた気がします)
以前はCが解けるか解けないかぐらいだった気がするのですが、最近は結構解けなくなってしまっているので、
改めてCをコンテスト中にコンスタントに解けるようになるのが、当面の目標です。