TCO '11 Round3 - simezi

ドハマリ回orz

94.91 / Unopened / Unopened
0チャレンジ

181位
1859 -> 1904

S[0],S[1],...,S[n-1]を色の配列とする。各色はWかBのいずれかである。
P[0],P[1],...,P[n-1]を0からn-1の順列（各数字がちょうど一度ずつ現れる数列）とする。

S[P[0]],S[P[1]],...,S[P[n-1]]を新しいSとすることで新しい配列が得られる。
この操作を何度も繰り返すことで、配列がいくつか得られる。

Sが与えられたとき、一つの順列から得られる異なる最大の配列の数を求めよ。
n≦30

これはWとBの順番には依存しないで、個数のみに依存するっぽい。
SとS'で、要素i,jが入れ替わっていたら、Pも同じようにiとjを入れ替えれば同じ数の配列が得られるので。

順列によって要素はいくつかのグループに分かれる。
P={1,2,0,4,3}とかだと0→2→1→0……というループと3→4→3……というループができる。
ループがいくつか出来て、それぞれの周期がわかると、全体の周期は全部の周期の最小公倍数。

じゃあdp[i][j][k]を残り長さi,残りWがj,今までの最小公倍数がkであるような周期の最大値とするようなDPはどうなるんだろう。
すごく頭がこんがらがる。
再帰だと、最小公倍数の部分がどう書けばいいのかわからないし、ループでも更新どうしていいのかわからない。

（……50分くらい悩む）

そもそも一つの輪のサイクルっていくつになるんだろう。（←いまさら）
あ、全部同じ色なら1で、そうでないなら長さに決まってるじゃんorz
ってことは、グループのうち二色以上入ってるものの大きさを全探索すればいい。

今までのところのループの周期の約数になってるグループの長さは考えなくていいので枝刈り。書いた。
最大ケース0.001秒。
もう敗北はほぼ確実なので、じっくりテストしてから送信。

みんな250がDP解だ。見てみるがよくわからない。
てか凄い勢いでチャレンジされていく。

日本人つながりでLayCurseさんのコードを見てみる。
あれ、dp[w][b]で公倍数考えないでmax取ってるけどいいのかこれ？
なんか落ちそうな気もするけどチャレンジケース思い浮かばないのであきらめる。

ぼーっと眺めて終了。

250も500もめちゃくちゃ落ちてる。
自分の250は通った。