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

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

JOI難易度6

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

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

JOIG 2023 D - コイン集め 2 (難易度 6)

データを上手に持って、差分更新する系の問題 問題へのリンク 問題概要 のグリッドがあって、各マスは文字 '#' か '.' のいずれかが書かれている。先手は '#' の個数が得点となり、後手は '.' の個数が得点となる。双方得点を最大化したい。 先手は行を 1 つ…

JOI 本選 2023 A - 碁石ならべ 2 (難易度 6)

どうなっているのかを観察して計算量を減らす系。観察力が問われる! 問題へのリンク editorials 問題概要 個の碁石を左から順に並べていく。 番目に並べる碁石の色は である ( 以上 以下の数値)。碁石を並べるときの規則は次のようになる。 番目の碁石を 番…

JOIG 春合宿 2022 day1-1 Relay (難易度 6)

面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…

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

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

JOI 本選 2011 B - 古本屋 (AOJ 0561, 難易度 6)

こういうのは DP! ジャッジページ AOJ の問題文 問題概要 冊の古本があって、 番目の本のベース価格は 円である。またこれらの本は 10 種類のジャンルに分かれており、 番目の本のジャンルは で与えられる。 これらの本から 冊を古本屋で売りたい。ただし同…

JOI 本選 2010 C - つらら (AOJ 0551, 難易度 6)

実装をどうしようかを色々悩んでしまう系 ジャッジページ AOJ の問題文 問題概要 本のつららが一列に並んでいる。それぞれ長さは となっている。各つららは以下のルールに従って長さが変わる。 一度でも長さが 0 になったならば、伸びることはない 左右のつ…

JOI 予選 2010 E - 通勤経路 (AOJ 0547, 難易度 6)

JOI 難易度 6 の中では難しい方だと思った! 問題へのリンク editorial 問題概要 のグリッドの左下マス から右上マス へと至る最短経路 (上または右にのみ移動可能) のうち、以下の条件を満たすものの個数を 100000 で割ったあまりを求めよ。 曲がってから、…

JOI 本選 2009 B - ピザ (AOJ 0539, 難易度 6)

ひょっとしたら難易度 5 との境界の問題だったかもしれない。lower_bound() を試すいい感じの例題。 ジャッジページへのリンク 問題文 editorial 問題概要 一周の長さが であるような周回コースがあって、コース上に 個の店舗がある。コース上の 1 点の座標…

JOI 予選 2009 C - 連鎖 (AOJ 0534, 難易度 6)

いろんな実装方法がありそう。でも が間に合うので、すべての書き換え方法について でできるなら十分。 問題へのリンク 問題概要 1 と 2 と 3 のみからなる長さ の数列が与えられる。同じ数値が 4 個以上連続することはない。 この数列のうちの 1 箇所の値を…

JOI 春合宿 2010 day1-3 Stairs (難易度 6)

区間分割していく DP を普通にやると になる (オレンジの出荷もそう)。それを累積和を用いて高速化する。 ジャッジページへのリンク 問題文へのリンク 問題概要 (意訳) 個の正の整数 が与えられる。これらをいくつかの連続した区間に分割していく。ただしど…

JOI 春合宿 2011 day1-1 Banner (難易度 6)

面白かった。単純にやると なので、そこから計算量オーダーを 1 つ落とすことを考える。 ジャッジページへのリンク 問題文へのリンク 問題概要 のグリッドが与えられる。各マスには 0, 1, 2 のうちのいずれかの値が描かれている。 これらの 個のマスのうちの…

JOI 春合宿 2008 day3-1 Origami (難易度 6)

一見すると典型的な「座標圧縮」+「二次元いもす法」なのだが、それだと TLE / MLE してしまう。 ジャッジへのリンク 問題文へのリンク 問題概要 のグリッド上に 枚の長方形の紙を敷いていく。 枚目の紙は を満たす座標 を覆う領域に配置される。最も多くの…

JOI 春合宿 2008 day2-1 Nile.Com (難易度 6)

いかにも ABC-E にありあそうな DP!! ジャッジへのリンク 問題文へのリンク これとか似てる atcoder.jp 問題概要 個の店がある。 日間にわたって、いずれか 1 つの店で買い物をする。 日目に 番目の店で買い物をしたときの値段は で与えられる (10 の倍数)…

JOI 本選 2008 C - ダーツ (AOJ 0529, 難易度 6)

