区間のk-th smallestが求められる謎データ構造 - 競技プログラミング+αなブログ
この記事は Competitive Programming Advent Calendar Div2013(http://partake.in/events/3a3bb090-1390-4b2a-b38b-4273bea4cc83) の16日目の記事です。 データ構造の話です。 地区予選の過去問を解いているときに、以下のような問題を見つけました。 【問題】 要素数Nの数列a(a[0],...,a[N-1])が与えられる。 以下の２種類からなるクエリがQ個与えられるので、それぞれ処理せよ。 ・Query1 l r k a[l],...,a[r-1]のk番目に小さい数は何か （1<=k<=r-l） ・Query2 l r x a[l],...,a[r-1]をソートしたとき、xは何番目か （x∈{a[l], ..., a[r]}） 【制約】 N<=10^5 Q<=10^5 0<=l 僕は解き方が
幾何での手抜き手法 - y_mazun’s blog
※この記事はCompetitive Programming Advent Calendar Div2012 の19日目の記事です。 競技プログラミングにおいて、時間内に正しい答えを出せる限り手を抜く(簡単なプログラムを書くの意)のが定石。 ということでとある問題を題材に探索っぽくして幾何で手を抜く方法でも紹介してみます。 問題 AOJ1093を題材にします。 詳しくは本家で読んでもらうとして概要はこんな感じ↓ N (≦ 100)個の点 p[i] = (x[i], y[i]) と速度 v[i] (0 ≦ i ≦ N - 1)が与えられます。 適当な座標を選び、(x[i], y[i]) に速度 v[i] で移動する時間の0 ≦ i ≦ N - 1での最大値を最小化する。 その時の最小値を出力しなさい。 解法 数学的な解法は私には思い浮かばないので、探索していくことにしましょう*1。 探索方法
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
