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

コンテスト中AC:A A - Dial Up に1しかないのにに1がある場合、-1です。0の場合も同様です。以下、そうでない時を考えます。 を円環とみなしたとき、と異なる数のうち最も近い位置と、との距離をとします。 への追加操作は明らかに回必要であるため、以下で…

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}です。 順序関係を崩さないように、小さい数字を割り当てていくと考えればよいかもしれませ…

C - Min difference Aの各要素について、差の絶対値が最小となるのは、Bの要素のうち、値の近い2つまたは1つです。これはBを予めソートしておくことで、二分探索によって求められます。 Bに予めを入れておくと、実装が楽になります。 差の絶対値は数直線上の…

A - LR Constraits 「全ての数字を必ず配置する」という条件があるので、制約iで指定されたには必ずiを配置する必要があります。逆に、にiを置くことにすれば、全ての数字を配置するという条件は満たされます。 ここで、K>Nなら答えは0です。以下、K≦Nとしま…

C - chokudai 典型的なDPだと思います。 dp[i][j] := i文字目まで考慮した時に"chokudai"のj文字目までが何通りあるか とします。 例えば、S[i] = 'k'だったとします。i-1文字目までに現れた全ての"cho"となる部分文字列に対して、i文字目を連結させて"chok"…

2022/01/16 追記 競技プログラミングを始めて3年ほど経ちました。 備忘録、アウトプットによる理解の向上を目的に記録をつけることにしました。参考になることがあれば幸いです。 なお、素人なので、間違いや厳密で無い場合があります。ご了承ください。