ARMERIA

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

Codeforces

Codeforces Round #653 (Div. 3) E2. Reading Books (hard version)

Problem - E2 - Codeforces 問題概要 冊の本があり、本 は読むための所要時間 、アリスがその本を好きかどうか 、ボブがその本を好きかどうか で特徴付けられる。 冊の本からちょうど 冊の本を以下の条件を満たすように選ぶとき、その合計所要時間の最小値と…

Educational Codeforces Round 58 G. (Zero XOR Subset)-less

お題箱より。 Problem - G - Codeforces 問題概要 長さ の数列 が与えられる。これをいくつかの区間(連続部分列)に分割する。この分割は以下の条件を満たす必要がある。 全ての要素はちょうど1つの区間に属する。 区間のうち1つ以上のものをどのように選ん…

Codeforcesのレーティング計算の仕組み

Codeforcesのパフォーマンスって計算できるんだろうか、という話が挙がる機会が多いので、レーティング計算について調べた内容をまとめます。 情報源 公式な情報源はこれです。 Open Codeforces Rating System [updated on October 2015] - Codeforces 5年前…

Educational Codeforces Round 89 F. Jog Around The Graph

Problem - F - Codeforces 問題概要 頂点 辺の重み付き無向グラフが与えられる。グラフは単純かつ連結である。 正整数 について を「頂点 から始まってちょうど 回移動する経路の、通った辺の重み合計の最大値」と定める。この経路では同じ辺や頂点を複数回…

Codeforces Round #641 (Div. 1) F1. Slime and Sequences (Easy Version)

Problem - F1 - Codeforces 問題概要 ※解説の都合上、0-indexedで表記します。 正整数 が与えられる。長さ の非負整数列 が以下の性質を満たす時、これを「良い数列」であると呼ぶ。 に1つ以上含まれる任意の正整数 について、 かつ かつ であるインデックス…

Codeforces Round #645 (Div. 2) F. Tasty Cookie

Problem - F - Codeforces 問題概要 長さがともに の数列 が与えられる。数列 に対して、以下の操作を 回以上好きな順番で行って に一致させたい。 数列 を反転する。 数列 を、 の先頭からの累積和を並べた数列に置き換える。 これが可能かどうか判定し、可…

Educational Codeforces Round 17 D. Maximum path

お題箱より。 Problem - D - Codeforces 問題概要 行 列のグリッドが与えられ、各マスには整数(非負とは限らない) が書かれている。 左上のマスからスタートし、隣り合うマスを辿って右下のマスまで移動する経路であって、同じマスを複数回通るものがない…

Codeforces Round #490 (Div. 3) F. Cards and Joy

お題箱より。 Problem - F - Codeforces 問題概要 人のプレイヤーに 枚ずつのカードを配る。 枚のカードそれぞれにかかれている数字 と、プレイヤー が好きな数字 が与えられる。 それぞれのプレイヤーは、配られたカードのうち好きな数字が書かれたものが …

Codeforces Round #641 (Div. 1) B. Orac and Medians

お題箱より。 Problem - D - Codeforces 問題概要 長さ の整数列 が与えられる。この数列に以下の操作を0回以上行ってよい。 ある連続部分列 を選び、それら全てをその中央値で置き換える。ただしこの問題において、 個の値の中央値は小さい方から 番目の値…

Educational Codeforces Round 35 G. Mass Change Queries

お題箱より。 Problem - G - Codeforces Editorialのコメント欄に色々別解が書かれているのですが、この記事はEditorial本文の解法を扱います。 問題概要 長さ の整数列 が与えられる。この数列に対する操作が 個与えられ、これを順番に施す。 操作 : であ…

Codeforces Round #614 (Div. 1) C. Xenon's Attack on the Gangs

お題箱より。 Problem - C - Codeforces 問題概要 頂点の木が与えられる。この木の辺に の値を1つずつ割り振ることを考える。 異なる2頂点 に対して を「 間パスに含まれる辺の値として登場しない最小の非負整数」と定義する。そして値の割り振り方のスコア …

Codeforces Round #501 (Div. 3) F. Bracket Substring

お題箱より。 Problem - F - Codeforces 問題概要 整数 と、開き括弧・閉じ括弧からなる文字列 が与えられる。長さ の正しい括弧列であって、その連続部分文字列として をどこかに含むものの個数を で求めよ。 制約 解法 DPを立てる 正しい括弧列の問題は、(…

Codeforces Round #636 (Div. 3) F. Restore the Permutation by Sorted Segments

Problem - F - Codeforces 問題概要 長さ の順列 がある(与えられない)。この順列に対して、 それぞれに対して以下のように計算される 個の数列が与えられる。 各 に対して、 なる を選び、 をソートした数列。 ここで 個の数列は並べ替えられた順番で与え…

Codeforces Round #630 (Div. 2) G. No Monotone Triples

お題箱より。けっこう難しかった… Problem - G - Codeforces 問題概要 数列 が与えられる。この数列の長さ 以上の部分列が「free from monotone triples」であるということを、「その部分列からさらに長さ の部分列をどのように取っても、広義単調増加にも広…

Codeforces Round #629 (Div. 3) F. Make k Equal

お題箱より。 Problem - F - Codeforces リクエストに沿って、正当性の説明をします。ちゃんと証明を組むとなかなか大変でした… 問題概要 要素の整数列 と整数 が与えられる。 1回の操作で、この数列に以下のいずれか1つを行うことができる。 操作 : の最小…

Codeforces Round #635 (Div. 1) E1. Chiori and Doll Picking (easy version)

Problem - E1 - Codeforces E1しか解けていないので、E1しか通らない解法を書きます…。この他にも色々な解法があるっぽい? 問題概要 個の非負整数 が与えられる。また非負整数 が与えられ、 である。 から任意個の要素を選ぶ選び方は全部で 通りある。選ん…

Codeforces Round #632 (Div. 2) F. Kate and imperfection

Problem - F - Codeforces 問題概要 正整数 が与えられ、集合 と定める。要素数2以上である の部分集合 について、 の値を「 に含まれる相異なる2要素 に対する の最大値」と定める。 に対して、要素数が である の部分集合 についての の最小値を求めよ。 …

Codeforces Round #631 (Div. 1) D. Dreamoon Likes Strings

Problem - D - Codeforces 問題概要 英小文字からなる文字列 が与えられる。この に以下の操作を繰り返して空文字列にしたい。 の連続する部分文字列であって、どの隣り合う文字も等しくないものを1箇所選ぶ。それを除去し、残った部分を結合する。 その最小…

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パートと呼ぶ。頂点を 、 と表記する。 について、 から …