BCの配点やばいし、nosubかなと思ってたけど500点ぐらいの難易度
■A - Remove Substrings
頭と末尾が異なる時は、明らかに1回
そうじゃないときはどこかにa[0]!= a[i],a[i+1]!=a[n-1]があれば2回
3回以上で成立するかを考える。
考えると無理なのがわかるので、-1を出力すればいい。
時間かかり過ぎなので提出を一旦見送る。
■B - Greedy Division
高橋と青木が最終的に手にする集合を入手順番を込みで決めると
もとの数列が一通りに決まる。
なので
dp[i][j][k]:=i番目までで、j個使って、和kを作る通り数とし
答えはΣdp[n][i][wSum/2] * fact[i] * fact[n - i]
階上を掛けているのは、集合それぞれに対する並び順を考慮するため。
wの合計が奇数の時は明らかに0
■C - Roughly Sorted
問題文を２回ぐらい誤読する。(転倒数の合計がKだと思った)
結局、最終的な状態の各要素が、そもそもどこから来たのかがわかればいい
のでそれぞれの初期位置の候補数をかければ良い
