ferinの競プロ帳

競プロについてのメモ

Codeforces

2020 ICPC Shanghai Site E. The Journey of Geor Autumn

問題ページ 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>…

2019-2020 ACM-ICPC Pacific Northwest Regional Contest (Div. 1)

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

チーム練習 (05/27)

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

Codeforces Round #643 (Div. 2)

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

チーム練習(05/13)

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

Codeforces Round #641 (Div. 1) C. Orac and Game of Life

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

Codeforces Round #641 (Div. 1) B. Orac and Medians

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

Codeforces Round #641 (Div. 1) A. Orac and LCM

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

チーム練習 (05/07)

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…

チーム練習 (04/29)

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

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest A問題 Bags of Candies

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

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest J問題 Space Gophers

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

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest F問題 The Halfwitters

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

2020 Petrozavodsk Winter Camp, Jagiellonian U Contest E問題 Contamination

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

Educational Codeforces Round 3 F. Frogs and mosquitoes

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

Educational Codeforces Round 1 F. Cut Length

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

Educational Codeforces Round 2 D. Area of Two Circles' Intersection

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

Educational Codeforces Round 83 E - Array Shrinking

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

Educational Codeforces Round 83 D - Count the Arrays

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

Codeforces Round #613 (Div. 2) F - Classical?

問題ページ Codeforces #613 (Div. 2) F. Classical? (R2800) - けんちょんの競プロ精進記録 のスタックの中に互いに素なものの個数を数える部分についてちょっと悩んだのでそこだけ書きます. 「スタックの中に が存在する. と互いに素なものの個数を数え…

Codeforces Round #613 (Div. 2) E. Delete a Segment

問題ページ 区間 が与えられたとき,数列 の区間 に+1した数列を考える.そのまま数列をつくるとMLEなので,座標圧縮しておく.区間が交差しているかどうかを考えたいとき, と隣接していると結構大変なので,各端点を2倍して としておくと交差しない区間の…

Codeforces Round #613 (Div. 2) D - Dr. Evil Underscores

問題ページ Trie木を考える.上の桁(Trie木の浅い方)から順番に見て,0にできるならば必ず0にするべきである ( なので). 上から 桁目に0しかない: の 桁目を0にすれば答えの 桁目を0にできる 上から 桁目に1しかない: の 桁目を1にすれば答えの 桁目を0にで…

チーム練習 12/20

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

2016-2017 ACM-ICPC Asia-Bangkok Regional Contest F - Dictionary Game

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

2016-2017 ACM-ICPC Asia-Bangkok Regional Contest E ACM Tax

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

2016-2017 ACM-ICPC Asia-Bangkok Regional Contest C - Big Bang

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

チーム練習 12/6

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

2017-2018 ACM-ICPC, Asia Daejeon Regional Contest L - Vacation Plans

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

2017-2018 ACM-ICPC, Asia Daejeon Regional Contest E - How Many to Be Happy?

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

2017-2018 ACM-ICPC, Asia Daejeon Regional Contest B - Connect3

問題ページ 盤面のマスは なし/黒/白 の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>…