ARMERIA

Rubyと競技プログラミングの話 AtCoderや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 問題概要 人のプレイヤーに 枚ずつのカードを配る。 枚のカードそれぞれにかかれている数字 と、プレイヤー が好きな数字 が与えられる。 それぞれのプレイヤーは、配られたカードのうち好きな数字が書かれたものが …

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

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

CodinGame Spring Challenge 2020 参加記

CodinGame Spring Challenge 2020に参加して、Legendリーグ57位でした! 対戦動画をTwitterで見て、何となく面白そうだなと思って参加したらドハマリしました。睡眠時間と休日とCodeforcesのコンテスト2回分が犠牲になりましたが、Legendリーグに進出するこ…

AtCoder Beginner Contest 168 F - . (Single Dot)

F - . (Single Dot) 解法の理解というよりは実装慣れのほうが重要な問題だと思います。末尾につけているACコード例と対応させながら読んでいくといいかもしれません。 解法 図における座標軸は問題文に従い、北を上にして図示するようにします。一般的なXY平…

AtCoder Beginner Contest 167 E - Colorful Blocks

E - Colorful Blocks 解法 「隣り合うブロックの組であって同じ色で塗られている組」がちょうど 個あるとして、 についてそれぞれ求めた場合の数を合計することで答えを求めます。 ブロックは全部で 個なので、ブロックが隣り合っている箇所は 箇所です。こ…

AtCoder Beginner Contest 167 F - Bracket Sequencing

F - Bracket Sequencing 解法 「正しい括弧列」について この問題だと単に括弧列という言葉が使われていますが、どちらかと言うと「正しい括弧列」みたいな呼ばれ方をされることが多いです。 正しい括弧列の条件は、言葉で書くと 開き括弧と閉じ括弧の数が等…

yukicoder No.1051 PQ Permutation

No.1051 PQ Permutation - yukicoder ※当初の公開時点での解説およびリンク先コードが誤っていたため、修正しました。 解法 ※以下の解説中で「辞書順で1つ進める」と書いた時には、「もし進められない(既に辞書順最大である)ときには -1 を出力して終了す…

Educational Codeforces Round 35 G. Mass Change Queries

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

AtCoder Beginner Contest 165 C - Many Requirements

AtCoder Beginner Contest 165 - AtCoder 解法 得点の計算方法が面倒で、賢い解き方はなかなか思い浮かびません。制約が小さいことに注目して全探索の方針を考えます。 制約上の最大値である で考えます。数列 としてあり得るものは、単純に見積もると 以上 …

パソコン甲子園2019本選 (AOJ 0426) 三角形の個数の和

お題箱より。 Aizu Online Judge 解いてなかったのでこのリクエストを見て解きました。 解法 言い換えを重ねる 全ての点の個数を と表記することにします。 「全ての点集合について、その集合に含まれる三角形を数えて合計する」を、「全ての三角形をなす3点…

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

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

AtCoder Grand Contest 037 A - Dividing a String

お題箱より。 A - Dividing a String 貪欲とDPどちらを書こうか迷いましたが、貪欲解法のほうで書きたいと思います。 問題概要 文字列 が与えられる。この をできるだけ多くの部分文字列に分割したい。ただし、隣り合う2つの部分文字列が一致してはならない…