ARMERIA

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

2019-01-01から1年間の記事一覧

第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times

お題箱より。 F - Count Permutations Many Times 難しめの(とはいえ上級者には比較的知名度が高い)テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。 解法 …

Codeforces Global Round 6 D. Decreasing Debts

Problem - D - Codeforces 問題概要 人の人がいて、「人 が 人 に 円借りた」という貸し借り履歴が 個与えられる。それらの貸し借り履歴を合計した、人 が人 に借りている金額を と表す。 この貸し借りの状態を、次のような規則で操作することができる。 操…

Codeforces Global Round 6 E. Spaceship Solitaire

Problem - E - Codeforces 問題概要 ゲームにおいて 種類の資源があり、 について資源 を 個以上所持するとクリアとなる。 プレイヤーは1ターンごとに1個好きな資源を得ることができる。さらに、以下のような形式で表されるボーナスイベントがいくつか存在す…

Codeforces Global Round 6 F. Almost Same Distance

Problem - F - Codeforces 問題概要 頂点の木が与えられる。いくつかの頂点からなる集合 が正整数 に対して以下の条件を満たすとき、 は almost -uniformであると呼ぶことにする。 に含まれる異なる2頂点のペア全てにおいて、その距離は または である。 そ…

CODE FESTIVAL 2016 Grand Final A - 1D Matching

お題箱より。 A - 1D Matching 解法 まずはケーブルの長さの合計が最小になる条件を考えましょう。 座標点を数直線上に並べて、小さい方(左)から見ていくことを考えましょう。このとき各点について「保留して、それより右側の座標点と繋ぐことにする」か「…

Codeforces Round #604 (Div. 1) C. Beautiful Mirrors with queries

お題箱より。 Problem - C - Codeforces 私のコンテスト中の思考をベースに書きます。ちょっとややこしいかも。 問題概要 個の門があり、これを門 から門 まで順番に突破していく。スタート地点は門 の直前であり、門 を突破すればクリアである。 門 の突破…

HACK TO THE FUTURE 2020 本戦 参加記録

オンサイト本戦に参加し、その1で8位、その2で10位のダブル入賞でした! ネタになるエピソードとか写真とかは特にないので、マジメにコンテストについて書こうと思います。 本戦1 A - 千の木 問題を理解し、正の得点を得る提出をするまで49分。ここまでのハ…

C++のイテレータを視覚的に理解する(競プロ向け)

この記事はCompetitive Programming (2) Advent Calendar 2019 - Adventarの4日目の記事です。 私がC++で競技プログラミングをやり始めた際によく分からなかったものの筆頭がイテレータでした。便利でv.begin(), v.end()のようなお決まりの書き方はできても…

AtCoder Regular Contest 067 E - Grouping

お題箱より。 E - Grouping 解法 グループを作れる条件がなかなか扱いづらいことや制約の小ささからDPの線を考えます。 上手くDPを組むコツは「覚えておくべき情報を減らす」、逆に言うと「状態を忘れられるようにする」ことです。例えばこの問題において、…

Codeforces Round #603 (Div. 2) F. Economic Difficulties

非想定解っぽいですがまとめておきます。 Problem - F - Codeforces 問題概要 問題文中の図のように、一列に並んだ 個のノードを挟むように根付き木が2つ与えられる。それぞれの頂点数は であり、葉の数はいずれも で、それぞれの木について各ノードごとに1…

AtCoder Beginner Contest 145 F - Laminate

お題箱より。 F - Laminate 解法 問題で最小化すべき値である「塗る操作の回数」を「コスト」と呼ぶことにします。また各 の値を「高さ」と呼ぶことにします。 説明をやりやすくするため、0列目に である列が存在すると考えます。 の値が確定した後、コスト…

DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選 E - Majority of Balls

E - Majority of Balls 解法 キーとなるのは以下の2つの気付きです。 に対する質問の答えと に対する質問の答えは必ず異なる。片方が Red であればもう片方は Blue である。 もし「赤青が半々ずつ」ということが分かっている 個のボールの集合が得られたとす…

AtCoder Beginner Contest 146 F - Sugoroku

