コンテスト中AC:A〜E C - Yamanote Line Game D - Swap Hats E - King Bombee C - Yamanote Line Game インタラクティブな問題を初めて解いたのでメモ 提出コード D - Swap Hats 自信ないまま通してしまいました。 操作を偶数回行った後に生成される状態には…

コンテスト中AC:なし A,B解説AC A - Coprime Pair B - Count 1's A - Coprime Pair 公式解説 素数の間隔(prime gap)が重要とのことです。 素数の間隔 - Wikipedia 公式解説及び上記のwikiによれば、問題の制約における素数間の極大の間隔(maximum gap)は1500…

解説AC 問題へのリンク 解説へのリンク 初Mo's Algotithm Mo's Algorithmの適用可能条件は以下の通りです。 配列が不変 クエリ先読み可 区間を+1, -1ずつ伸縮しても値の再計算が容易 1,2は満たすので3が満たせればよく、以下の方法で容易に計算できることが…

AtCoder Biginner Contestに出題されたので、実装してみました。 解説へのリンク(ネタバレ注意) 解説に書かれている以下のリンクに詳細があるので、アルゴリズムについては要約して書きます。 概要 数列についての個の閉区間のクエリにで答える。 やっている…

コンテスト中AC:A〜D D - Moves on Binary Tree D - Moves on Binary Tree 公式解説の解法1とほぼ同じでした。 まず、根からへの移動方法の文字列を得ます。具体的には、 が1となるまで以下を行う。 の末尾に、が偶数なら'L'を、奇数なら'R'を追加。 と更新…

解説AC 問題へのリンク 公式解説へのリンク テキストとyoutubeの解説の自分用まとめです。特に新しいことはありません。公式を見た方が詳細です。 二分木として考える 各文字が2つの文字になることを順に図示すると、二分木の構成になります。 よって、この…

コンテスト中AC:A〜C,E コンテスト後、Dは自力AC 2022/07/06追記 Eの実装に単射や同値類という記載がありますが、誤りです。 無視してください。 D - Sequence Query E - Putting Candies D - Sequence Query 実装が複雑になりましたが、自作双方向連結リス…

解説AC 問題へのリンク 解説1へのリンク 解説2へのリンク web解説を見てよくわからなかったので、自分なりに証明してみました。 素人なので、間違っていたらすみません。 森と、森の各連結成分について、他の連結成分と連結しなければならない次数の不足数が…