問題リンク 解説 基本的にE1と同じで、AliceとBobが両方好きな本を使った数を固定した全探索をします。 このとき、at least を満たすようにとってまだ冊に届いていない場合、使っていない中で小さいほうからとっていくのが最適なのは明らかでしょう。 あとは…

問題リンク 解説 まず与えられる操作は偶置換なので、もし値が全部異なるなら、ソート済みの数列と与えられる数列の置換の偶奇が違えばその時点で-1です。そうでなければ、適当に操作すれば答えが出ます。 以下同じ数字が存在するものとします ここでいった…

問題リンク 解説 を満たすが存在する は となるが存在する と同値です。ここまでくると後は桁DPで dp[i][j][k][l] := i bit目までみたとき、j(すでに下限を超えたか)、k(すでに上限を下回ったか)、l(すでに二つの大小関係は満たされたか) の桁DPを丁寧にしま…

問題リンク リンクについてる解説が結構どれもTLEが厳しそうでしたが、300msぐらいで通ります。 解説 フィボナッチ数列になるのは他の解説を参考にしてください。 ここまでくると求めるのは になります。 フィボナッチ数列は普通に行列累乗で求めても高速に…

問題リンク 解説 想定より少し計算量が悪いですが、ダブリングをしていきましょう。 現在の和と行き先だけもっていればそれでとけます。 提出コード yukicoder.me

問題リンク 解説 ある値にを加算すると、 となります。 よって、 となって遅延セグ木に乗るので乗せたらおしまいです。 提出コード yukicoder.me

問題リンク 解説 行列累乗をすればいい。 ただ愚直にやると精度上の問題でおちてしまう。 ここで行列累乗の誤差対策として、正規化を行う。 具体的には「スイッチが押される確率+ スイッチが押されない確率」は必ず1なのでそこが1になるように正規化する。 …

問題リンク 解説 閉路の中に閉路がないという条件なので、閉路を圧縮して1つの頂点とみなしましょう。そうすると、木になります。 この閉路を圧縮した頂点を通るときは、2通りの通り方があるので2倍するといいです。 適当に前計算をすれば、各クエリで解くこ…

問題リンク 解説 右隣と同じならば、どの数字を選んでも点数に差がでないです。 以下、右隣と違うものを考えます。 右隣と違うものが個あるとしましょう。 右の数字を選ぶ→点数の差が+1 左の数字を選ぶ→点数の差が-1 どちらも選ばない→点数の差がそのまま と…

問題リンク 解説 問題文に与えられた入力をそのまま扱うのはちょっとやりにくいので、.でまずは囲ってしまいましょう。 そうすると、この問題は明らかに単調性があるので二分探索で解けます。 秒で可能かどうかを判定できれば、後はこの問題はとけました。 …

問題リンク 解説 イメージとしては重心分解です！ 1-multihedgehogにおけるcenterは木の中心になっています。(そしてこの木の直径は2です。) 2-multihedgehogになると木の直径が2つふえるだけで、centerの位置はかわりません。 一般に-multihedgehogから -mu…

問題リンク 解説 まず0がある場合、あきらかに0なので0と出力します。 を固定したときの、はあきらかに単調性があります。 よって尺取り法です。 尺取り法をする際に、現在の積とを固定したときの、現在までの積の積を持ちながら尺取り法をすれば、繰り返し…

問題リンク 解説 任意の非負整数に対して、 となります。よって 一番小さい値は必ずmodを取られます。それ以外は取るかどうかをえらぶことができます。(選ぶ奴は降順に、選ばないやつは最小値の後にmodをとればいい) これで全探索できるので、求めることがで…

問題リンク 解説 ある整数の桁和を繰り返していくと、基本的には9で割った余りになる。ただし、9で割った余りが0の場合がやっかいで、 となる。ここまで分かれば、あとは簡単で、 遷移は簡単です。 提出コード yukicoder.me

問題リンク 解説 真面目にbitDPをしてももちろんいいのだが、制約が小さいので予め使える集合を全探索する方針をする。 そうすると、その使える数字の中で桁DPをすればいい。 bitDPをしなくていい分気持ち実装が楽 提出コード atcoder.jp

問題リンク これの制約が緩いのが、AtCoderの過去問にあるので、これは理解してるという前提で書きます。 解説 座圧して、数値はにあるものとします。 この問題とAtCoderの過去問との唯一の違いが同じ数字を含むというところである。 ある数値が連続するsubs…

問題リンク 類題 と聞いてたのに、こっちのほうがかなり難しいじゃないですか( ；∀；) 解説 とします。 全域木をとってきて、根つき木としてかんがえましょう！ 根から順にみていって、全域木に使っていない辺を1つつかって、サイクル長が以上のサイクルを作…

少し話題になったので、自分のメモも兼ねて 2ⁿ パターン列挙してソートする Θ(2ⁿ log(2ⁿ)) = Θ(n2ⁿ) と比べて n が落ちる半分全列挙でこれを使って、最後の合わせるパートも尺取で n を落とせるのでオーダーが落ちます— 熨斗袋 (@noshi91) June 13, 2020 方…

問題リンク 解説 が作れるかどうかはxor基底を管理しておけばいい。 自由に決めれる要素数はなので解はになる。 計算量は 提出コード atcoder.jp

問題リンク 解説 広義単調増加な数をつくればいいので、欲しいのは直前の情報だけでいいのでdpをしたくなります。 ここで作る数列は としていいです。こうなると簡単にdpが定義できて、 となるでしょう。 後は遷移ですが、広義単調増加でないといけないので…

問題リンク 解説 要求される誤差も緩く、指数関数的に確率はへっていくので愚直にやってもACできます。 単語目を打てる確率はです。 提出コード yukicoder.me

問題リンク (コンテストページです) 解説 文字が1つ以上区間を開けて、個作るわけですから、ならば作ることはできないので、-1を出力します。 以下 であるものとします。 この時、なわけですから、が間に合うということに注意しましょう。 そうすると あとは…

問題リンク 解説 全部のモンスターを倒す場合 これは明らかにDEFのをギリギリ倒せるやつで倒してから、殴るのが最適 それ以外 この場合は最小費用流で解ける。 攻撃しないモンスター用の頂点を用意しておこう！ 提出コード codeforces.com まとめ 普通に全部…