ARC107参戦記
はじめに
2020年10月31日21:00-22:40に開催されたARC107では2完1ペナ80分02秒でパフォーマンスは757、レーティングは3下がって777になりました。
少し冷えましたが目標の２完ができ，手応えがあった回でした。
A問題
式変形はすぐにできましたが割り算がでてくることからMODの逆元をとるのに苦労しました。
なんどもやってますが自力で組み切れず，ライブラリからmodintを拾ってきて出力。
結局29分16秒かかりましたがライブラリを使いやすい形でもっておけば10分以内にはできたはずです。
このあたりは事前準備で改善可能なところですが整理できていないライブラリがふくれあがっているので，優先順位を考えながら手をつけたいと思います。
B問題
35分46秒＋1WA。時間がかかりましたが解ききれてほっとしています。
N＜＝10^5なので計算量をいかに落とすかの工夫ですが，全探索でよくでてくるところです。
ちょうどこの１週間は精選とけんちょん本で全探索をじっくりやっていたのがさいわいでした。
この問題を簡単にしたものがけんちょん本３章巻末問題3.6(ABC051B）にあり，計算量の落とし方の考え方はおなじです。
ちなみにABC051Bの推定difが704なのに対し，本問のdifは推定difは577ですので，昔のdifの甘さは明らかだと思います。
a+ｂを2～2Nの範囲で探索し，c+dのところはKから和がでますので，和がある数になるN以下の数の組み合わせの数を加算していきます。
＜和がある数になるN以下の数の組み合わせの数＞に苦労しました。
手を動かしてみると，例えば和が６になる，だけだと（1,5）～（5,1）まで５通りありますが，N＝３とすると，（2,3)と(3,2）の２つだけになります。だいぶ悩んで数式化に成功。
1ペナはintのオーバーフローで余計でした。
int,long long混じりのときの型を決め方はまだ悩みながらやってます。
min関数などは型が混在してるとエラーになるのもいやなところです。
ACしたコード
#include <bits/stdc++.h> using namespace std; int main(){ long long N,K; cin>>N>>K; long long ans=0; long long a,b; for(long long i=2;i<=2*N;i++){ if(i-K>=2 && i-K<=2*N){ a=min(i-2,2*N-i)+1; b=min(i-K-2,2*N-i+K)+1; ans+=a*b; } } cout<<ans<<endl; return 0; }
