ABC166 やっと緑や

AtCoder始めたときはすぐに緑になれるかなと思ってた。

まさか５ヶ月もかかるとは。それより遅い人を馬鹿にしてるのじゃなくて、自分の元からの数学に対する知識とか、プログラミンングに当ててる時間とかを考慮すると少しおそいなと。

でも素直に嬉しいな。

明らかに茶色で一回止まってるしな。このまま水色目指したい。

なんか最近のコンテスト、DPとかBFSあまり出てない？難易度高いものばっかりに出てるのかな。中くらいのレベルで出して欲しいな。

昨日書いたけど、今日は友達に勝ててすごく嬉しい。

次もまた勝負やな。

今日のEはO(N)で解けた。NlogNかと思ってたけどその時は思いつかなかった。

1. int64_t N,ans=0;
2. cin>>N;
3. vector<int> A(N+1);
4. unordered_map<int64_t,int> um;
5. for(int i=0; i<N; i++){
6. int a;
7. cin>>a;
8. A[i+1]=a;
9. if(um.count(a+i+1))um[a+i+1]++;
10. else um[a+i+1]=1;
11. }
12. for(int i=0; i<N; i++){
13. if(um.count(i+1-A[i+1]))ans+=um[i+1-A[i+1]];
14. }
15. cout<<ans<<endl;

ある二人、番号A,Bで身長C,Dやとしたら

B-A=C+Dになればいいから

B-D=A+Cって式変形したら右辺左辺で一人の情報に変換できる。

全員のB-Dをunordered_mapに突っこむ。

A+Cがunordered_mapに存在するか探せばいい。

明日は仕事やな。ゴールデンウイークとか関係ないから気合入れてがんばるぞ。