ABC-Dへんてこ辞書
abc030.contest.atcoder.jp
いろいろバグりました+満点は取っていません(多分満点解は実装力のNasaで死ぬ)
問題概要+方針
配列の中をどんどん移動するパターンです。こういう複雑なの、苦手なのでいい経験になりました。(といっても完全に自分でとけたわけではない)
規則性を見つけて、そこから計算量を減らすって感じです。
具体的には
- メモする配列を用意、i番目の辞書に何回目に調べたかを代入しとく
- もうすでにメモってあったならば、その時点で閉路ができてるので終了
- もし閉路の開始地点よりkが小さければ、シミュレーション
こんな感じです。
まいコード
#include<iostream> #include<algorithm> #include <string> #include<cstdio> #include<vector> #include<queue> typedef long long ll; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) using namespace std; int main() { ll n, a, k, b[10000] = { 0 }; ll memo[10000] = { 0 }; cin >> n >> a >> k;//代入 ll nextsiraberu, count = 1;//調べようとしているもの、何回目かのカウント REP(i, n) { cin >> b[i]; }//代入 nextsiraberu = b[a - 1];//次調べようとしているものを代入 ll soremade, shuuki;//それまで何回作業したか,周期 while (1) { memo[nextsiraberu] = count;//memo[今調べようとしているもの]に1をたす(一個前のwhile文で、もしもうすでに調べられていたらその時点でbreakされてるのでそこは心配しなくておけ) nextsiraberu = b[nextsiraberu - 1];//次に調べようとするもの(いまのcount+1)を代入 if (memo[nextsiraberu]) {//もしもうすでに次に調べようとしているものが調べられていたら soremade = memo[nextsiraberu]-1;//周期に達するまで何個あったか shuuki = count - soremade;//最後のカウントから、最初-1のカウントを引き、周期の長さを求める break; } count++;//countをたす } if (k < soremade) {//もしkが周期に達する前で終わってたら bool b = true; REP(i, 100001) { if (memo[i] == k) { b = false; cout << i << endl; break; } } if (b) { cout << nise << endl; } } else { k -= soremade;//ここ忘れてたし k %= shuuki; REP(i, 100001) { if (memo[i] == k + soremade) { cout << i << endl; break; } } } return 0; }
こんな感じです。このような問題は演習量かなあとか思っているので、理解はしているがまだもやもやしている今の状況は許容範囲と自分で勝手に決めます。
教えて下さったarukukaさん、本当に有難うございます!