6完1258で本番13位相当 (開始) いつもどおり手分けして読む．Lが簡単そうだったのでおるふぇに説明して書いてもらう． (14分) Lが通る．Bが簡単らしくおるふぇが書き始める．Iが解かれてるので考えると，LCAで2点の位置関係を見ればできそう． (42分) BがTLE…

問題ページ trie木を構成すると D - Game on Tree に帰着できる．追加するクエリが存在するが，文字列追加でgrundy数が変更される頂点の数は高々40個なのでその部分だけgrundy数を再計算すればよい． #include <bits/stdc++.h> using namespace std; using ll = long long; </bits/stdc++.h>…

問題ページ http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2270 のL番目を中央値に変更したものであるが，複数テストケースで15ケースあってTLが厳しくなっている．HL分解 + BIT でlog3つ，並列二分探索 + 辺重みを変更できるLCA でlog2つの解…

問題ページ 時刻 に座標 にいる粒子は，時刻 に座標 に存在する．よって， が同じ場合，同じ粒子であると判定できる． であるような4数が何通り存在するか求める問題に帰着できた． これは約数系包除で解ける．gcdがi以上であるような4数の組は 個で簡単に求…

問題ページ サイクル基底入門として解いた サイクル基底・サイクルの個数について - 競プロ練習記録 グラフのサイクルについて扱いたいけれど，サイクルの個数は多すぎてどうしようもないみたいなときに使える話．サイクルの対称差を演算として考えると，い…

問題ページ ナップサック問題のように 重みが最大の価値 としたDPテーブルを更新することを考える．このDPテーブルに となるクッキーを追加する場合，chmax(dp[(i+w)%mod], dp[i]+v) となる．クッキーを追加する順番にかかわらずDPの結果は同じであり，この…

問題ページ 解法1 横棒の消去を無視すると周期 で同じ列に戻ってくる．ある横棒 を消す場合，その横棒の左端/右端にくる列が何列目なのか求め，その位置をswapする．左端/右端にくる列を求めるには，0列目/w-1列目に当たるまで上に戻るを繰り返すことで で求…

問題ページ ぬくもり需要 をソートしておくと，おふとんを増やす操作のみに置き換えられる．したがっておふとんを積む順番は記録せずに，使ったおふとんの集合だけ記録すればよくなる． 日目使った布団の集合 最小の不快度の和としたDPを考える．このDPの遷…

問題ページ 障害物がなければ行列累乗をすればよい．障害物に対応するため障害物が存在する行ごとに区切って考える．行列累乗で 列目に到達する方法を求めたあと，障害物が存在する位置に到達する方法を0通りに置き換える． で解けた． #include <bits/stdc++.h> using name</bits/stdc++.h>…

問題ページ 直線 上の点 を決めたときに， 上のどの位置に点を置けば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に言い換える．区間の部分文字列が正しい括弧列であるとは，区間の始点までの累積和と終点までの累積和がで一致していて，区間の間に累積和が 未満の点が存在しないことと等しい． ある')'に対応する，部分文字列が正し…