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

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

青色diff

AtCoder ABC 357 F - Two Sequence Queries (2D, 青色, 550 点)

maspy さんの次のツイートがすべて!! F(cnt,sum) という組と定数加算作用が遅延セグ木にのるというのはよく知られていると思いますが、これは要素に対する (0乗和, 1乗和) と解釈できて、組 (0,1,...,k 乗和) などに一般化できます。今回は要素 (x,y) に対…

AtCoder ABC 173 E - Multiplication 4 (1D, 青色, 500 点)

個から 個を選ぶ設定の問題! 問題へのリンク 問題概要 個の整数値 が与えられる (負値もありうる)。 これらの整数から 個選んで積をとった値の最大値を、1000000007 で割った余りを求めよ。 制約 考えたこと 本質的に、次の 2 パターンに分かれると考えた。…

AtCoder ABC 207 E - Mod i (2D, 青色, 500 点)

この手の累積和高速化が半端じゃなく苦手なことがわかった。 問題へのリンク 問題概要 長さ の数列 が与えられる。 この数列をいくつかの区間に分割する方法のうち、 番目の区間に含まれる数列の要素の総和が で割り切れるようなものの個数を 1000000007 で…

AtCoder ABC 354 F - Useless for LIS (2D, 青色, 525 点)

LIS の応用問題。LIS を分かっていれば、その DP の過程を保存しておくことで、この問題が解けることがわかる! 問題へのリンク 問題概要 長さ の数列 が与えられる。 各 について、要素 を含むような数列 の LIS が存在するかどうかを判定せよ。 (マルチテ…

AtCoder ABC 353 G - Merchant Takahashi (2D, 青色, 550 点)

の計算量までなら比較的すぐできる! 問題へのリンク 問題概要 街 があって、街 間の行き来には だけの通行料がかかる。 回の市場がそれぞれ街 で行われ、 円えられる。 最初、無限の所持金を持っている。いくつかの市場に参加する (全く参加しなくてもよい)…

AtCoder ARC 174 C - Catastrophic Roulette (青色, 500 点)

コンテスト中には通しきれなかった。流石に疲れていて頭が働かなかった......これはメモ代わりに記す。 問題へのリンク 問題概要 整数値 が等確率で出てくるルーレットがある。 先手と後手が交互にルーレットを回す すべての整数値が揃ったら終了である すで…

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 で分類した木を作る!!! こどふぉではよく見るやつですね。 問題へのリンク 問題概要 個の非負整数 が与えられる。ある非負整数 を上手に選んだときの、 の値の最小値を求めよ。 制約 考えたこと…