ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Codeforces

Codeforces Round #622 (Div. 2) D. Happy New Year

お題箱より。 Problem - D - Codeforces 問題概要 人の子供がいて の番号を持っている。以下の 個の操作についてそれぞれ、実行するかしないかを選ぶことができる。 区間 に属する子供に1個ずつキャンディを与える。 ここで整数 が与えられ、 個を超える操作…

Educational Codeforces Round 84 F. AND Segments

Problem - F - Codeforces 問題概要 整数 と、整数の組 が 個与えられる。以下の条件を満たす長さ の整数列 の個数を で求めよ。 全ての要素は を満たす。 整数の組 で表現される以下の条件を 個全て満たす。 のビットANDを取った値がちょうど となる。 制約…

Codeforces Global Round 7 E. Bombs

Problem - E - Codeforces 問題概要 から までの順列 が与えられる。 爆弾が仕掛けられているインデックスの集合 を考える。 に対して以下のように計算される値を と定義する。 を空集合とする。 の順に以下の操作を行う。 集合 に を追加する。その後 なら…

Educational Codeforces Round 83 G. Autocompletion

Problem - G - Codeforces 問題概要 個の相異なる英小文字列からなる集合 がある。この集合の要素 それぞれについて以下を求めよ。 文字列 を空文字列から始めて、以下の2つの操作を好きな順番で繰り返して と一致させるための最小コストを求めよ。 操作1: …

Codeforces Round #626 (Div. 1) C. Instant Noodles

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

Codeforces Ozon Tech Challenge 2020 (Div.1 + Div.2) E. Kuroni and the Score Distribution

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

Codeforces Round #458 (Div. 1 + Div. 2, combined) E. Palindromes in a Tree

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

Codeforces Round #624 (Div. 3) E. Construct the Binary Tree

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

Codeforces Round #599 (Div. 1) B. 0-1 MST

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

Codeforces Round #623 (Div. 1) D. Tourism

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

Codeforces Round #579 (Div. 3) F1. Complete the Projects (easy version)

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

Educational Codeforces Round 34 G. Yet Another Maxflow Problem

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

Codeforces Round #621 (Div. 1 + Div. 2) E. Cow and Treats

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

Codeforces Round #619 (Div.2) E. Nanosoft

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

Educational Codeforces Round 82 F. Number of Components

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

Codeforces Round #618 C. Water Balance

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

Codeforces Round #616 C. Prefix Enlightenment

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

Educational Codeforces Round 81 F. Good Contest

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

Educational Codeforces Round 81 E. Permutation Separation

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

Codeforces Round #605 (Div. 3) F. Two Bracket Sequences

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

Educational Codeforces Round 21 E. Selling Souvenirs

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

Codeforces Round #612 (Div. 1) D. LCC

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

Codeforces Hello 2020 E. New Year and Castle Construction

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

Codeforces Hello 2020 D. New Year and Conference

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

Codeforces Global Round 6 D. Decreasing Debts

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

Codeforces Global Round 6 E. Spaceship Solitaire

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

Codeforces Global Round 6 F. Almost Same Distance

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

Codeforces Round #604 (Div. 1) C. Beautiful Mirrors with queries

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

Codeforces Round #603 (Div. 2) F. Economic Difficulties

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

Educational Codeforces Round 69 D. Yet Another Subarray Problem

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