F - Sugoroku 解法 個の連続するゲームオーバーマスがある場合はゴール不可能なので、そうでないことを仮定します。「最小ターン数」と「辞書順最小」、それぞれに注目します。 ゴールするための最小ターン数はDP等で求めることができます(後で具体的に説明…

Educational Codeforces Round 69 D. Yet Another Subarray Problem

お題箱より。 Problem - D - Codeforces 問題概要 ※解説の都合上、0-indexedと半開区間での記述に書き換えます。 非負とは限らない整数列 と、正整数 が与えられる。 この数列の連続部分列 について、そのスコアを と定める。ただし長さ0の連続部分列のスコ…

AtCoder Beginner Contest 141 F - Xor Sum 3

お題箱より。 F - Xor Sum 3 線形代数を用いた解法の正当性について理解したい…というリクエストだったので、そこを重点的に書きます。 前段の考察 を表すビット桁を 桁目と表記することにします。一番下が0桁目です。 各ビット桁ごとに、 のうち 桁目が立っ…

HACK TO THE FUTURE 2020予選 参加記録

HACK TO THE FUTURE 2020予選 - AtCoder なんと全体10位で本戦に進むことができました! やったことを軽く書いておこうかと思います。けっこう雑な焼きなまし法なので、あまり参考になるかは分かりませんが… ビジュアライザのスクリーンショット等はexample_…

AtCoder Grand Contest 040 B - Two Contests

B - Two Contests 本番では考察不足で2ペナを出しましたが…自分の考察がある程度整理できたので書きます。 解法 公式解説にならい、それぞれのコンテストを「集合」、問題 を解ける人の範囲を「区間 」、コンテストの楽しさを「含まれる区間の共通部分の長さ…

JOI春合宿2015 K - 遺産相続

お題箱より。JOIの解説記事は初めてかな…? K - 遺産相続 解説途中の証明についてのリクエストだったのでそこを重点的に書きます。 解法 最大全域木として考える 都市を「頂点」、鉄道を「辺」、鉄道の収益を「辺重み」と考えます。 「閉路ができない範囲で…

Educational Codeforces Round 75 E2. Voting (Hard Version)

お題箱より。 Problem - E2 - Codeforces 問題概要 選挙の投票者が 人いて、全員が自分を支持するようにしたい。投票者 が自分を支持する条件は2つあり、どちらかを満たすと支持する。 金額 を払って買収する。 他の投票者のうち 人以上が自分を支持している…

CPSCO2019 Session1 F - Fruits in Season

お題箱より。 F - Fruits in Season 解法 最小値の最大化問題です。このタイプの問題はまず二分探索を考えてみる価値があります。 判定問題として、ある に対して「果物の美味しさの最小値を 以上にできるか?」という問題を考えます。最小値の最大化問題に…

Codeforces Round #358 (Div. 2) D. Alyona and Strings

お題箱より。 Problem - D - Codeforces 問題概要 文字列 が与えられ、それぞれの長さは である。また整数 が与えられる。 以下の条件を満たすような 個の文字列の組 の、長さの総和の最大値を求めよ。 のどの文字列も空でない。 のどちらにも、 がこの順番…

AtCoder Beginner Contest 144 E - Gluttony

E - Gluttony 解法 この問題はいくつか考察ステップが必要なので、順に見ていきましょう。 記法などについて 簡単のため、入力として与えられる値の集合 を単に 、 を単に と書くことにします。 また、最小化すべき値である「メンバーと食べ物の組み方を決め…

Codeforces Round #595 (Div. 3) D2. Too Many Segments (hard version)

お題箱より。 Problem - D2 - Codeforces 問題概要 整数を端点とする 個の閉区間 が与えられる。これらから0個以上の区間を捨てて、全ての整数点について「その整数点を含んでいる区間は 個以下である」という状態にしたい。 捨てる区間の最小個数と、その選…

Kyoto University Programming Contest 2019 E - 根付き森二人用ゲーム

お題箱より。 E - 根付き森二人用ゲーム 解法 それぞれの木を小規模なゲームとして解く スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手…

Codeforces Round #594 (Div. 1) B. The World Is Just a Programming Task (Hard Version)

Problem - B - Codeforces 問題概要 長さ の括弧列 が与えられる。長さ の括弧列のスコアを、「 を 回だけ右巡回シフトした文字列が正しい括弧列になっている」という条件を満たす の個数とする。 に対して1度だけ、2箇所を選んでスワップする操作を行うこと…

AtCoder Beginner Contest 143 F - Distinct Numbers

F - Distinct Numbers 解法 色々な解法があるみたいですが…この記事ではそれぞれの について独立に解きます。ある について解くときには、可能な操作回数には単調性があるので二分探索できます。 ある と操作回数 を固定したときに、操作を 回行えるかどうか…

AtCoder Regular Contest 077 E - guruguru

お題箱より。 E - guruguru 後半は公式解説と少し違う方法になっています。 解法 お気に入りで節約できる回数を定式化する ある1つの に対する から への移動を考えます。まず簡単のため、 と仮定しておきます。移動元と移動先をそれぞれ と書くことにします…

Codeforces Global Round 5 E. Balanced Binary Search Trees

Problem - E - Codeforces 問題概要 以下の条件を満たす根付き木を二分探索木と呼ぶ。 任意の頂点 について以下が成り立つ。 「左側の子」と「右側の子」がそれぞれ高々1個存在する。 左側の子孫が存在する場合、それら全ての頂点番号は より小さい。 右側の…

Codeforces Round #590 (Div. 3) E. Special Permutations

お題箱より。 Problem - E - Codeforces Editorialのソースコードがよく分からないというリクエストだったんですが、見たところ確かによく分からなかったので、私の解法を書きます。 問題概要 長さ の順列 を と定義する。 長さ の整数列 ()が与えられる。…

Educational Codeforces Round 74 E. Keyboard Purchase

お題箱より。ただ、この問題は元々書こうと思っていました。 Problem - E - Codeforces 問題概要 文字のアルファベットからなる長さ の文字列 が与えられる。アルファベット 個を並べる順列 を1つ決めた時、「 の隣り合う2文字のペアそれぞれについて、その…