コンテストページ: AtCoder Beginner Contest 294 - AtCoder コンテスト中AC: A〜E, G G - Distance Queries on a Tree G - Distance Queries on a Tree 値の一点更新が可能な、木上のパスクエリを処理するデータ構造があれば、そのまま適用して解けます。 …
コンテストページ: AtCoder Regular Contest 158 - AtCoder コンテスト中AC: A A - +3 +5 +7 3つの値を同じにする問題は割と良く見る気がします。そして、この系統の問題は、差をどのように詰めるのか、という視点で見ると解ける場合が多いです。 今回、及び…
コンテストページ: AtCoder Beginner Contest 292 - AtCoder コンテスト中AC: A〜D コンテスト後にE,Fを解説ACしました。要点ををまとめておきます。 D - Unicyclic Components Union-Findで連結成分の何らかのデータを統合していく問題はよく出題されます。…
コンテストページ: Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 289） - AtCoder コンテスト中AC: A〜E コンテスト後にFをAC。WAが出たので、解説を見たが、解法は合っていて実装が間違っていた。 E - Swap Places 高橋くんがいる頂点…
コンテストページ: https://atcoder.jp/contests/abc291 コンテスト中AC:A〜E Fは大方の解法まではコンテスト中に辿りついたが、最後の詰めと実装が間に合わず。コンテスト後に自力AC。 D - Flip Cards E - Find Permutation F - Teleporter and Closed off …
コンテストページ: Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288） - AtCoder コンテスト中AC: A〜C コンテスト後自力AC: D〜F D - Range Add Query 0-indexedとします。 を愚直に全て0にできるか試すときどうするかを考え…
コンテストページ: https://atcoder.jp/contests/abc287 コンテスト中AC: A〜E C - Path Graph? D - Match or Not E - Karuta C - Path Graph? パスグラフのとき、両端の次数は1で、それ以外は2です。また、連結成分の数はただ1つになる必要があります。 以…
コンテストページ: UL Systems Programming Contest 2023(AtCoder Beginner Contest 286) - AtCoder コンテスト中AC: A〜E D - Money in Hand 公式解説とは異なる方法でとする方法を書いておきます。 Sliding Window Agrregationを使います。 DP遷移の一例を…
コンテストページ:AtCoder Beginner Contest 285 - AtCoder コンテスト中AC:A〜D コンテスト後自力AC:E,F D - Change Usernames E - Work or Rest F - Substring of Sorted String D - Change Usernames ユーザ名の重複を取り除き、番号を振り直したものをと…
コンテストページ: HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) - AtCoder コンテスト後にAC: A〜C コンテスト後にD,Eは自力で解けず 。Fは自力AC D - Make Bipartite 2 E - Choose Two and Eat One F - Union of Two Sets D - Mak…
コンテストページ: https://atcoder.jp/contests/abc281 コンテスト中AC: A〜D コンテスト後にEをAC(自力) D - Max Multiple が小さい 倍数はの情報があれば良い これらからDPだろうと判断しました。 情報としては、 何項目までを考慮したか 選んだ項の総和…
コンテストページ: コンテスト中AC: A〜E D - Factorial and Multiple E - Critical Hit D - Factorial and Multiple 制約上、くらいの解法、すなわち素因数分解や約数を利用した解法を疑います。今回は素因数分解で解けました。 が素因数を1つだけ持つとし…
コンテストページ: TOYOTA SYSTEMS Programming Contest 2022(AtCoder Beginner Contest 279) - AtCoder コンテスト中AC:A〜D コンテスト後にE,Fを自力AC。 D - Freefall 整数の三分探索の方法 探索範囲の最大値 下に凸であることの判定 E - Cheating Amidak…
コンテストページ:AtCoder Beginner Contest 278 - AtCoder コンテスト中AC:A〜D E,Fはコンテスト後に自力AC E - Grid Filling F - Shiritori E - Grid Filling このユーザ解説と同じ方法で解きました。 想定解法は二次元累積和だったようです。 実装:Editor…
コンテスト中AC:A〜E D - Takahashi's Solitaire E - Crystal Switches D - Takahashi's Solitaire コンテスト後に考え直したので、メモしておきます。 一旦modを無視します。 以下の問題を解けばこの問題に答えられます。 から要素を順に選び、とする。但し…
コンテストページ:AtCoder Beginner Contest 275 - AtCoder コンテスト中AC:A,B,D コンテスト後AC:E,F(自力) Cでハマったのと、Eで回数制限があることを忘れて考察してしまいました。 C - Counting Squares D - Yet Another Recursive Function E - Sugoroku…
コンテスト中AC:A〜D コンテスト後AC:E,F (いずれも自力) D - Robot Arm 2 E - Booster 宝箱に訪れた個数によって、移動速度が異なる 宝箱には行かなくてもよい 原点を出発し、原点に戻る F - Fishing D - Robot Arm 2 過去問に類題があります。 過去問のリ…
2022/10/20 Eに永続スタックによる解答を追記 コンテストページ:Panasonic Programming Contest 2022(AtCoder Beginner Contest 273) - AtCoder コンテスト中AC:A〜D Eもコンテスト後に自力で解けました。 D - LRUD Instructions E - Notebook D - LRUD Inst…
コンテストページ:https://atcoder.jp/contests/abc270 コンテスト中AC:A〜D Eはコンテスト中は実装ミスで間に合いませんでしたが、コンテスト後に解けたので書いておきます。 D - Stones E - Apple Baskets on Circle D - Stones 石が個の状態からは、石が…
最遠点を求めた後にLink-Cut Treeで回移動する解法で解いてみました。 ここでは、Link-Cut Treeの詳細な説明は割愛し、必要な部分だけを記載します。 詳細は以下のサイトを見るのが良いと思います。 Link-Cut Treeの実装メモ - 日々ｄｒｄｒする人のメモ Lin…
コンテストページ： UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder コンテスト中AC:A〜E Fがあと一歩だったので、書いておきます。 F - Numbered Checker 長方形領域の列は以下の2つに大別されます。 ?には整数が入ります。 0 …
コンテストページ:UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) - AtCoder コンテスト中AC:A〜D D - Unique Username 文字列の並べ替え方が通りです。 アンダーバーの入れ方ですが、まず、アンダーバーを入れる残り個数は…
コンテストページ:https://atcoder.jp/contests/abc267 コンテスト中AC: A〜D コンテスト中にもう少しのところでACできなかったEについてコンテスト後に解けたので書きます。 E - Erasing Verticles 2 とり得る値の最小値を求める問題では、二分探索できない…
コンテストページ AtCoder Beginner Contest 266 - AtCoder コンテスト中AC:A,B,D コンテスト後にC,E,Fを自力(AtCoderの解説を見ず)AC C - Convex Quadrilateral 下のサイトに判定方法がありました。 第6回 多角形の幾何（前編） | gihyo.jp 多角形上を半時…
コンテスト中AC:A〜D A〜Dで特に書くことがないので、コンテスト後に解いたE問題について書いておきます(解説AC)。 問題 E - Warp 公式解説 Editorial - AtCoder Beginner Contest 265 コンテスト中に考えていた誤りの解法 コンテスト中は、全体の移動方法か…
コンテストページ:LINE Verda Programming Contest（AtCoder Beginner Contest 263） - AtCoder コンテスト中AC: A〜E E - Sugoroku 3 E - Sugoroku 3 期待値DPが使えます。 サイコロを振ることを操作と呼ぶことにします。 マスからマスまでにかかる操作回数…
コンテストへのリンク:■ コンテスト中AC:A〜D D - I Hate Non-integer Number 数列の部分和に関する問題なので、部分和DPを考えます。 数列の項目までの部分和であって、和がとなるものの個数 今回は、何個選んだかも必要なので、情報を足します。 数列の項…
コンテスト中AC:A〜F D - Flipping and Bonus E - Many Operations F - Sorting Color Balls D - Flipping and Bonus 説明のため、お金をスコア、コイントスによって表か裏かを選んでスコアを得ることを操作と呼びます。 その時々の操作後のスコアを最大化す…
コンテスト後に自力ACしましたが、記事を書いていて計算量の見積もりが誤っていたので、公式解説を読みました。 頂点集合を以下の通りとします。 は独立集合であるという条件から、4-cycleをもつ条件は以下に限定されます。 に属するある頂点と、に属するあ…
コンテスト中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<>…
