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

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

JOI

JOI 本選 2016 B - スタンプラリー 2 (AOJ 0626, 難易度 6)

面白かった! 問題へのリンク editorial 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす整数 の組の個数として定めます。 = "J" = "O" = "I" 今、文字列 の両端および隙間の好きな…

JOI 本選 2017 A - フェーン現象 (AOJ 0636, 難易度 6)

差分だけ更新していく系の問題!!! 問題へのリンク editorial 問題概要 正の整数 が与えられる。長さ の数列 のスコアが次のように定まる。 各 に対して以下の値を合算する のとき: のとき: を満たすような初期数列 が与えられる。以下の 個のクエリに答…

JOI 本選 2020 A - 長いだけのネクタイ (AOJ ????, 難易度 6)

Greedy を考察して、さらに左右から累積和を求める!結構難しい! 問題へのリンク editorial 問題概要 長さ の数列 と、長さ の数列 が与えられます。各 に対して、次の値を求めよ。 数列 から を除去してできる長さ の数列 を考えて、数列 を適切に並び替え…

JOI 本選 2020 B - JJOOII 2 (AOJ ????, 難易度 6)

最初 DP とか考えたくなるやつ。落ち着くと見えてくる。 問題へのリンク 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。ところで、レベル の JOI 文字列とは、"JJ...JOO...OII...I" (それぞれ 個ずつ) のことを指すものとする。 文字…

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

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

JOI 本選 2019 B - 展覧会 (AOJ 0659, 難易度 7)

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

JOI 本選 2019 C - たのしいたのしいたのしい家庭菜園 (AOJ 0660, 難易度 9)

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

JOI 本選 2019 A - 勇者ビ太郎 (AOJ 0658, 難易度 5)

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

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

JOI 本選 2011 E - JOI 国のお祭り事情 (AOJ 0575, 難易度 10)

並列二分探索が想定ではなさそうだけど、並列二分探索のいい練習問題になったん!!! 問題へのリンク 問題概要 制約 解法 #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>…