Codeforces

計算量がなぜ間に合うのか自信がない。 fig.1fig.2ある頂点P（色c）に注目したとき、パスをつくれる頂点は図のようになる。 DFSで戻るときにパスの数を計算しながら、部分木の色のヒストグラムをマージしていく。 （色c以外は合計して、色cは1にする。） 深さが最悪ケースではマージテクをつかうことで計算量を抑えることができる。 逆にマージする色のヒストグラムが大きいときは、二分木が最悪ケースで、深さがlogNに抑えられる。 以上から実行時間が間に合う、のだと思う。 実装時はサイズが大きいヒストグラムをコピーしないよこうに注意する。 作れるパスの数の計算の仕方は図にかいた通り。

公式解説は、インデックス1まで移動してきた敵を一気に倒す。 使わずに余った弾丸は次のターンに持ち越すことにしても結果は変わらない。 というもの。 気づかずに少しめんどくさい解法をつかったのでメモしておく。 敵を攻撃し始めないと間に合わない締め切りを求める。 締切は 。 これをpriority queueにいれて。締切が早い順に処理していく。 各ターンで、残弾がある限り、もっとも締切が近いものを、1ターン締切を伸ばすように処理してpriority queueに入れなおす。 締め切りを伸ばすのに必要なダメージは (ただし0のときはK) で求める。 締め切りが現ターンより小さければNOを出力。 （締…

[0] 扱う問題 問題解説も同時にするので、問題を先に見たい人はここを開いて、適当に検索してください。 扱う問題一覧 ABC 336 G Codeforces 925 G AGC 051 D ARC 146 E Codeforces Hello 2024 E ARC 117 E yukicoder No. 310 [1] 概要 BEST theorem (BEST 定理) とはオイラーグラフのオイラー路の数え上げに非常に有効な定理です。 この定理を用いることで解くことができる競プロの問題に対する解法と、その実装例を紹介します。 実装は全て c++ gcc で行っています。 [2] BEST 定…

はじめに... はじめまして！ ルクといいます！ 誰なのかを一言で言うと弱々学生競プロerです... もうすぐatcoder入緑の茶色コーダーです それで、このアカウントを作成した一番の理由ですがメモ用です それを皆さんに共有できたらと思います！ これからやっていきたいことのメモ AtCoder・Codeforcesの解いた問題の解説！ 初心者のためのAtCoder入門講座！ この2つを主にやっていきたいと思います AtCoderは主にABCを、稀にARCのA問題の考え方をまとめていきます 初心者のためのAtCoder入門講座は適当な時間の余ったときに作ります X(Twitter)やってる人で…

主客転倒がすんなり発想できたけど、実装バグって間に合わなかった。 残念だったので簡単に書いておく。 2点だけを決めると真ん中に一つの不動点ができる。 いわゆる主客転倒で、この不動点が現れる組み合わせを数える。 任意の2点 , ()を決めた時、 ,の間には他に選ばれる点はない。（間の点を選ぶと、別の不動点ができるか、同じ位置に別の2点によって不動点がつくられる） ,の距離をとするとき、から左により大離れた点は選んでも選ばなくても影響しない。（等しい場合が左に動いてしまう） ,の距離をとするとき、から右に以上離れた点は選んでも選ばなくても影響しない。（等しいときはは左に動くので影響しない） よって…

まずは条件を整理する。 インデックス があって（ ） 、 から までで条件が「2」のとき、長さ1に 両方を含むことはできないので明らかに0通り。 から までの条件が「1」で までの条件が「2」のとき までに2種類を含むので0通り。 以上から答えが「0」のときは予め出力して処理を打ち切っておく。 上の条件を含まない時、 から の条件が「2」のときかつ の条件が「2」のとき、 の条件は「0」と同一視してよい（ から ですでに二種類ふくむ）。 から の条件が「1」のとき、すべての の条件は「1」と同一視してよい。 よって が始点になる条件は、「 最後の条件1のインデックス」と「最初の条件2のインデッ…

先日開催されたCodeforces Round #839 (Div. 3)のD問題を解説します。 本番中に通せなかったのと、あまりみたことのないタイプの問題だったので記憶に残すためにも書きます。 問題概要 問題文 正の数からなるある数列Aが与えられる。あるxを選び、と置換した時にAがソートされた状態になるようなxを1つ探す。 制約 解説 まずは小さいケースから考えます。 ] この場合は、すでにソートされていますが、どんなxを選ぶことができるでしょうか？ の時条件を満たし、になると条件を満たしません。 ] この場合はどうでしょうか？ になると条件を満たします。 この2ケースを比較すると、連続する…