ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC008 C - コイン,D - 金塊ゲーム

C - コイン

提出コード
重要なのは、あるコインについて、その数字の約数となっているコインが左側にどれだけあるか、です。
なので、それぞれのコインについて、その数字の約数となっているコインの枚数をまず数えておきます。
あとは、それぞれのコインについて表側になっている確率を求め、足し合わせれば答えが求まります。
表側になるには、あるコインより左側に、その約数となっているコインが偶数枚存在する必要があります。
なので、まずはあるコインと、その約数のコイン(これをi枚とします)だけをすべて並べることを考えると、(i+1)!通りになります。
次に、表となるような並べ方を考えます。
あるコインを先に配置してしまい、残った場所を約数のコインで並べる、というように考えると、
あるコインが表となるような場所の配置の仕方→(i+2)/2通り(切り捨てです)
残ったコインの並べ方→i!通り
となるので、全体で
(i+2)/2×i!通り
となります。
あとは、これを全事象となる(i+1)!で割れば確率が求まりますので、約分すると
\frac{(i+2)/2}{i+1}
となります(切り捨ては区別するため、表記方法を変えました)。
あとはこれを全てのコインについて行い、和を求めれば答えとなります。

D - 金塊ゲーム

提出コード
1度何かしらの装置を起動させると、金塊がある領域は全部で4つに分かれます。
そこで、その領域を状態としたメモをします。
dp[i][j][k][l] = 長方形の上下左右の端の座標がijklのときにとれる金塊の最大値、とします。
答えはdp[1][1][w][h]のような感じの場所に入っているはずです。
と、ここで上記のような4次元配列を取ることを考えるのですが、それでは配列のメモリを確保しきれません。そこで、mapを使いごり押しをします(キーを4つの座標、そこに最大値を記録していきます)。
あとは、メモ化再帰をします。
今現在の4つの座標を引数にとります。
その範囲内に装置がそもそもなければ、最大値は0になります。
それ以外のときについて考えます。
その範囲内のうちの任意の装置をそれぞれ起動したとき、わかれる4つの領域で再帰をし、それぞれの領域での最大値を足し合わせます。これをループを用いて、領域内の装置について全探索し、一番多く取れたときの個数を選びます。
最後に、求めた最大値に、現在の領域で装置を起動したときにとることができる金塊の数を足します。
金塊の数は、その領域の大きさで決まっており、
(右端の座標)-(左端の座標)+(上端の座標)-(下端の座標)+1
となっています。
これをメモして再帰していけば、答えが求まるはずです。