CodeFestival-qualC D Yet Another Palindrome Partitioning(700)

bit単位への圧縮

よくある、偶奇とかmod2とかの 0と1にするやつ

こうするとNが一つ2になるので、今回は2^26で通った

1. #include<iostream>
2. #include<algorithm>
3. #include<vector>
4. #include<queue>
5. #define lol(i,n) for(int i=0;i<n;i++)
6. #define mod 1000000007
7. typedef long long ll;
8. using namespace std;
9. #include<unordered_map>
10. unordered_map<int,vector<int> >v;
11. //vector<int> v[1<<26];
12. int mark[200010];
13. int dp[200010];
14. int main(){
15. string s;
16. cin>>s;
17. int r=1;
18. lol(i,26)r*=2;
19. lol(i,s.size()+1)dp[i]=mod;
20. dp[0]=0;
21. mark[0]=0;
22. int cnt[26]={0};
23. for(int i=0;i<s.size();i++){
24. cnt[s[i]-'a']++;
25. cnt[s[i]-'a']%=2;
26. int tmp=0;
27. int a=1;
28. lol(j,26){
29. tmp+=a*cnt[j];
30. a*=2;
31. }
32. v[tmp].push_back(i+1);
33. mark[i+1]=tmp;
34. }
35.  
36. for(int i=0;i<s.size();i++){
37. int k=mark[i];
39. if(upper_bound(v[k].begin(),v[k].end(),i)!=v[k].end()){
40. int it=*upper_bound(v[k].begin(),v[k].end(),i);
41. dp[it]=min(dp[it],dp[i]);
42. }
43. int a=1;
44. for(int j=0;j<26;j++){
45. int tmp=mark[i];
46. if(mark[i]%(a*2)<a){
47. tmp+=a;
48. }
49. else tmp-=a;
50. //tmpが,mark[i]から1bitだけ変化したもの
51. a*=2;
52. k=tmp;
53. if(upper_bound(v[k].begin(),v[k].end(),i)!=v[k].end()){
54. int it=*upper_bound(v[k].begin(),v[k].end(),i);
55. dp[it]=min(dp[it],dp[i]+1);
56. }
57. }
58. //cout<<dp[i]<<" ";
59. }
60. cout<<max(1,dp[s.size()])<<endl;
61. return 0;
62. }

unordered_mapを使うと速い（mapと交換したらTLEが取れた）

時間ギリギリ(117:57 / 120:00)