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

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

2020-12-22から1日間の記事一覧

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

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

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 本選 2007 A - 最大の和 (AOJ 0516, 難易度 4)

累積和ですぐ!! ジャッジへのリンク 問題文へのリンク 問題概要 個の整数からなる数列 と、整数 が与えられる。 数列から連続する 個の値を選んで総和をとる。この総和として考えられる最大値を求めよ。 制約 考えたこと 「数列の連続する部分の総和」は累…

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

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