ドワコン→s8pc→DDPCと全部同じ順位。
http://discovery2016-qual.contest.atcoder.jp/tasks/discovery_2016_qual_b
問題
1~N番の部屋が円周上に並んでおり、それぞれ番号が増える方向に一方通行で移動可能である。(N番から1番には当然移動可能)
部屋を経由する際、部屋を見学することができる。(せずに通り過ぎても良い)
i番の部屋を見学する面白さはA[i]である。
1番の部屋から初めて、部屋間を移動しながら見学を行う。
見学した部屋の面白さが単調増加になるように見学順を定め、最終的に1番の部屋に戻りたい場合、最低何周する必要があるか。
解法
まず面白さ毎に部屋番号をビンソートしよう。
ある面白さの部屋を全部訪れたら、次の面白さの最寄の番号に訪れる、という手順を繰り返せばよい。
1番の部屋を最後に訪れても周回数は増えない点に注意。
int N; vector<int> A[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>x, A[x].push_back(i); int ret=0; int cur=101010; FOR(i,101000) if(A[i].size()) { FOR(j,A[i].size()) if(A[i][j]>cur) break; if(j==0) cur=A[i].back(); else ret++, cur=A[i][j-1]; } if(cur==0) ret--; cout<<ret<<endl; }
まとめ
17年卒が80人通るというから、ABCやCodeFestival予選級の問題を予想していたら、完全にARCレベルの問題が出てきた。