問題ページ 直線 上の点 を決めたときに， 上のどの位置に点を置けば2等分できるか？ を原点として 点を偏角でソートする．このとき 番目と 番目の点の間を通るような線分を引くと，2等分することができる． と 番目の点を結ぶ線分が のときに取る 座標 から…

チーム練習で 2017-2018 ACM-ICPC, Asia Daejeon Regional Contest をやった．7完1035で本番23位相当だった．記憶にない場所があるのでだいぶ嘘が混じってるかも (開始) divくんと手分けして読みつつ．おるふぇがテンプレを書く．Dが簡単らしいのでおるふぇ…

問題ページ 人ごとに独立に 日目まで頂点にいる必要なコスト としたDPを解く．遷移するときに日数は必ず+1されるのでDAGになるため，dijkstraではなくDPででき，logが落とせる． 目的地についたとしても頂点にとどまらずに辺を巡回する方が良いパターンが存…

問題ページ クラスカルのようにコストが小さい辺から追加していくことを考える．コストがの辺を追加しようとしているときにサイクルが存在する場合，その辺をMSTに含めることができない．サイクルが存在しないようにするために削除する必要のある辺の本数は…

問題ページ 盤面のマスは なし/黒/白 の3通りで16マスなので 通りしか存在しない．注意してDFSを実装すると状態数が少ないので間に合う． #include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a;</ll,></bits/stdc++.h>…

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

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

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

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

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

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

問題ページ 連結成分が2個のグラフが与えられたときを考える．各連結成分の大きさを ，辺の数を とすると，操作できる回数は 回である．よって，この回数の偶奇でどちらが勝つか判定することができる． の偶奇は で判定でき，0もしくは1のときは偶数で，2も…

問題ページ と にクエリを飛ばしてRBと返ってきた場合，『x 「n-1個』 y」 で２つの区間でRBの数の変動に影響するのはxとyの高々2個しかない．n-1個の部分でRとBの数が異なる場合は不可能．よって の範囲内にはRBが 個ずつ存在する． このような範囲 + 1個 …

問題ページ 最短路問題+の条件なので dist[マスi][k] = 最短経路 というような拡張dijkstraをすればよさそう． 個の各頂点を始点として拡張dijkstra コンクリートのマスの数を とすると 止まる頂点はコンクリートとゴールのマスのみ 拡張dijkstraの頂点数，…

問題ページ ボロノイMSTの要領でcentralが頂点となっていて辺の重みが元のグラフのcentral間の最短距離であるようなグラフを構成する． capacityが のときにクエリ を達成可能か？ グラフで と のパスの重みのmaxが以下 となる． を決め打つと，使用できる辺…

チーム練習で 2018 ICPC Asia Jakarta Regional Contest を解いた．9完ペナ1434で本番6位相当． (開始) 問題を手分けして読む．Iが簡単らしくdivくんが実装しはじめる．その間におるふぇにAを伝えると，01反転すればよくない？と言われて確かに～～～と言っ…

Heavy-Light Decomposition を参考にHL分解を実装していましたが Easiest HLD with subtree queries を見たら思ってたより短く実装できることを今更知ったのでそれについて書きます． の子のうち，部分木のサイズが最も大きいものが g[v][0] に来るように並…

参考資料 橋と関節点, lowlink - Lilliput Steps 二重辺連結成分分解(Two-Edge-Connected-Components) | Luzhiled’s memo 競技プログラミングにおける無向グラフに関する（橋、関節点、サイクル基底、lowlink）問題まとめ - はまやんはまやんはまやん DFS木 …

問題ページ 問題概要 頂点 辺のグラフが与えられる． 個の経路 が到達可能なように，辺の向きを定めることが可能か？可能な場合どのような向きにするかも出力せよ． 解法 グラフに対して二重辺連結成分分解を行う．二重辺連結成分については，一つのサイクル…

問題ページ 問題を整理すると，長さの数列を長さ以下の増加列に分解する方法が何通りあるか？となる． であるような が同じ増加列に属することはない．逆にこれ以外の についてはどのように増加列に振り分けても問題ない． 「上述のような をつないだグラフ…

問題ページ '('，')'をそれぞれ+1，-1に言い換える．区間の部分文字列が正しい括弧列であるとは，区間の始点までの累積和と終点までの累積和がで一致していて，区間の間に累積和が 未満の点が存在しないことと等しい． ある')'に対応する，部分文字列が正し…

問題ページ 速度を何回も上げ下げする必要はない．したがって1,3,9,27,9,9,3,3,1のように一回上げて下げるような変化を考えればよい．時間を短くするには，貪欲にできるだけ早い速度にするべきである． 速度を上げられる 秒で目標の時間を過ぎない 速度を維…

問題ページ ある列の高さを変更する場合，隣の高さに合わせる以外の中途半端な高さにして解が改善されることはない．よって前からDPを行うとき，番目を変更するならば番目の高さに揃えるとしてよい．番目の高さをのどれに揃えたか？という情報を持っておけば…

桁に着目して状態をまとめてDPするテク 取り扱える条件の代表的な例としては 以下の数，桁和，倍数 などである 桁DP自体の解説は以下のサイトなどがわかりやすい Digit DP 入門 by とーらすさん 桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか …

問題ページ 自分のコンテスト中の思考過程に沿って書きますが，公式解説の方がシンプルで高速に解けると思います．というか未証明です． まず， のペアを並び替えて が昇順になるようにする．この操作をしても一般性を失わない． 最も大きい に着目する． を…

問題ページ これは を最小化するように空港を設置する問題である．もし と が同じ木の頂点であれば，どのように空港を配置しても2点間の距離は変化しない．木の2点間の距離はLCAなどを用いることによって で求めることができる． ここからは と が違う木に属…

問題ページ が の中央値のとき は最小になる．Wavelet Matrixを用いると数列のある連続する区間のk番目の数を求めることができるので，各クエリに対して中央値を求めることができる． 未満の要素の個数 未満の要素の和 以上の要素の和 以上の要素の個数 が答…

問題ページ で0である桁について， を1にしたとしても と のビットカウントが1ずつ増加するだけである． が増えて損するだけなので， で1にする桁は も1の桁だけである． 下の桁から順に を0にするか1にするかを決定していくdpを行う． のうち を0/1のどちら…

問題ページ i桁目で一致する状況 下の桁で繰り下がりがない && X[i]=0 && A[i]=0 下の桁で繰り下がりがある && X[i]=9 && A[i]=9 dp[下からi桁目][下の桁で繰り下がりが発生したか？」 という DPテーブルを持ち，以下の遷移を行う． chmax(dp[i+1][0], max(d…

問題ページ 基本的にやるべきことは問題文に書いてあるのでそのシミュレーションを行う．ただし， の範囲で を1ずつ増やしてシミュレーションをすると当然TLEなので，シミュレーションに関わってくる重要な時刻のみ取り扱う．人が席を立つ時刻 と水を汲み終…