AOJ 1175 - そして，いくつになった？

問題
提出コード
個人的にICPCの中でも結構好きな部類の問題です。

解法

今回もc言語です。
メモ化再帰をしていきます。
円盤の枚数はたかだか24で、状態としては”残っている”か、”取り去られている”の2通りです。なので、全体で種類の状態が存在しますが、これは未満ですから、int型の配列を準備してあげることができます。
また、2種類の状態がそれぞれの円盤に存在しますが、これは2進数で管理することができます。x桁目を円盤のx番目とリンクさせておくと、x桁目が1ならx番目の円盤が取り去られていて、0なら残っている、というようにしてint型の変数1つで現在の状態が表現できます。
check[i] = 現在の状態がiのとき、ここから取り除くことができる最大の円盤の枚数
とします。
このとき、残っている円盤から2枚選び、その円盤が

• 上に何も乗っかっていない

• 同じ色である

という条件を満たす場合、その2枚を取り去ることができます。
取り去る2枚の情報を現在の状態に加え、再帰をしていけば、答えを求めることができます。
check[i] = max(check[j] + 2)
です。ここで、jは状態iからさらに2枚取り除いた場合の状態を表します。
また、2つの円盤が重なっているかどうか、というのは高校(中学?)数学を利用して、前計算しておきます。2つの円盤の中心間の距離を求め、それが2つの円盤の半径の和未満ならば2つの円盤が重なっていることになります。これも、int型の変数と2進数を利用することで、コンパクトに情報を保持することができます。
あとは、色ごとに円盤を先に分けておいたりなど、余分な計算がなくなるような工夫を加えつつ書いていけば、ギリギリ答えが求まります。最初に状態数はと述べましたが、実際は奇数枚取り除くパターンは存在しないので、その半分になっています。