なぜJMO-yoは閲覧・入力以外のPC使用が厳禁なのか
※注意 この記事は競技数学のプログラミング使用を推奨するものではありません 予めご了承ください
今回は競プロの威力を体感するために、JMO2021-yoをC++パンチしていきたいと思います
問題はここ:https://www.imojp.org/archive/mo2021/jmo2021/problems/jmo31yq.html
1.
さすがにやるだけです
int main(){ int res=0; rep(n,1,90){ int m=90-n; if(gcd(n,m)==1)chmax(res,n*m); } cout<<res<<'\n'; // 2021 return 0; }
2.
幾何ライブラリを使って、1辺の長さをにぶたんします
参考記事:https://tk0-math.hatenablog.com/entry/2020/12/27/180738
int main(){ vector<P> vs(10); double lb=0,rb=1; rep(_,0,60){ double mid=(lb+rb)/2.; vs[0]=P(mid,0); rep(i,0,9)vs[i+1]=rot(vs[i],2*M_PI/10.); double S=Area(vs); if(S>1.)rb=mid; else lb=mid; } double res=Area({vs[0],vs[1],vs[2]}); res+=Area({vs[2],vs[3],vs[4],vs[7]}); printf("%.12f\n",res); // 0.400000000000 -> 2/5 return 0; }
3.
ABではなくDPの長さを探索します tangentとIntersectionを駆使すると
Aが求められるのでどちらの象限に属すかで判定問題を解けばよいです
int main(){ double lb=0,rb=20; P b(-7,0),d(2,0),c(7,0),a,f,e; rep(_,0,60){ double mid=(lb+rb)/2.; P p(2,mid); Circle C1(p,5),C2(p,2); auto vs=tangent(b,C1); f=vs[0]; if(f.X>vs[1].X)f=vs[1]; vs=tangent(c,C2); e=vs[0]; if(e.X<vs[1].X)e=vs[1]; a=Intersection(Line(b,f),Line(c,e)); if(a.X<0)lb=mid; else rb=mid; } double res=abs(a-b); printf("%.12f\n",res); // 10.583005244258 -> 4sqrt(7) return 0; }
4.
答えが指数オーダーでつらいので、小さい数で実験してエスパーする方針にします
今回は運よくヒットしましたが、もし当たらなければ「差分を取る」「初項を削る」なども有効だと思います
void dodo(double& a,double& b,double& c){ double na=(b+c)/2.; double nb=(a+c)/2.; double nc=(a+b)/2.; swap(a,na); swap(b,nb); swap(c,nc); } int main(){ rep(n,1,8){ int res=inf; rep(a,1,201)rep(b,1,201)rep(c,1,201){ if(a==b or b==c or c==a)continue; if(a+b+c>res)continue; double x=a,y=b,z=c; rep(_,0,n)dodo(x,y,z); int ex=round(x),ey=round(y),ez=round(z); if(abs(x-ex)<eps and abs(y-ey)<eps and abs(z-ez)<eps){ chmin(res,a+b+c); } } cout<<n<<':'<<res<<'\n'; //9,15,27,51,99,... //https://oeis.org/A060013 -> 3*2^n+3 } return 0; }
5.
あり得る状態数は高々2^16なのでbitDPをすることができます
実装は死ぬほど長くなったので省略(outputはちゃんと379になりました) 多分頭を使った方が早いです
6.
適当にN<=10^7まで探索すると新たなf(N)が出現するNはごく少ないことが分かります
1足してOEISに投げると https://oeis.org/A002110 であることがわかり、後は10^10の制約に合わせればよいです
int main(){ set<int> fs; rep(n,1,10000001){ for(int m=1;;m++){ if(gcd(n,m)==1 and gcd(n+1,m+1)==1){ if(!fs.count(m))cout<<n<<'\n'; //1,2,5,29,209,... fs.insert(m); break; } } } return 0; }
7.
実は垂心は初めて実装しました 各角度のtanと頂点座標で出来るんですねーーー
int main(){ P b(-5,0),p(0,0),q,c,a; double lb=0,rb=10; rep(_,0,60){ double mid=(lb+rb)/2.; q=P(mid,0); c=P(mid+6,0); Circle C1(b,10),C2(c,11); auto as=Intersection(C1,C2); a=as[0]; P h1=orthocenter(a,b,q),h2=orthocenter(a,p,c); if(h1.Y<h2.Y)rb=mid; else lb=mid; } printf("%.12f\n",lb+11); // 15.198684153571 -> sqrt(231) return 0; }
8.
https://hos-lyric.hatenablog.com/entry/2018/12/28/025852
これがかなりヒントになります
累乗の部分はおおよそ周期 に入っています
以下の整数が例外ですが、これは高々5程度でテトレーションに勝てるわけがないので無視してOKです
using P=pair<int,int>; //a*19^b P rec(int d,int m,int n){ //a_1^a_2^...^a_n mod m == d if(m==1){ return {1,n}; } if(n==16){ auto [td,tm]=crt({d,1},{m,17}); d=td; m=tm; } P res={0,20}; int pre=5,nm=phi(m); rep(a,2,21)for(int x=pre;x<pre+nm;x++){ if(mpow(a,x,m)==d%m){ P add=rec(x,nm,n-1); if(add.first==0)continue; if(res.second==20){ res=add; continue; } if(abs(res.second-add.second)>5)assert(0); if(res.second<add.second){ rep(_,0,add.second-res.second)add.first*=19; } else{ rep(_,0,res.second-add.second)res.first*=19; res.second=add.second; } res.first+=add.first; } } return res; } int main(){ auto res=rec(1,17,17); cout<<res.first<<' '<<res.second<<'\n'; // 2042 14 return 0; }
9.
愚直DFSを書いてOEISに投げると https://oeis.org/A183632 が出てくる
あとは書いてある通りにやるだけ
ll mod(ll a,ll m){return (a%m+m)%m;}
ll mpow(ll a,ll t,ll m){
ll res=1;
while(t){
if(t&1)res=mod(res*a,m);
a=mod(a*a,m); t>>=1;
} return res;
}
int main(){
const int n=2020;
const int m=100;
vector<int> a(n+10);
a[0]=mod(2+mpow(2,n+2,m)+mpow(3,n+1,m),m);
a[1]=mod(3*(4+mpow(2,n+2,m)+mpow(3,n,m)),m);
a[2]=mod(50+7*mpow(2,n+2,m)+mpow(3,n+1,m),m);
rep(i,3,n+5){
a[i]=mod(6*a[i-1]-11*a[i-2]+6*a[i-3],m);
}
cout<<a[n-1]<<'\n';
// 3
return 0;
}
10.
幾何をC++で殴る記事はここでもまとめています（まとまってない）
https://tk0-math.hatenablog.com/entry/2020/12/27/180738?_ga=2.5473715.1249954011.1615963450-720260241.1585136235
∠BACとADの長さを固定すると図が一意に定まるので、評価関数を∠BDP,∠BPC,∠PECの各差の二乗和として山登り法をします
int main(){ P a(0,0),b(9,0),c,d,e,p; auto rec=[&](auto self,double Ld,double Rd,double lb,double rb,int lvl)->void{ if(lvl==30)return; double rgd=Rd-Ld,rgb=rb-lb; double best=inf,D,B; rep(i,0,501)rep(j,0,501){ double ds=Ld+rgd*i*.002; double bs=lb+rgb*j*.002; c=P(11*cos(ds),11*sin(ds)); d=P(bs,0); double acb=arg(a,c,b); P tmp(bs+(9-bs)*cos(acb),(9-bs)*-sin(acb)); e=Intersection(Line(a,c),Line(d,tmp)); if(ccw(a,e,c)!=-2)continue; auto ps=Intersection(Circle(d,1),Circle(e,3)); if(ps.empty())continue; if(ps.size()==2 and isIntersect(Segment(a,ps[1]),Segment(d,e)))p=ps[1]; else p=ps[0]; double A[3]={arg(b,d,p),arg(b,p,c),arg(p,e,c)},score=0; rep(k,0,3)score+=(A[k]-A[(k+1)%3])*(A[k]-A[(k+1)%3]); if(chmin(best,score)){ D=ds; B=bs; } } self(self,D-rgd*.2,D+rgd*.2,B-rgb*.2,B+rgb*.2,lvl+1); }; rec(rec,0,M_PI,0,9,0); double res=abs(b-p)/abs(c-p); printf("%.12f\n",res); // 0.522232967868 -> sqrt(33)/11 return 0; }
11,12.
TODO
総括
一応7完は出来ました モチベが上がったら後半もやります
共通テスト前なのでかなり雑です 何か誤字脱字あったら @tk0_math までどうぞ
(2021/3/19 追記)8~10を追加しました
