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

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

座標圧縮

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

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

AOJ 2426 Treasure Hunt

BIT を Wavelet Matrix に乗せたやつで解いてみた。加算クエリがないので大袈裟ではある。 問題へのリンク 問題概要 二次元平面上に 個の格子点がある。これらの格子点について、次の 個のクエリに答えよ。 長方形領域が与えられるので、その領域に含まれる…

AtCoder ABC 318 F - Octopus (黄色, 575 点)

高速な解法もあるっぽいけど、愚直に解いた。 問題へのリンク 問題概要 一直線上に 個の宝が座標 に配置されている。一方、長さが である 本の棒がある。次の条件を満たす整数 の個数を求めよ。 各 に対して、座標 の点を始点とするように棒を置いたとき、棒…

AtCoder ABC 277 C - Ladder Takahashi (茶色, 300 点)

グラフで考えよう! 問題へのリンク 問題概要 階建てのビルがあります。 ハシゴが 個あり、 個目のハシゴは 階と 階を結んでいます。これらのハシゴは双方に行き来できます。ただし、ハシゴ以外の手段によって、異なる階の行き来はできません。 高橋くんは最…

AtCoder ABC 304 D - A Piece of Cake (緑色, 400 点)

「点がどの区間に属するか」は極めて典型的な問題で、それを二次元にしたバージョン! 問題へのリンク 問題概要 二次元平面上で、左下の頂点が 、右上の頂点が であるような長方形状のケーキがあります。 このケーキ上には 個のいちごが乗っていて、 番目の…

AOJ 1088 School Excursion

最小費用の最大流を流すネットワークフロー問題! 問題へのリンク editorial 問題概要 個の駅があり、 と番号づけられている。 駅 と駅 の間には 種類の電車が走っていて、 番目の電車は 駅 を時刻 に出発して、 駅 に時刻 に到着し、 料金は である。 今、 …

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

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

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

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

AtCoder ABC 213 C - Reorder Cards (茶色, 300 点)

一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。 問題へのリンク 問題概要 のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。 このグリッドに対して、次の操作を可能な…

AtCoder ABC 036 C - 座圧 (試験管緑色)

文字通り、与えられた数列を座標圧縮する問題ですね。 問題へのリンク 問題概要 長さ の数列 が与えられます。 これらの数列から重複を除外して小さい順に並び直して得られる数列を とします。 各 に対して、 となるような を出力してください。 制約 座標圧…

座標圧縮 (座圧)

