水色diff

このタグの解説について

この解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

競技プログラミング日記•3年前

AtCoder Regular Contest 111B

ARC111B カードの表裏に書かれた数字を頂点として，カードを辺とみなしたグラフを考える．カードの表裏を選ぶ事は，辺に向きを付けることとみなす．連結成分毎に考えればよい．連結成分をtreeの場合を先に解いて，そうで無い場合はtree に帰着させる．連結成分を固定し，頂点の個数を個とする． (i) がtreeのとき根を一つ任意にとる．DFSをして，親から子に向かって辺に向きをつければ，根以外の頂点個をすべて選べる．また，辺が個なので，に対してはこれが最大． (ii) がtreeでないとき全域木をとることで treeに帰着させたい．全域木以外に1つ以上辺があるので，…

#AtCoder#AtCoder Regular Contest#水色diff#サイクル検出

関連ブログ

競技プログラミング日記•3年前

AtCoder Beginner Contest 270D

ABC270Dmin-max法．まず，簡単な問題を考える．何個取れるのかは無視して，先手が必勝か必敗か引き分けかを判定する．先に判定問題を解いて，それを改良する手法はよくある．判定問題 := (先手の取った石の個数) - (後手の取った石の個数)を考える．最善を尽くすとは，先手はを最大化して，後手は最小化すること．ゲームが終わった段階でなら先手必勝，なら必敗，なら引き分け，と判定できる．最大値問題判定問題では，最善を尽くしたときにという情報しか持っていないから，判定しかできなかった．そこで，先手の石の個数と，後手の石の個数も持っておくことにする． tuple を使って遷…

#AtCoder#AtCoder Beginner Contest#水色diff#min-max法

競技プログラミング日記•3年前

AtCoder Regular Contest 126B

ARC126一般化したLIS.LIS まず普通のLISを考える． vector に対して，連続するとは限らない部分列であって狭義単調増加になるもののうち，最長の長さを求める問題．増加列は2つの図形的な捉え方がある．一つ目は，の組を頂点として2次元平面に図示すれば，右肩上がりに頂点を選ぶことになる．二つ目は，との頂点をそれぞれ列に並べて平行に置き，部分列として使うを辺で結んだとき，辺同士が交わらないことと言える．一般化したLIS 今回の問題は，LISの二つ目の方法と同じ．つまり，LISの一つ目の方法とみなせる．の組を2次元平面に図示する． LISとの違いは，LISにおいては一つ…

#AtCoder#AtCoder Regular Contest#水色diff#LIS

競技プログラミング日記•3年前

AtCoder Beginner Contest 275E

E - Sugoroku 4 確率dp. をと書く．に対して，とする． for を回すとき，移動した回数を一番外側に持ってくることに注意． dp では，すでに正しく求まっている計算を利用して次を求めるため．回目を求めるには，回目が正しく求まっている必要がある．逆元を何度も使うので，前計算すると速い． typedef long long ll; const ll INFL = 1LL << 60; using vll = vector<long long>; using vvll = vector<vll>; using pll = pair<ll,ll>; int main() …

#AtCoder#AtCoder Beginner Contest#水色diff