いもす法 - いもす研 (imos laboratory)
いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています． いもす法の基本: 1 次元 0 次いもす法 最もシンプルな「いもす法」は 1 次元上に 0 次関数（矩形関数や階段関数などのように上部が平らな関数）を足すものです． 問題例 あなたは喫茶店を経営しています．あなたの喫茶店を訪れたそれぞれのお客さん i\ (0 \leq i \lt C) について入店時刻 S_i と出店時刻 E_i が与えられます（0 \leq S_i \lt E_i \leq T）．同時刻にお店にいた客の数の最大値 M はいくつでしょうか．ただし，同時刻に出店と入店がある場
貰う DP と配る DP、メモ化再帰、個数制限なしナップサック問題 - Qiita
はじめに ついこないだの AtCoder 上のコンテストで出題された問題 AtCoder Beginner Contest 099 C 問題 - Strange Bank が、初心者向けの 300 点問題としては史上最難ではないかということで話題沸騰になりました。 何も考えずに DP (動的計画法) した 辺の長さが 1 の DAG なので BFS でも DP でも Dijkstra でも OK 個数制限なしナップサック問題を復習しないと 全探索 + Greedy でやった といった色んな声が飛び交いました。動的計画法アルゴリズムの設計法などを具体的に学べるすごく教育的な問題だと思ったので、上記の事柄をまとめて整理することを試みます。それにしてもこの問題はコイン両替問題の 1 パターンとして位置付けられますが、色んな取り組み方ができますね。 ABC 099 C - Strange Bank
DPの話 - aizuzia
この記事は Competitive Programming Advent Calendar のために作成されました。 「DP (Dynamic Programminng: 動的計画法) がよく分からない」というつぶやきをよく目にします。何から何まで分からないというわけではないけど、 「こういうDPをすれば解けるよ」と説明されれば理解できるけど、一からそれを思い付けない メモ再帰だと書けるけどループだと書けない、またはその逆 とかいう。 この記事は、DPという技法をより深く理解する手助けをすることを目的として書かれています。これを読めばどんなDPの問題もさくさく解ける・・・ことはないと思いますが、あんまり悩まずに実装できるようになるぐらいの効果はあるんじゃないかなと思います。想定する読者層は、簡単なDPの問題をいくつか解いたことがある、TopCoderレーティング 1500 未満ぐらいの人と
プログラミングコンテストでのデータ構造
2. 内容 • Union-Find 木 • バケット法と平方分割 • セグメント木 • 共通点：自分で実装するデータ構造 • セグメント木が中心 – IOI でのセグメント木の出題が非常に多い
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ - Qiita
はじめに --- DP は役に立つ はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 巷ではよく「DP なんて実務では使わない」といった言説が定期的に流れますが、そんなことはないです。僕自身この 2 年間で DP が使える実務案件に 3 件くらい関わりました！ それはともかくとして、DP を学び立ての方がよく抱く悩みとして「バリエーションが多すぎて混乱するし、統一的なフレームワークがほしい」というのがあります。確かに DP のバリエーションは非常に多岐にわたるのですが、そのほとんどが以下の 3 つのフレームワークで説明できると思います: ナップサック DP 区間 DP bit DP 今回はこのうちのナップサック DP について、とにかく
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
