ARMERIA

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

プログラミング

Educational Codeforces Round 94 F. x-prime Substrings

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

DDCC 2016 本選 C - 特別講演「括弧列と塗り分け」

お題箱より。 C - 特別講演「括弧列と塗り分け」 解法 この問題を考えるにあたって重要なのが、正しい括弧列を根付き木と対応づけることです。 それぞれの括弧1組ずつを頂点とみなします。そしてその括弧の1つ外側を囲っている括弧を親とみなすように辺を張…

yukicoder No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)

お題箱より。 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder 解法 箱を並び替えても答えが変わることはないので、 の昇順に並べておきます。 各箱から玉を1個ずつ取り出し、ある1つの色 の玉がちょうど 個選ばれる場…

University of Aizu Programming Contest 2014 (AOJ 1548) Yu-kun Likes a Directed Graph

お題箱より。 Aizu Online Judge 解法 重み の負辺を足してできるだけ重み合計が大きい( に近い)負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が 未満であるもののうち一番大きいものの重み」が分かれば良…

University of Aizu Programming Contest 2012(AOJ 1508)RMQ

お題箱より。 Aizu Online Judge 解法 1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存…

AtCoder Beginner Contest 170 E - Smart Infants

お題箱より。実装方法に関するリクエストだったので実装中心で書きます。 E - Smart Infants 解法 解法としてはシミュレーションです。園児が移動したときに、どのようなデータを管理しておけば効率的に答えを更新できるかを考えます。 今回は以下のようなデ…

CPSCO2019 Session3 F - Flexible Permutation O(N^2)解法

お題箱より。 解法が知りたいというリクエストだったので考えてみました。 F - Flexible Permutation 解法 後に扱うDPの都合上、個人的にはインデックスよりも値に注目したほうが理解しやすいので、条件を値中心の言葉に言い換えます。 であるような値 を「…

Educational Codeforces Round 92 F. Bicolored Segments

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

エイシング プログラミング コンテスト 2020 F - Two Snuke

F - Two Snuke 公式解説とは違う解法です。 解法 のときは答えは なので、 とします。 まずは 解法を まず答えを で求める方法を考えます。 の値を として、これを全通り試しましょう。そうすると、この を つに分ける分け方が 通りあります。 個並んだボー…

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

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

Codeforces Global Round 9 E. Inversion SwapSort

Problem - E - Codeforces 問題概要 長さ の数列 が与えられる。この数列についてインデックスのペア が かつ を満たすとき、このペアは転倒していると呼ぶ。 与えられた について転倒している全てのペアを並べた列であって、「列に並んでいる順に、ペアが示…

AtCoder Grand Contest 043 C - Giant Graph

お題箱より。 C - Giant Graph この問題は数ヶ月前に「なぜこの発想を思いつけるのか分からない」というリクエストをもらっていて、私にも分からなかったので記事を書けずにいました。でしたが、(同じ人が違う人かは分かりませんが)2つ目のリクエストをも…

Introduction to Heuristics Contest 参加記録

Introduction to Heuristics Contest - AtCoder 33位でした。 戦略 焼きなまし法を選択しました。 理由は、問題の性質として解の局所改善がやりやすく、スコアの差分計算を高速化して大量に回せそうだと考えたからです。対して、1手の変更がその後の展開を大…

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

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

yukicoder No.1100 Boxes

No.1100 Boxes - yukicoder 解法 まずボールが1つも入っていない箱の数を固定します。これを とすると、その選び方は 通りです。 その上で、残りの 個の箱全てにボールが入るような場合の数を求めます。これは包除原理を用いて と求めることができます。 先…

AtCoder Beginner Contest 171 F - Strivore

F - Strivore 解法 文字列 の長さを とします。また最終的に出来上がる文字列を と表記します。 の長さは になります。そのうち元々あった文字と追加した文字の場所の割り当て方が 通りで、追加した文字の種類が 通りで…とやりたくなりますが、これでは最終…

AtCoder Grand Contest 046 C - Shift

C - Shift 解法 に含まれる 0 の個数を 、1 の個数を と書くことにします。 を、0 で区切られた 個のエリアに分割します。 図に示すように、エリア に含まれる 1 の個数を とし、エリア を含むそれ以前に含まれる 1 の個数を とします。 本問題の操作は、1 …

AtCoder Grand Contest 046 B - Extension

B - Extension 解法 まず以下のようなDPを考えてみましょう。 本問題の操作によって、縦 行、横 列になるまで操作してできる盤面の数 このDPで「上側に行を足し、その1つを黒く塗る」遷移と「右側に列を足し、その1つを黒く塗る」遷移をすれば良さそうですが…

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

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

AtCoder Beginner Contest 170 F - Pond Skater

F - Pond Skater 解法 1ターンに1マスの移動であればグリッド上のBFSで解けますが、今回は1ターンに マスまで動くことができます。これをそのままBFSで処理すると1つのマスから遷移可能なマスが最大 個になり、全体計算量 になって間に合いません。 具体的に…

東京海上日動 プログラミングコンテスト2020 D - Knapsack Queries on a tree

D - Knapsack Queries on a tree Editorialと同じ解法で解いたのでそっちを書きます。クエリごとに独立に解く方法もあって、そっちで解いた人のほうが多そうな印象です。 解法 が十分大きいという前提で解説をします。また扱う重みの最大値を 、最大深さの半…

Educational Codeforces Round 89 F. Jog Around The Graph

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

AtCoder Grand Contest 045 C - Range Set

C - Range Set 解法 必要十分条件への言い換え ある01文字列が与えられた時に、それが操作によって生成可能であるかを判定することを考えます。 ここで今回のように「塗り潰す」系の操作の場合、「判定したい文字列から逆順で操作を行い、初期状態に戻せるか…

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

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

AtCoder Beginner Contest 011 D - 大ジャンプ

お題箱より。 D - 大ジャンプ 解法 まずは計算しやすいようにいくつか前処理をします。 ゴールまでの 軸方向それぞれの距離を で割ることで「正の方向にジャンプ○回分」という値に変換します。ここで割り切れない場合、答えは です。今後は で割った後の値を…

TopCoder Marathon Match 118 DanceFloor 参加記

Topcoder 初めてのTopCoderマラソンマッチ。34位/68人とちょうど真ん中の成績でした。 問題概要 のグリッドの各マスが 色のうちいずれかで塗られている。 人のダンサーがいて、 単位時間かけてグリッド上を移動する。このとき各マスが1回踏まれるたびに、周…

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

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

AtCoder Grand Contest 044 A - Pay to Win

A - Pay to Win 公式解説、丁寧だけど英語なんですよね…だいたいそのまま訳す感じの解説になってしまいそうですが許してください。 解法 操作を限定できる形に持ち込む いきなりですが、操作を逆から考えます。 気持ちとしては、 からの操作を考えるとどの遷…

Educational Codeforces Round 17 D. Maximum path

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

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

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