ちょっと整理が大変な複雑な問題。 問題へのリンク 問題概要 ルーレットによって 0 から 36 までのいずれかの整数が出される。 人 はどの整数が出されるかを賭けた。人 は 個の整数 にかけた。 実際に出た整数は であった。 に賭けていた人のうち、賭けた整…

が関係ないやんけ！ 問題へのリンク 問題概要 高橋君は街 の順に訪れる。街 ではりんごの価値は 円である。 高橋君は街 で 円でりんごを好きな数だけ買うことができて、 を満たす街 でそのりんごを好きな数だけ 円で売ることができる。ただし、高橋君はりん…

「最適解の個数」を求めるという超典型！ 問題へのリンク 問題概要 頂点数 、辺数 の単純無向グラフが与えられます。 頂点 から頂点 へと至る最短経路の本数を 1000000007 で割った余りを答えてください。 制約 解法 最短路を求めるだけならば、BFS を使うこ…

ネットワークフローアルゴリズムの構造をちゃんと理解しているかを問う良問ですね！！ 問題へのリンク editorials 問題概要 頂点数 、辺数 の有向グラフ と、2 頂点 が与えられます。 いま、グラフの辺を 1 本選んで向きを反転させます。それによって、- 間…

一見すると典型的な「座標圧縮」+「二次元いもす法」なのだが、それだと TLE / MLE してしまう。 ジャッジへのリンク 問題文へのリンク 問題概要 のグリッド上に 枚の長方形の紙を敷いていく。 枚目の紙は を満たす座標 を覆う領域に配置される。最も多くの…

マージテク童貞を卒業した！！！ 問題へのリンク 問題概要 頂点の根付き木が与えられる (根の番号は 1)。また各頂点 には色 が塗られている。色は整数値で表される。各頂点 について、以下の問いに答えよ。 その頂点を根とした部分木を考える その部分木で「…

きっかけは、タピオカ流競プロ優勝ガール、マリーさんのツイートでした。 100個ぐらいある整数から自由に選んでK円になる組み合わせを探せ！複数通りある場合は列挙！みたいな仕事がだるすぎてdpで列挙してくれるやつ作った競プロは事務員を救う— マリー (@C…

これは単に二項係数知っているかを問う感じ...？ この頃と今とでは、多少問題傾向も違う気がする。 問題へのリンク 問題概要 個の数値が与えられる。このうち 個以上 個以下を選ぶときのその平均値の最大値を求めよ。 また最大を達成する選び方が何通りある…

今回は Suffix Array でやってみたけど、ローリングハッシュとか、KMP とか、Z-Algorithm とか、色んな方法があるみたいなので追々やってみたい。 → やってみた (3/14) 問題へのリンク 問題概要 文字列 がよい文字列であるとは「いかなる文字列 および 2 以…

まさにこれだったん。 CSA 069 DIV2 C Build Correct Brackets ()()))(())() のようなカッコ列が与えられる。 最小回数flipして正しいカッコ列にせよ。 また最小回数flipで正しいカッコ列にする方法の数を数え上げよ。 ・1 <= 文字列長 <= 2500 まさに最短路…

ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp…