ferinの競プロ帳

競プロについてのメモ

2019-11-30から1日間の記事一覧

チーム練習 11/29

チーム練で 2018-2019 ACM-ICPC, Asia Seoul Regional Contest をやった.6完961で20位相当 (開始) おるふぇがテンプレを書き,手分けして問題を読む.Lマッチングでフローか?とか言ってた. (11分) Dが簡単らしくおるふぇが書いてAC.Lが通っているので考…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest K - TV Show Game

問題ページ 2SATで解く. 番目の電球がBならtrue というbool変数を用意する.例えば,1 R 2 B 3 R が与えられたとする.このとき ( or ) and ( or ) and ( or ) を満たす真偽値の組合せが存在すればよい.これはSCCを用いると で解ける. #include "iostream…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest J - Starwars

問題ページ ij = human側からスタートして頂点 にいる,not human側からスタートして頂点 にいる という状態が可能か? という配列を持つ.もし に到達可能で が同じ である辺が存在したら にも到達することができる. human側の頂点,not human側の頂点から…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest G - Secret Code

問題ページ の順列6通り全てについてそれぞれ確率を計算し足し合わせることで答えが求められる.以下では について考える. を固定したとき, が出会う確率 は となる. が出会う確率 は となる. がその時刻である確率は で求められる. は独立であるから,…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest C - Disks Arrangement

問題ページ まず答えを とする.ここから円盤を隣接させて被る分を引いていく. と を隣接させるときに減少させられる幅は である.順列をうまく定めることでこの幅の和を最大化したい.グラフで表現すると 頂点の完全グラフで,頂点 と の間に の重みの辺を…

2018-2019 ACM-ICPC, Asia Seoul Regional Contest A - Circuits

問題ページ 長方形のx座標は何も関係がなくて結局区間の問題になる.区間の端点以外に線を引くことで得をすることはない.よって「 個の区間が与えられる.区間の端点のから2点を選ぶ.この2点の少なくとも一方を含む区間の個数を最大化しろ.」という問題に…