ABC040D グラフとクエリがあるが，いずれも年に関して降順ソートする． ソートすることで，クエリ毎にUnion-find を作り直す必要が無くなり， 同じUnion-find を使いまわせる．年が同じときは，クエリに答える方を，Union-find の merge より先に行う． 使っ…

ABC038D \((w,h)\)の組を考える． 基本的にはソートして考える．\(dp_{i} := \{dp_{j} \vert w_{j} < w_{i} \ and \ h_{j} < h_{i} \}\). ここで \(w\)が昇順にソートされているとする． 整数全体が全順序であることから， \(j < i \iff w_{j} < w_{i} \). …

本問: M - おまかせ 類題: D - 食塩水 平均の最大化は binary search.\(f_{x} \in Bool\)を，\(x\)以上にできるときtrue, そうでないときにfalse とする．お助け無しの場合 \(\sum_{i \in K} \frac{b_{i}}{a_{i}} \geq x \iff \sum_{i \in K} (b_{i} - x a_{…

C - Cash Register シュミレーションする問題． 基本的にはキーを一つ押すと1つindexが増える．文字列に0が並んでいるときだけ，1回押すと2つindexが増える． typedef long long ll; int main() { ll n, m, k, q; string s; cin >> s; n = s.length(); ll c …

集合 自然数に対して， により を表す．この表記を使っている人は見かけないが，便利だと思っている． cpp のマクロ等 typedef long long ll; const ll INFL = 1LL << 60; using vll = vector<long long>; using vvll = vector<vll>; using pll = pair<ll,ll>; #define srep(i,s,t) </ll,ll></vll></long>…

C - ハイスコア 0-indexed で考える． で を表す． imos法区間 に対して得点 が対応している．もしからまでの全ての値を，選んだ区間で覆うと得点は0.また，0点より大きい得点が欲しければ，一か所でも覆えていなければよい．この場合，選んだ区間のたちの和…

D - 徒競走 トポロジカルソートの場合の数を数え上げる問題．これはDPで可能． を頂点集合の部分集合とする．をトポロジカルソートする場合の数，を，の元のうち，出次数が0の頂点全体とする．の元 に関して場合分けして数え上げる．を一番端にもってくる場…

D - 大ジャンプ 縦と横を独立に解くことと，全探索する部分を決める方針． 問題を簡単にする (i) d = 1 に帰着 (x,y がともに d の倍数)でなければ不可能．(x,yがともに ｄの倍数)のとき，x,y を d で割ることで d = 1と仮定してよい． 今回は関係ないが，最…

D - トランプ挿入ソート 操作をまとめる 同じカードを選ぶ意味は無いので，各カードに対して高々1回としてよい． (1枚抜く) -> (1枚入れる) -> (1枚抜く) -> (1枚入れる) -> ... の操作列だが順序を入れ替えて，カードをまとめて抜く，まとめて入れるとして…

D - 禁止された数字 整数をvector に入れて桁DP. 部分問題として，区間 ] に対する答え を求める． これが出来れば，元の問題に対する答えは . 今回の桁DPは上の桁から調べていく．下の桁から決めるケースもあるが，多くの場合は上から決めれば良い． 桁目ま…

E - Shiritori 3しりとりのルールから，最初の3文字と最後の3文字が重要になる．それらを頂点として，高橋辞書に登録された文字列を辺とみたグラフを考える． ゲーム理論の問題では，・ルールに従った移動を辺で表して，現在の局面を頂点で表す・勝敗が決ま…

E - Sugoroku 4 確率dp. を と書く． に対して， とする． for を回すとき，移動した回数 を一番外側に持ってくることに注意． dp では，すでに正しく求まっている計算を利用して次を求めるため． 回目を求めるには， 回目が正しく求まっている必要がある． …

F - Erase Subarrays 残す場所をo, 消す場所をx と考えて，ox 列を作る． 連続する x のブロックの個数を数えるが，それは ox が連続している場所の個数と一致． ただし，形式的にの前にo があるものと考える． としてdp. typedef long long ll; const ll IN…

D - Equal Cut 4つに分割する，つまり境目は3か所． 3つの場合は，真ん中を全探索して残りを高速に求めるケースが多く，今回もそれ． 分割する場所を左から l, i, r とおいて，i を全探索． 2分探索で，残りの2か所を求める． ・なるべく均等に分割するのが…

D - Built? 余分に辺を追加する必要はないから，最小全域木を求めればよい． このままだと辺の本数がO(N^2)であるから，辺を減らすことを考える． 隣同士の辺しか使う必要がないため，辺の本数がO(N)となって間に合う． 実装は，tupleを用いて <x,y,index> , <y,x,index> を lex or</y,x,index></x,y,index>…

ABC282D atcoder.jp DFSで連結成分ごとに計算する． 与えられたグラフに対して，すべての連結成分が2部グラフになっている必要がある．なぜなら，辺を追加して2部グラフなら，追加する前に2部グラフになっている必要があるため． DFSにより，2部グラフか判定…