JOI 2019/2020 二次予選 過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
「競技プログラミング」を略して、「競プロ」などと呼ばれています。
#D - テンキー (Tenkey)
僕が作成、提出したコードは、以下のとおりです。
/* AtCoder Problems in C++ #D - テンキー (Tenkey) https://atcoder.jp/contests/joi2020yo2/tasks/joi2020_yo2_d 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; using ll=long long; ll vv[10][1000000]; int main(void){ ll v[10][4]={ {1,-1,-1,-1},{0,2,4,-1}, {1,3,5,-1},{2,6,-1,-1}, {1,5,7,-1},{2,4,6,8}, {3,5,9,-1},{4,8,-1,-1}, {5,7,9,-1},{6,8,-1,-1} }; ll m,r; cin>>m>>r; ll ans,a,b,c,d; queue<ll> q1,q2,q3; for(ll i=0;i<10;i++){ for(ll j=0;j<m;j++){ vv[i][j]=-1; } } vv[0][0]=0; q1.push(0); q2.push(0); q3.push(0); while(1){ ans=q1.front(); a=q2.front(); b=q3.front(); q1.pop(); q2.pop(); q3.pop(); c=(a*10+b)%m; if(c==r){ ans++; break; } if(vv[b][c]==-1){ vv[b][c]=ans+1; q1.push(ans+1); q2.push(c); q3.push(b); } for(ll i=0;i<4;i++){ if(v[b][i]==-1){ break; } d=v[b][i]; if(vv[d][a]==-1){ vv[d][a]=ans+1; q1.push(ans+1); q2.push(a); q3.push(d); } } } cout<<ans<<endl; return 0; }