解説 できるだけ一文字目の方に大きい文字(z,y,x,...,a)を作っていく。繰り上げしていくイメージ。 Ai C[S_i] + Ai+1 C[S_(i+1)] => Ai (C[S_i] + A) + Ai+1 * (C[S_(i+1)] - 1)。 N文字目から繰り上げできるだけしていく。 コード #include <algorithm> #include <cstdio> #inc</cstdio></algorithm>…

解説 a,...,zを頂点としてトポロジカルソート。 頂点数が少ないので、O(N3)のアルゴリズムでOK。 トポロジカルソートの参考サイト。 Topological sort コード #include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #</stack></sstream></set></queue></cmath></map></iostream></cstdio></algorithm>…

解説 dp[i][j] = i人未満のグループのみで、j人を分ける通り数とする。 このようにdpを定義すると、dpの更新式は以下のようになる。 i人のグループを一個も作らないとき、 残りのN-j人のうち、i人のグループをk個作るとき、 で割るのはグループを区別しない…