Problem - E - Codeforces 問題概要 ※解説と合わせるために0-indexedで表記します。 長さ の順列 が与えられる。また を移動させるためのコスト がそれぞれ与えられる。 この順列に対して以下の処理を行う。 順列の隣り合う2要素間の境界を自由に選び、左グ…

E - Increasing Numbers 公式解説と少し違う方法で解いたので記録しておきます。 解法 十進法の桁を、一番下の桁を 桁目とするように表記します。 桁目は に対応する桁です。 「各桁から を引く回数」の条件への言い換え 非負整数が増加的であることは、「1…

F - Monochromization 解説放送を観て解いたので、その方針をベースに書きます。 解法 まずは判定問題 まず、ある盤面が初期盤面から操作を繰り返した後の最終状態として作れるかどうかの判定方法を考えます。 ある最終状態の盤面から操作を逆回しして考えま…

お題箱より。 Problem - F - Codeforces 問題概要 カッコ列 が与えられる。「正しい」カッコ列であって、 の両方を部分列として含むようなカッコ列のうち、長さが最小のものを1つ求めよ。 制約 解法 文字列のインデックスは0-indexedで表記します。 まずは正…

お題箱より。 Problem - E - Codeforces 少し前にバチャで扱われて話題になっていましたね。公式解説のDPの正当性が分からないというリクエストだったのですが、私もわからないので（ごめんなさい…）もう少し汎用的に使える解法を書きます。 問題概要 個の要…

E - Span Covering 本番中実装しきれなかったけど、公式解説と違う方法で解いたので記録。 解法 包除原理の適用 土地を 個のマスが並んだものとして扱います。このマスのうち0個以上のマスを選んだ集合 について、 に含まれるマスだけに全てのシートを置く（…

C - Cookie Distribution 解法 式変形と言い換え 全てのクッキーの配り方の集合を 、答えを とします。答えは の期待値に全ての配り方の通り数を掛けたものなので、 を全ての配り方について合計したもの、つまり以下のように表現できます。 実際には各 は配…

D - Arrangement 公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず… 解法 まずは貪欲に作ってみる 「カード の右隣のカードがカード であってはならない」という条件は、そんなに厳しい条件ではないように思います。なので…

Problem - D - Codeforces 異常実装になったけどなんとか自力で解けた… 問題概要 数直線上に 個の粒子がある。粒子 は初期位置 、速さ 、右に動く確率 で特徴づけられる。 この粒子を用いて以下の実験を行う。 まず各粒子の移動方向を確率に従って決める。粒…

Problem - E - Codeforces 問題概要 座標平面上に 個の点があり、 番目の点の座標は である。これら 個の点からなる集合を と表記する。全ての点は相異なり、どの3点をとってもそれらが一直線上に存在することはない。 点 のスコア を、「 に含まれる4点の選…

Problem - D - Codeforces 問題概要 講演会において 個の講演がある。A会場とB会場の2つがあり、講演 をA会場で行う場合の講演時間は時刻の閉区間 で、B会場で行う場合の講演時間は時刻の閉区間 で表される。 2つ以上の講演の集合 のうち、以下のようなもの…