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

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

ABC-E

AtCoder ABC 330 E - Mex and Update (緑色, 475 点)

データ構造をいい感じに設計する地力が問われる! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対する以下の 個のクエリに答えよ。 各クエリでは整数 が与えられる を に置き換える 置き換えたあとの数列 の mex を出力せよ 制約 考えたこ…

AtCoder ABC 328 E - Modulo MST (?色, 475 点)

next_combination を使った! 普通に STL の next_permutation() でもできる。 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き無向グラフが与えられる。 このグラフの全域木をすべて考えたときの、全域木に含まれる辺の重みの総和を で割ったあま…

AtCoder ABC 327 E - Maximize Ratin (水色, 475 点)

式がいかめしくて戸惑うけど、DP 自体は比較的単純 問題へのリンク 問題概要 個の値 が与えられる。 これらの中から順序を保っていくつか選ぶ。選び方のスコアは、 個の整数 を選んだとしたとき、 で与えられる。このスコアの最大値を求めよ。 制約 考えたこ…

AtCoder ABC 325 E - Our clients, please wait a moment (緑色, 450 点)

少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題! 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…

AtCoder ABC 324 E - Joint Two Strings (緑色, 500 点)

問題を典型パーツに分解して考察を積み上げていく系の、とても教育的な問題! 問題へのリンク 問題概要 個の文字列 と文字列 が与えられる。以下の条件を満たす の組の個数を求めよ。 と をこの順に連結してできる文字列から、いくつかの文字を選び、順序を…

AtCoder ABC 323 E - Playlist (水色, 450 点)

よくある区間分割の DP だけど、それでよいことに思い至るのが難しいかもしれない。 問題へのリンク 問題概要 曲あって、それぞれの曲の長さは である。 今、時刻 0 から開始して「曲を一様ランダムに流し、それが終わったらまた一様ランダムに曲を選択して…

AtCoder ABC 322 E - Product Development (緑色, 475 点)

chokudai さんの思想が詰まった問題 問題へのリンク 問題概要 個の開発案がある。これらの開発案によって上昇し得るパラメータが 種類ある。 開発案 () を採用すると、パラメータ () の値が だけ上昇する。その分、 のコストがかかる。 すべてのパラメータを…

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

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

AtCoder ABC 318 E - Sandwiches (緑色, 450 点)

色んな解法がありそう。今回は、あまり解説書かずに備忘録程度に。 問題へのリンク 問題概要 長さ の数列 がある。各要素は 以上 以下の整数値である。 制約 メモ 各値ごとに考えていった。つまり、 として、 について求めていった。 各 について、 となる添…

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

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

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

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

AtCoder ABC 256 E - Takahashi's Anguish (水色, 500 点)

最近話題の Functional Graph の問題! 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…

AtCoder ABC 311 E - Defect-free Squares (水色, 475 点)

有名な DP をするか、二次元累積和 + 二分探索をするか 問題へのリンク 問題概要 のグリッドが与えられる。グリッドの各マスのうち、指定された 個のマスには穴があいている。その他のマスは穴があいていない。 グリッドに含まれる正方形であって、その内部…

AtCoder ABC 235 E - MST + 1 (水色, 500 点)

MST の理解が問われる面白い教育的問題! 問題へのリンク 問題概要 頂点数 、辺数 の連結な重み付き単純無向グラフ が与えられる。なお、各辺の重みはすべて互いに異なることが保証されている。 の最小全域木を とする (一意に定まることが示せる)。 このグ…

AtCoder ABC 304 E - Good Graph (緑色, 475 点)

Union-Find 慣れしていれば解きやすい! 問題へのリンク 問題概要 頂点数 、辺数 の無向単純グラフ が与えられる。 組の頂点対 について、どの頂点対間のもパスがないグラフを良いグラフと呼ぶことにする。 与えられるグラフ は良いグラフである。 このグラ…

AtCoder ABC 302 E - Isolation (緑色, 425 点)

