問題のリンク 問題概要 $N \times N$ のグリッドにルークを互いに攻撃し合わないように配置する。ただし、斜めに隣接するルークのペアが丁度 $ K $ となる配置の数を $10^{9}+7$ で割った余りを求めよ。 制約 $1 \leq N \leq 1000$ $0 \leq K \leq N-1$ 解法…

TLで流れていた解法よりも直感的に理解しやすい(と個人的に思っている)のでメモ

問題のリンク 問題概要 $N$ 種類の1ドル切手と $ M $ 種類の2ドル切手が販売されている。丁度 $K$ ドル使うような切手の買い方の総数を素数 $ P $ で割った余りを求めよ。 ただしどの種類の切手も無限に存在するとして良い。 制約 $1 \leq N,M \leq 300$ $1 …

問題のリンク 問題概要 次の条件を全て満たす、長さ $N$ の文字列をRSBS文字列という。与えられる文字列の subsequence であって、RSBS文字列であるものの個数を $10^{9}+7$ で割った余りを求めよ。 長さ $N$ が偶数である 前半 $\frac{N}{2}$ 個は全て '(' …

問題のリンク 問題概要 次の条件を満たす順列の総数を $998244353$ で割った余りを求めよ。 長さが $N$ である $K \leqq i \lt N$ を満たす全ての $i$ について、前 $K$ 個の最小値よりも $i$ 番目の値の方が大きい 制約 $1 \leqq N \leqq 10^{7}$ $1 \leqq …

問題概要 $1$ から $2N$ の数字の中から7つ選び出して6角形グリッドに書き込む。 隣接する全てのペア $a$, $b$ について $a \bmod N \neq b \bmod N$ が成立するような書き込み方の総数は何通りか求めよ。ただし回転して一致するものは同一とみなす。 制約 $…

問題のリンク 問題概要 N×Mのグリッドが与えられ、その内幾つかのマスに数字の書かれたタイルが置かれている。このグリッドに対して左詰め右詰め上詰め下詰めの操作を好きな順番で好きな回数行える。初期盤面は左下詰めで与えられる。左下詰めの盤面の状態で…

リンク atcoder.jp 問題概要 N個のマスがあり最初はどのマスにも積み木は乗っていない。N個のマスのうち積み木が最小のマスを一つを選んで、現在の積み木の高さのMAX~MAX+Dの高さの好きな高さまで積み木を載せる操作を行う。N個のマスの積み木の高さが全てH…

これのK問題を解いたので、解法のメモを残します。 問題概要 2*Nのグリッドが与えられ、好きな点を一つ選びそこから縦横斜めに隣接する一つのマスを選んで移動する、ただし同じ頂点は二度通ることができない。この時全てのマスを丁度一回通るような移動の総…

問題のリンク 問題概要 匹のうさぎの徒競走について、 のうさぎは のうさぎよりも先にゴールしたという情報が 個与えられる。 この時徒競走の順位として矛盾しないものの総数を求めよ。 解法 与えられる情報を有向グラフとして捉えると、トポロジカルソート…