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

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

区間ソート

AtCoder ABC 355 D - Intersecting Intervals (2Q, 茶色, 400 点)

ものすごく教育的な典型問題! 色んな方法が考えられるが、ここでは区間ソートで解いてみる。 問題へのリンク 問題概要 数直線上に 個の区間が与えられる。 番目の区間は である。 これら区間の組であって、共有点をもつ (端点含む) ものの個数を求めよ。 制…

JOIG 春合宿 2023 day2-1 Smartphone (難易度 8)

JOI ではお馴染みの「 個の区間を扱う問題」。ただし実装がしんどかった。僕は区間を set で管理する方法で実装した。 問題へのリンク editorials 問題概要 制約 考えたこと いかにも貪欲法の香りが漂っている問題ですね。この手の問題では、 個の区間を終端…

AtCoder ABC 325 D - Printing Machine (水色, 450 点)

とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

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

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

Codeforces Round 892 (Div. 2) D. Andrey and Escape from Capygrad (R??00)

区間を整理する考え方が楽しかった。 問題へのリンク 問題概要 下図のように 組の「黒い区間」と「赤い区間」がある。赤い区間は黒い区間に完全に包含されている。 この区間上でコマを動かしていく。コマが 番目の黒い区間の内部にあるとき、 番目の赤い区間…

AtCoder ARC 104 C - Fair Elevator (黄色, 600 点)

コーナーケースがえぐい!! 僕は最初、(1, -1), (-1, 3) で Yes を返してしまっていた。 問題へのリンク 問題概要 個の区間 があって、 両端の座標は のいずれか 両端の座標をかき集めたとき、重複がない 区間 と区間 がもし重なっているならば、区間 の長…

AOJ 3181 Proper Instructions (HUPC 2020 day3-J)

比較的素直な考察で解ける問題 問題へのリンク 問題概要 umgくんは 1 次元上の座標 0 にいます。今は時刻 0 です。時刻が 1 進むごとに、今いる座標より 1 大きい座標に移動するか、 1 小さい座標に移動するか、その座標にとどまるかという行動ができます。 …

Educational Codeforces Round 84 F. AND Segments (R2500)

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

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

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

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

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

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

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

AtCoder ARC 085 F - NRE (赤色, 1000 点)

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

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

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

AtCoder ARC 074 E - RGB Sequence (橙色, 800 点)

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

AtCoder ARC 068 E - Snuke Line (黄色, 700 点)

こういうのを得意になるぞー!!! でも AtCoder でこういうデータ構造をしっかり準備する必要がある系は珍しい気がする。 問題へのリンク 問題概要 個のマス () があって、マス上に 個の区間がある。 各 に対して、 と移動したときに何個の区間を踏むかを答…

AOJ 3060 Rings (RUPC 2019 day2-J)

有理数さん。。。 誤差がとんでもなく厳しいらしく、有理数ライブラリを使うということをついに覚えた!!! あと、問題の解法自体は「区間串刺し」といういわゆる「区間スケジューリング問題」の亜種。 問題へのリンク 問題概要 とある水族館に住むイルカ君…

Codeforces Yandex.Algorithm 2011 Round 2 D - Powerful array (R2200)

Mo のアルゴリズムの練習第三弾!!!!! 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内について、各数値 について が何個出現しているかを として表して、 を求め、その総和を求めよ 制約 考えたこと…

SPOJ FREQUENT - Frequent values

Mo のアルゴリズムの練習第二弾。 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に最も多く登場する値が、何回登場しているかを答えよ 制約 考えたこと Mo の練習第二弾。 最頻値の頻度を求めるのは、…

SPOJ DQUERY - D-query

種類数クエリをマスターするぞ! 問題へのリンク 問題概要 要素の整数列 が与えられる。以下の 個のクエリに答えよ: 数列の区間 [ ) 内に何種類の整数があるかを答えよ 制約 解法 1: BIT (区間加算、1 点取得) まずは BIT を用いる方法から。 考えやすいよ…

JOI 予選 2019 E - イルミネーション (AOJ 0656, 難易度 7)

区間についてどうのこうのする問題、大抵は DP! 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …

AtCoder ABC 106 D - AtCoder Express 2 (水色, 400 点)

いろんな方法が考えられそう。 せっかくなので、敢えて、N が大きくても OK な方法でやってみる。hama_du さんの記事を参照。 問題概要 M 個の区間 [l_i, r_i] が与えられる。以下の Q 個のクエリに答えよ: 区間 [p, q] に完全に含まれる区間が何個あるかを…

AtCoder ABC 103 D - Islands War (水色, 400 点)

問題へのリンク 実は、こないだの RUPC 2018 で出てた (最後の部分のみほぼ同じ) AOJ 2873 - 検閲により置換 見た目は区間スケジューリング問題とは違うけど、実は区間スケジューリング問題 (こういうの双対問題と言ったりする)。双対性の知識がまったくなく…

CS Academy 076 DIV2 D - Pyramids

えーーーーー、どうしてバグに気づかなかった。。。orz 問題へのリンク 問題概要 x 軸上に斜辺を持つような直角二等辺三角形 (三頂点はどれも格子点) が N 個与えられる。N 個の直角二等辺三角形によって被覆される格子点の総数を求めよ。 制約 1 <= N <= 10…