geam1113’s diary

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

AtCoder Beginner Contest 278 備忘録

コンテストページ:AtCoder Beginner Contest 278 - AtCoder コンテスト中AC:A〜D E,Fはコンテスト後に自力AC E - Grid Filling F - Shiritori E - Grid Filling このユーザ解説と同じ方法で解きました。 想定解法は二次元累積和だったようです。 実装:Editor…

AtCoder Beginner Contest 277 備忘録

コンテスト中AC:A〜E D - Takahashi's Solitaire E - Crystal Switches D - Takahashi's Solitaire コンテスト後に考え直したので、メモしておきます。 一旦modを無視します。 以下の問題を解けばこの問題に答えられます。 から要素を順に選び、とする。但し…

AtCoder Beginner Contest 275 備忘録

コンテストページ:AtCoder Beginner Contest 275 - AtCoder コンテスト中AC:A,B,D コンテスト後AC:E,F(自力) Cでハマったのと、Eで回数制限があることを忘れて考察してしまいました。 C - Counting Squares D - Yet Another Recursive Function E - Sugoroku…

AtCoder Beginner Contest 274 メモ

コンテスト中AC:A〜D コンテスト後AC:E,F (いずれも自力) D - Robot Arm 2 E - Booster 宝箱に訪れた個数によって、移動速度が異なる 宝箱には行かなくてもよい 原点を出発し、原点に戻る F - Fishing D - Robot Arm 2 過去問に類題があります。 過去問のリ…

AtCoder Beginner Contest 273 参加記録

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…

AtCoder Beginner Contest 270 参加記録

コンテストページ:https://atcoder.jp/contests/abc270 コンテスト中AC:A〜D Eはコンテスト中は実装ミスで間に合いませんでしたが、コンテスト後に解けたので書いておきます。 D - Stones E - Apple Baskets on Circle D - Stones 石が個の状態からは、石が…

AtCoder Beginner Contest 267 F - Exactly K Steps

最遠点を求めた後にLink-Cut Treeで回移動する解法で解いてみました。 ここでは、Link-Cut Treeの詳細な説明は割愛し、必要な部分だけを記載します。 詳細は以下のサイトを見るのが良いと思います。 Link-Cut Treeの実装メモ - 日々drdrする人のメモ Lin…

AtCoder Beginner Contest 269 参加記録

コンテストページ: UNICORN Programming Contest 2022(AtCoder Beginner Contest 269) - AtCoder コンテスト中AC:A〜E Fがあと一歩だったので、書いておきます。 F - Numbered Checker 長方形領域の列は以下の2つに大別されます。 ?には整数が入ります。 0 …

AtcCoder Beginner Contest 268 参加記録

コンテストページ:UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) - AtCoder コンテスト中AC:A〜D D - Unique Username 文字列の並べ替え方が通りです。 アンダーバーの入れ方ですが、まず、アンダーバーを入れる残り個数は…

AtCoder Beginner Contest 267 参加記録

コンテストページ:https://atcoder.jp/contests/abc267 コンテスト中AC: A〜D コンテスト中にもう少しのところでACできなかったEについてコンテスト後に解けたので書きます。 E - Erasing Verticles 2 とり得る値の最小値を求める問題では、二分探索できない…

AtCoder Biginner Contest 266 記録

コンテストページ AtCoder Beginner Contest 266 - AtCoder コンテスト中AC:A,B,D コンテスト後にC,E,Fを自力(AtCoderの解説を見ず)AC C - Convex Quadrilateral 下のサイトに判定方法がありました。 第6回 多角形の幾何(前編) | gihyo.jp 多角形上を半時…

AtCoder Begginer Contest 265 E - Warp (兼参加記録)

コンテスト中AC:A〜D A〜Dで特に書くことがないので、コンテスト後に解いたE問題について書いておきます(解説AC)。 問題 E - Warp 公式解説 Editorial - AtCoder Beginner Contest 265 コンテスト中に考えていた誤りの解法 コンテスト中は、全体の移動方法か…

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++では角度はラジアンにしないといけないので、として、の代わりにを渡します。 実装は、よう…

構造体Loop

初めに 概要 コンストラクタ build get count 実装 アルゴリズム 前処理について getについて countについて AtCoderでの過去問でLoopを使える問題 初めに 独自で実装している構造体Loopについて書いておきます(C++です)。 AtCoderでこの構造体を使用して解…

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 自分の実装 方…

ARC139 参加記録

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

ABC249 参加記録

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