2021-03-22から1日間の記事一覧
「決めてから、整合性を確認する」というタイプの問題の典型例ですね! 問題へのリンク 問題概要 の非負整数を成分とする行列 が与えられる。 すべての について を満たすような非負整数列 と の組が存在するか判定し、存在するなら一つ出力せよ。 制約 考え…
AtCoder
AtCoder500点
茶色diff
彩色問題
Dilworthの定理
DAG
最大安定集合問題
数学(整数問題)
クリーク
最適化テク:自明な上界が最適解
素因数分解
mex
グラフ
構築
どれか1つ求める
数列
復元
最大値の最小化
非自明な線形時間
ARC-C
これ茶色はさすがにびっくりした! 問題へのリンク 問題概要 整数 が与えられる。 正の整数からなる数列 であって、 が の約数であるような任意の に対して という条件を満たすものを考える。そのような数列のうち、数列に登場する値の最大値が最小となるよ…
AtCoder
AtCoder600点
ARC-D
黄色diff
グラフ
木
グラフの辺数を削減する
全域木を考える
数え上げ問題
各kに対して
制約条件:グラフの次数列
パリティ
実験
FFT
二分木のような計算順序
priority_queue
連結成分
数学的帰納法に基づく考察
二項係数
サイクル
XOR
Greedy
「選ぶ」と「選ばない」の一対一対応
連結成分ごとに分解して考える
分割統治法
なんとか解けた。若干エスパー気味に解いた。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられる。 各 に対して、この誘導部分グラフ (頂点集合はそのまま、辺集合は部分集合) であって、次数が奇数の頂点が 個であるようなものの個数を …