AtCoder 版蟻本記事で、登竜門として紹介している問題。 ずばり「半分全列挙 + 二分探索」です! 問題へのリンク 類題とか drken1215.hatenablog.com 問題概要 個の正の整数 が与えられる。これらの整数のうちから重複を許して 4 個まで選んで総和をとる (1 …

JOI 予選 2018 E - おせんべい (AOJ 0525, 難易度 6)

幅が小さいので、幅についての 通りの探索が間に合う! 問題へのリンク 問題概要 のマス目がある。各マスの値は 0 または 1 である。次の操作を好きな順序で好きな回数だけ行うことができる。 ある行を選択して、その行の数値をすべてひっくり返す (0 を 1 …

JOI 春合宿 2007 day3-1 anagram (難易度 6)

桁DPとは違うけど、桁DP的な発想で解けた ジャッジページへのリンク 問題概要 長さ の文字列 が与えられる。 の各文字を並び替えてできる文字列をすべて考えたとき、 はその中で辞書順で何番目の文字列に相当するのかを求めよ。 制約 の文字はすべて英大文字…

JOI 春合宿 2011 day4-3 IOI (難易度 6)

lower_bound を上手に駆使する系 ジャッジページへのリンク 問題概要 人の選手が、コンテストに参加している。各選手の現在の得点は である。 どの選手についても、今後加算される可能性のある得点は、 点以上 点以下となっている ( 問中 問の競技が終了して…

JOI 予選 2012 E - イルミネーション (AOJ 0569, 難易度 6)

ハニカムつらい 問題へのリンク editorial 問題概要 下図で表されるようなハニカム状のグリッドが与えられる (図は問題文より)。 黒色マスは建物があるマスを表している。赤太線は、「外側」から見て見える外壁を表している。 このような のマップが与えられ…

JOI 本選 2012 C - 夜店 (AOJ 0573, 難易度 6)

左右からナップサックした結果を前処理する系! (他の解法もあり) 問題へのリンク editorial 問題概要 (意訳) (実際の問題文は時刻に関する問題) 個の品物がある。それぞれ の番号がついている。番号が の品物は 価値が 重さが となっている。これらを 2 つ…

JOI 春合宿 2013 day1-4 JOI Poster (難易度 6)

幾何だ!! ジャッジページへのリンク editorial 問題概要 の長方形の紙上に 個の点がある。これらの点は互いに相異なる。 これらの点から 4 つの点 A, B, C, D を選ぶ (選ぶ順番も考慮する)。そして、点 A を中心として点 B を通る円を O1 とし、点 C を中…

JOI 予選 2014 D - 部活のスケジュール表 (AOJ 0595, 難易度 6)

J, O, I の 3 人しかいないと、意外と bit DP を発想しづらいかもしれない。でもこういうのめっちゃ見るね。 問題へのリンク 問題概要 J 君と、O 君と、I 君の 3 人が所属する部活動がある。 日間の活動が行われる。それぞれの日において責任者が誰なのかが…

JOI 本選 2014 B - IOI饅頭 (AOJ 0599, 難易度 6)

まさにナップサック問題!!! 問題へのリンク 問題概要 個の饅頭がある。それぞれ 円で売り出そうとしている (全部売るとは限らない)。 饅頭を得るための箱をいくつか購入することにした。箱は 種類あって、 番目の箱は 饅頭を 個まで詰められる 仕入れるの…

JOI 本選 2014 A - JOI紋章 (AOJ 0598, 難易度 6)

ちょっと実装大変だった。差分のみ更新していく系の問題。 問題へのリンク editorial 問題概要 のグリッドがあって、各マスには "J"、"O"、"I" が書かれている。 またこれとは別に、2 × 2 の "J", "O", "I" のパターンが与えられる ( 通りありうる)。 今、与…

JOI 春合宿 2014 day3-1 JOIOJI (難易度 6)

Zero-Sum Ranges の応用問題だけど、最初難しく考えてしまって「解けない...」となってました ジャッジページへのリンク 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられる。…

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

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

JOI 本選 2016 A - オレンジの出荷 (AOJ 0625, 難易度 6)

区間を分割していくタイプの DP。とても教育的な典型問題という感じですね。 問題へのリンク editorial 類題は超多数!!! drken1215.hatenablog.com 問題概要 正の整数 と、 個の正の整数 が一列に並んでいる。これを左から順に何個かのグループに分けてい…

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

「3 つのものの真ん中に着目する」という典型が学べる。面白かった! 問題へのリンク editorial 類題とか drken1215.hatenablog.com 問題概要 "J" と "O" と "I" のみからなる長さ の文字列 が与えられます。このような文字列のスコアを、以下の条件を満たす…

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

差分だけ更新していく系の問題!!! 問題へのリンク editorial 類題集 (めちゃむずいのもある) drken1215.hatenablog.com 問題概要 正の整数 が与えられる。長さ の数列 のスコアが次のように定まる。 各 に対して以下の値を合算する のとき: のとき: を…

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

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