問題ページ dp[長さiの数列] = 何通り とDPをする。 1をi番目に置く [1,i) は自由においてok → P(n-1, i-1) (i,n] は dp[n-i] 通り の累積和をもちつつ更新すれば ▶ソースコード(クリックで展開) #include <bits/stdc++.h> using namespace std; using ll = long long; usin</bits/stdc++.h>…

チーム練でやった https://codeforces.com/gym/102433 BCLMは気づいたら通ってた E 個数+1 を種類ごとに掛け合わせる D 減らすのは/2で増やすのは+1しかないので適当にシミュレーション I 同時に入れられないやつに辺をはると最大独立集合 swapのparityを考…

2019 ICPC Asia-East Continent Final をやった A は気づいたら通ってた M となるような の組はあまりない や のように素数のべき乗に分割する 各集合の要素数は 個でbit全探索の要領で全部見てもok E universeなグラフ： 頂点1とn以外は次数が2で分岐しない…

A 15:30 証明が全然できないけどみんなめっちゃ通していく 仕方がないのでK回普通に漸化式を計算して0が含まれたら終了にした 未証明 提出 B 30:41 全員どこかしらに入らないといけないんだと思って1ペナ あと普通に実装が下手なので強い人のをあとで見る 提…

Dashboard - 2019-2020 ICPC Northwestern European Regional Programming Contest (NWERC 2019) - Codeforces をやった。 C,F,I は気づいたら通ってた B,K はわからん A 得点が同じ人ごとにまとめておいて、点数が変化した人の分だけ更新するようにシミュレ…

問題ページ サンプル1,2のようにすべてのマスについて同じ色が隣接、もしくは異なる色と隣接しているような状況のときは明らか。そうではないケースについて、とりあえず実験してみる。 01 01 00 10 → 11 → 00 00 11 00 同じ色が隣接しているマスが一つ以上…

問題ページ が2つ連続して並んでいる場合、 に操作を適用すればすべて にできるので の並びをつくれるならば 'yes' となる。また 以上 と並んでいる場合、操作を適用すれば の並びをつくれるのでこの場合も 'yes' となる。 あとは 以上 の数を の隣に持って…

問題ページ gcdを求めたいので素因数ごとに独立に考えて、最後に掛け合わせても問題ない。 例えば数列が であったとする。このときのlcmの集合は となる。このときの は となる。このように指数が小さい方から2番目の値のものが の指数となる。 あとは素因数…

この間のABCで話題になってたのでダブリングについてちょっと考えたことのメモ コードは適当なので雰囲気です を繰り返す 関数 が存在 について を 回実行 これは の計算量 で計算可能 繰り返し二乗法などが具体例としてあげられる template<class T, class F> T binpow(T y, l</class>…

問題ページ 経路を一つ固定したとき、寝過ごしたときに最悪となるパターンについて考える。辺 で寝過ごした場合、かかる時間は (始点からuまでの時間) + (uから終点までの時間) + (終点からtまでの時間) となる。経路上の各辺で寝過ごした場合の時間のmaxが…

問題ページ と表す。 は下から 桁目の値であり、 である。 となるような を求めたい。 の組は 通り存在するため、普通に全列挙するとTLEしてしまう。そこで半分全列挙を行う。 と についてそれぞれ和を列挙する。足したときに で0になるようなものが何個ある…

問題ページ まず のときの解き方を考える。 についてソートしておく。この数列の差分について小さい方から 個の和が答えになる。差分が大きいところから 個と一番小さい箱にドーナツを入れることでこれは達成できる。 数列の小さい方から 個の和を求めるのに…

問題ページ 原点からの半直線を引くので関係があるのは始点と終点の偏角である。各線分を[始点の偏角、終点の偏角]の区間に置き換えると、「ある区間の集合が与えられる。任意の区間についていずれかの要素を含むような偏角の集合のうち、最小の要素のものを…

Dashboard - 2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20) - Codeforces 8完ペナ1044で本番9位相当 A dp[頂点][距離] = コストでDP dijkstraしなくていいのでlog落とせる B,C 気づいたら通されてたので知らない D st…

