Problem - C - Codeforces 問題概要 左側、右側それぞれに 個の頂点があり、その間に合計 本の辺が存在する二部グラフが与えられる。右側の頂点にはそれぞれ正整数 が書かれている。 左側の頂点の部分集合 について、 を「右側の頂点のうち の要素のいずれか…

Problem - E - Codeforces 問題概要 整数 が与えられる。以下の条件を満たす長さ の数列 を1つ構築するか、そのようなものが存在しないことを判定せよ。 各要素は 以下の正整数である。 狭義単調増加である。 かつ を満たす3つ組 の個数はちょうど 個である…

お題箱より。 Problem - E - Codeforces 問題概要 頂点の木が与えられ、各頂点には a から t までのうち1文字のアルファベットが書かれている。 この木の2点間を結ぶパスであって、「通過する頂点のアルファベットを並び替えることで回文にすることができる…

お題箱より。 Problem - E - Codeforces 問題概要 整数 が与えられる。頂点数 の木であって、根を頂点 としたときに二分木になっていて、全頂点の深さ（根までの距離）の合計が であるものを構築せよ。またはそのような二分木が存在しないことを判定せよ。 …

お題箱より。 Problem - B - Codeforces 問題概要 頂点の無向完全グラフがある。このグラフの辺のうち、指定される 本の辺の重みは であり、それ以外の辺の重みは全て である。 このグラフの最小全域木の重み合計を求めよ。 制約 解法 クラスカル法のアルゴ…

Problem - D - Codeforces 計算量がキツキツなので想定解じゃないような気もするのですが、通せたので私の解法を書きます。 問題概要 頂点の有向完全グラフが与えられ、各辺にコストが設定されている。 頂点1からスタートしてちょうど 辺を通って頂点1に戻る…

お題箱より。 Problem - F1 - Codeforces 問題概要 Polycarpは初期評価 のフリーランスである。 依頼が 個ある。 番目の依頼は受諾時点で 以上の評価が必要であり、完了後に評価が 変化する（これは負であることもあり得る）。依頼の順序は好きに選んで良い…

バチャでやってて結構面白かったので。 Problem - G - Codeforces 問題概要 以下のように構成される、頂点数 ・辺数 の有向グラフを考える。 頂点は 個ずつの2グループに分類され、それぞれAパート・Bパートと呼ぶ。頂点を 、 と表記する。 について、 から …

Problem - E - Codeforces 問題概要 本の草が横一列に並んでいて、 本目の草の味は整数 で表現される。また 頭の牛がいて、 頭目の牛は味 の草を好み、それを 本食べると満足する。 以下の処理を行う。 互いに素な牛の集合 を選ぶ。一方または両方が空であっ…

Problem - E - Codeforces 問題概要 のマス目が与えられ、各マスは赤・緑・黄・青のいずれかに塗られている。 このマス目から の連続する正方形領域を取り出したときに、それが問題文の図の位置関係通りに4色の の正方形で構成されているとき、これをレベル …

Problem - F - Codeforces ※解説の都合上、マスに書かれている整数を「色」と表現することにします。記号も だし。 問題概要 のマスからなる盤面があり、各マスには色が塗られている。このマスそれぞれを頂点とし、隣り合うマスの色が等しいときにその間に辺…

Problem - C - Codeforces 問題概要 ※0-indexedで記載します。 実数列 が与えられる。（初期状態では各要素は正整数） この実数列に対して、「ある連続する区間を選び、その区間に含まれる要素全てをそれらの平均で置き換える」という操作を好きな回数繰り返…

Problem - C - Codeforces コンテスト本番は闇実装に突っ込んだので、ながたかなさんの解法をベースに書き直しました… 問題概要 ※解説・コードと合わせるため0-indexedで記述します。 番号 の電球が並んでいて、それぞれ初期状態でON/OFFどちらになっている…

Problem - F - Codeforces 問題概要 問の問題からなるコンテストがある。 番目の問題の正解者数は、区間 に含まれる整数の中から等確率で決まる。 問題 の正解者数が広義単調減少になる確率を求めよ。これは有理数になるため、 で出力せよ。 制約 解法 問題 …

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

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

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

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

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

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

Problem - D - Codeforces 問題概要 人の人がいて、「人 が 人 に 円借りた」という貸し借り履歴が 個与えられる。それらの貸し借り履歴を合計した、人 が人 に借りている金額を と表す。 この貸し借りの状態を、次のような規則で操作することができる。 操…

Problem - E - Codeforces 問題概要 ゲームにおいて 種類の資源があり、 について資源 を 個以上所持するとクリアとなる。 プレイヤーは1ターンごとに1個好きな資源を得ることができる。さらに、以下のような形式で表されるボーナスイベントがいくつか存在す…

Problem - F - Codeforces 問題概要 頂点の木が与えられる。いくつかの頂点からなる集合 が正整数 に対して以下の条件を満たすとき、 は almost -uniformであると呼ぶことにする。 に含まれる異なる2頂点のペア全てにおいて、その距離は または である。 そ…

お題箱より。 Problem - C - Codeforces 私のコンテスト中の思考をベースに書きます。ちょっとややこしいかも。 問題概要 個の門があり、これを門 から門 まで順番に突破していく。スタート地点は門 の直前であり、門 を突破すればクリアである。 門 の突破…

非想定解っぽいですがまとめておきます。 Problem - F - Codeforces 問題概要 問題文中の図のように、一列に並んだ 個のノードを挟むように根付き木が2つ与えられる。それぞれの頂点数は であり、葉の数はいずれも で、それぞれの木について各ノードごとに1…

お題箱より。 Problem - D - Codeforces 問題概要 ※解説の都合上、0-indexedと半開区間での記述に書き換えます。 非負とは限らない整数列 と、正整数 が与えられる。 この数列の連続部分列 について、そのスコアを と定める。ただし長さ0の連続部分列のスコ…

お題箱より。 Problem - E2 - Codeforces 問題概要 選挙の投票者が 人いて、全員が自分を支持するようにしたい。投票者 が自分を支持する条件は2つあり、どちらかを満たすと支持する。 金額 を払って買収する。 他の投票者のうち 人以上が自分を支持している…

お題箱より。 Problem - D - Codeforces 問題概要 文字列 が与えられ、それぞれの長さは である。また整数 が与えられる。 以下の条件を満たすような 個の文字列の組 の、長さの総和の最大値を求めよ。 のどの文字列も空でない。 のどちらにも、 がこの順番…

お題箱より。 Problem - D2 - Codeforces 問題概要 整数を端点とする 個の閉区間 が与えられる。これらから0個以上の区間を捨てて、全ての整数点について「その整数点を含んでいる区間は 個以下である」という状態にしたい。 捨てる区間の最小個数と、その選…

Problem - B - Codeforces 問題概要 長さ の括弧列 が与えられる。長さ の括弧列のスコアを、「 を 回だけ右巡回シフトした文字列が正しい括弧列になっている」という条件を満たす の個数とする。 に対して1度だけ、2箇所を選んでスワップする操作を行うこと…