問題 atcoder.jp 解法 k=0における転倒数はBITで求められる。 $a_i$にkを足してmodNをとるという操作は、数列の先頭の要素が削除されて最後尾に追加されるという操作と等しい。 $a_i$ が削除されると転倒数が$a_i$減り（$a_i$を転倒数として数えられるのは、…

問題 https://atcoder.jp/contests/typical90/tasks/typical90_h 解法 DPで解く。基本的な考え方はナップサック 問題と同じで、dp[i][j]:=i番目まで見て、状態jとなる個数の数え上げとする。 文字列t="atcoder"とした時、遷移先は以下の２通り。 dp[i+1][j]+…

問題 atcoder.jp 解法 各桁をどの順番で足し合わせても答えは変わらない 桁を2つ選んで足し合わせたとき、繰り上がりが起きない場合は桁が一つ減り、起きる場合は桁はそのままで桁和が9減る。 桁上がりが起きる回数は(桁和-1)/9回 コード int main(){ int n;…

問題 atcoder.jp 解法 数列の要素が隣り合うm-1か所について、数字の差がdになる確率を考える。 2個のサイコロを振って差がdになる確率は、 どの箇所も確率は等しいので、上記で求めた確率をm-1倍する。 コード int main() { ll n,m,d; cin >> n >> m >> d; …

問題 atcoder.jp 解法 範囲を列挙してそこに含まれる2番目に大きい数を探すのではなく、順列の値X[i]それぞれに対してX[i]が2番目に大きくなるような範囲を数え上げる X[i]より大きい値を一つだけ含み、j<=iとなる最小値jを求める。また、X[i]より大きい値を…

問題 atcoder.jp 解法 各数字を目的の位置に移動させるためには、素直にswapするしかない。 1から順番にswapしていけばいい。いくら他の数字をswapしていも、結局1を1番目にするという操作は必要。 得られた操作手順を確認し、重複がある場合やちょうどn-1回…

問題 atcoder.jp 解法 ゲーム開始からの経過時間をT分として T×P枚のコインの支払いが要求される→一回の移動で獲得できるコインの枚数をすべて-Pすればよい。 獲得できるコインの枚数を負にした値を移動コストと考えれば、最短経路問題となる。 頂点1からNま…

問題 atcoder.jp 解法 各行(列)の中で、最も左(上)側にある白マスの位置を効率よく管理する。 ax[i]:i行目で最も左側にある白マスの座標 ay[i]:i列目で最も上側にある白マスの座標 入力例1での説明。初期状態では、白マスはそれぞれ行列の右下端の置かれてい…

問題 atcoder.jp 解法 生徒の合流をUnionFind木で管理する。 各生徒の集合状態をmapで管理し、生徒たちが合流したときにmapをマージする。 このとき、mapの小さいほうから大きいほうへマージすることで、マージに必要な計算量を抑えることができる。 「デー…

問題 atcoder.jp 解法 メモ化しながら再帰的に解く。 s="RPS", k=4の例。 トーナメント参加者の出す手は文字列sを周回して決まっていくため、同じパターンが出現する。 テーブルを以下のように定義し、一度計算した値を格納していく。 dp[k][i] = f(dp[k-1][…