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

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

区間

AtCoder ABC 169 E - Count Median (500 点)

未証明でも確信持てる系。でも、こういう風に「作れるものは連続している」というのはたまに見るパターン。そういう問題には「とりうる状態が連結」というタグをつけているので是非に!! drken1215.hatenablog.com 問題へのリンク 問題概要 個の整数 を次の…

AtCoder ABC 140 D - Face Produces Unhappiness (400 点)

ABC では数少ない発想力系。 問題へのリンク 問題概要 L と R から成る 文字の文字列 が与えられる。文字列のスコアは次のようにして決められる。 各 index i について S[ i ] = 'L' ならば、i + 1 >= 0 かつ S[ i - 1 ] = 'L' のときに限り、1 を加算 S[ i …

AtCoder ARC 075 E - Meaningful Mean (600 点)

じょえちゃんえるから。 「平均値が 以上」という条件を見たときにパッと考えつく話がある。 問題へのリンク 問題概要 個の正の整数列 と整数 が与えられる。 整数列の連続する部分列であって、その平均値が 以上であるものが何個あるかを求めよ。 制約 考え…

AtCoder ABC 122 B - ATCoder (200 点)

E8君問題集第3問! 問題へのリンク 問題概要 長さ の文字列 が与えられる。 の連続する部分列であって、'A', 'C', 'G', 'T' のみからなる部分の長さの最大値を求めよ。 制約 考えたこと が小さいので、全部調べても間に合う。連続する部分列は 個ある。 それ…

Educational Codeforces Round 84 F. AND Segments (R2500)

実家 DP 苦手すぎる。今回は解法を簡単なものにするにあたって、「区間の左端も右端も単調増加と思って良い」というのが、割と効いてる気がする。 問題へのリンク 問題概要 長さ の数列であって、各要素の値が 以上 未満であるもののうち、以下の 個の条件を…

AtCoder ABC 159 E - Dividing Chocolate (500 点)

制約が縦方向の bit 管理を要求している感満載 問題へのリンク 問題概要 のグリッドがあって各マスに 0 か 1 が書き込まれている。これに対し、縦横にラインでカットして、部分長方形区域に分けたい。どの区域も 1 の個数が 以下になるようにする。 これを実…

AtCoder ABC 159 F - Knapsack for All Segments (600 点)

ごちゃごちゃとばぐらせながら何とか通した... 問題へのリンク 問題概要 要素の数列 が与えられる。この数列の 通りの区間それぞれについての 区間内の要素の部分集合であって総和が であるものの個数 の総和を求め、998244353 で割ったあまりを求めよ。 制…

AtCoder AGC 043 A - Range Flip Find Route (400 点)

「予め盤面をいじることができる」という設定の問題にはある程度の定石があるように思う! 問題へのリンク 問題概要 の盤面が与えられ、左上から右下まで行きたい。'#' マスは壁を表し、'.' マスは通路を表す。 予め盤面に以下の操作を行うことができる。最…

AOJ 1611 ダルマ落とし (ICPC 国内予選 2016 D)

このブログの「区間 DP」タグを充実させたい。この問題は本当に典型的な区間 DP なのでちょうどいい!!! 問題へのリンク 問題概要 長さ の整数数列 が与えられる。これらに対して以下の操作を好きな順序で好きな回数だけ行う。 値の差が 1 以下であるよう…

フォルシアゆるふわ競プロオンサイト #3 E - Sweets Distribution(Hard)

面白かった。セグ木にこういうの乗っけるの楽しい! 問題へのリンク 問題概要 の盤面の各マスに整数値が書かれている。このマスに対して、適切に を決めて、 盤面の 0 行目の区間 の総和 盤面の 1 行目の区間 の総和 盤面の 2 行目の区間 の総和 盤面の 3 行…

CODE FESTIVAL 2017 qual C D - Yet Another Palindrome Partitioning (700 点)

遷移先を絞れる系の DP 問題へのリンク 問題概要 長さ の文字列 が与えられる。これを以下の条件を満たすように最小個数の区間に分割したい。最小個数を求めよ。 どの区間についても、区間内の文字を適切に並び替えると回文になる 制約 考えたこと まず「文…

Educational Codeforces Round 74 F. The Maximum Subtree (R2300)

木 DP シリーズ!!! 問題へのリンク 問題概要 区間グラフとは、 個の区間が与えられたときに、各区間を各頂点に対応させ、intersection がある区間同士に辺が張られたようなグラフのことである。 さて、 頂点の木が与えられる。この木の連結な部分グラフ (…

Educational Codeforces Round 81 F. Good Contest (R2600)

座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 [tex \lbrack L_{i}, R_{i} \rbrack] が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制…

第6回 ドワンゴからの挑戦状 2020 予選 E - Span Covering (1100 点)

すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AOJ 2600 Koto Distance (JAG 夏合宿 2013 day2-A)

面白かった 問題へのリンク 問題概要 二次元平面上に 個の点がある。これらの各点 に対し、 を満たす点 に電波が届く。 から までの長方形区間全体に電波が届くかどうかを判定せよ。 制約 考えたこと 全体を覆っているとき、以下のいずれかは成立しているこ…

AtCoder ABC 153 F - Silver Fox vs Monster (600 点)

区間加算に対応したデータ構造の出番! 問題へのリンク 問題概要 体のモンスターがいて、それぞれ座標 にいて、HP は である。すべてのモンスターを倒したい。 1 回の魔法で、座標 を指定して、[ ] の範囲内にいるモンスターの HP をすべて ずつ減少すること…

キーエンス プログラミング コンテスト 2020 B - Robot Arms (200 点)

区間スケジューリング問題そのものだった!!! ...とはいえ 200 点というのは衝撃!!! 問題へのリンク 問題概要 ある工場では、 数直線上に 個のロボットが設置されている。 ロボット は座標 に設置されていて、左右に長さ のアームを伸ばしている。 これ…

Educational Codeforces 80 E. Messenger Simulator (R2100)

面白かった。 数列の区間に含まれる値の種類数を答えるクエリに素早く答える技術が必要になった。 問題へのリンク 問題概要 がこの順に並んでいる。ここから 回の操作を行う。 回目の走査は、 以上 以下の値 で表され 現在の順列のうち、値 を先頭にもってく…

Codeforces #613 (Div. 2) E. Delete a Segment (R2300)

嘘に悩んだ。なぜ嘘だと気付けなかった... 問題へのリンク 問題概要 以下の問いに 回答えよ (各問いは完全独立)。 個の区間 が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。 個の区間からど…

AtCoder ARC 099 F - Eating Symbols Hard (1200 点)

楽しかった。こういうのでロリハ使うの楽しい。発想自体は Zero-Sum Ranges (200 点) と似てる。 問題へのリンク 問題概要 高橋君は、いつも頭の中に長さ 2000000001 の数列 と、整数値 を思い浮かべている。初期状態では、数列の各要素値と、 の値はすべて …

AtCoder ARC 101 F - Robots and Exits (900 点)

またしても、in-place DP のいい練習になった!!! 最初は絶望感が漂うのだけど、これも結局「必要条件を列挙したら十分条件になっていた」系な気もする。 問題へのリンク 問題概要 個のロボットと、 個の穴が一直線上に並んでいる。ロボットは穴に重なると…

AtCoder ARC 085 F - NRE (1000 点)

実家なんだと思うけど...意外とはまりやすい問題な気がします 問題へのリンク 問題概要 マスの値が最初はすべて 0 に固定されている。以下の 種類の操作の中からいくつか選んで操作する。その結果と、 とのハミング距離の最小値を求めよ。 番目の操作では、…

AtCoder ABC 143 C - Slimes (300 点)

区間ごとに分割していく処理は、ものすごく大事な典型処理なので、是非ともテンプレ化してノータイムで書けたらすごくいい感じ!!!!! 問題へのリンク 問題概要 "aabbbbccbaaa" のような長さ N の文字列 S が与えられる。同じ文字が連続している区間が何…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion (500 点)

区間反転操作問題シリーズ!!! それにしてもいろんな見方ができる問題な気がする。 問題へのリンク 問題概要 長さ の 'B', 'W' からなる文字列 があたえられる。今この文字列に 回の操作を行う。 まだ選んでいない 2 マス を選んで区間 [ ] の 'B' と 'W' …

Educational Codeforces Round 73 F. Choose a Square (R2500)

「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする!!! 問題へのリンク 問題概要 二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。 対角線のうちの一つが 上にあるよ…

AtCoder ARC 074 E - RGB Sequence (800 点)

わかってる...!わかってるんだ!!!この問題が超ド典型だってことくらい!!!!!!!! でも典型だからって、そんなパッと解けるわけじゃない。すごく苦手なんだこういうの。。。 問題へのリンク 問題概要 マスを RGB の三色で塗り分ける 通りの方法のう…

AtCoder ABC 132 D - Blue and Red Balls (400 点)

二項係数が吹き荒れる!!!!!!!!! そして、重複組み合わせに関する理解がすごく問われる問題!!!!!!! 問題へのリンク 問題概要 個のボールがあって、そのうちの 個が青で、残りの 個が赤である。同じ色のボールは互いに区別できない。 各 に対…

AtCoder ABC 131 D - Megalomania (400 点)

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題!!! 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべて…

AtCoder AGC 017 B - Moderate Differences (400 点)

むむむ 問題へのリンク 問題概要 長さ の整数列 であって、 が 以上 以下の整数 となるものが存在するかどうかを判定せよ。 制約 考えたこと とりあえず , としてよい。 さて、 からスタートして、 ターン目にどんなのを作れるかを考察してみる。 1 ターン目…

AtCoder ABC 130 D - Enough Array (400 点)

超典型的なしゃくとり法そのものだった!!! 問題へのリンク 問題概要 個の整数 があたえられる。数列の連続した区間であって、その総和が 以上となっているものを数え上げよ。 制約 考えたこと しゃくとり法については以前に記事を書いた。 qiita.com この…