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

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

一直線上のN点の問題

AtCoder ABC 123 A - Five Antennas (灰色, 100 点)

ちょっと数学的な部分が難しい問題かもしれない。 問題へのリンク 問題概要 5 つのアンテナがこの順に一直線上に並んでいて、それぞれ座標値は () である。 2 つのアンテナは、距離が 以内であるとき、通信できる。 これらのアンテナの組であって、通信でき…

JOIG 2024 C - 座席 2 (難易度 6)

色んな解法が考えられそうな問題で、ドツボにハマりやすくて危険な問題だったと思う。落ち着いて整理してシンプルに考える力が問われる。実は、二分探索などは必要ない問題である。 問題へのリンク editorial 問題概要 人の選手 がいる。選手 の出身国は で…

AtCoder ABC 097 A - Colorful Transceivers (灰色, 100 点)

ちょっと整理するのが大変な問題。 問題へのリンク 問題概要 一直線上の座標 の点に、それぞれ A さん、B さん、C さんがいる。 2 人は、距離が 以内にいるとき、直接的に通信ができる。 A さんと C さんが、直接的に、あるいは間接的に、通信ができるかどう…

AtCoder ABC 071 A - Meal Delivery (灰色, 100 点)

整数 の差は、絶対値記号を用いて と表せる。絶対値は、たとえば C++ では関数 abs() が使える! 問題へのリンク 問題概要 座標軸上で、店 A, B がそれぞれ座標 にある。 今、すぬけ君は座標 の地点にいる。すぬけ君にとって、店 A, B のどちらに近いかを判…

AtCoder ABC 326 C - Peak (灰色, 300 点)

lower_bound() 系の教育的問題 問題へのリンク 問題概要 一直線上に 個の点がある。点 の座標は である。 この直線上で幅 の区間を配置する。左端の座標を とするとき、 を満たす の個数をスコアとする。最大スコアを求めよ。 制約 考えたこと まず重要な考…

JOIG 2023 C - 鐘 (AOJ 0759, 難易度 4)

直線がいくつかの区間に分かれているとき、点がどの区間に属するかを求めたいとなったら、lower_bound()!!! 問題へのリンク 問題概要 数直線上に 個の鐘がある。 番目の鐘は座標 の地点に配置されている。 地点 の人の聞く鐘の音の強さは、各鐘 に対する …

AtCoder ABC 320 F - Fuel Round Trip (黄色, 550 点)

少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…

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

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

AtCoder Library Practice Contest H - Two SAT

2-SAT は強連結成分分解の典型的な応用例! 問題へのリンク 問題概要 旗 を数直線上に設置したい。旗 は、座標 または座標 に設置可能である。 ただし、どの 2 つの旗も、その距離が 以上となるようにする必要がある。 本の旗を設置することが可能かどうかを…

AOJ 1088 School Excursion

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

JOIG 2021 D - 展覧会 2 (AOJ 0704, 難易度 6)

「競プロ典型 90 問 001 - Yokan Party」とよく似た問題! 問題へのリンク editorial 前提知識 基本的な二分探索 問題概要 枚の絵が一直線上に順に並んでいます。 枚目の絵は座標 の位置にあり、その価値は です。 今これらの絵から 枚の絵を選びます。この…

JOI 二次予選 2021 D - 安全点検 (AOJ 0694, 難易度 7)

難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…

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

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

JOI 二次予選 2021 A - 往復すごろく (AOJ 0691, 難易度 5)

結構アドホックで難しいと思った! 問題へのリンク 問題概要 マスが横一列に並んだすごろくが与えられる ( と番号づけされている)。すごろくの各マスは . と x と # のいずれかである。 マス とマス は X である 他のマスは長さ の文字列 で与えられる X は…

JOI 予選 2016 D - JOI国のお散歩事情 (AOJ 0622, 難易度 6)

手を動かしてみると、どうなってるかが見えてくる! 問題へのリンク 問題概要 人がそれぞれ座標 に並んでいる (単調増加、負もありうる、各 は偶数)。そして時刻 0 において、 人はそれぞれ正の方向 ( で与えられる) または負の方向 ( で与えられる) に 1 秒…

AtCoder AGC 049 C - Robots (黄色, 800 点)

11 WA の末に通した... 問題へのリンク 問題概要 初期状態では、数直線上の座標 の位置にロボット がいる。 一方、たくさんのボールがある。ボールの情報は長さ の整数列 と で表される。具体的には、各 について、 の書かれたボールが 個ある。 今からすぬ…

