AtCoder AGC 029 C - Lexicographic constraints

問題リンク解説解が1となる場合を考えます。解が1となるのはが狭義単調増加の場合のみです。以下、解が2以上である場合を考えます。明らかに解に単調性があるので二分探索です解をとすると、文字列は進数の数字と考えるのが簡単で、のときのとき (要…

2020-11-26

Codeforces Round #685 (Div. 2) - E1. Bitwise Queries (Easy Version)

問題リンク解説重要な事実としてが成り立ちます。よって、に気づくと、が5クエリで求まるので、が5クエリで求まります。あとは残りのクエリはとのxorをとればそれぞれ1クエリでわかるのでこの問題は解けました提出コード codeforces.com

2020-11-25

Codeforces Round #686 (Div. 3) - E. Number of Simple Paths

問題リンク解説問題文をよーーーーーーく読むと個の頂点と個の辺があって、連結です。つまり、のようにサイクルにひげが生えた形になります。グッと睨むと、サイクルからの頂点からの最短経路がどこから来るかでグループわけできて、同じグループなら…

2020-11-23

TROC #16 E - Multiple Multiplication

問題リンク解説各要素において、その素因数毎にLCMの要素になる区間の幅はstackを用いるとならしで線形になります。素因数分解は前計算をしていけば毎回でできます。最後に繰り返し二乗法もすることを考えると、全体でで解けました提出コード https://t…

2020-11-23

TROC #16 D - Compassionate Companions

問題リンク解説単調性があるのは自明なので二分探索をします。二分探索をすると、ダメな関係にedgeを結んだとき、このedgeで結んだところを一緒にしないように二つのグループに分けられるかという問題になりますこれはまさしく二部グラフ判定なので、こ…

2020-11-22

半分全列挙 ( F - Programming Contest )を O(2 ^ (n / 2))で解く

問題リンク解説一般的に有名な半分全列挙はソートをする関係でになりがちですが、で解けるよという話をします。まず、マージソートなどで有名な話として、ソートされた二つの列をソートされた状態でmergeするのはでできます。 C++ですと、std::merge とい…

2020-11-21

yukicoder - No.1293 2種類の道路

問題リンク解説 UnionFindUndoを持っていますか？僕は持っています。道路と歩行者でそれぞれ頂点を用意し、それぞれ道路のみ歩行者のみいけるところをつなげておきましょう。ここで、頂点1の場合で考えてみましょう。 1において、道路のみをつかっていけ…

2020-11-20

Codeforces Round #620 (Div. 2) - F2. Animal Observation (hard version)

問題リンク Easyの記事まず読んでね jupiro.hatenablog.com 解説被らない区間はが大きくなっても変わらないのでEasyと同様に解けばいい問題は被るところで、被った場合は取る区間が1つの区間とあらわせる！！！！！よって、1つの区間さえ見ればいいので…

2020-11-20

Codeforces Round #620 (Div. 2) - F1. Animal Observation (easy version)

問題リンク EasyからHardへの誘導がいいね解説この制約ではが小さいのでこれが小さいことを利用する解法を考える。 i日目において、前日の区間を取った時の最大値とdpを定義しよう。そうすると、の区間をとるとき、前と区間が被らないのであれば要素をそ…

2020-11-20

Educational Codeforces Round 98 (Rated for Div. 2) - E. Two Editorials

問題リンク感動解説 E：L[i]+R[i]でソート、問題ごとに境界を定めれば作問者二人のどちらに振り分けるかが一意に定まるあとは作問者ごとにBITで区間加算、区間和を取得すればO(N^2logN)— Ryota (@re_re0101) November 19, 2020 ↑の方針ですね。自分が聞…