E - Increasing Numbers 公式解説と少し違う方法で解いたので記録しておきます。 解法 十進法の桁を、一番下の桁を 桁目とするように表記します。 桁目は に対応する桁です。 「各桁から を引く回数」の条件への言い換え 非負整数が増加的であることは、「1…

F - Monochromization 解説放送を観て解いたので、その方針をベースに書きます。 解法 まずは判定問題 まず、ある盤面が初期盤面から操作を繰り返した後の最終状態として作れるかどうかの判定方法を考えます。 ある最終状態の盤面から操作を逆回しして考えま…

お題箱より。 Problem - F - Codeforces 問題概要 カッコ列 が与えられる。「正しい」カッコ列であって、 の両方を部分列として含むようなカッコ列のうち、長さが最小のものを1つ求めよ。 制約 解法 文字列のインデックスは0-indexedで表記します。 まずは正…

お題箱より。 Problem - E - Codeforces 少し前にバチャで扱われて話題になっていましたね。公式解説のDPの正当性が分からないというリクエストだったのですが、私もわからないので（ごめんなさい…）もう少し汎用的に使える解法を書きます。 問題概要 個の要…

E - Span Covering 本番中実装しきれなかったけど、公式解説と違う方法で解いたので記録。 解法 包除原理の適用 土地を 個のマスが並んだものとして扱います。このマスのうち0個以上のマスを選んだ集合 について、 に含まれるマスだけに全てのシートを置く（…

C - Cookie Distribution 解法 式変形と言い換え 全てのクッキーの配り方の集合を 、答えを とします。答えは の期待値に全ての配り方の通り数を掛けたものなので、 を全ての配り方について合計したもの、つまり以下のように表現できます。 実際には各 は配…

D - Arrangement 公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず… 解法 まずは貪欲に作ってみる 「カード の右隣のカードがカード であってはならない」という条件は、そんなに厳しい条件ではないように思います。なので…

Problem - D - Codeforces 異常実装になったけどなんとか自力で解けた… 問題概要 数直線上に 個の粒子がある。粒子 は初期位置 、速さ 、右に動く確率 で特徴づけられる。 この粒子を用いて以下の実験を行う。 まず各粒子の移動方向を確率に従って決める。粒…

Problem - E - Codeforces 問題概要 座標平面上に 個の点があり、 番目の点の座標は である。これら 個の点からなる集合を と表記する。全ての点は相異なり、どの3点をとってもそれらが一直線上に存在することはない。 点 のスコア を、「 に含まれる4点の選…

Problem - D - Codeforces 問題概要 講演会において 個の講演がある。A会場とB会場の2つがあり、講演 をA会場で行う場合の講演時間は時刻の閉区間 で、B会場で行う場合の講演時間は時刻の閉区間 で表される。 2つ以上の講演の集合 のうち、以下のようなもの…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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