参加者の正答率が非常に低かった今回、何気に一発AC出たので本番参加しておきたかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=14544
問題
N個のスロットが円周上に並んでおり、それぞれS[i]個ずつ石が並んでいる。
この状態で、以下のいずれかの処理を任意に繰り返す。
- 処理A : 空でないスロットを1つ選び、すべての石を回収する。そして時計回りにスロットを回りながら、手持ちが空になるまで1つずつ石をスロットに入れていく。
- 処理B : 空でないスロットを1つ選ぶ。そこから、スロット内の石を1つ拾い、反時計回りに1つずつ移動する。途中で空のスロットに到達したら、すべての石をそこに入れる。
上記処理を用いて、各スロットの石の個数がT[i]個になるようにせよ。
解法
処理Aと処理Bは逆の処理であることがわかる。
スロットのある状態をUとする。S→Uに処理Aだけで到達可能であり、同様にT→Uも処理Aだけで到達可能とする。
処理Bを用いて、T→Uの手順を逆にたどればU→Tに到達可能である。
よってS→U→Tという遷移が可能となる。
あとは、そのようなUを作ればよいだけである。
実はこの問題はDiv2 Mediumと同じで、ある1個のスロットにすべての石を集めるという手順は容易に求まる。
集める先以外のスロットに対し、処理Aを繰り返すだけでよい。
class ReverseMancala { public: int N; vector <int> findMoves(vector <int> S, vector <int> T) { int N=S.size(); vector<int> R,R2; int tot=accumulate(ALL(S),0); int i; while(S[0]!=tot) { for(i=1;i<N;i++) if(S[i]) { R.push_back(i); int v=S[i]; S[i]=0; int j=(i+1)%N; while(v) S[j]++, v--, j=(j+1)%N; } } while(T[0]!=tot) { for(i=1;i<N;i++) if(T[i]) { R2.push_back((i+T[i])%N+N); int v=T[i]; T[i]=0; int j=(i+1)%N; while(v) T[j]++, v--, j=(j+1)%N; } } while(R2.size()) R.push_back(R2.back()),R2.pop_back(); return R; } }
まとめ
450ptのMediumでもよかったかもね。