はじめに 累積和高速化型貰うDPの添字に苦しめられたことはありませんか？私はあります。 なんと、貰う配る変換をしなくても、配るDPのまま高速化できるデータ構造があります。その名も Shuz* 木！（勝手に名付けた） といっても非直感的なので係数セグ木と…

問題 void f(unsigned int x, unsigned int y, unsigned int z) { if (!x || !y || !z) return; f(x / 2, y, z), f(x, y / 2, z), f(x, y, z / 2); } この関数の計算量を解析せよ。 ▽正解（クリックして展開）

たくさんの空でない開区間を乱数で生成したいとき、l = rand([0, N - 1]), r = rand([l + 1, N]) としていないだろうか？これでは分布に偏りが生じてしまう。例えば、 の出現確率は の出現確率の になってしまう。これを避けるには、 l = rand([0, N]) r = r…

概要 NavigationLinkで, 例えばpresentationMode.wrappedValue.dismiss()をした直後にタスキルすると親Viewが初期化される. 他にもいくつかのタイミングでNavigationViewに限らずViewが初期化され, .onAppear()も同時に呼ばれるので, Viewにデータを保存して…

TL;DR NavigationView { } の下に .navigationViewStyle(StackNavigationViewStyle()) を追加しましょう. 経緯 タイトル付きで NavigationView 使うと発生して邪魔. iPad に localize していたら解決法がわかった. 急募 [LayoutConstraints] (ActionSheet) …

atcoder.jp なんか同じ考え方の人が全然いないので書きます とすれば, 遷移は高々「被覆を開始する」「被覆を終了する」だけになるので, disjointに気をつけてDPして終わりです int main() { int N; cin >> N; int A[N]; rep(i, N) cin >> A[i]; mint DP[200…

まえがき このように、直感に頼った未証明のGreedyは危険です。 概要 状態に対してコストが定まるような状況を考える. コストが最小になるための状態の必要十分条件を とする. このとき, 以下のいずれかを仮定できるなら, 条件 を の必要条件に代るものとし…

1:09 4完 ちょっと参加が10分くらい遅くなってしまった。 Aを見る。ただでさえ問題文がわかりにくい上、変数が衝突していて読み解くのに時間がかかったが、適当に交互にすると問題の性質を満たすと分かったので提出。 (0:16 WA) ソートを忘れていたのでなお…

2:01全完←間に合ってない Aを眺めると数学 なので提出する (0:01 AC) Bの制約を眺めると優先度付きキューでシミュレーションしたら通りそうなので提出する (0:07 AC) Cを見て、なんか面倒そうなので先にDを見る Dを見ると、ただのエラトステネス+累積和なの…

No.944 煎っぞ! - yukicoder 問題概要 をいくつかに区切ってすべての区間和を等しくするとき、区切った区間数の最大値を求めよ。 解法 Writer解とは違うアプローチをしたので軽く解説する。 まず、最も左の区間を決め打ちすると、その区間は全部で 個存在す…

Minimum(Maximum) Scalar Product 与えられた つの実ベクトル に対して適当な を選び、 を最小・最大化する問題。解法は、最小の場合は をそれぞれ昇順、降順に、最大の場合は をそれぞれ昇順にソートするだけである。 蟻本に証明が載っているが、ちょっとだ…

はじめに 木の最大マッチングとは、直接辺で結ばれたいくつかの 頂点の組 ( 「ペア」と呼ぶ ) からなる集合であって、どの頂点も高々 つのペアに属するようなもののうち、もっともペアの多いものを言う。ここでは、木の最大マッチングが、再帰的に葉を選ぶこ…

No.10 ＋か×か - yukicoder 問題概要 列に並んだ数列 を順番を変えずに加法・乗法で結び、 に等しくなるように式を作る。ただし演算は左から順に行うものとし、辞書順最小の演算子列を求める。 解法 文字列を持ってDP。計算量がちょっとだけ大きいがまあ間に…

No.9 モンスターのレベル上げ - yukicoder 問題概要 味方モンスター(レベルはそれぞれ )を以下の方法でレベル上げするとき、各味方モンスターのレベル上げ最大回数の最小を求める。 最初に、円形に並んだ敵モンスターの始点を定める。 始点から順(添字の昇順…

No.6 使いものにならないハッシュ - yukicoder 問題概要 で素数の連続部分列のうち、桁和ハッシュ( 桁になるまで行う)が衝突しない最大のものを求めよ。 解法 しゃくとり実装面倒だったのでズルをした。素数の個数が対数オーダー、かつハッシュがたかだか 種…

No.2 素因数ゲーム - yukicoder 問題概要 からはじめて、二人交互に、素因数を一つ決めて任意回数ずつ割っていく。先に にした人の勝ち。 解法 典型。素因数分解した後、NimのXOR判定条件を用いる。 struct Factor { inline vector<ll> factorize(ll N) { vector<ll></ll></ll>…

今日から、yukicoderの星 〜 を全埋めしていこうと思います。 No.1 道のショートカット - yukicoder 問題概要 辺のコストが費用、距離の つあるDAGにおいて、費用が 以下になるように頂点 から頂点 へ移動する(距離の)最短経路を求める。 解法 典型。状態 (…