AtCoder Regular Contest (ARC) #032 参加記

atcoder初め、 ARC #032参加しました。

前回のABCに参加した際には、全問通していたのでそのまま全部簡易解説を書きましたが、
Atcoderのコンテストに関しては、公式に解説、および提出コードや解説コードが公開されているので、基本的には自分のメモとして自分の解法+αとコードを載せるぐらいにしておきます。(後日、追加で解いたらコード等は追記しますが…)

A – ホリドッグ

問題概要

数字、Nが与えられるので、1+2+…Nが素数か否かを判定する。

解法

最初にエラトステネスの篩で1+2+…1000(N>=1000)までの値について、素数のリストを作成します。
次に、入力Nに対しての累積和を求めます。累積和は以下の公式で求められます。
\sum_{i=1}^{n} = \frac{(n*(n+1))}{2}
この求めた累積和が素数か否かを判定すればOKです。

ただし実は、N=2のみ素数でそれ以外の時は全て素数ではありません。

これは、上記の累積和の公式を見れば明らかで、nが奇数の時は、(n)((n+1)/2)が整数同士の積となり、明らかに素数ではありません。同じくnが偶数の時は、(n/2)(n+1)が整数同士の積となります。ただしn=2の時は1*2=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をコンテスト中にコンスタントに解けるようになるのが、当面の目標です。

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>