久々のratedコンテストに出た。

問題のリンク 問題概要 $N$ マスのすごろくを2人で遊んでいる。サイコロは等確率で $1$ から $d$ までの目を出し、出た目の数だけマスを進める。ただし、ゴールを超える場合はその分だけ折り返す。 先手と後手の現在位置はそれぞれ $x,y$ で、今先手の手番で…

問題のリンク 問題概要 $N$ 頂点 $M $ 辺からなる重み付き有向グラフが与えられる。 頂点1 から頂点2 まで向かいたいが、辺のうち1本が通行不可になっている。通行不可になっていることは辺の始点に訪れるまで知ることができない。 最悪ケースでの総移動距離…

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

問題概要 始め頂点(0,0)にいる。1回の操作で隣接する格子点を1つ選んで移動することができる。ただし、 かつ を満たす範囲には障害物があり移動することが出来ない。 回以内の操作で到達可能な格子点の総数を求めよ。 制約 解法 まず障害物が無い時を考える…

問題のリンク 問題概要 N個の景品から成るコンプガチャがあり当選確率はいずれも同様に確からしい。全ての景品をM個以上手に入れるまでの操作回数の期待値を求めよ。 制約 解法 が小さいのでのDPが間に合う。 を1個揃ってるのが 種類、2個揃ってるのが 種類…