AtCoder ARC 105 C - Camels and Bridge (青色, 500 点)

難しかった 問題へのリンク 問題概要 体重が であるような 体のラクダがいる。ラクダを一列に並べる方法のうち、次の条件を満たすものについて、左端のラクダと右端のラクダの距離として考えられる最小値を求めよ。また、そのようにラクダを並べることが不可…

ACL Contest 1 D - Keep Distances (橙色, 800 点)

これは天才!!! 問題へのリンク 問題概要 一直線上に 個の点が順に並んでいる (座標が )。 個のクエリが与えられる。 各クエリでは区間 () が与えられる 個の点のうち のみを取り出してできる 個の点について以下の問に答えよ 与えられた点集合から、どの …

AOJ 3182 Umg Kart (HUPC 2020 day3-K)

確かに、えでゅふぉのラス問にありそう! 問題へのリンク 問題概要 人の選手が距離 のレースを走る。 人目はデフォルトでは距離 1 走るのに 秒かかる。 スタートから距離が のところにアイテムがある。各アイテムは各選手に対して独立に、確率 で減速 (距離 …

AOJ 3178 Katsusando (HUPC 2020 day3-G)

いわゆる区間分割する系の DP。こういう系は高速化を要求するタイプの問題が多いけど、今回は素直な二乗 DP で OK! 問題へのリンク 問題概要 直線上にカツが 個ある。 個目のカツは位置 にあり、その重さは である。これらのカツを、次のようにしてすべて回…

AtCoder AGC 006 C - Rabbit Exercise (赤色, 800 点)

操作を 回行った結果を求める系、苦手意識あるけど克服したい! 問題へのリンク 問題概要 と番号の振られた 個のボールがあって、初期状態ではそれぞれ の位置にある。以下の操作を 回行う。最終的な各ボールの座標の期待値をそれぞれ求めよ。 各操作は 個の…

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

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

第6回 ドワンゴからの挑戦状 予選 B - Fusing Slimes (青色, 600 点)

期待値の線形性的な。 問題へのリンク 問題概要 体のスライムがそれぞれ の位置にいる (これらは単調増加)。 以下の 通りのスライム合体過程それぞれについて、スライムの移動距離の総和を考える。その総和距離の総和を求めよ。1000000007 で割ったあまりで…

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

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

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

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

AtCoder AGC 007 D - Shik and Game (橙色, 1200 点)

すごく典型的な問題。 現代なら企業コンの 800 点問題とかに出そうな雰囲気だね。このころはまだあまり典型じゃなかったのかな。 問題へのリンク 問題概要 一直線上に 個の点 があってこの順に並んでいる。さらに左側に 、右側に がある。 からスタートする …

AtCoder ABC 119 D - Lazy Faith (水色, 400 点)

二分探索で lower_bound とかきっちり無意識的に使いこなせるようになりたいのんな!!! 問題へのリンク 問題概要 一次元の世界を考える。 A 個の神社と、B 個の寺が並んでいる (各神社と各寺の位置情報が 1 つの整数値で与えられる)。 以下の Q 個のクエリ…

AtCoder ABC 117 C - Streamline (茶色, 300 点)

ソートする問題。 問題へのリンク 問題概要 個のコマを数直線上に配置して、それぞれ移動させる。 それによって、 個の地点 をすべて訪れるようにしたい。総移動距離の最小値を求めよ。 制約 考えたこと とりあえず、各コマについて、「行って、引き返して」…

技術室奥プログラミングコンテスト #2 E - 歩くNPCたち(Walking NPCs)

えーーーこれが平方分割的解法って天才すぎでは 問題へのリンク 問題概要 人が一直線上を、初期位置 、速度 で等速直線運動を行う。以下の 個のクエリに答えよ: 秒後に座標 から座標 までの間にいる人数を数えよ 制約 考えたこと が 以下と小さいことが大き…

CODE FESTIVAL 2018 qual A D - 通勤 (700 点)

ひたすらバグってつらかった。。。DP 高速化系。セグ木を使ってもいいが、累積和だけで解ける。 問題へのリンク 問題概要 座標 地点から座標 地点へと移動する。 移動途中に 個のガソリンスタンドがあって、それらの座標は で与えられる。 燃料 の状態でスタ…