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

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

[yukicoder] yukicoder contest 191 に参加した感想

yukicoder Java

yukicoder contest 191

AtCoderのコンテストにしか参加したことがなかったのですが、偶然yukicoderのコンテストに参加する機会があったので、挑戦しました。

yukicoder contest 191 - yukicoder

時間内に解けた問題はAとBだけでしたが、コンテスト終了後にCも解くことが出来ました。

No.687 E869120 and Constructing Array 1

A問題なので、解きやすい問題でした。

$n$ を0以上の整数とします。

$N = 2n$ のとき、

$a_1 = n$ , $a_2 = n$

とします。

$N = 2n + 1$ のとき、

$a_1 = n$ , $a_2 = n + 1$

とします。

もちろん、解答の候補はこれ以外にもあります。

No.688 E869120 and Constructing Array 2

$1$ の個数を $n$ 、 $0$ の個数を $m$ とします。

このとき、

$2 \leq n \leq 30$

$0 \leq m \leq 30 - n$

を満たすものとします。

$K$ の値は数字の並びに関係ないので、数字の個数のみ依存することに注意します。

$K = {}_n \mathrm{C}\ _2 2^m$

を満たす $n, m$ を求めます。これは、選んだ数の合計が $2$ となる条件は、 $n$ 個から $2$ つ選ぶ組み合わせと、 $m$ 個から $0$ ～ $m$ 個選ぶ組み合わせを掛け合わせた値となっています。

$0$ の方の選び方は、二項係数の和を考えています。つまり、

${ \displaystyle 2^n = \sum_{k=1}^{N} {}_n C_2 }$

となることを利用しています。これは、次のサイトを見ると分かると思います。

二項係数の和，二乗和，三乗和 | 高校数学の美しい物語

No.689 E869120 and Constructing Array 3

時間中に解くことはできませんでしたが、終了後に解きました。

この問題はどの数字を選ぶかが重要だと思います。僕は色々考えた結果、「３、４、５、６」を使って問題を解くことにしました。

解き方の方針

まず初めに、二つの数字の掛け算を考えます。これは、3と4を選んだ時、素数となる数はそれぞれの個数を掛けた値に対応しています。

自然数 $x, y$ が

$xy \lt K$

を満たす最大の $xy$ を考えます。数列の長さの最大値が $250$ であることから、

$1 \leq x \leq 110$

$1 \leq y \leq 110$

の範囲で考えてみます。( $100 \times 100 = 10000$ となることから、当たりをつけています)

$0 \leq K \leq 10000$ に対して、

$K - xy$ の最大値を $z$ とすると、 $250 - (x + y) \ge z$ であれば、5と6を適切に選ぶことで、解答が得られます。

つまり、「３、４、５、６」を用いて、それぞれの個数を $a, b, c, d$ とします。ここで、

$K = ab + cd$

となりますが、ここで $d = 1$ とすると、

$K = ab + c$

になります。

$ab \leq K$

$1 \leq a \leq 110$

$1 \leq b \leq 110$

の条件の下で、 $ab$ を最大化する $a, b$ を求めます。求めたら、

$c = K - ab$

となります。 $c \lt 250 - (a + b)$ を満たすことを確認してください。