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

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

JOI春合宿

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

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

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

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

JOI 春合宿 2007 day1-3 Mall (難易度 5)

二次元累積和!! ジャッジページ 問題文 問題概要 のグリッドが与えられる。各マスには整数値 が描かれている。整数値は 以上 以下である。 これらのグリッド中の の長方形領域であって、その内部に -1 を含まないものを考える。そのような長方形領域に含ま…

JOI 春合宿 2007 day1-2 Factorial (難易度 5)

素因数分解ゲー! 今なら ABC D あたりに出てきそう ジャッジページ 問題文 問題概要 正の整数 が与えられる。 が の倍数となるような最小の正の整数 を求めよ。 制約 解法 (1):素因数分解 まず を素因数分解しよう。 とする。さらに、 をそれぞれ素因数分…

JOI 春合宿 2007 day2-1 Building (難易度 5)

まさに LIS を求めよ、という問題!! ジャッジページ 問題文へのリンク 問題概要 個の整数からなる数列 が与えられる。これらの部分列であって、狭義単調増加であるもののうち、部分列の長さの最大値を求めよ。 制約 考えたこと LIS を求めよ、という問題。…

JOI 春合宿 2007 day1-1 Score (難易度 3)

まさに「座標圧縮」をしてください、という問題! ジャッジページへのリンク 問題文へのリンク 問題概要 個の整数 が与えられる。それぞれについて、「大きい順に何番目か」を求めよ。 たとえば に対しては、答えは となる。 制約 考えたこと 今回の問題のよ…

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

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

JOI 春合宿 2010 day1-1 JOI Poster (難易度 5)

めっちゃフラクタルな問題だ! ジャッジページへのリンク 問題文へのリンク 類題とか drken1215.hatenablog.com 問題概要 JOI のロゴは、下図のようになっている (問題文より)。 レベル のロゴは 1 × 1 のグリッドで "J" のみからなる レベル のロゴは、 の…

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 春合宿 2007 day4-1 Fiber (難易度 5)

無向グラフの連結成分の個数を数える問題 ジャッジへのリンク 問題へのリンク 問題概要 頂点数 、辺数 の無向グラフが与えられる。このグラフにいくつかの辺を新たに追加することによって、グラフ全体が連結となるようにしたい。 追加すべき辺の本数の最小値…

JOI 春合宿 2007 day4-2 Lines (難易度 9)

平面グラフの面の個数を考える系問題 ジャッジへのリンク 問題へのリンク 問題概要 二次元平面上に 本の直線が与えられる。これらの直線は、それらを通る 2 点の座標 ( と を通る) で与えられる。 これらの直線によって、平面全体が何個の領域に分割されるの…

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

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

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

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

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

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

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

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

JOI 春合宿 2011 day2-2 Keycards (難易度9)

包除原理と聞いて 問題へのリンク 問題概要 JOI の春合宿が行われる施設の宿泊棟の部屋の鍵は,カードに穴がいくつか開いた形状をしている.穴を開ける位置の候補は N 個あり,これらのうちいくつかに穴を開けた 2N 枚の異なる鍵が作られた. あなたは,JOI …