geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。

ABC

AtCoder Biginner Contest 263 参加記録

コンテストページ:LINE Verda Programming Contest(AtCoder Beginner Contest 263) - AtCoder コンテスト中AC: A〜E E - Sugoroku 3 E - Sugoroku 3 期待値DPが使えます。 サイコロを振ることを操作と呼ぶことにします。 マスからマスまでにかかる操作回数…

AtCoder Biginner Contest 262 参加記録

コンテストへのリンク:■ コンテスト中AC:A〜D D - I Hate Non-integer Number 数列の部分和に関する問題なので、部分和DPを考えます。 数列の項目までの部分和であって、和がとなるものの個数 今回は、何個選んだかも必要なので、情報を足します。 数列の項…

AtCoder Beginner Contest 261 参加記録

コンテスト中AC:A〜F D - Flipping and Bonus E - Many Operations F - Sorting Color Balls D - Flipping and Bonus 説明のため、お金をスコア、コイントスによって表か裏かを選んでスコアを得ることを操作と呼びます。 その時々の操作後のスコアを最大化す…

AtCoder Biginner Contest 260 F - Find 4-cycle

コンテスト後に自力ACしましたが、記事を書いていて計算量の見積もりが誤っていたので、公式解説を読みました。 頂点集合を以下の通りとします。 は独立集合であるという条件から、4-cycleをもつ条件は以下に限定されます。 に属するある頂点と、に属するあ…

AtCoder Biginner Contest 260 参加記録

コンテスト中AC:A〜D B - Better Students Are Needed! C - Changing Jewels D - Draw Your Cards B - Better Students Are Needed! 配列を用意し、各要素は以下のようにします。 この配列は例えば、C++ならvector<pair< long long, long long >>を使用します。 について、各要素の1つ目を</pair<>…

AtCodet Beginner Contest 259 参加記録

コンテスト中AC:A〜D B - Counterclockwise Rotation ベクトルの反時計回りの回転行列は以下の通りです。 よって、求めたい座標をとすれば、 となります。 但し、C++では角度はラジアンにしないといけないので、として、の代わりにを渡します。 実装は、よう…

AtCoder Biginner Contest 258 参加記録

コンテスト中AC:A〜D コンテスト後にEを自力AC。コンテスト中に漠然とした解法まで思い浮かんでましたが、実装間に合わず。 A〜Dは特に書くことがないので、Eについて書きます。 2022/07/08追記 Eの実装中の同値類などは誤りなので、無視してください。 E - …

AtCoder Biginner Contest 257 参加記録

コンテスト中AC:A〜D コンテスト後にEを自力ACできたので、こちらに書いておきます。 2022/07/01 追記 Fも自力で解けたため追記 C - Robot Takahashi D - Jumping Takahashi 2 E - Addition and Multiplication 2 F - Teleporter Setting C - Robot Takahash…

AtCoder Beginner Contest 256 参加記録

コンテスト中AC:A〜E C - Filling 3x3 array E - Takahashi's Anguish C - Filling 3x3 array となるの組が何通りあるか考えます。これは、個の区別のないボールを横1列に並べ、個のボールの間から2つ選んで区別のない仕切りを置き、仕切りの左から順にボー…

AtCoder Beginner Contest 255 参加記録

コンテスト中AC:A 惨敗でした。コンテスト後ですが、自力でEまでは解けました。 2022/07/14 E問題の赤字部分がになっていたので、に修正 B - Light It Up C - ±1 Operation 1 D - ±1 Operation 2 E - Lucky Numbers B - Light It Up 半径の2乗を二分探索しま…

AtCoder Beginner Contest 254

コンテスト中AC:A〜C,E AtCoder Beginner Contest 254 - AtCoder 解けなかったDを解説見てACしたので少しだけ付け足しして書いておきます。 D - Together Square D - Together Square この問題では、以下の命題が重要そうです。 が平方数となるための必要十…

AtCoder Biginner Contest 253 参加記録

コンテスト中AC:A〜E NOMURA Programming Contest 2022(AtCoder Beginner Contest 253) - AtCoder B - Distance Between Tokens C - Max - Min Query D - FizzBuzz Sum Hard E - Distance Sequence B - Distance Between Tokens マンハッタン距離に関する…

AtCoder Beginner Contest 252 参加記録

コンテスト中AC: A〜F C - Slot Strategy D - Distinct Trio E - Road Reduction F - Bread C - Slot Strategy 解法は公式解説と同じだったので、実装例だけ書いておきます。 の左から番目に文字があるとして、を配列に記録しておきます。これを、 とします…

AtCoder Beginner Contest 251 参加記録

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

ABC250E Prefix Equality(ABC250 参加記録)

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

ABC249 参加記録

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

ABC248 参加記録

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

ABC243G Sqrt

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

ABC246 参加記録

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

ABC245 参加記録

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

ABC244 参加記録

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

ABC242G Range Pairing Query

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

Mo's Algorithm

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

ABC243 参加記録

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

ABC242D ABC Transform

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

ABC241 参加記録

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

ABC239F Construct Highway

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

ABC240 参加記録

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

ABC239 参加記録

コンテスト中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>…

ABC237F |LIS| = 3

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