AtCoder Regular Contest 049 B - 高橋ノルム君
XとYは互いに干渉しないので、独立してX, Yを考えることができる。 \(x_i, x_{i+1}\)の間に最適な\(X\)があるとすると、\(X\)の位置を\(x_i, x_{i+1}\)を境界として三分探索で求めることができる。 これをすべての\(i\)について試行すればいい。
Posts
Your Coffee Shop Doesn't Use Two-Phase Commit(2005)
非同期処理を、スターバックスの注文からコーヒーの提供までの流れにたとえたアネクドートである。 注文をうけたレジの店員は、どの客の注文か分かる目印をコーヒーカップに書き、カップをエスプレッソマシンの上にならべる。 客はバリスタのいるカウンターに移動し、レジの店員は次の顧客の注文をうけつける。 バリスタは、ならべられたカップをとり、コーヒーを注ぎ、客に提供する。
レジの店員とバリスタは非同期にはたらいている。 バリスタのコーヒーの提供が滞っても、レジの店員は注文をうけることができる。 カップの列が長くなれば、バリスタの人数を増やせば、レジの店員に影響することなく、より速くコーヒーを提供できる。 それはキューで通信するプロデューサーとコンシューマーのようである。
抄訳 Indexing by Latent Semantic Analysis (1990)
特異値分解を応用した潜在的な意味にもとづく文書検索の手法である。 文書を、単語の出現回数が成分の列ベクトルとしてあつかう。 その列ベクトルからなる文書集合の行列に特異値分解(Singular Value Decomposition, SVD)を適用する。 大きい順に\(k\)個の特異値とその特異ベクトルを選んで、低ランクの行列をつくり、もとの行列を近似する。 単語の数が\(t\), 文書数が\(d\)のとき、低ランクの行列の左特異ベクトルの行列\(T\)と右特異ベクトルの転置行列\(D'\)のサイズは、それぞれ、\(t\times k\), \(k \times d\)になる。
ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging(1992)
ARIES(Algorithm for Recovery and Isolation Exploiting Semantics)は、ログ先行書き込み(write-ahead-logging, WAL)によるSAVEPOINTまでの部分的なトランザクションのロールバック、レコード単位のロック、回復のためのアルゴリズムである。 ログの対象と粒度はページの更新であり、レコードには単調増加するLSN(Log Sequence number)をわりあてる。 レコードは直前の更新のレコードへのポインタであるPrevLSNも含み、あるレコードから以前の更新のレコードへ遡行できる。
ロールバックやリスタート時の更新は、通常時の更新とは別に、保証ログレコード(compensation log record, CLR)に記録される。 ARIESのCLSに記録された更新はUNDOされない。 一方、IMS, AS/400, DB2のCLSは、あるトランザクションが何度もロールバックされると、対応するCLSの更新をUNDOすることがある。
Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections(1992)
Scatter/Gatherは、ユーザーにクエリを入力するかわりに、システムが提示する文書のクラスタをユーザーに選ばせる情報検索の手法である。 ユーザーが目的の情報にだどりつける適当なクエリをいつも作れるとはかぎらない。 ユーザーが詳しくない分野の情報を調べるときは、クエリにつかえる用語を知らないかもしれない。 また、ある分野の情報を広く浅く収集したいときは、クエリの単語によって検索対象を狭く限定したくないかもしれない。
AtCoder Regular Contest 028 B 特別賞
Pythonであればheap, C++であればsetを2つ使えばよい。 新しい要素を追加する度に、一方に上位kの要素、他方にk+1以降の要素があるように、2つのset, heap間で要素を交換する。 類似の問題をLeetCodeのHard modeで見かけたことがある。
Zookeeper: Wait-free coordination for Internet-scale systems (2010)
ZooKeeperは、リーダ選出と構成管理の機能を提供するためのインメモリーデータベースである。 データーベースは、ファイルシステムのような階層構造のwait-freeな抽象データ型であり、各ノードにはデフォルトで最大1MBの少量のデータを保存できる。 たとえば、ノードに設定を保存して共有することも、設定ファイルが編集中でないことを示すフラグ代わりのファイルを置くこともできる。
AtCoder Regular Contest 007 C - 節約生活
文字数を\(n\)とすると複数のテレビを組合せたときの視聴パターンの重ね方は\(2^n\)個ある。 最大文字数は整数型のビット数より数分の1しかないので、ビット操作ですべての重ね方を試行することを考える。 各重ね方について、パターンを十分に連結した値の論理和に最大文字数以上連続する1があれば、その試行は要件を満たす。
ARC 005C 器物損壊！高橋君
ダイクストラ法を使えば、スタート地点から各区画への最短距離を求められる。 塀に移動にかかる時間を十分に大きい値、かりに\(HM+1\)として、ダイクストラ法適用すると、 ゴール地点が\(3(HM+1)\)以下未満であり、そのときに限り、塀を壊す回数が2回以下でゴール地点に到達できる。
From RankNet to LambdaRank to LambdaMART: An Overview(2010)
LambdaMARTは、勾配ブースティング決定木(MART)の訓練に、RankNetとLambdaRankを応用したランキング学習である。 RankNetとLambdaRankを以前抄訳で解説した(RankNet, LambdaRank)。 RankNetは、名前にNetがついているが、RankNetの論文で提案されたものは、ネットワークアーキテクチャではなくランキング学習のための損失関数である。 入力されたベクトルをモデルが実数に写像することができれば、ニューラルネットワークでなくてもよい。 RankNetの学習は、モデルの出力する実数をスコアとみなし、あるクエリに該当する2つの事例のうち、より該当する事例に高いスコアを与えられるようにモデルを訓練する。 各訓練データはランキングの異なる2つの特徴とランキングの高い方を示すラベルであり、2つのスコアの差をシグモイドに与えたときの出力を、一方のサンプルが他方よりもランキングが高い確率とみなす。 そして、交差エントロピーが最小になるようにモデルを訓練する。 LambdaRankは、損失の計算を省き、スコアと損失の勾配で重みを更新することで、RankNetの学習を高速化する。 LambdaMARTは、RankNetに勾配ブースティング決定木を使い、残差の計算にLambdaRankを応用したランキング学習のモデルである。