貪欲法

ABC173E 解法 マイナスの個数に気を付けて貪欲にとる． 最初は 0 は除外して考えると楽． 今回は，0 を正に含めば大丈夫． \(K\)個の積を 0 以上にできるかで場合分け． 0 以上に出来るときは abs が大きくなる様にとればよいし， 出来ないときは abs が小さくなる様にとればよい． 0 以上に出来るかどうかは，マイナスから2個ずつ選ぶ貪欲法で判定できる． 2個ずつペアにしていき，残った物を 0 以上から選べ場良い． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main()…

ABC332C 解法 シミュレーションというか，貪欲法． 気を付けることは， 無地のシャツを買う必要はないので，足りないときは印刷されてる方だけ買う． 洗濯したら枚数を回復するので，今持っているシャツの枚数をそれぞれ記録しておく． 最後に，印刷したシャツの枚数が，買った枚数の答え． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n,m; cin >> n >> m; string s; cin >> s; ll x_ma = m, y_ma = 0; ll x = m…

ABC329E 解法 操作を逆に行う． 文字列\(S\)からスタートして，\(S\)を ##...# にする． # はワイルドカードだと思ってよい． つまり，何が入っていいても良い文字と考える． \(S\)において，文字列 \(T\) を連続部分列として含むかどうかを判定して， 含む場合は # で置き換える． # がワイルドカードであることから， 置き換えが可能な場所はすぐに置き換えてよい． 次に，更新すべき箇所を減らすことを考える． \(S\)における \(i\)番目から \(T\)で置き換えた場合， 同じ \(i\) に対しては操作をする必要がない． また，# で置き換えた場合，新しく置き…

ABC236F \(V := (\mathbb{F}_{2}\) における \(N\) 次元ベクトル空間) の基底を求める問題． コストの小さいほうから貪欲に選んでいく． コストを無視すれば，吐き出し法で基底は求まる． \(b\) を 1次独立な vector の集合として，\(V\) を span できるまで vector を追加する． 今調べている vector \(v\) が \(Span(b)\) に含まれていれば何もしない， そうでなければ \(v\) を \(b\) に追加する． コストが有る場合も，コストが小さい方から vector を貪欲に選べばよい． 実装\(b\) の中は順…

ABC312F 3つタイプがあるが，いずれも貪欲に取れる． どれか一つを全探索しよう． 缶切りを使わない缶全体， 缶切りを使う缶全体， 缶切り全体 をそれぞれ \(a,b,c\) とおく． \(a,b,c\) を全てソートしておく． \(a\) を全探索する． \(i \in size(a)\) に対して，\([0,i)\) まで使ったとする． このとき，\(b,c\) からどちらを選ぶべきかは貪欲に決まる． 缶切りが残っていれば \(b\) から買えばよい． 残ってなければ，\(c\) から買って缶切りを補充． 実装するときは，\(b,c\) が空になる場合に注意． 使っている記号，マクロ等…

ABC181E 先生の身長を固定して考えて，\(h\) に追加しておく． このとき，ペアの作り方の最適解の一つは， ソートした \(h\) に対して先頭から貪欲に 2人ずつ組んでいく方法が挙げられる． それが解ければ，あとは先生の身長を全探索すれば OK. 前もって \(h\) をソートしておくことと， \(h\) のペア達の累積和を前もって計算しておくことで， クエリ毎に \(O(log (h.size))\) で答えられる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() {…

はじめに この記事でやること 注意点 （前半）マトロイドと貪欲法 マトロイドの定義 【定義 1.1.1】*2 マトロイドに関する用語 【定義 1.2.1】 【定義 1.2.2】 【定義 1.2.3】 【定義 1.2.4】 【命題 1.2.5】*3 マトロイドと貪欲法 【定義 1.3.1】 【定義 1.3.2】 【定義 1.3.3】 【定義 1.3.4】 【定理 1.3.5】 【定理 1.3.6】 【定理 1.3.5】の証明 【補題 1.4.1】 【定理 1.3.6】の証明 【補題 1.4.2】 （後半）マトロイドのクラスカル法への適用 ベクトルマトロイド 【命題 2.1.1】 グラフのマトロイ…