けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

青色diff

AtCoder ABC 330 F - Minimize Bounding Square (青色, 525 点)

すごく典型盛り合わせな教育的問題! 問題へのリンク 問題概要 二次元平面上に 個の点が配置されている (同じ座標に複数個の点が配置されることもある)。これらの点に対して、以下の操作を 回まで行える。 個の点の中から 1 個選ぶ その点を上下左右のいずれ…

AtCoder ABC 327 F - Apples (青色, 550 点)

遅延セグ木 (区間加算 + 区間 max 取得) を用いた平面走査! 問題へのリンク 問題概要 二次元平面上に 個の点がある。点 の座標は である。 この 2 次元平面上でサイズが の長方形領域 (右辺と上辺は含まない) を自由に動かしていくとき、この長方形領域に覆…

AtCoder ABC 315 F - Shortcuts (青色, 500 点)

実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…

AtCoder ABC 325 F - Sensor Optimization Dilemma (青色, 500 点)

個の区間を、プチ区間たちを用いて、最小コストですべて被覆しようという問題。DP 状態の持ち方を工夫することで計算量を小さくしたい。 問題へのリンク 問題概要 個の区間があって、長さが である。これらすべてを 2 種類の区間で被覆したい。 長さが であ…

AtCoder ARC 026 C - 蛍光灯 (試験管青色)

セグ木上で DP する問題として、人生で最初に解くべき問題と言えるかもしれない! 問題へのリンク 問題概要 個の区間がある。各区間 は、 で重みは である。 これらの区間からいくつか選ぶ方法のうち、 全体を被覆するものについて、最小重みを求めよ。 制約…

AtCoder ABC 324 F - Beautiful Path (青色, 500 点)

とても教育的問題!! 蟻本の二分探索の節に「平均値の最大化」があるけど、まさにそれ!!! 問題へのリンク 問題概要 頂点数 、辺数 の DAG が与えられる。各辺 について、 であることが保証される。 各辺 には、美しさ と、コスト がついている。 頂点 0 …

AtCoder ABC 322 F - Vacation Query (青色, 550 点)

遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 0 と 1 のみからなる長さ の文字列 が与えられる。次の 2 種類のクエリに答えよ。 クエリ (1 L R):文字列 の区間 内における、1 が連続する区間の長さの最大値を答えよ クエリ (2 L R):文字列 …

AtCoder ABC 321 F - #(subset sum = K) with Add and Erase (青色, 525 点)

「戻す DP」または「FPS」で! 問題へのリンク 問題概要 最初、箱は空である。以下の操作を 回行う。各操作後において、以下の値を答えよ。 箱に入っているボールをいくつか選ぶ方法であって、ボールに書かれた数値の総和が となる方法の個数を 998244353 で…

AtCoder ABC 321 E - Complete Binary Tree (青色, 450 点)

この問題をキッカケに準完全二分木のライブラリを拡充した! 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。頂点番号は である。各頂点 (> 2) について、親頂点は である。 この根付き木において、頂点 からの距離が であるような頂点の個数を求…

AtCoder ABC 210 E - Ring MST (青色, 500 点)

また 1 つ、MST 系の問題のストックが増えた。でも実質的には整数問題だった。 問題へのリンク 問題概要 頂点数 、辺数 のグラフがある。このグラフに以下の操作 を実施することで重み付き無向グラフを作る。 に対して、頂点 と頂点 % の間に、重み の辺を張…

AtCoder ABC 313 E - Duplicate (青色, 600 点)

こういうの詰めるの時間かかる。サンプルも弱いので、愚直シミュレーション解も実装して、それとの一致を確かめたりなどした! 問題へのリンク 問題概要 '1'〜'9' のみからなる文字列 が与えられる。この文字列に対して文字列を返す関数 がある。 は次の操作…

AtCoder ABC 313 D - Odd or Even (青色, 550 点)

みたいな連立方程式を解いた経験があれば、思いつきやすいかもしれない。 問題へのリンク 問題概要 (インタラクティブ) 0 と 1 のみからなるサイズ の数列 があるが、未知である。いくつか質問を繰り返すことで、この数列を特定したい。 最大で 回まで質問す…

AtCoder AGC 063 B - Insert 1, 2, 3, ... (青色, 600 点)

セグ木とか必要なくて、本当に単純な実装で解けるの面白い 問題へのリンク 問題 制約 考えたこと まずは、生成可能であるための分かりやすい特徴付けを考えようと思った。数列の生成手順が、いかにも入れ子構造をしているので、カッコ列を連想した。 カッコ…

AtCoder ABC 311 F - Yet Another Grid Task (青色, 525 点)

最初、各マスをタスクに見立てて、タスクの依存関係を考える DAG 上で DP できないかなどと考えたけど、うまくいかなかった。普通にグリッドを左から舐めていく DP でよかった! 問題へのリンク 問題概要 のグリッドがある。各マスはすでに白色 (文字 '.') …

AtCoder ABC 025 C - 双子と○×ゲーム (試験管青色)

ゲーム探索 + bit DP。やや実装重たい。 問題へのリンク 問題概要 先手と後手が交互に のグリッドの各マス目に o や x を書いていく。先手は o を書き、後手は x を書く。 書き終わったとき、次のように得点を計算する および に対して、 マス とマス が同じ…

