コンテスト中AC:A〜C,E E - Takahashi and Animals E - Takahashi and Animals グラフの問題として考えていたので、言い換えておきます。 頂点について、頂点と頂点の間には辺があり、そのコストはです。 ここから、以下の条件を満たすように辺をいくつか削…

コンテスト中AC:A〜D Eはコンテスト後に解説を読み、自分がコンテスト中に考えていた発想で問題なさそうだったので、その方針でなんとかACできました。 E問題について書いたので、記事のタイトルはEをメインにしました。 E - Prefix Equality 自分の実装 方…

コンテスト中AC:A A - Trailing Zeros A - Trailing Zeros 説明のため、二進数10桁しかないと仮定します。 例えば、の時、??????1000となり、?の部分が未確定です。 この時、??????の部分は、000000〜111111があり得ます。 000000, 000001, ...と増加させて…

コンテスト中AC:A〜D D - Index Trio D - Index Trio を変形すると、となります。 を固定すると、はの約数の組に限定されます。 よって、について、である約数についてのみ調べれば良く、各について、で全探索できます。 計算量は、の最大値を として、とな…

コンテスト中AC:A〜D D - Range Count Query E - K-colinear Line ので管理 ので管理 探索済みの点対を管理 基準となる2点を管理 点が直線上にあるかの判定 D - Range Count Query ウェーブレット行列が使えます。 ウェーブレット行列には以下の関数がありま…

コンテスト中AC:A A - Larger Score 入れ替えに必要な操作回数 複数個入れ替える場合に必要な操作回数 問題の条件を満たすのに必要な操作回数 A - Larger Score 一応、考察した内容ですが、あまり自信はないです。 番目までのから順番を保ったまま抜き出した…

自力AC 解をとします。 まず、以下の最大の整数は二分探索により、で得られます。ここでは、とします。 くらいの場合 が与えられた時に生成可能な数列の種類数 と定義すると、 と求められます。 ここで、の累積和をとっておけば、 と求められるので、の計算…

コンテスト中AC:A〜C,E D,Fも自力ACできたので、書きます。 コンテスト全体の感想 D - 2-variable Function E - Bishop 2 F - typewriter コンテスト全体の感想 Dが思いつかなかったので、Eを先に解きました。Eは解法自体はわかったのですが、実装に時間がか…

コンテスト中AC:A〜C コンテスト後解説なしでE,FをAC。 Dは解説見たが、方針は間違っていなかったが、考慮できていない部分があった。 D - Polynomial division E - Wrapping Chocolate F - Endless Walk D - Polynomial division であるので、 の時、 の時…

コンテスト中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解説を見てよくわからなかったので、自分なりに証明してみました。 素人なので、間違っていたらすみません。 森と、森の各連結成分について、他の連結成分と連結しなければならない次数の不足数が…

コンテスト中AC:A〜E E - Ranges on Tree コンテスト中は確信が持てないまま通してしまいました。 解法に至った経緯をメモしておきます。 まず、問題文の意味がパッと見で理解できませんでした。そこで、入出力例を確認して、ざっくりと以下のような制約であ…

コンテスト中AC:A〜E B - Intenger Division 以前、このような自作関数を作っていました。 template<typename T> T Floor(T a, T b) { if ((a<0 && b<0) || (a>0 && b>0)) return a/b; else return (Abs(a)+Abs(b)-1)/Abs(b)*-1LL; } これを使うことで、Floor(X,10LL)で</typename>…

コンテスト中AC:A,C Bはコンテスト後自力AC。もう少しで解けそうでした。 A - Floor, Ceil - Decomposition 実際に10まで、xとfloor(x/2)×ceil(x/2)のどちらが大きいか手計算しました。 すると、 x≦4なら、x≧floor(x/2)×ceil(x/2) x≧5なら、x

解説AC 問題 公式解説 公式解説で解法だけみて、実装は自力でしてみようと思ったのですが、これも上手くいきませんでした。結局、実装も解説のものを確認しました。 LISの長さが3未満の保持方法 未確定の部分はinf、今回ならM+1としておけばよいようです。 …

解説AC 問題へのリンク 公式解説 単純に部分列を得るだけなら部分列DPなどが考えられますが、今回はすべての並び替えを得る必要があるので適用できません。 重複を含む並び替えの計算方法から考えてみます。 の選んだ個数をそれぞれとします。この時の並び替…

解説AC 問題へのリンク 公式解説 公式解説のメモ程度です。 の累積和をとおくと、与えられる情報は、 という風になり、 との一方が分かれば、もう一方がわかる という関係になる。 この関係をグラフ化し、とが連結ならYes。 ここまでが公式解説の内容です。 …

コンテスト中AC: A〜D A - Exponential or Quadratic D - AND and SUM 公式解説メモ 連立方程式の解き方 A - Exponential or Quadratic から、が64bit整数型に収まらなければ、直ちにYesです。 よって、64bit型を超えるまでは、実際に2を掛けていきます。そ…

コンテスト中にACしたものの、after_contestでTLEで、嘘解法でした。 この記事は公式解説を自分用にまとめたもので、新たな情報などは無いです。 ここでは、標高が低いところから高いところに行く坂を下り坂、逆を上り坂と言うことにします。 2個目の条件を…

コンテスト中AC:A〜E Eは嘘解法(Cも若干そうでしたが)だったので、ここでは省略します。 C - kasaka D - LR insertion C - kasaka 先頭から連続しているaの個数をhead、末尾から連続しているaの個数をtailとします。 先頭に付け加えるのに必要な個数は、tail…

コンテスト中AC:A,B Cはコンテスト後自力AC A - Bridge and Sheets B - Reserve or Reverse C - The Majority A - Bridge and Sheets 便宜上、を追加しておきます。 最初からかけられているシートのうち、最も右端をとします。最初としておきます。 にかけら…

コンテスト中AC:A,B A - Erase by Value B - Dividing Subsequence A - Erase by Value 同じ数は消えるので、一旦連続して重複した数について、重複を削除して考えます。 から始めて、単調増加している間は、消すと辞書順では大きくなってしまうので、消さな…

コンテスト中AC:A〜C D - Dance 状態遷移を伴うDFS 考慮すべき事項 状態の管理に必要な情報 情報の受け渡し方法 値渡し グローバル変数等で共有 終了条件 D - Dance 解けなかったので、反省点含めて記録します。 まず、Nが小さいことから全探索が可能と予想…

自力AC(一度TLEになったので、解法を見て、合っているか確認した) 条件を満たす桁に関する問題 以下の整数全てに関する問題 という条件から、桁DPが有力候補となります。 桁DPに関する情報はネット上に多くあるため、ここでは割愛しますが、大雑把に説明しま…