サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
会話術
y-mazun.hatenablog.com
※この記事は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。 探索方法
(※この記事はCompetitive Programming Advent Calendar 3日目用の記事です) 「競技プログラミングで利用できそう」なC++のSTLをまとめたいと思います。 すべてを網羅するのではなく、独断と偏見で使えそうなものだけピックアップしています。 またコンテナ系はスキップし、Algorithmを中心にまとめます。 見出しがそのままヘッダの名前になっています。 algorithm find ある値を探すときに使う。イテレータが帰ってくる。 // v = { 1, 2, 3, 4, 5 } find(v.begin(), v.end(), 3); // v.begin() + 2 find(v.begin(), v.end(), 7); // v.end() count 個数を数える。 // v = { 1, 2, 1, 3, 2 } count(v.begin(
このページを最初にブックマークしてみませんか?
『y_mazun’s blog』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く