ACL Beginner Contest F - Heights and Pairs (橙色, 600 点)

こういうのは包除原理しかない！問題へのリンク問題概要人の人がいる。人の身長はである。以下の条件を満たすように、組のペアを作る方法は何通りあるか、998,244,353 で割ったあまりを求めよ。どの人もちょうど一つのペアに含まれる。どのペアも、…

ACL Beginner Contest E - Replace Digits (青色, 500 点)

まさに遅延評価セグメント木の練習問題！！！問題へのリンク問題概要長さの文字列 S がある。最初はのすべての文字が 1 である。以下の回のクエリに答えよ。各クエリは整数が与えられる () の番目から番目までをすべてに書き換えるを数値とみな…

AtCoder AtCoder400点 ABC-D ABC-like DP DP高速化 in-place DP DP高速化:セグメント木数列転倒数制約:数値が10^6以下バケット部分列セグメント木データ構造水色diff

LIS を求める in-place DP を応用すればできる！でも、400 点問題で「DP 配列をセグ木に乗せて」「in-place に更新することで高速化する」という問題が出るとは思わなかった！ in-place DP に馴染みのない方は先にこっちを qiita.com 問題へのリンク問題概…

AtCoder AtCoder300点 ABC-like ABC-C Union-Find 連結成分 DFS BFS グラフデータ構造茶色diff 【問題集】グラフの入門そのまま覚えたい典型問題

Union-Find の練習問題という雰囲気ながら、DFS や BFS でも解ける問題へのリンク問題概要頂点数、辺数の単純無向グラフが与えられる。これに最小本数の辺を追加することで全体が連結となるようにしたい。その最小本数を求めよ。制約考えたこと全体…