geam1113’s diary

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

Union-Find

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

ABC238E Range Sums

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

ABC229 参加記録

コンテスト中AC:A〜E D - Longest X E - Graph Destruction D - Longest X 連続させたい個数をm個に固定すると、S連続する部分列のうち、m個の要素を含むものについて、いずれか1つでも全てXにできれば、連続m個を達成できます。 必要な操作回数は、部分列に…

ABC214 参加記録

C -Distribution すぬけくんの番号を0-indexedとします。i番目のすぬけくんが宝石をもらう最短時刻ans[i]が分かっていれば、i+1番目(正確には(i+1)%N)のすぬけくんが宝石をもらう最短時刻ans[i+1]は、 ans[i+1] = min(T[i+1], ans[i] + S[i]) で求まります。…