ARMERIA

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

Codeforces

Codeforces Round #673 (Div. 1) D. Graph and Queries

Problem - D - Codeforces コンテスト中に自分が通した解法を書きます。 問題概要 頂点 辺の無向グラフが与えられ、頂点 には相異なる整数 が書かれている。 以下のクエリを合計 個処理せよ。 1 v:頂点 と連結な頂点の中で最も大きい整数が書かれている頂点…

Educational Codeforces Round 11 E. Different Subsets For All Tuples

お題箱より。 Problem - E - Codeforces 公式解説より楽な解法があるのでそっちを紹介します。記事最後に、リクエストにあった公式解説の補足についても説明します。 問題概要 整数列 に対して、 を「 の部分列(連続でなくても良い)として登場する長さ 以…

Codeforces Round #670 (Div. 2) E. Deleting Numbers

Problem - E - Codeforces 問題概要 インタラクティブ問題である。 まず正整数 が与えられる。ジャッジは 以上 以下の整数 を持っている。また集合 があり、初期状態では である。 以下のクエリを合計 回まで投げることができる。 の値を特定し、Cクエリで解…

Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps

お題箱より。 Problem - D - Codeforces 問題概要 本のビルがあり、 番目のビルの高さは である。 ビル からビル へは、 かつ以下の3条件のいずれか1つを満たす場合にジャンプして移動することができる。 :ビル は隣り合っている。 :間にあるビルが全て、…

Educational Codeforces Round 94 F. x-prime Substrings

Problem - F - Codeforces 自分の解法が非想定解っぽいので書き残しておきます。 問題概要 を正整数とする。 の数字からなる文字列が -primeであることを、以下の2つをともに満たすことと定義する。 全ての数字の和が である。 任意の連続部分列について、そ…

Educational Codeforces Round 92 F. Bicolored Segments

お題箱より。 Problem - F - Codeforces 問題概要 個の閉区間 が与えられ、それぞれは赤または青のいずれか1色に塗られている。 「異なる色の2つの区間が共有点を持ってはいけない」という条件のもとで、これらのうちできるだけ多くの区間を選びたい。選ぶ個…

Codeforces Round #654 (Div. 2) E2. Asterism (Hard Version)

Problem - E2 - Codeforces 問題概要 長さ の数列 と素数 が与えられる。まず、以下の問題を考える。 整数 が与えられる。 を並び替えた順列 であって、全ての について が成り立つようなものは何通りか? この問題の答えが の倍数とならないような を全て列…

Codeforces Global Round 9 E. Inversion SwapSort

Problem - E - 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: …