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

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

JOI予選

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

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

JOI 二次予選 2020 D - テンキー (AOJ ????, 難易度 7)

本選参加のボーダーとなった問題らしい!それにしても JOI は実装が重たい...!!! 問題へのリンク 問題概要 初期状態では下図のようなテンキーの「0」のところにカーソルがある。 上下左右への移動 ボタンを押す (315 に 4 を押すと 3154 になる) を最小回…

JOI 予選 2014 F - 財宝 (AOJ 0613, 難易度 8)

スライド最小値の練習 問題へのリンク 問題概要 個のアイテムがって、それぞれ市場価値 と貴重度 が与えられる。 今、A さんと B さんがそれぞれアイテムのうちの何個かをとる。このとき、A さんと B さんは同じアイテムを取ることはできず、2 人ともとらな…

JOI 予選 2019 D - 日本沈没 (AOJ 0655, 難易度 6)

これまたちょっと重たい。。。 問題へのリンク 問題概要 折れ線グラフが与えられる。これは に対して () を結んでいる。あらゆる水平な直線を考えたときの、折れ線グラフのうち直線の上に来ている部分を連結成分ごとに分解したとき、連結成分の個数として考…

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

区間に対してどうこうする DP 苦手意識ある。。。 区間スケジューリング問題に近い感じ。 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間…

JOI 予選 2019 F - 座席 (AOJ 0657, 難易度 11)

挿入 DP。。。TDPC O - 文字列を複雑にした問題。アイディアはシンプルだけど詳細詰めが重たい。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 が 個 が 個 ... が 個 を合わせた 個の数を並べる方法のうち、どの隣り合う箇所も数値の差が 以上…