部活12

部活です。

テーマは変わらず。

はてなだと二重パーレンで注釈になるんですね、Markdown記法というらしい。

知らなかった。

さて、19枚の同値類の組を、和が-1になるように選択しなおすについて。

実は前提条件が抜けていて、和を-1する前に「99枚のパネル群から最高得点の和がSになるように19枚を選ぶ」必要があります。詳しくはこちら

非常に単純で、各同値類の中で、最高のものから順に19枚選ぶだけです。

「19」から、前回出てきた各同値類のパネルの枚数を上から順に引いていきます。

もちろん、何点を何枚選んだかと最高点Sは、以降の探索で使うため覚えておく必要があります。同値類の枚数カウント配列と同じ用に保存しておくと、取り出しが簡単かなと思います。

で、本題。

こちらでも取り上げていますが、19枚の和Sを-1するためには、

①同値類のうち、任意の点数の選択されている数を1減らす

②①で減らした点数より1点低い同値類が選択されている数を1増やす

とすればよいわけです。

15*19を-1したければ、15*18+14*1のように15を1つ取り除いて14を1つ入れるだけですよね。

ここでポイントになるのは、同値類が選べる最大値が決まっていることです。

したがって、実装する場合は次のようになります。

※各同値類Eについて、現在の使用数をn_E、使用上限をN_Eとします

①和がSとなる19枚の同値類の中から、最大の同値類Emを選択する

②Emに対して得点が-1となる同値類Em-1について(N_Em-1)-(n_Em-1)が1以上であれば、その19枚の組をS-1の同値類群として記憶する

③①～②を、選べる同値類がなくなるまで繰り返す

④③で得られたS-1の同値類群が空だった場合、探索は行わず、Sの結果から-2となるように選択する(不要)

④に関しては、今回の場合最高得点が連番になっているためありえないので、実装しません。

たとえば、最高得点10のパネルを19枚選択している状態で、最高得点9のパネルが存在しない場合が該当します。

それから、②で得られる結果は、S-pという数に対して複数存在します。しかも、pが大きくなるほど増えます。よって、今回は配列のリスト構造を用いて記憶することにします。

ちなみに、S-2の結果を得た時点で、Sの同値類群は忘れることができます。省エネ。

今日はここまで。