AtCoder ABC 304 F - Shift Table (青色, 525 点)

メビウス関数を用いた約数系包除原理を使いこなそう! 問題へのリンク 問題概要 (表現改) 文字 '.' と '#' のみからなる長さ の文字列 が与えられる。今、文字 '#' をいくつか '.' に書き換えることによって、文字列 が周期的文字列となるようにしたい。 な…

AtCoder ABC 301 E - Pac-Takahashi (青色, 475 点)

前処理して頂点数を減らしたグラフ上で TSP!!! ICPC ではすごくよく見るパターンですね! 問題へのリンク 問題概要 サイズのグリッドがある。各マスは 壁マス:'#' 通路マス:'.' お菓子マス:'o' (18 個以内であることが保証される) スタートマス:'S' …

AtCoder ABC 009 C - 辞書式順序ふたたび (試験管青色)

旧 ABC の C 問題の中でも、個人的に最難だと思う問題! 現代の ABC で出題されても水色 diff になると思う。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の各文字を並べ替えてできる文字列 のうち、 となる が 個以下であ…

AtCoder ABC 259 F - Select Edges (青色, 500 点)

木 DP のいい感じの練習問題だった! 問題へのリンク 問題概要 頂点数 の重み付き木が与えられる (重みは負のこともある)。 この木の辺の部分集合であって、各頂点 に接続する辺の本数が 本以下であるようなものに対して、辺の重みの総和の最大値を求めよ。 …

AtCoder ABC 300 F - More Holidays (青色, 500 点)

二分探索すれば楽できることをすぐに思いつけてよかった。 問題へのリンク 問題概要 o と x のみからなる長さ の文字列 が与えられる。 文字列 を 回繰り返して得られる文字列 を考える。この文字列 に対して、最大 回まで、x を o に書き換える操作を行うこ…

AtCoder ABC 282 F - Union of Two Sets (青色, 600 点)

コンテスト中、Sparse Table だと思わずに解いていた。コンテスト後に TL で Sparse Table だと見て、「確かに!」と思った。 問題へのリンク 問題概要 インタラクティブ問題である。次のフェーズ I とフェーズ II に分かれる。 フェーズ I ジャッジから整数…

AtCoder ABC 282 E - Choose Two and Eat One (青色, 500 点)

これをグラフの問題だと思えるかどうか! 問題へのリンク 問題概要 箱の中に 個のボールが入っており、各ボールには 以上 以下の整数が書かれている。 番目のボールに書かれた整数は ​ である。 箱の中に 2 個以上のボールが残っている限り、下記の行動を繰…

DISCO presents 2016 予選 B - ディスコ社内ツアー (青色)

シミュレーションの仕方を工夫する問題。数値ごとに index をまとめあげるデータを持つとうまくいく。 問題へのリンク 問題概要 長さ の正の整数列 が与えられる。 の順列 であって、 を満たすものを考える。そのような順列の (ただし である場合の の場合は…

AtCoder ABC 281 F - Xor Minimization (青色, 500 点)

数列に対して、2 進法で表して、再帰的に上位桁から 0 と 1 で分類した木を作る!!! こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…

AtCoder ABC 280 F - Pay or Receive (青色, 500 点)

重み付き Union-Find が使える鮮やかな楽しい問題! 問題へのリンク 問題概要 頂点数 (頂点番号が ) のグラフが与えられる。このグラフには 組の辺があり、 組目の辺は、 頂点 から頂点 へと、長さ の有向辺 頂点 から頂点 へと、長さ の有向辺 となっている…

AtCoder AGC 059 A - My Last ABC Problem (青色, 500 点)

ひたすらに迷走してしまった。今回の記事は解説というより、個人的備忘録として書く。 問題へのリンク 問題概要 一般に、'A' と 'B' と 'C' の 3 種類の文字からなる文字列 のスコアを次のように定める 文字列 に対して、以下の操作を繰り返し実施していく。…

AtCoder ABC 010 D - 浮気予防 (試験管青色)

最小カットのよい練習問題ですね。 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフが与えられます。頂点番号を とします。また、頂点 0 以外の 個の頂点 が与えられます。 今、次の操作を行っていくことで、頂点 0 からは頂点 のいずれにも到達で…

AtCoder ABC 049 D - 連結 (ARC 065 D) (青色, 400 点)

Union-Find を上手に使うと解けるいい練習問題ですね。 問題へのリンク 問題概要 個の都市があって、都市間を 本の「道路」と 本の「鉄道」が結んでいる。各道路と各鉄道は、結んでいる都市間を双方向に移動することができる。 各都市 に対して、以下の条件…

AtCoder ABC 023 C - 収集王 (試験管青色)

これが ABC の C 問題だったとは...!!! 典型90問の問 4 が結構近いと思った。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッド (メモリにおさまらない規模) が与えられる。そのうちの 個のマスには飴が置いてある。 次の条件を満たすマスの…

AtCoder ARC 037 C - 億マス計算 (試験管青色)

二分探索法の教育的典型問題ですね!! 問題へのリンク 問題概要 正の整数からなる長さ の数列が 2 つ ( と ) 与えられます。 各 に対して を計算することで得られる 個の整数を考えます。 これらの整数を小さい順に並べたとき、 番目 (1-indexed) に来る値…