問題ページ レベルが のときの答え、レベルが のときに2点を結ぶ方法、レベルが のときに同じ点を2回通るパターンを各レベルについて計算していく。それぞれ と表す。 各三角形内で完結するパターン + 三角形をまたぐパターン 三角形を2つ使うパターン + 三…

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest をやった。本番51位相当、参加者のレベル帯めっちゃ高くないか (開始) 手分けして読む。L,Bが解かれているので考える。 (0:22) Lは貪欲でいいことがわかるのでolpheが書きはじめる。 (0:25) Lが通る…

問題ページ 概要 の 種類の味のキャンディがある バッグに1か2種類を入れる ただし2種類の場合、味の が2以上でなければならない バッグの数を最小化しろ 解法 2種類のペアをつくる数を最大化すればバッグの数を最小化できる。味1のキャンディと より大きい…

問題ページ トンネルが連結なパターンを2通りに分ける 並行な場合 隣接している4パターンのみ考えられる。mapかsetで存在するトンネルを保持しておけばこの判定はできる。 垂直な場合 x軸に垂直なトンネルとy軸に垂直なトンネルが連結となるのはz座標の差が1…

問題ページ 概要 要素の順列が与えられる 以下の操作を繰り返して順列を昇順に並べる 隣接要素のswap：分かかる 順列のreverse：分かかる ランダムシャッフル：分かかる 初期状態が個与えられるのでそれぞれについて、最適に操作したときにかかる時間の期待…

問題ページ 概要 個の円(中心がで半径) が存在 個のクエリが与えられる 2点を以下の条件を満たしつつ行き来できるか？ 円の内部を通らない となる範囲のみ 円は重ならない 解法 と仮定しても一般性を失わない。クエリが'NO'となる条件は「 かつ となる円が存…

問題ページ まず答えの一番上の行を適当に定める。このとき入力の1~n-1行目までが正しく生成されるように、答えの2~n行目までを定めると一意に定まる。入力のn行目についても正しく生成されるような、一番上の行を探したい。 通りを全列挙することは不可能な…

問題ページ ビットごとに独立 ビットごとの論理和・論理積について考えているため、ビットごとに独立に考えることができる。したがって要素が0か1の の行列を構築できるか？の問題に帰着できた。 容易に決定できる要素 まず、0か1か確定させられる要素を決め…

問題ページ 文字列の長さは についてフィボナッチ数列になっている。したがって については一意に定まる。また、フィボナッチ数列で20000以下となるのは22番目までなので、 である。文字列は高々 個程度しか存在しないので、 を全列挙し、 と一致するか判定…

問題ページ flogに対応する区間を持つ集合・まだ食べられていないmosquitoを保持する集合をそれぞれ保持しておく。 mosquito が現れたとする。このとき を含む区間が存在するか？存在するなら左端が最も小さいものはどれか？を判定したい。内包される区間に…

問題ページ 直線上に多角形の頂点が存在しない場合、直線と辺の交点をに近い方から順番に見ていき、番目と番目の点の距離の和が答えになる。問題は直線上に多角形の頂点が存在する場合で、2つの辺と交わっていると判定されて困る。 点を通過して中に入るパタ…

問題ページ まず2円が離れているか外接の関係にある場合、答えは0です。2円が内包か内接の関係にある場合、答えは です。2円が2点で交差する場合について、2通りに場合分けを行います。 交点からなる線分から見て、 が反対側にある 扇形ABCから三角形ABCを引…

問題ページ 幅が小さい区間から順に参照していくようなDPである、区間DPをします。 区間 をマージするときに操作を行って長さを減少させるのは、 が両方とも長さ1で、値が同じときだけ考えればよいです。これ以外のときに に操作を行うようなことを考慮しな…

問題ページ 数列内の一番大きい数を とします。同じ数のペアを とします。このときの数列は となっています。 の選び方は 通りあります。 数列に存在する数として 個から 個を選びます。これは 通りあります。 個の数を の左と右のどちらにするか？を決めま…

参考文献 https://www.hamayanhamayan.com/entry/2017/12/19/152143 https://qiita.com/drken/items/4b4c3f1824339b090202 木の重心: その頂点を取り除いたときにできる部分木の要素数が元の半分以下になる頂点 重心は1個か2個必ず存在する 部分木の要素数を…

黄色difficultyあたりの適正難易度帯を昔やって忘れてるのもったいないので2周目 D - Connectivity UF2本もって(道路のufの根,鉄道のufの根)のペアをkeyにまとめる D - Ears 0, 偶数, 奇数, 偶数, 0 の5個の領域のどこにいるか？をDPのkeyに持つ 耳DP，DFAの…