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

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

そのまま覚えたいシンプル設定の中堅以上の典型問題

EDPC (Educational DP Contest) V - Subtree

全方位木 DP の練習問題!! が素数とは限らないので「左右から累積和」が必要なタイプの全方位木 DP。 問題へのリンク 問題概要 正の整数 と、頂点数 の木 が与えられる。この木の各頂点を「黒色」または「白色」に塗る。 各頂点 について、以下の条件をみ…

AtCoder ABC 076 A - Rating Goal (灰色, 100 点)

平均算! 問題へのリンク 問題概要 整数 が与えられる。 と の平均が になるような整数 を求めよ。 解法 平均の定義から、 となる。これを について解くと、 となる。このような式変形は中2「式の計算」で学ぶ。 #include <bits/stdc++.h> using namespace std; int main() </bits/stdc++.h>…

AtCoder ABC 058 A - ι⊥l (灰色, 100 点)

が等差数列かどうかを判定する問題 問題へのリンク 問題概要 3 つの整数 が等差数列かを判定せよ。 すなわち、 であるかどうかを判定せよ。 解法 問題文の通りに、b - a == c - b かどうかを判定すれば OK。 #include <bits/stdc++.h> using namespace std; int main() { in</bits/stdc++.h>…

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

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

AtCoder ABC 329 C - Count xxx (灰色, 300 点)

ランレングス圧縮の典型題! なお、ランレングス圧縮は鹿本でみっちり解説している。 問題へのリンク 問題概要 英小文字のみからなる長さ の文字列 が与えられる。 の連続する部分文字列のうち、1 種類の文字のみからなる文字列の種類数を答えよ。 制約 考え…

AtCoder Library Practice Contest L - Lazy Segment Tree

タイトル "Lazy Segment Tree" の名の通り、遅延評価セグメント木の練習問題! 問題へのリンク 問題概要 長さ の 0 と 1 のみからなる数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値につい…

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

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

AOJ 4003 演算装置の接続 (PCK 2022 本選 4)

次数制約つきのグラフを構築するためには、次数の大きいところから Greedy というよく知られた問題! 問題へのリンク 問題概要 正の整数からなる長さ の数列 が与えられる。 以下の条件を満たすような、頂点数 のグラフが存在するかどうかを判定せよ。 単純…

KUPC 2016 E - 柵

最小カットの練習問題。問題設定がとても面白い! 問題へのリンク 問題概要 のグリッドがある。いくつかのマスにはヤギがいる。具体的な入力では、ヤギのいるマスは文字 'X' で表される。 6 6 ...... ...... ..X... .X..X. ..X... ...... グリッドの外周は外…

TDPC (Typical DP Contest) R - グラフ

「与えられたグラフを強連結成分分解すると DAG になるので、DAG 上で DP する」というのが想定解だが、フローでも解けると話題になった問題! 問題へのリンク 問題概要 頂点数 の有向グラフがある。最初、すべての頂点は白色である。以下の操作を 2 回行う…

AOJ Course GRL_6_A 最大流

最大流アルゴリズムを実装したときの verify に 問題へのリンク 問題概要 頂点数 、辺数 のフローネットワークが与えられる。 番目の辺は頂点 から頂点 へ張られていて、容量は である。 頂点 を始点、頂点 を終点とした最大流値を求めよ。 制約 考えたこと …

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

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

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

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

TTPC 2023 H - 404 Chotto Found

Suffix Array 上をひたすら頑張って探索する感じ 問題へのリンク 問題概要 個の文字列 が与えられる (これらの文字列はすべて英小文字のみからなる)。 以下の条件を満たす文字列 の個数を求めよ。 英小文字のみからなる のうち、ちょうど 1 個の部分文字列で…

AtCoder ABC 048 A - AtCoder *** Contest (灰色, 100 点)

文字列の標準入力と、先頭の文字がわかっていれば解ける系 問題へのリンク 問題概要 "AtCoder s Contest" という形の文字列 が与えられる (s の部分は任意)。 たとえば、"AtCoder Beginner Contest" のような文字列が与えられる。これを "ABC" のように略し…

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

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

New Year Contest 2015 E - ひも

プリューファーコードが使える問題! 今でこそ高度典型となったが、当時は知られていなかった気がする。 問題へのリンク 問題概要 頂点数が であるような完全グラフの全域木であって、以下の条件を満たすものの個数を 1000000007 で割ったあまりを求めよ。 …

AOJ 2373 HullMarathon (JAG 冬合宿 2010 day3-E) (700 点)

