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

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

コンテスト中AC:A 難しかったです。辛うじてAだけ解けました。 A - Make 10 本番でも自身の解法に確証がなかったので、公式解説を参照したほうがよいかもしれません。 使う数字をできるだけ少なくするようにする貪欲法を考えます。使う数字が少なければ、そ…

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