2020-01-01から1年間の記事一覧
問題リンク 解説 いろいろ解き方があると思います。 ある程度1で埋めてしまいましょう。1を個置いたとき、のペアが素数になります。 次に2と6を1つずつおきます。2と6は1とペアを組むと素数になるので、ペアが増えます。 最後に、5を1つ置くと2個ペアが増え…
問題リンク 解説 遅延セグ木のノードに(総和、偶数の個数、奇数の個数)を持ちます。 更新クエリは(クエリ1パターン、加算)という風にします。 クエリ1パターンは3通りあって、 クエリ1パターンがない (実装の0) クエリ1パターンがある(偶奇はそのまま) (実装…
問題リンク 解説 前処理として、各要素の左にあるものかつその要素より大きいもので、最も近いものをメモしておきましょう。 これはstd::setなどで簡単にできます。 次にクエリを先に読んでが小さいものから見ていきます。 現状条件をみたしてるものをBITに…
問題リンク 解説 変更クエリなしで解くことから考えてみましょう。 dp[i] := i番目までみたときのとの組み合わせ とすると、との各桁の和はせいぜいであることから、2桁のみ考えたらいいことがわかります。 よって、s[i]となる組み合わせを、s[i-1]s[i]の2桁…
問題リンク 解説 いろいろやり方はあるらしいですが、マージテクを用いる方法を解説します。 この問題の解はとを辺で結んだときのになります。 ということでまず最初にこれを愚直に求めてしまいましょう。 その後はクエリ毎にマージをしていきます。 マージ…
問題リンク 解説 次数が10以下であるので、11個の異なる値が分かればラグランジュ補間を使うと次数をとして、で係数が分かります。 係数が分かれば、のはであるので全探索をしても十分間に合います。 提出コード codeforces.com
問題リンク 解説 が列目にいくときの、座標の最小値をとする。 ここで、明らかなこととして、以上のポーンの個数が個あれば、必ずであることが必要である。 で実はこれが十分であることも示せるらしい(Editorial曰くHallの定理を使うといいらしい) 上を実現…
問題リンク 解説 先手が必ず勝ちます。 常に変化するものが最大値になるように意識しましょう。 そうすると、 とすると、 であるとき、であるので、を投げると先手が勝ちます あとはこうなるようにするだけです。 提出コード codeforces.com
問題リンク テスターでした。 解説 として、根から木DPすると解けます。 子供から親にいくときに、距離が1ずつ増えることに注意しましょう。 提出コード yukicoder.me
問題リンク 解説 基本的に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