問題 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][…