ヤマカサのプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

AtCoder Beginner Contest 096 の感想

AtCoder Java 日記

AtCoder Beginner Contest 096

abc096.contest.atcoder.jp

結果

今回のコンテストでは時間内に全て解くことができました。D問題の配点が400だったので、いつもより優しい？感じだったんでしょうか。

各問題に対する考え方

A問題

日付に関する問題で、指定された範囲で月と日が同じになる日数を数えます。

a 月 b 日

とすると、 a \geq b ならば、答えは aで、 a \lt b ならば a - 1 となります。

B問題

三つの中の最大値に 2^K を掛けて残りの数字を足します。

C問題

方眼紙を指定された通りに塗ることができるかという問題でした。 考え方はある'#'の位置を p_{(i, j)} とすると、その位置の上下左右の4方向に'#'が存在すれば、塗ることができます。具体的には、

p_{(i, j)} に対して、 p_{(i+1, j)}, p_{(i-1, j)}, p_{(i, j+1)}, p_{(i, j-1)} の位置のどれかに'#'があれば、塗ることができます。

for文で書くために、列と行を二つ増やして、キャンバスを囲むように配列を作れば、注目するキャンバスのブロック全てに4方向に対応する要素が存在することになります。

D問題

素数に関する問題でした。

問題を見たときに、ゲゲゲと思ったんですが、素数の性質と倍数を考えることで解くことができました。

最初考えたときに、2以外の素数はすべて奇数であるので、2を含む数列から選ばれる5つの素数の和は偶数となります。つまり、合成数となります。

N \gt 5 の時はどうするか悩んだんですが、最終的に次の結論に至りました。

2以外の素数について、

5n + 1 が素数となる数を選ぶと、任意の5つの素数の和は次のようになります。

(5n_1 + 1) + (5n_2 + 1) + (5n_3 + 1) + (5n_4 + 1) + (5n_5 + 1) = 5k k = n_1 + n_2 + n_3 + n_4 + n_5 + 1

となります。幸い、 2 \leq N \leq 55555 の中に、 5n + 1 型の素数の数は、1408個あるので、題意を満たすことができます。

また、 5n + 2 型のような他の素数を選んでも大丈夫だと思います。

感想

初めてD問題まで解くことができたので嬉しかったです。次も頑張りたいと思います。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?