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

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

区分線形関数

AtCoder ABC 080 A - Parking (灰色, 100 点)

これは簡単だけど、頭がごちゃごちゃにならないようにしよう! 問題へのリンク 問題概要 ある駐車場では 2 パターンが選べる 時間駐車したときに、 円かかる 駐車時間にかかわらず、 円かかる 時間駐車したときの料金の最小値を求めよ。 解法 2 パターンの駐…

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

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

AtCoder ABC 044 A - 高橋君とホテルイージー (灰色, 100 点)

ちょっと数学的素養が必要な問題 問題へのリンク 問題概要 あるホテルの宿泊代は、 最初の 泊は、1 泊 円 それ以降は、1 泊 円 である。 泊したときの宿泊代を求めよ。 コード if 文を使おう。 泊以内の場合、つまり N <= K の場合は、X * N 円となる。 泊を…

CPSCO2019 Session3 G - Grand Election (800 点設定)

資源配分問題とも言われるタイプの問題。均等配分からの摂動で良さそう (嘘解法) だと騙すことを狙った! 問題へのリンク 問題概要 個の正の整数 (総和を とする) が与えられたとき、 が最小値となる を満たすような非負整数の組 を求めよ。複数通り考えられ…

AtCoder ABC 102 C - Linear Approximation (ARC 100 C) (緑色, 300 点)

| x - a | + | x - b | + | x - c | + ... の最小値を求める問題には定石があるぞいぞい 問題へのリンク 問題概要 長さ の整数列 が与えられます。整数 をいろいろ変えたときの の最小値を求めてください。 制約 考えたこと 非本質だけど、 って普通「変数」…

AtCoder ABC 130 F - Minimum Bounding Box (黄色, 600 点)

時刻 に対する面積関数 の最小化問題。 全体で三分探索をするのは嘘。 問題へのリンク 問題概要 二次元平面上に 個の点がある。各点は初期位置から出発して秒速 1 の速度で上下左右のいずれかに動いている。 このとき、 点の の値の最小値を求めよ。 制約 考…

AtCoder ABC 127 F - Absolute Minima (黄色, 600 点)

超絶苦手系。でもこういうのパッとできるようにせな。 問題へのリンク 問題概要 関数 があります。 はじめ、これは定数関数 です。 個のクエリが与えられるので、順番に処理してください。クエリは 2 種類あり、入力形式とクエリの内容は以下の通りです。 更…