面白い最適化問題! 問題へのリンク 問題概要 二次元平面上で、原点からの距離が であるような 点の凸包の面積として考えられる最大値を求めよ。 制約 考えたこと 凸包というところが面倒だが、要は 本のうちの何本かを選んで それを適切な順序に並び替えた…

CodeQUEEN 2023 決勝 E - Good Partition

これは学びの深い DP 問題! 問題へのリンク 問題概要 長さ の数列 がある (負値もありうる)。これらの数列をいくつかの連続する区間に分割する。 区間分割の仕方を最適化したときの、各区間における「最大値と最小値の差」の総和として、考えられる最大値を…

yukicoder No.2417 Div Count

整数の入門にいい感じの問題! 問題へのリンク 問題概要 正の整数 と非負整数 が与えられる。次の条件を満たす正の整数 の個数を求めよ。 を で割った余りが である 制約 解法 を で割ったときの商を とおくと、 と表せる。これを式変形すると となる。この…

AtCoder ABC 210 F - Coprime Solitaire (橙色, 600 点)

2-SAT の「密」を解消する累積 OR テクを学んだ! 問題へのリンク 問題概要 枚のカードがあり、表には 、裏には が書かれている。各カードについて、表を上にするか、裏を上にするかを選択していく。 上手く選択することで、上を向いている数値がどの 2 つも…

ウクーニャたんお誕生日コンテスト D - ukuku

ネタコンテストなのかと思いきや、問題面白くて、この D 問題は勉強になった。答え決め打ちの二分探索! 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 この文字列について 回のクエリに答えたい。 各クエリでは整数値 が与えられ…

AtCoder ABC 207 D - Congruence Points (黄色, 400 点)

すごくシンプルだけど詰まる部分もたくさんありそうな問題 問題へのリンク 問題概要 二次元平面上に、2 組の 個の点集合 、 がある。 に含まれる 個の点に対して、一律に 原点を中心とした回転をする (角度は任意) 平行移動をする (移動量は任意) を実施する…

AtCoder ABC 311 G - One More Grid Task (黄色, 575 点)

黒マスを避けながら、長方形領域の値の総和を最大化する問題として解いた! 問題へのリンク 問題概要 のグリッドがあって、各マス には正の整数 が書かれている。 グリッドに含まれる長方形領域のうち、「長方形領域に含まれる値の総和」と「長方形領域に含…

AtCoder ABC 267 G - Increasing K Time (橙色, 600 点)

順列を数え上げる系の問題、うまく「個数」を持った天才的な DP をするイメージ 問題へのリンク 問題概要 整数列 が与えられる。 この数列の 通りの順列のうち、 であるような がちょうど 個であるようなものの個数を 998244353 で割ったあまりを求めよ。 制…

AtCoder ABC 259 G - Grid Card Game (橙色, 600 点)

opt さんの「そのままだと優モジュラ最適化なので、青木君の選ぶ・選ばないをひっくり返せば劣モジュラ最適化。よって最小カットでできる」が賢かった。 競プロで言うところの「燃やす埋める」 問題へのリンク 問題概要 のグリッドがあって、各マス には整数…

TDPC (Typical DP Contest) T - フィボナッチ

Boston--Mori 法を履修した! 問題へのリンク 問題概要 () によって定義される数列において、 を 1000000007 で割ったあまりを求めよ。 制約 解法 0-indexed にして考えることにする。つまり、 () によって定義される数列において、 を求めることにする。 こ…

AOJ 2828 マトリョーシカ (JAG 模擬国内 2017 F) (550 点)

DAG の最小パス被覆、忘れた頃に出て来るイメージ! 問題へのリンク editorials 問題概要 個の直方体があり、 番目の直方体の大きさは である。 今、ある直方体の中に他のある直方体を入れたりすることで、外部から見えている直方体の体積を小さくしたい。た…

AOJ 2293 Dangerous Tower (JAG 夏合宿 2011 day2-D) (600 点)

めっちゃ面白い問題! 問題へのリンク editorials 問題概要 個の直方体がある。 番目の直方体は の形をしている。 今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが になるようにする。 縦または横方向については、 …

yukicoder No.2066 Simple Math !

floor sum のいい感じの練習問題! 問題へのリンク 問題概要 正整数 が与えられる。 非負整数 を用いて という形で表せる正の整数のうち、 番目に小さいものを求めよ。 ( 個の入力ケースが与えられる) 制約 考えたこと いかにも二分探索という問題。次の判定…