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>…