ARMERIA

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

2020-02-01から1ヶ月間の記事一覧

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

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

ゆるふわ競プロオンサイト #3 (Div. 1) Yet Another Cake Division

Programming Problems and Competitions :: HackerRank 解法 最初の気付き まず初手に気づけるかどうかが勝負です。この問題は、以下のような2本の経路のペアを数える問題に言い換えられます。 このように、下と右の移動だけで左上隅→右下隅を結ぶ経路と、上…

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のほうが楽なので、数列 を あとは同様の漸化式で定義される数列、としておきます。クエリ…