競技プログラミングで時々問われる「座標圧縮」について簡単に解説します。 1. 座標圧縮とは 数列 が与えられたときに、それぞれの要素が「全体の中で何番目に小さいか」を求めていく作業を、競プロ界では座標圧縮 (座圧) とよびます。 たとえば A = (8, 100…

AtCoder ARC 115 E - LEQ and NEQ (黄色, 700 点)

間に合わなかった!!!悔しい!!! 問題へのリンク 問題概要 長さ の数列 が与えられます。以下の条件を満たすような、長さ の数列 の個数を 998244353 で割ったあまりを答えよ。 制約 考えたこと という条件は扱いづらいので、包除原理でやると良さそう。…

JOI 二次予選 2021 C - イベント巡り (AOJ 0693, 難易度 8)

これはアレだ!!! DP の最適値そのものの値を利用して次の遷移を作る系。フクロモモンガなんかもそういう系の問題だった覚えがある。 問題へのリンク 問題概要 2 つの町 (1 と 2) がある。 個のイベントがあって、それぞれ町 において発生し、時刻 に始ま…

JOI 春合宿 2007 day1-1 Score (難易度 3)

まさに「座標圧縮」をしてください、という問題! ジャッジページへのリンク 問題文へのリンク 問題概要 個の整数 が与えられる。それぞれについて、「大きい順に何番目か」を求めよ。 たとえば に対しては、答えは となる。 制約 前提知識 座標圧縮について…

AOJ 3212 Intimate Slimes (OUPC 2020 D)

|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった! 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …

AtCoder AGC 048 C - Penguin Skating (黄色, 700 点)

想定解法とちょっと違うやり方したっぽい 問題へのリンク editorial 問題概要 個のマスが横一列に並んでいる ()。 匹のペンギンがマス にいる。 あなたは,次の操作を好きな回数行うことができる。 ペンギンを 1 匹選び、左または右へ向かって滑らせる ペン…

HHKB プログラミングコンテスト 2020 F - Random Max (橙色, 600 点)

時々やってくる積分ゲー。同時に多項式ゲーでもあった。 問題へのリンク 問題概要 個の区間 が与えられる。これらの区間から一様分布にしたがって点をとってくる (連続値)。 各点の座標の最大値の期待値を をかけた値 (整数値になる) を 1000000007 で割った…

AtCoder ARC 104 E - Random LIS (赤色, 700 点)

ゲーは確かに面白いかもしれない。 問題へのリンク 問題概要 長さ の整数列 が与えらる。 同じく長さ の整数列 は、 各 について独立に、 を満たす整数の一様分布からランダムに選ばれる。 このとき、 の最長増加部分列の長さの期待値を mod 1000000007 で計…

AOJ 3196 Increasing Sequence (AUPC 2020 day1-D)

in-place な DP にもっと慣れていきたい 問題へのリンク 問題概要 個の数列がある。 個目の数列は 個の要素からなる。 個目の数列の 番目の要素は と表す。 個目の数列から 1 個以下の要素を選び、選んだ要素を元の数列の順番通りに並べた数列を とする。 数…

AOJ 3181 Proper Instructions (HUPC 2020 day3-J)

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

Codeforces CodeCraft-20 (Div. 2) F. Battalion Strength (R2800)

実装がエグエグのエグだけど、実はなんと、遅延評価セグ木すら必要なくて、普通のセグ木だけあれば解けてしまう! 問題へのリンク 問題概要 個の整数 に対して定まる量 を次のように定義する: の部分集合を選ぶ 通りの方法から一様ランダムに選んで、さらに…

Educational Codeforces Round 81 F. Good Contest (R2600)

座標圧縮をがんばる 問題へのリンク 問題概要 個の区間 が与えられる。それぞれの区間から一様ランダムに整数を選んでいく。 これが広義単調減少となる確率を求め、それを 998244353 で割ったあまりの形式で求めよ。 制約 考えたこと 区間の幅は大きいが、 …

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

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

Codeforces Round #479 (Div. 3) F. Consecutive Subsequence (R1700)

教育的で楽しい 問題へのリンク 問題概要 長さ の数列 が与えられる。数列中の部分列 (連続でなくてよい) であって、連続する自然数となっているもののうち、最長のものを求めよ。 また、それを復元せよ (添字を答える)。 ex: (3, 3, 4, 7, 5, 6, 8) -> (3, …

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

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

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

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

AtCoder ABC 128 E - Roadwork (青色, 500 点)

これと似てる!!! これの解法 3 みたいなやり方をイベントソートって呼ぶのね。 drken1215.hatenablog.com 問題へのリンク 問題概要 (意訳) くらいのサイズの配列があって最初は INF に初期化されている。 回の以下の操作を行う 整数 が与えられて、区間 […

Chokudai SpeedRun 002 K - 種類数 β (600 点)

これがこのセットで一番難しかった。 こういうのをグラフで考えるのは典型と言えば典型か。 問題へのリンク 問題概要 組の整数組 がある。それぞれの組から整数を選んだ 種類の整数に含まれる整数の種類数の最大値を求めよ。 制約 考えたこと 数値をノードに…

AtCoder ABC 113 C - ID (緑色, 300 点)

いわゆる「座標圧縮」を練習できる問題!!! 問題へのリンク 問題概要 組の 2 整数 が与えられる。 の値は のいずれかである。 各 に対して、 という値が、 の値が等しいようなものの中で何番目に小さい値なのかを求めよ。 (出力形式については特殊なので、…

2018 codeFlyer 予選 D ハンコ (500 点)

座標圧縮して二次元いもす法だけど、頭がごっちゃになった。 問題へのリンク 問題概要 白黒からなる N × M の二次元盤面が与えられる。これをより大きな盤面 H × W の左上隅に置く。N × M 盤面を H × W 盤面からはみ出さない範囲で動かしていく。このとき「…