プログラミング練習問題で学ぶオンライン広告のしくみ

こんにちは。ソフトウェアエンジニアの hayasaka です。

弊社フライウィールのプロダクトの一つに、オンライン広告に関するプロダクトがあります。オンライン広告は、とても巨大で複雑なシステムです。今回は、オンライン広告のネットワークの仕組み、特に Real-Time Bidding（リアルタイムビッディング / リアルタイム入札、以後 RTB と略す）の仕組みをわかりやすい形で解説したいと思います。

とはいっても、単に解説を書くだけでは何もヒネりもありませんね。なので、RTBの仕組みを元にした、プログラミング練習用の問題を作ってみました。いわゆる競技プログラミング_（※1）やコーディング面接_（※2）における問題に近いものにしたつもりです。比較的易しいので、エンジニアの方はぜひ、ちょっとした息抜きにプログラムを書いてみてください。そうでない方も、問題そのものがRTBによるオンライン広告の仕組みの簡単な解説になっていますので、読み物として読んでいただければ幸いです。

（※1）競技プログラミング：与えられた問題を解くプログラムを、早く正確に記述することを競うもの
（※2）コーディング面接：面接官に与えられた問題を解くプログラムを、その場でコーディングするタイプの面接形式

以下問題文です。「だ・である調」の文章に切り変わっておりますのでご了承ください。

Problem: 広告ネットワーク

インターネット上で表示されるバナーなどのオンライン広告。そこでは、数百ミリ秒といったとても短い時間で、表示される広告が決定されている。この仕組みを、「SSP」「DSP」「RTB」というキーワードからみていくことにしよう。

SSP は、「Supply-Side Platform（サプライサイドプラットフォーム）」の略である。これはメディア、つまり「広告枠を売りたい側」のシステムである。別の言い方をすれば、広告枠を「供給＝サプライ」する側のプラットフォームということである。例えばあなたが、たくさんのアクセスがあるWebサイトを所有しているとしよう。あなたは、そこに広告バナーの枠を作り、そこに広告を載せる権利を売ることで収入を得ようと考えた。そこであなたは当然「できるだけ高い値段で広告枠を売りたい」と考えることだろう。それを実現するためのシステムが SSP である。

一方 DSP は、「Demand-Side Platform（デマンドサイドプラットフォーム）」の略である。これは広告主、つまり「広告を出したいと思っている側」のシステムである。別の言い方をすれば、広告枠を「要求＝デマンド」する側のプラットフォームということである。例えば、あなたがアプリの製作者であるとしよう。そしてあなたは、アプリを宣伝する広告を出すために、「できるだけ安い値段で、効果的な広告枠を買いたい」と考えたとしよう。それを実現するためのシステムが DSP である。

広告枠がユーザーに表示された時、「広告枠を高い値段で売りたい」SSPと、「広告枠を安く買いたい」DSPとの間で瞬時にオークションが行われ、表示される広告が決定される。この仕組みを「Real-Time Bidding（リアルタイムビッティング）」、略して RTB という。RTB は、以下のような流れで行われる。

ユーザーが広告枠があるページを訪問し、SSPが広告リクエストを受け取る
SSPがその広告枠をオークションにかける。すなわち、SSPに接続された複数のDSPに一斉に入札リクエストを送信する
各DSPは、入札するかしないか、入札するとしていくらにするかを決定し、SSPに入札レスポンスを返信する
SSPはDSPからのレスポンスのうち、最も入札価格が高いものを選択し、ユーザーに送信する
ユーザーに広告が表示される

図：RTBの動きの模式図。最も高い５０円をつけたDSPの広告が選ばれている。ただし、実際には入札価格はもっと小さな値である。

DSPは、広告枠やユーザーの情報と表示させたい広告の情報とを照らし合わせることで、入札するかしないか及び入札価格を決定する。簡単な例を挙げれば、同じユーザーに直近に何度も同じ広告を表示してもあまり意味がないことから、回数制限をかけて入札を止めることがある。これをフリークエンシーキャップと呼ぶ。また、入札に勝って広告が表示されたときは「広告枠を購入した」ということであるから、多くの回数広告が表示されて広告枠購入費の累計が予算を超過しそうな場合には、その時点で入札を停止する必要がある。

