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

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

JOI

JOI 二次予選 2020 D - テンキー (Tenkey)

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

JOI 2019 本選 B - 展覧会 (AOJ 0659)

Greedy を信じよう...じゃなくて、証明しよう! 問題へのリンク 問題概要 枚の絵画があって、それぞれ大きさは 、価値は で与えられる。 個の額があって、それぞれ大きさが で与えられる。 絵画と額とをマッチングさせる。ここで、以下の条件を満たすような…

JOI 2019 本選 C - たのしいたのしいたのしい家庭菜園 (AOJ 0660)

結構苦手系。想定解法かはわからないけどやってみた 問題へのリンク 問題概要 'R', 'G', 'Y' の 3 種類の文字で構成された長さ の文字列 が与えられる。これに以下の操作を行って「隣り合う 2 文字が同じになることはない」ようにしたい。それが可能となる操…

JOI 2019 本選 A - 勇者ビ太郎 (AOJ 0658)

とりあえず 1 問目やってみた!累積和の典型題 問題へのリンク 問題概要 以下のような J, O, I で構成される N × M の盤面があたえられる。以下の条件を満たすような 3 マスの組が何個あるか求めよ。 3 マスはそれぞれ J, O, I である J の右側 (行は一緒) …

JOI 2014 予選 F - 財宝 (AOJ 0613)

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

JOI 2019 予選 D - 日本沈没 (AOJ 0655)

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

JOI 2019 予選 E - イルミネーション (AOJ 0656)

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

JOI 2019 予選 F - 座席 (AOJ 0657)

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

JOI 2011 本選 E - JOI 国のお祭り事情 (AOJ 0575)

並列二分探索が想定ではなさそうだけど、並列二分探索のいい練習問題になったん!!! 問題へのリンク 問題概要 制約 解法 #include <iostream> #include <vector> #include <queue> #include <map> #include <algorithm> using namespace std; struct UnionFind { vector<int> par, rank, sz; UnionFind(in</int></algorithm></map></queue></vector></iostream>…