SRM 648 Div2 Hard

問題

整数NとKが入力として与えられる。
次の二つの条件を満たす長さnの文字列sをどれでも良いので一つ出力せよ。
1. sの各文字はA,B,Cのどれかである
2. s[i]<s[j]かつi<jとなるような(i,j)のペアがちょうどK個ある

3<=N<=30, K<=N(N-1)/2

解法

A,B,Cで構成出来る10文字くらいまでの全ての文字列に対してKを求めて色々眺めてみると、「前半2/3はA,Bのみで構成しても良い」ということが分かる。

(例えばN=8とN=9に対して並べたもの)

よって前半2/3文字は全探索で予めテーブルを
tbl[Aの個数][Kの値]
で作っておき、残りの1/3は全探索して足してvalidになったらそれを出力する。
残りの1/3の全探索の時、テーブルのどこが条件を満たすかの条件はO(N)で分かる。

N<=30なので、計算量としては2^(20)*3^(10)*30でかなり危なかったけどなんとか通った。

他のコードを見ると場合分けしまくっててかなり賢かった。