ferinの競プロ帳

競プロについてのメモ

SRM

SRM716 div2 hard

概要 最初のm個がp[i] != iとなっているという条件を満たす長さn+mの順列pの個数をmod 10^9+7で求める。 解法 条件がなかったとしたら順列の個数は(n+m)!となる。次にm個のうち1個が条件を満たしていない個数を考える。m個の中から1個を選び、残りのm+n-1個…

SRM 716 div2 med

概要 文字列sと文字列tが与えられる。sの各文字をtの文字で置き換えることができる。tの文字はそれぞれ1回ずつしか使用できない。書き換えた後の辞書順最大となるsを出力する。 解法 先に現れる文字を大きいものにしたほうが辞書順としては後のものになる。…

SRM 717 div2 easy

概要 要素が0か1の2次元配列tが与えられる。x[i] xor y[j] == t[i][j] となる要素が0か1の配列x、yを構成することが可能か判定する。与えられる配列のサイズは5×5以下。 解法 1行目(y[0])を0か1で固定すれば残りの列の数字(x[i])は一意に定まる。残りの行に…

SRM 710 div2

Easy 問題概要 解法 Med 問題概要 解法 Hard 問題概要 解法 Writerの方の解説 codeforces.com Easy 問題概要 n要素の配列Aが与えられる。この配列の部分列の和を最大化したい。ただし、配列の最初の要素のA[0]を選択した場合、部分列の和の正負を反転させる…