競プロ
問題のリンク 問題概要 $N \times N$ のグリッドにルークを互いに攻撃し合わないように配置する。ただし、斜めに隣接するルークのペアが丁度 $ K $ となる配置の数を $10^{9}+7$ で割った余りを求めよ。 制約 $1 \leq N \leq 1000$ $0 \leq K \leq N-1$ 解法…
今日のCFは良いとこ無し…。
問題のリンク Twitterで教えて貰ったのでブログに残そうと思います。
問題のリンク
本番ではLCAをゴチャゴチャして解いた。
TLで流れていた解法よりも直感的に理解しやすい(と個人的に思っている)のでメモ
問題のリンク
問題のリンク
問題のリンク 問題概要 $N$ 種類の1ドル切手と $ M $ 種類の2ドル切手が販売されている。丁度 $K$ ドル使うような切手の買い方の総数を素数 $ P $ で割った余りを求めよ。 ただしどの種類の切手も無限に存在するとして良い。 制約 $1 \leq N,M \leq 300$ $1 …
問題のリンク 問題概要 自然数 $N$ が与えられる。次の条件を満たす自然数 $(i,j)$ の組の総数を求めよ。 $1 \leq i,j \leq N$ $\frac{i}{i+1} \cdot \frac{j+1}{j}$ と $ \frac{m}{m+1} $ が等しくなる自然数 $ m $ が存在する 制約 $1 \leq N \leq 10^{6}$…
問題のリンク 問題概要 長さ $N$ の数列 $ A _ {i} $ が与えられる。数列の値を $1$ 変更するのにコスト $1$ がかかる。この数列を狭義単調増加列にするのに必要な最小コストを求めよ。 制約 $1 \leq N \leq 3000$ $1 \leq A _ {i} \leq 10^{9}$ 解法 CFブロ…
問題のリンク 問題概要 次の条件を満たす有向グラフを一つ出力せよ。ただし解の存在は保証される。 $N$ 頂点のDAGである 多重辺や自己ループは含まれない 頂点 $ M $ から頂点 $i$ への経路の総数は $D _ {i}$ に等しい 制約 $1 \leq N \leq 60$ $1 \leq M \…
問題のリンク 問題概要 次の条件を全て満たす、長さ $N$ の文字列をRSBS文字列という。与えられる文字列の subsequence であって、RSBS文字列であるものの個数を $10^{9}+7$ で割った余りを求めよ。 長さ $N$ が偶数である 前半 $\frac{N}{2}$ 個は全て '(' …
問題のリンク 問題概要 1日につき $K$コアを必要としている。次の $ M $ 個の契約のうち任意の組合せを選択できる時、$N$日間における最小コストを求めよ。ただし、その日にレンタル可能なCPUが $K$コアに満たない場合、全てと契約するものとする。 契約毎に…
過去記事の修正版です
問題のリンク 問題概要 $N$ マスのすごろくを2人で遊んでいる。サイコロは等確率で $1$ から $d$ までの目を出し、出た目の数だけマスを進める。ただし、ゴールを超える場合はその分だけ折り返す。 先手と後手の現在位置はそれぞれ $x,y$ で、今先手の手番で…
問題のリンク 問題概要 $N$ 頂点 $M $ 辺からなる重み付き有向グラフが与えられる。 頂点1 から頂点2 まで向かいたいが、辺のうち1本が通行不可になっている。通行不可になっていることは辺の始点に訪れるまで知ることができない。 最悪ケースでの総移動距離…
問題のリンク 問題概要 次の条件を満たす順列の総数を $998244353$ で割った余りを求めよ。 長さが $N$ である $K \leqq i \lt N$ を満たす全ての $i$ について、前 $K$ 個の最小値よりも $i$ 番目の値の方が大きい 制約 $1 \leqq N \leqq 10^{7}$ $1 \leqq …
問題のリンク 問題概要 $N$ 個の電球と $N$ 個のスイッチがある。スイッチは1つに限らず複数の電球に接続していることがあり、この情報は入力で与えられる。この電球は、接続してるスイッチのうち奇数個のスイッチがonになっている場合に限り点灯する。 全て…
問題概要 $1$ から $2N$ の数字の中から7つ選び出して6角形グリッドに書き込む。 隣接する全てのペア $a$, $b$ について $a \bmod N \neq b \bmod N$ が成立するような書き込み方の総数は何通りか求めよ。ただし回転して一致するものは同一とみなす。 制約 $…
問題のリンク 問題概要 $T$ 個のクエリ毎に $N$ が与えられるので以下について求めたい。 $ \frac{1}{N}$ を循環小数で表した時の循環節の長さ 制約 $ 1 \leqq T \leqq 100$ $ 1 \leqq N \leqq 10^{9}$ 解法 分母の値にに2や5をかけても循環節の長さは変わら…
問題のリンク 問題概要 頂点辺からなる単純グラフが与えられる。次の条件のいずれかを満たすような部分グラフを1つ求めよ。存在しない場合は-1を出力。 部分グラフ内の全ての頂点が少なくとも個以上の隣接する頂点を持つ サイズのクリークである 制約 解法 …
問題のリンク 問題概要 のグリッドが与えられ、このグリッドを上下左右方向に傾けてタイルを動かす操作を行う。操作列は、(操作)*数字のように圧縮された状態で与えられる。最終的なタイルの状態を求めよ。 制約 解法 タイルに書かれた文字を無視すると、一…
問題のリンク 問題概要 クエリ毎にN個の区間が与えられる。次の条件を満たす区間の部分集合のサイズの最大値を求めよ。 部分集合内の任意の区間のペアについて、どちらかが片方を完全に包含している。または共有点を持たないかのいずれかが成立する。 制約 …
問題概要 始め頂点(0,0)にいる。1回の操作で隣接する格子点を1つ選んで移動することができる。ただし、 かつ を満たす範囲には障害物があり移動することが出来ない。 回以内の操作で到達可能な格子点の総数を求めよ。 制約 解法 まず障害物が無い時を考える…
問題のリンク 問題概要 内接円の半径がRとなるような、辺の長さが全て整数の三角形を全て求めよ。 制約 考察 内接円の半径と三角形の3辺の長さの関係を知りたい→面積についての等式を立てる 三角形の3辺の長さをとします。この時ヘロンの公式を用いると、 と…
問題のリンク 問題概要 N個の景品から成るコンプガチャがあり当選確率はいずれも同様に確からしい。全ての景品をM個以上手に入れるまでの操作回数の期待値を求めよ。 制約 解法 が小さいのでのDPが間に合う。 を1個揃ってるのが 種類、2個揃ってるのが 種類…
問題のリンク 問題概要 N×Mのグリッドが与えられ、その内幾つかのマスに数字の書かれたタイルが置かれている。このグリッドに対して左詰め右詰め上詰め下詰めの操作を好きな順番で好きな回数行える。初期盤面は左下詰めで与えられる。左下詰めの盤面の状態で…
これのK問題を解いたので、解法のメモを残します。 問題概要 2*Nのグリッドが与えられ、好きな点を一つ選びそこから縦横斜めに隣接する一つのマスを選んで移動する、ただし同じ頂点は二度通ることができない。この時全てのマスを丁度一回通るような移動の総…
問題のリンク 問題概要 匹のうさぎの徒競走について、 のうさぎは のうさぎよりも先にゴールしたという情報が 個与えられる。 この時徒競走の順位として矛盾しないものの総数を求めよ。 解法 与えられる情報を有向グラフとして捉えると、トポロジカルソート…
