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

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

JOI難易度7

JOIG 2023 E - 運河 (難易度 7)

UnionFind を使って、差分更新を頑張る! UnionFind はオンラインの処理を簡単に実現できることが強みで、それを問いかける教育的問題ですね。他にも「左右からの結果を前処理する」という典型テクも使います! 問題へのリンク 問題概要 のグリッドがあって…

JOI 春合宿 2007 day3-2 Route (難易度 7)

DIjkstra をするときに、直前の頂点ももつ系 問題へのリンク 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点 の座標は となっている。 頂点 1 から頂点 2 へと至る経路のうち、鋭角に曲がる箇所がないようなものを考える (頂点 の前の頂点…

JOI 本選 2007 E - 最軽量のモビール (AOJ 0520, 難易度 7)

読解が大変だけど、本質的には木 DP な問題 ジャッジへのリンク AOJ ページ 問題概要 本の棒を用いて、下図のようなモビールを作りたい。 入力としては、各棒 についての 左端から支点までの長さ 右端から支点までの長さ 左端からつながっている棒の index (…

JOI 本選 2007 D - 最悪の記者 (AOJ 0519, 難易度 7)

トポロジカルソートせよ、という問題! 問題へのリンク 問題概要 頂点数 、辺数 の DAG (閉路のない単純有向グラフ) が与えられる。 このグラフのトポロジカルソート順を一つ求めよ。また、トポロジカルソート順が唯一かどうかを判定せよ。 制約 考えたこと …

JOI 二次予選 2021 D - 安全点検 (AOJ 0694, 難易度 7)

難易度 8 でもおかしくないと思った。 B や C より易しい気がしなくもないけど、本番の緊張感で B や C を飛ばして D を本気で考える決断はなかなかできなさそう。今回は B - パンケーキを見て冷静になれたか勝負だね... 問題へのリンク 問題概要 個の工場が…

JOI 二次予選 2021 B - パンケーキ (AOJ 0692, 難易度 7)

難しかった!!! 予選の問 2 からこういうの出るのびっくり!!! 問題へのリンク 問題概要 "A", "B", "C" からなる文字列 に対して、以下の操作を繰り返すことでソートされた状態 ("A" の前には "B" や "C" がなく、"B" の前には "C" がない状態) にするこ…

JOI 春合宿 2007 day2-2 Fermat (難易度 7)

これ FFT を使えば でもできるね。実際は で間に合う。 ジャッジページ 問題文 問題概要 正の素数 と、正の整数 が与えられる。 は 以上 以下の整数 を満たすような の組の個数を求めよ。 制約 は素数 考えたこと まずは次のように集計処理をしよう。このよ…

JOI 本選 2014 C - バームクーヘン (AOJ 0600, 難易度 7)

以前にしゃくとり法の記事で特集した問題のひとつだった! 問題へのリンク editorial 問題概要 環状のバームクーヘンを 3 つに分けたい。 バームクーヘンは下図 (問題文から引用) のように 個のピースに分かれていて、それぞれのサイズは となっている。 バ…

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

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

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

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

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

区間についてどうのこうのする問題、大抵は DP! 問題へのリンク 問題概要 個の整数 がある。これらのうちいくつか選んだ合計を最大化したい。ただし、 の区間 [ ] があって、選んだ数のどの 2 つをとっても同一区間上にならないようにしなければならない。 …