ARMERIA

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

競技プログラミング

AtCoder Beginner Contest 138 D - Ki

お題箱より。 D - Ki 様々な木の問題を解く上で基本となるような実装なので、実装も含めて解説します。 解法 1回の操作のイメージを図にすると以下のようになります。 実際には大量の操作があるので、これを1つ1つ処理していくことはできません。ではどうす…

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は初期評価 のフリーランスである。 依頼が 個ある。 番目の依頼は受諾時点で 以上の評価が必要であり、完了後にレートが 変化する(これは負であることもあり得る)。依頼の順序は好きに選んで良…

合成数modでの二項係数を用いた数え上げ

先日やっていたバチャで出てきたので、まとめておきます。 この記事では二項係数を と表記します。また法を とします。 はじめに が必要となる の最大値をそれぞれ として、 や が許される制約であれば、パスカルの三角形で全部計算できます。こちらのほうが…

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

AtCoder Beginner Contest 155 E - Payment

E - Payment 上から派と下から派がいたようですが、私は上からで解いたのでそちらで書きます。 解法 上の桁から見ていって、その桁までで支払う&お釣りとして受け取る硬貨の枚数をなるべく小さくすることを考えます。 例えば 円だったとして、 の位の桁まで…

AtCoder Beginner Contest 155 D - Pairs

D - Pairs ※正直、これがABC-Dとして出るのはここ最近の傾向からすると異常です。じっくり解説を読んで理解するか、どうしても分からなければ温めておくのも手でしょう。 解法 二分探索に落とし込む 与えられた数列などに対して大量の数を計算し、その 番目…

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

AtCoder Regular Contest 059 E - キャンディーとN人の子供

お題箱より。 E - Children and Candies 部分点解法から満点解法へのステップアップについて重点的に書きます。 解法 部分点解法 部分点解法は公式解説にもしっかり書かれているので軽く。各 について なので、ある1つの組 に対してだけ を求めてください、…

Codeforces Round #616 C. Prefix Enlightenment

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

Educational Codeforces Round 81 F. Good Contest

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

yukicoder No.980 Fibonacci Convolution Hard

No.980 Fibonacci Convolution Hard - yukicoder 変な解き方をしました…。後述するように厳密に正しい解法ではないので、あまりオススメはしません。 解法 0-indexedのほうが楽なので、数列 を あとは同様の漸化式で定義される数列、としておきます。クエリ…

Educational Codeforces Round 81 E. Permutation Separation

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

AtCoder Grand Contest 011 E - Increasing Numbers

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

キーエンス プログラミング コンテスト 2020 F - Monochromization

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

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の正当性が分からないというリクエストだったのですが、私もわからないので(ごめんなさい…)もう少し汎用的に使える解法を書きます。 問題概要 個の要…

第6回 ドワンゴからの挑戦状 予選 E - Span Covering

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

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution

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

第6回 ドワンゴからの挑戦状 予選 D - Arrangement

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

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つ以上の講演の集合 のうち、以下のようなもの…

第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times

お題箱より。 F - Count Permutations Many Times 難しめの(とはいえ上級者には比較的知名度が高い)テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。 解法 …

Codeforces Global Round 6 D. Decreasing Debts

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

Codeforces Global Round 6 E. Spaceship Solitaire

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