コンテスト中AC:A〜D D - Online Games の制約が小さければ、以下のimos法で解けます。 ・人目について、配列のに+1、に-1する。 ・最後に、を2から最大日数まで順に+=する ・日目のログイン数は人である。 今回制約が大きいので配列保持することはできませ…

コンテスト中AC:A,B,D C - Long Sequence の合計をとすると、は個のとの番目の要素までの和で構成されているはずです。すなわち、 です。 は、を満たす最小の整数で、は順番に足していけば求まります。 コンテスト中にACできなかったのですが、実装に問題が…

解説ありで解きました。 メモ コンテスト中はDFSや全探索など実装方針がたたず、解けませんでした。 コンテスト後にbit全探索で解いてみましたが、入力例1があわず、公式解説とユーザー解説を確認し、多角形は穴があってはいけないことがわかりました。 そこ…

コンテスト中AC:A〜C 戦績が良くなかったので、コンテスト後に解けたDだけ書きます。 D - Strange Lunchbox 購入したお弁当の個数の情報と、その時のたこ焼き及びたい焼きの個数の情報が欲しいので、以下のDPを考えます。 種類目までのお弁当のうち個のお弁…

解説なし 辺の距離が全て1なので、最短距離、最短パスはBFSで求まります。 BFSはなので、すべての辺が通れないときを計算すると、で間に合いません。 元のグラフの最短距離が変化するのは、最短パス上の辺が通れなくなった場合だけです。したがって、このと…

2022/03/25 Eに追記 コンテスト中AC:A〜E C - Shapes D - Rectangles E - Destruction C - Shapes 難しかったです。 以下の2点を解決する必要があります。 90°回転の実装 平行移動の方法 90°回転は回転行列で解決しました。なお、全てのマスはxy座標上の点と…

前に解説読んでよくわからなかったので寝かしていましたが、今回やってみたら解けました。 まず、以下に頻出の考え方について説明します。 ある整数列のを末尾とする連続した部分列の要素の和がの倍数となるような、全てのを求めることを考えます。 とすると…

コンテスト中AC:A〜E D - Cutting Woods 結合している座標情報を管理する場合、操作列を逆順にしてUnion-Findで結合していくなどが考えられます。しかし、なので、全ての座標を保持することはできません。 そこで、切られた座標を管理することを考えます。 …

解説を見て解きました。 問題文の条件は、同じ色を連続して全て取ってから次の色を取るということを示します。 入力例1なら、32123の順で並んでいるボールを12233の順で取ります。同じ数字内での取り方に指定はありません。 ある色のボールを全て取ることを…

コンテスト中AC：A, B, C, D C - Many Balls 操作を逆順に考えるのは典型です。Nから始めて0にすることを考えると、魔法Aは-1、魔法Bは÷2することになります。 すると、奇数なら魔法Aしかできず、偶数なら魔法Bを使用する方が0に近づけます。 奇数ならA、偶…

B - log2(N) GCCの組み込み関数__builtin_clzllを使うと、 __builtin_clzll(1LL) - __builtin_clzll(N) で求められます。 提出コード：https://atcoder.jp/contests/abc215/submissions/25200114 C - One More aab aba baa 文字列の並び替えの総数は最大でも…

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]) で求まります。…

C - Reorder Cards 座標圧縮の問題です。 座標圧縮は昇順ソートして、小さい方から順に順位を割り振っていけばよいです。 例えば、{3 5 7 7 8 10}は、{1 2 3 3 4 5}です。 順序関係を崩さないように、小さい数字を割り当てていくと考えればよいかもしれませ…