問題リンク 解説 o と x の個数は o の個数 xの個数 oの個数 x の個数 のどちらかです。そうでないときはNOを出力します。 oもxもないときはまだ何もしていないのでYESです。 上記の場合以外は一手前の状態が存在します。 一手前の盤面が5目並んでるような盤…

問題リンク 解説 から始めた時に勝てるかどうか とすると、 それ以外 であるので となる をqueueなどで管理することで、 で解けました 提出コード yukicoder.me

問題リンク 解説 公式解説のほうが賢いのでそちらを参考にしてください。 にいて にビーコンを置いてるときの最短距離 としましょう。 愚直にやると、ですが、ビーコンを置くのは通るpath上のどこかでいいのでHLDと双対セグ木を用いて、 でもとまります 提出…

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

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

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

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

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

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

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

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

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

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

問題リンク 解説 の期間でまだ倒していないのに、捨ててリロードする必要はありません。 よって、 として、毎回シミュレーションしてもと小さいので余裕で間に合います。 計算量はです 提出コード codeforces.com

問題リンク 復元いる？？？？ 解説 値が無駄にでかいので、[1, n]に座圧で収めましょう。 初期位置は値が0だとすると実装が楽です。 ここでdpを2つ考えます。 dp1[i][j] := 今数字iを取ろうとしていて、iを1つも取っていないときjにいるような最小値 dp2[i][…

問題リンク 解説 functionalグラフでかつ、とはpermutationなので、とはとなる有向グラフを考えた時、シンプルなサイクルになることがわかる。 となるを考えよう。 このとき、、となるが必要なことがわかる が偶数のとき とすればよい が奇数のとき となるの…

問題リンク 解説 区間の左端が小さいほうから見ていく。 以上になったら区間の左端になって、を切ったら区間の右端にする あとは実装するだけなのでコードを参考にしてください 提出コード codeforces.com

問題リンク 解説 想定のではおそらくAtCoder上ではACするのは困難です。 実は半分全列挙はこのでできます。 詳しくは実装を見てください 提出コード atcoder.jp

埋める E - シャッフル 実装やるだけ D - 散歩 回目の状態が簡単にわかるので、後はシュミレーション E - 認証レベル やるだけ sequence - 数列 (Sequence) 問題そのものはまともでおもしろいが、MLEが厳しいためにちょっと定数倍むだにとるけどねみたいな方…

問題リンク 解説 どの売人とどの購入者が対応するかは通りあります。 売人のみがどの順番でくるかを考えましょう。これはあります。 ここで売人の並び方と、売人と購入者のペアを固定した状態で考えます。 売人の後ろから、購入者の順番を決めていくと、の並…

問題リンク 解説 としましょう。 これはで前計算できます。 後は全探索です。 グループ分けをしたときに、前のグループとのorで伸ばさないといけない距離が前計算からわかります。 計算量は全体で です 提出コード atcoder.jp

問題リンク これは勉強不足だった 解説 まずはが2べきで表される時を考えましょう。 そうすると分割統治法のようなイメージで半分ごとにわけてそれぞれで1種類にしたあと、全体で1種類にすることは簡単でこれは回でできます。 では2べきでないときは、スパー…

問題リンク これに時間かかったのは反省 解説 に着目すると、 右に移動させる距離が]においては少なくとも上に移動させることが必要です。 以上から、右に移動させた距離ごとに上に必要な距離がわかります。 提出コード codeforces.com

問題リンク 解説 C1は dp[i][j] := i番目まで見た時、次が+ならj=0 次が-ならj=1 みたいに定義したら解けます。 これの応用で[l, r]の区間で dp[j][k] := lが(+ or -)ではじまり、rが(+ or -)でおわる 見たいな風にするとセグ木にのります 提出コード codefo…

問題リンク 解説と少し違ったので 解説 の場合はサンプルにあります。 以下とします であるので、 です よって となるをみつけたらよく、これはの逆元です。 提出コード yukicoder.me

解説 区間DPです。 dp[l][r]:= [l, r)の部分列の回文の数とすると、 dp[l][r] += dp[l + 1][r] + dp[l][r-1] - dp[l+1][r-1] に加えて、s[l] == s[r-1]なら dp[l][r] += dp[l+1][r-1]+1 です 計算量は 提出コード #include <iostream> #include <string> #include <sstream> #include <stack> #</stack></sstream></string></iostream>…

問題リンク 解説 式変形すると となります。とは互いに素であるので、の素因数をとのどちらかに押し付けます あとは拡大ユークリッド互除法を用いれば、差が1でかつ最小になるようなものを求められます 提出コード atcoder.jp

問題リンク 解説 直接中央値がとなるようなsubstringを数え上げるのは大変です。 ここで とするとを求めるのはBITなどを用いて簡単です 中央値がとなるようなsubstringはとなり求めることができました。 提出コード codeforces.com

問題リンク 解説 最短経路木を列挙してくださいという問題です。 頂点1からBFSなどで各頂点までの最短経路を求めましょう。 ある頂点の親はとなるものに限り、かつこれを満たすならどれでも構わないです。 あとはこのパターンを列挙するだけで、列挙の仕方は…

問題リンク ゆきこにこれの簡単バージョンがある 解説 各経路を考えると大変なので、各辺が合計で何回通るかを考えましょう これは部分木サイズを注目することで、で求めることができます。 あとは通る回数が小さいほうから、小さいを割り当てていけば終わり…