ARC 077 E guruguru(700)

式の整理

方針は直感的にわかりやすいが、条件整理が難しい

おはじきを使うと考えやすかった

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. ll u[100010];
10. ll v[100010];
11. int d[100010];
12. int main(){
13. int n,m;
14. cin>>n>>m;
15. lol(i,m)u[i]=v[i]=0;
16. lol(i,n)cin>>d[i];
17. ll sum=0;
18. int within=0;
19. lol(i,n-1){
20. int a=d[i]-1,b=d[i+1]-1;
21. u[a+1]++;
22. u[b]--;
23. int tmp=(b-a+m)%m;
24. v[b]+=tmp-1;
25. sum+=min(tmp,b+1);
26. if(b<a)within++;
27. }
28. ll ans=sum;
29. lol(x,m){
30. ans=min(ans,sum);
31. within+=u[x];
32. sum+=v[x]-within;
33. }
34. cout<<ans<<endl;
35. return 0;
36. }

難しい問題はこれ（式を正しくする力）がベースになければいけないと思うので、鍛える