このように、複数のシステムが複雑に組み合わさってオンライン広告が動作しているが、これを簡略化した上でその動きをシミュレーションすることを考えよう。

まず、ある一つの SSP に対して、DSP が n 個接続されているとする。各DSPは表示すべき広告を一つだけ持っている。 i番目の DSP が持つ広告の ID を ad_i としたとき、その広告には固定の入札価格 bid_i、フリークエンシーキャップ fcap_i 及び累計表示回数制限 limit_i が設定されているとする。SSP は m個の入札リクエストを各 DSP に対して順番に送信する。j番目の入札リクエストは、広告ターゲットユーザーの固有 ID user_j 及び最低入札価格 price_j から構成されている。 i番目のDSPは、以下の条件が全て満たされる時に限り、そのリクエストに対し固定の入札価格 bid_i を用いて入札するとする。

固定の入札価格が、そのリクエストの最低入札価格以上であること。すなわち：
最低入札価格 price_j ≤ 固定の入札価格 bid_i
ユーザーに対して、まだ広告を出し過ぎていないこと。すなわち：
これまでにユーザーID user_j に広告 ad_i が表示された回数 < フリークエンシーキャップ fcap_i
これまでに広告が表示された回数が、累計の表示回数の制限に達していないこと。すなわち：
これまでに広告 ad_i が表示された回数 < 累計表示回数制限 limit_i

SSP は、入札された広告のうち、最も入札価格が高いものを選択し、その広告がターゲットユーザーに表示されるとする。この動きをシミュレートするプログラムを作成することが、この問題のゴールである。

Input

入力は複数のデータセットからなる。各データセットは次の形式で表される。

n m
ad₁ bid₁ fcap₁ limit₁
ad₂ bid₂ fcap₂ limit₂
…
ad_n bid_n fcap_n limit_n
user₁ price₁
user₂ price₂
…
user_m price_m

データセットの最初の行は、二つの整数 n と m からなる。 n はDSP の個数 (1 ≤ n ≤ 20)、 m は入札リクエストの個数 (1 ≤ m ≤ 100) である。

続く n 行のそれぞれには、各 DSP が持つ広告についての情報が与えられる。i行目には、i番目の DSP が持つ広告の情報として、広告ID ad_i （アルファベット大文字１文字）、固定の入札価格 bid_i (整数、1 ≤ bid_i ≤ 100)、フリークエンシーキャップ fcap_i (整数、1 ≤ fcap_i ≤ 100) 及び累計表示回数制限 limit_i (整数、1 ≤ limit_i ≤ 100) が空白区切で与えられる。なお、広告ID ad_i と入札価格 bid_i はユニークであることが保証される。

それに続く m 行のそれぞれには、各入札リクエストについての情報が与えられる。j行目には、j番目のリクエストの情報として、ユーザーID user_j （アルファベット小文字1文字）及び最低入札価格 price_j（整数、1 ≤ price_j ≤ 100）が空白区切で与えられる。

入力の終わりは二つのゼロからなる行で表される。データセットの個数は 10 を超えない。

Output

各データセットについて、与えられた DSP とリクエストから、選択される広告ID を並べた長さ m の文字列を一行に出力せよ。もしあるリクエストで入札が発生しない場合には、広告IDの代わりに “_” （アンダースコア）を出力せよ。

Sample Input

2 7
A 20 2 3
B 10 2 2
x 10
x 10
x 10
x 30
y 10
y 10
y 10
1 3
C 20 2 2
x 20
y 20
z 20
0 0

Sample Output

AAB_AB_
CC_

テスト用 Input

テスト用 Input は次のリンクから入手せよ（注意：Data URL で記述されており、クリックしただけでは遷移しないため、リンクを右クリックして「新しいタブで開く」あるいは「リンク先を保存」を選ぶ、といった操作をする必要がある）：テスト用Input

対応する正答 Output は用意されていない。しかしながら、もし出力が正しければ一見してわかるようになっている。