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

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

2023-11-01から1ヶ月間の記事一覧

Yosupo Library Checker - Longest Common Substring (2D)

2 つの文字列の最長の共通部分文字列 (部分列ではなく) を求める問題! これ、蟻本の例題にもあるけど、POJ ではなく Yosupo Judge で解けるようになったのは大きい! なお、Suffix Automation があれば本当に貼るだけみたい。 問題へのリンク 問題概要 2 つ…

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

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

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

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

AtCoder ABC 330 D - Counting Ls (2Q, 茶色, 400 点)

次の問題にとても似ていた! drken1215.hatenablog.com 問題へのリンク 問題概要 のグリッドが与えられる。各マスには文字 'o' または 'x' が描かれている。これらのマスから 3 個選ぶ方法であって、 3 マスに書かれた文字はすべて 'o' である 3 マスのうち…

AtCoder ABC 330 C - Minimize Abs 2 (3Q, 茶色, 300 点)

文字を固定したり、数式処理したりなど、総合力が問われる問題! 問題へのリンク 問題概要 正の整数 が与えられる。非負整数 をすべて考えたときの、 の最小値を求めよ。 制約 まず、問題の理解 数学に慣れていないと、何がしたいのかわかりづらいと感じるか…

AtCoder ABC 330 B - Minimize Abs 1 (5Q, 灰色, 200 点)

問題の理解がちょっと大変。数学の素養がないと厳しいかもしれない。 問題へのリンク 問題概要 正の整数 ( を満たす) が与えられる。 また、 個の整数 が与えられるので、各 について、次の条件を満たす整数 を求めよ。 である 以上 以下の任意の整数 に対し…

AtCoder ABC 330 A - Counting Passes (8Q, 灰色, 100 点)

最近、易しめのいい感じの A 問題多いね! 問題へのリンク 問題概要 個の整数 のうち、 以上であるものの個数を求めよ。 解法 配列を使って入力を受け取って、for 文を使って配列の要素を 1 個 1 個見ていけばいい。 #include <bits/stdc++.h> using namespace std; int mai</bits/stdc++.h>…

AtCoder ABC 225 G - X (4D, 橙色, 600 点)

2 変数劣モジュラ関数の和の最小化! 俗にいう燃やす埋める 問題へのリンク 問題概要 のグリッドがあって、各マス には値 が記されている。 いくつかのマスに「x」を描いていく。「x」は書かれるマスの左上の角と右下の角を結ぶ線分、および右上の角と左下の…

競プロ典型 90 問 040 - Get More Money(3D, ★7)

Project Selection がピッタリハマる問題! 問題へのリンク 問題概要 個の家 がある。家 に入るためには のコストがかかるが、その代わり の利得が得られる。また、各家 に対して、次の 個の制約条件が付随している。 家 に入ることなくして、家 に入ること…

2 変数劣モジュラ関数のグラフ表現 〜 「燃やす埋める」の早見表 〜

競プロにおいて、「Project Selection」や「2 変数劣モジュラ関数の和の最小化」などと呼ばれるテクニックがあります。いずれも、最小カット問題に帰着して解くことができます。これらは次のような関係にあります。なお、俗に「燃やす埋める」と呼ばれている…

AtCoder ABC 329 D - Election Quick Report (4Q, 灰色, 350 点)

「差分更新」の良い練習問題! 問題へのリンク 問題概要 以上 以下の整数からなる長さ の数列 が与えられる。 各 に対して、 の中で最も多く登場する値を答えよ。複数個ある場合はそのうちの最小の値を答えよ。 制約 考えたこと この問題のように、各 に対し…

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

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

AtCoder ABC 329 B - Next (7Q, 灰色, 200 点)

昔の ABC B 問題って感じ! 問題へのリンク 問題概要 長さ の数列 が与えられる。すべての値が等しいわけではないことが保証される。 これらのうち、最大値でない中での最大値を求めよ。 解法 まず for 文を回すなどして、 個の値 の最大値を求める。たとえ…

AtCoder ABC 329 A - Spread (8Q, 灰色, 100 点)

与えられた文字列を空白区切りで出力する問題。なお、末尾に空白が入っていても AC になる! 問題へのリンク 問題概要 文字列 が与えられるので、各文字を空白区切りで出力せよ。 解法 次のコードのように、文字列 の各文字 について、 文字 を出力する 空白…

競プロ典型 90 問 038 - Large LCM(5Q, ★3)

最小公倍数を求める。その際にはオーバーフローに注意! 問題へのリンク 問題概要 正の整数 が与えられる。 の最小公倍数を求めよ。ただし、 を超える場合は "Large" と出力せよ。 制約 解法:最大公約数から最小公倍数を求める まず、整数 の最大公約数を …

AtCoder ARC 168 D - Maximize Update (橙色, 700 点)