「要素の削除」をする必要がある場合は set が使えたりする 問題へのリンク 問題概要 最初、頂点数 、辺数 のグラフがある。 このグラフに対して次の 個のクエリに答えて、毎クエリ後にその時点での「グラフの孤立点の個数」を出力せよ。 クエリタイプ 1 (1 …

AtCoder ABC 303 E - A Gift From the Stars (緑色, 475 点)

DFS などの探索をしても解けるし、単に次数を見るだけでも解ける。 問題へのリンク 問題概要 個の葉をもつスターグラフを、レベル のスターと呼ぶことにする。 高橋君は、はじめ何個かのスターからなるグラフを持っている。これらのスターの頂点数の総和は …

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

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

AtCoder ABC 300 E - Dice Product 3 (水色, 500 点)

確率や期待値を計算する DP をするときは、自己ループを除去することが多いね。 問題へのリンク 「EDPC J - ボール」などは類題と言える。先にこの問題を解いておくと、今回の問題も解きやすいかもしれない! qiita.com 問題概要 以上 以下の整数が等確率で…

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

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

AtCoder ABC 281 E - Least Elements (水色, 500 点)

よくあるデータ構造問題!! めっちゃ色んな解法がある! 問題へのリンク 問題概要 長さ の整数列 と整数 が与えられる (0-indexed で表している)。 各 に対して、次の問題に答えてください。 個の整数 を小さい順に並び替えたときの先頭 個の総和を求めよ。…

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

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

AtCoder ABC 280 E - Critical Hit (水色, 500 点)

EDPC A - Frog 1 とほとんど同じ DP で解けますね! 問題へのリンク 問題概要 体力が であるモンスターが 1 体います。高橋君はモンスターに対し、モンスターの体力が 1 以上残っている限り繰り返し攻撃を行います。 高橋君は 1 回の攻撃で、 の確率でモンス…

AtCoder ABC 250 E - Prefix Equality (水色, 500 点)

とても色んな解法が考えられる問題ですね。ハッシュで殴るのが最も簡単だとは思います。そのほかにもさまざまな解法が考えられます。 問題へのリンク 問題概要 2 つのサイズ の整数列 と が与えられます。 これらの数列に対して 回のクエリが与えられます。…

AtCoder ABC 246 E - Bishop 2 (水色, 500 点)

迷路の最短路問題なので BFS でやりたくなるが、まともにやると で TLE してしまう!! 頂点の持ち方を工夫して 0-1 BFS で解く! 別解として枝刈り BFS も。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられます。各マスは通路 (文…

AtCoder ABC 245 E - Wrapping Chocolate (水色, 500 点)

これ!!! ABC 091 C - 2D Plane 2N Point とほとんど同じ!! ただ制約が大きいので、貪欲法を高速化する必要がありますね。 問題へのリンク 問題概要 個のチョコレートと、 個の箱があります。 番目のチョコレートはサイズ であり、 番目の箱はサイズ で…

AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点)

かの有名な「器物損壊!高橋君」の類題ですね。 drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。 今、左上のマス から右下のマス へと移動したいです。上下左右に移動することが…

AtCoder ABC 206 E - Divide Both (青色, 500 点)

約数系包除原理の教育的問題 問題へのリンク 問題概要 整数 が与えられるので、以下の条件を満たす整数 の組の個数を求めてください。 としたとき、, , 制約 解法 (1):約数系包除 まさに約数系包除原理の教育的良問。この問題をきっかけとして、次の記事を…

AtCoder ABC 187 E - Through Path (水色, 500 点)

これの応用問題って感じだった!! drken1215.hatenablog.com 問題へのリンク 問題概要 頂点数 の木が与えられる。 番目の辺は頂点 と頂点 とを結んでいる。はじめ、各頂点には、値 0 が書き込まれている。以下の 個のクエリを処理したあとの、各頂点に書き…

AtCoder ABC 134 E - Sequence Decomposing (水色, 500 点)

実は双対性が深く絡んでるけど、割と素直な Greedy でも解ける 問題へのリンク 問題概要 要素からなる整数列 が与えられる。これらの要素をいくつかの色に塗り分けたい。ただし、同じ色で塗られた要素は狭義単調増加になるようにしなければならない。 このよ…