コンテスト中は迷走しまくってしまった 問題へのリンク 問題概要 マスがあって、最初はすべて白色である。以下の 種類の操作を好きな順序で好きな回数行うことができる。 種類目の操作: マス からマス までを黒色で塗る マス目の状態を変化させるような操作…

AtCoder Library Practice Contest L - Lazy Segment Tree (2D)

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

AtCoder ABC 305 A - Water Station (7Q, 灰色, 100 点)

この処理は今後めっちゃ頻出なので、スラスラ書けるようになっておきたい! 問題へのリンク 問題概要 正の整数 が与えられる。 に最も近い 5 の倍数を求めよ。 解法 たとえば としてみよう。5 の倍数は 0, 5, 10, 15, 20, 25, 30, 35, 40, ... と続いていく…

AtCoder ABC 306 A - Echo (8Q, 灰色, 100 点)

これは最近の ABC A 問題では易しめ!! 問題へのリンク 問題概要 文字列 が与えられる。この文字列の各文字を 2 回ずつ繰り返した文字列を出力せよ。 たとえば、"beginner" は "bbeeggiinnnneerr" となる。 コード for 文を用いて、文字列 の各文字 を順に…

AtCoder ABC 307 A - Weekly Records (7Q, 灰色, 100 点)

for 文の練習。色んな書き方がありそう。 問題へのリンク 問題概要 高橋君は 週間歩いた距離を記録した。 日目には、それぞれ 歩歩いた。 各週について、高橋君が 1 週間で歩いた歩数の合計を出力してください。 解法 前提として、配列を 0 始まりで考えるこ…

AtCoder ABC 308 A - New Scheme (7Q, 灰色, 100 点)

「単調増加かどうか判定」は典型。そのような処理の実装に慣れよう! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列が以下の条件を全て満たすかどうかを判定せよ。 広義単調増加である すべて 100 以上 675 以下である すべて 25 の倍数であ…

Yosupo Library Checker - Range Affine Range Sum (2D)

これ実は ACL Practice Contest の K 問題と同じらしい atcoder.jp 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ():数…

AtCoder Library Practice Contest K - Range Affine Range Sum (2D)

遅延評価セグメント木の練習! 問題へのリンク 問題概要 長さ の数列 が与えられる。この数列に対して、次の 回のクエリに答えよ。 クエリタイプ 1 ():数列の区間 内の各要素の値を 倍して を足せ クエリタイプ 2 ():数列の区間 内の要素の総和を 99824435…

AtCoder Library Practice Contest J - Segment Tree (1D)

セグメント木の練習問題です。 クエリタイプ 1, 2 のみなら、ただの RMQ ですね。クエリタイプ 3 は、セグメント木上の二分探索を実行する関数 max_right() が使えます。 問題へのリンク 問題概要 長さ の数列 がある。この数列に対して、以下の 2 種類のク…

競プロ典型 90 問 077 - Planes on a 2D Plane(2D, ★7)

二部マッチングの練習問題 問題へのリンク editorial へのリンク 問題概要 二次元平面上に 体の飛行機がある。飛行機 は座標 にいる。各飛行機に対して適切に 8 種類の向き付けをしたい (上・下・左・右・左上・左下・右上・右下)。 具体的には、 秒後におい…

AtCoder ABC 328 A - Not Too Hard (8Q, 灰色, 100 点)

これは A 問題らしい A 問題 問題へのリンク 問題概要 個の整数 のうち、 以下のものの総和を求めよ。 コード for 文を回していき、 以下であるかを判定して、 以下であるものを足していけば OK。 #include <bits/stdc++.h> using namespace std; int main() { int N, X; ci</bits/stdc++.h>…

AtCoder ABC 328 B - 11/11 (6Q, 灰色, 200 点)

少し複雑めの全探索。 問題へのリンク 問題概要 1 年が ヶ月からなる暦がある。 月はそれぞれ 日ある。 この暦において、ゾロ目に日付は何日あるかを答えよ。 制約 考えたこと について順に調べていけば良い。 自体がゾロ目でないとダメ がゾロ目なら、その…

AtCoder ABC 328 C - Consecutive (4Q, 灰色, 300 点)

すごくよく似た過去問がある。これ → ABC 122 C - GeT AC 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。この文字列に対する次の 個のクエリに答えよ。 各クエリでは、文字列の区間 が与えられる。この区間を取り出した部分文字列に…

AtCoder ABC 328 D - Take ABC (3Q, 茶色, 425 点)

stack を使ってカッコ列判定をする問題の亜種! 問題へのリンク 問題概要 3 種類の文字 'A'、'B'、'C' からなる文字列 が与えられる。この文字列に対して、「左から見ていって "ABC" があったら消す」を何度も繰り返していって残る文字列を答えよ。 制約 考…

AtCoder ABC 328 E - Modulo MST (1Q, 緑色, 475 点)

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