2019-10-30

ABC 144 F - Fork in the Road

解説を読みつつRubyだとTLEなのかな。とおもいつつclimpetさんがACしていて、コードゴルフじゃないC++のコードがあったので、そちらから読み解いてみた。

各頂点毎に辺を一つ潰したときと一つも潰さないときの1 -> Nへの期待パス長への差分の最小値を求めていて、差分を求めるために各頂点への遷移確率を使っていた。
時間計算量はO(M)で解いているっぽい。

元のグラフをG, 潰す辺 e = {s,t}、辺を一つ潰したグラフを G - e,
グラフ H上の i -> Nへの期待パス長を返す関数をf(H,i), 同じくグラフH上の1 -> sへの遷移確率をg(H,s)とすると下記の式で書けることになる。

f(G - e,1) = f(G,1) - g(G,s) * f(G,s) + g(G,s) * f(G - e, s)

期待パス長が $\sum_{p \in P} |p| / |P|$ (Pは1 -> Nへのパスの集合)になるので、sを通るパス集合と通らないパス集合に分けて考える。
sを通るパス集合のs以降の部分のみ、期待パス長に変化があるため、G上のs->Nへの期待パス長 * sへの遷移確率を引いて、G-e上のs->Nへの期待パス長 * sへの遷移確率を足すことで求まる。
sへの遷移確率はG,G-eも同じなので前処理でやはりO(M)で計算できる

それを踏まえた書いたコードが以下のリンク

atcoder.jp

2019-10-03

ABC142 F - Pure

atcoder.jp

誘導部分グラフが閉路になっているような頂点集合を求める問題、解説通りに実装してみた。コンテスト中は閉路からより小さい閉路ってどうやんの？だけど、解説見るとなるほど!だった。

閉路を検出して、その誘導部分グラフ内の閉路として使われていない辺を見つけて、それを使った経路検出をするとより小さな閉路が求められる。

atcoder.jp

ほとんどRubyで書いているけど、DFSを再帰関数で書いて、スタックオーバーフローさせることが結構あったのでstack使ったループになれないといけないなとはおもっていてちょうどよかった。

DFSでの経路復元がスタックからACTIVEなものを取り出すだけでできるので再帰のDFSより簡単だなという感じもする。
閉路復元も閉路検出時の辺をもとに経路から前方部分を削除すればよいので楽にできた。

N,M = gets.split.map(&:to_i)
G = Array.new(N + 1){ [] }
E = M.times.map{ gets.split.map(&:to_i) }
E.each do |from,to|
  G[from] << to
end

ACTIVE = Array.new(N + 1)
USED = Array.new(N + 1)
SUBGRAPH = Array.new(N + 1)

def active?(v); ACTIVE[v]; end
def activate!(v);  ACTIVE[v] = true; end
def inactivate!(v); ACTIVE[v] = false; end
def used?(v); USED[v]; end
def use!(v); USED[v] = true; end
def subgraph_include?(v); SUBGRAPH[v]; end
def subgraph_init!(vset)
  ACTIVE.fill(false)
  USED.fill(true)
  SUBGRAPH.fill(false)
  vset.each{|v| USED[v] = false; SUBGRAPH[v] = true }
end
  
def cycle_exists?
  (1 .. N).each do |s|
    next if used?(s)
    
    stack = [s]; use!(s)
    cycle = find_cycle(stack)
    return cycle if cycle
  end
  return false
end

def smaller_cycle?(cycle)
  subgraph_init!(cycle)
  
  stack = nil
  smaller_not_found = cycle.each_with_index.none? do |from, i|
    to = (i + 1 == cycle.size ? cycle[0] : cycle[i + 1])
    to_ = G[from].find{|to_| subgraph_include?(to_) && to_ != to }
    stack = [from, to_] if to_
  end
  return false if smaller_not_found

  use!(stack[0])
  use!(stack[1])
  activate!(stack[0])

  find_cycle(stack)
end

def find_cycle(stack)
  until stack.empty?
    u = stack.pop
    
    if active?(u)
      inactivate!(u)
      next
    else
      activate!(u)
      stack << u
    end
    
    G[u].each do |v|
      return stack.select{|r| active?(r) }.drop_while{|r| r != v } if active?(v)
      next if used?(v)
      use!(v)
      stack << v
    end
  end
  false
end

cycle = cycle_exists?
if !cycle
  puts -1
else
  loop do
    smaller = smaller_cycle?(cycle)
    if smaller  
      cycle = smaller
    else
      break
    end
  end
  puts cycle.size
  puts cycle
end

2019-08-19

ABC137 D - Summer Vacation

D - Summer Vacation

解説(別解のマトロイドのほう)を読みながら、UnionFind木の構造を少し変えると、うまく解けそうとおもったら解けたので記念に貼っておく。

解説では以下のようにセグメント木を使う説明だったけど、セグメント木とかつかわず、もうすこし簡単にやりたいとおもって考えていた。

すなわち、上の手順 2 は、M 日後から x 日前よりも以前であって、まだどの日雇いアルバイトも割り当て
られていない日のうち最も遅い日が高速に求まれば高速に判定できます。これは、区間の最大値を求められ、
一点更新が可能なセグメント木を使えば、S に対する割り当ての情報を保持しながら y に対して O(logM)
で判定できるため、ソートも合わせて全体として O(NlogN + NlogM) で解くことができます。

APIとしてはJavaのBitset#nextClearBitが高速ならよいのだよなとおもって考えていたら、UnionFind木の要領でビットが連続して立っている区間の終端を管理/更新しておけばよいのだよなと気づいた。
UnionFInd木でunion(a,b)するのをunion(a,a+1)に限定するイメージでできたコードがこれ。

N, M = gets.split.map(&:to_i)
S = N.times.map { gets.split.map(&:to_i) }.sort_by{|v| -v[1] }
bitset = Array.new(M + 1, &:itself) # a variant of Union Find Tree.

class << bitset
  def next_clear_bit(base)
    return size if base >= size
    return base if self[base] == base
    self[base] = next_clear_bit(self[base])
  end
  
  def extend_trailing_set_bits(base)
    r = next_clear_bit(base)
    return nil if r >= size
    self[r] = next_clear_bit(r + 1)
    r
  end
end

puts S.inject(0){|s, (a, b)| 
  bitset.extend_trailing_set_bits(a) ? s + b : s 
}

これでたぶん計算量としては N log N + N α(M) になる。(αはアッカーマン関数)

このデータ構造は実装も簡単だし、重複のない区間を併合するみたいな感じっぽいので、もしかしたら使いどころが結構あるかもしれないとおもった。

また2部グラフの最小(最大)コストマッチングが下記条件を満たす場合はこのアルゴリズムでできるってことだと思うのでメモ

2部グラフ $G \left( U \cup V, E \right)$ は頂点集合U（今回はアルバイト) , V(今回は日付)と辺集合E (マッチング候補)からなる
Uは重みによりソート可能
Vは $\{ 1 \dots |V| \}$ に対して、全単射でUから見たマッチングの優先度もこれに従う
Uの任意の点uを終端とする辺の集合 $E_u \subset E$ が、 $\exists d \in \mathbb{N}$ に割り当て可能(今回はuの報酬の受取日でVをマッチング可能、不可能に分割できる)

atcoder.jp

2019-03-15

gradle-swagger-generator-pluginにOpenAPI Generator対応のPRがマージされた

OpenAPI / Swagger関連の勉強をしていて、gradle-swagger-generator-pluginを見つけました。

gradle-swagger-generator-pluginはOpenAPI文書から、Swagger UI, ReDocなどのHTMLやコード生成を行ってくれます。

コード生成の有名どころだとswagger-code-genとopenapi-generatorが、OpenAPI文書からコード生成をしてくれます。
gradle-swagger-generator-pluginでは、コード生成はバックエンドとして、swagger-code-genのCLIを使用しています。

openapi-generatorはもともとはswagger-code-genからフォークしたものらしいのですが、
機能としてはswagger-code-genにはバリデーションがないけれど、openapi-generatorにはバリデーションがあるという状況で、
gradle-swagger-generator-pluginは独自にJSON Schemaを使用したバリデーションも提供しています。

ただし、OpenAPI 3.0のほうのバリデーションは行ってくれません。これはまだOpenAPI 3.0のスキーマファイルは作業中だからだそうです。

いろいろ試した結果、gradle-swagger-generator-pluginのほうが、DSLが私の好みだったが、バックエンドとしてはopenapi-generatorが使いたいという状況だったので、
コード生成にOpenAPI Generatorを使用する変更を行ってPRしていました。

github.com

無事マージされてよかったです。

下記のような学びがあって、やってよかったなと思います。

gradle自体の理解 / これまでも使ってはいましたが、汎用ビルドシステムとしての理解は深まっていませんでした。Project / Task / Artifact / Dependencyなどの概念がだいぶ頭に入ってきました。
gradleプラグインの作り方 / Gradleにおけるプラグインとは何か? またGradle Test Kitの存在をしりました。
Groovyのテストフレームワーク Spock / パラメータの違うテストを一つにまとめるのは本当に便利でした。やってみると「おなじテストを複数回実行する」から見るSpockのUnrollの世界 - Qiitaがすごく実感できます。
OpenAPIの仕様や議論/問題点などの把握 / OpenAPI 3.0はXMLを返すAPIのスキーマ(Relax NGやXML Scheme)なども実は議論のなかにあるということを知りました。その辺いらないよとは思います。
GitHubのPRの実際 / これまでは自身のリポジトリにPRから自己解決マージするみたいのをやっていましたが、初めてPRしたのでやっぱりいろいろ戸惑いました。下記2つの記事は読んでおくべきです。

hnw.hatenablog.com
stackoverflow.com

2018-10-17

グラフの密度

k-coreが気になるのでDensity-friendly graph decomposition ( https://users.ics.aalto.fi/gionis/friendly.pdf )を読む。超訳

Abstract

最新のグラフマイニングツールでは、k-core分析によりグラフを階層構造に分解するのは標準的な操作です。

k-core分解は次数の分布によってグラフを分析する、単純ですが効率的な方法です。
中心にむかって連結性が増加するように、グラフ内の領域を識別し、構成を明らかにします。

k-core分析は頂点の次数に依存しますが、k-coreは自然な密度特性を満たしません。簡単に言えば、最も中央のk-coreが、必ずしも最も密度の高いサブグラフであるとは限りません。
k-coreとグラフの密度のこの不一致が我々の研究の土台です。

サブグラフが局所的に密集している(locally-dense)ということを定義することから始め、私たちの定義にはk-coreと同様にグラフのネストされたチェーン分解が必要であることを示します。
この分解の結果、密度が増加する順に構成されます。

グラフ G=(V,E)に対するこのような局所的に密な分解は多項式時間で計算できることを示します。
正確な分解アルゴリズムの実行時間はO(|V|^2|E|)ですが、実際にはかなり速い。さらに、局所的に最適な最適分解に第2因子近似を提供する線形アルゴリズムも開発しました。
またk-core分解が第2因子近似であることを示します。

しかし、我々の実験評価によって示されるように、実際にはk-coreは局所的に密なサブグラフとは構造が異なり、理論によって予測されるように、k-coreは必ずしもグラフ密度とよく一致するとは限りません。

INTRODUCTION

高密度サブグラフとコミュニティを見つけることは、グラフマイニングで最もよく研究されている問題の1つです。
高密度サブグラフを識別する技術は、生物学からウェブマイニング、社会および情報ネットワークの分析まで多数の応用分野で使用されている。
高密度サブグラフを発見するために提案された多くの概念の中でk-coreは、その定義の単純さと線形時間で識別できるために特に魅力的です。

グラフのk-coreは、すべての頂点がそのサブグラフ内の少なくともk個の他の頂点に接続されている最大部分グラフとして定義されます。
k-core分解は、サブグラフのネストされたシーケンスを形成するという素晴らしい特性があり、グラフを分析するのに有用なツールになります。

グラフのk-core分解が、内側コアの頂点の度数が高いサブグラフの連鎖を与えるという事実は、内側コアが特定の意味では、外側コアよりも密度が高く接続されていることを期待させますが、この記述は真実ではありません。この論文では上記が真である、すなわち分解の内側の部分グラフが外側のグラフよりも密度が高いグラフ分解を得る方法を示します。

密度を定量化するために、densest-subgraph問題で使用される古典的な概念を採用します。密度は、サブグラフのエッジと頂点の比として定義されます。
この密度の定義は、平均次数を2で割ったものとして見ることもできます。

我々の動機づけは、この密度の定義に従ってk-coreが順序付けされていないことである。
次の例は、最も内側のコアが必ずしも最も密なサブグラフではないことを示しています。実際、頂点を追加または削除することで密度を上げることができます。

例1 6つの頂点と9つの辺からなる図1のグラフG1(画像は略)　を考えてみましょう。
グラフ全体の密度は9/6 = 1.5です。
このグラフには、3つのkコアがあります。C1としてマークされた3コア、C2としてマークされた2コア、および1コアであり、グラフ全体に対応し、C3としてマークされています。
コアC1は密度6/4 = 1.5（6つのエッジと4つの頂点を含む）を有し、コアC2は密度8/5 = 1.6（8つのエッジと5つの頂点を含む）を有する。
言い換えれば、C1は内部コアであるにもかかわらずC2よりも密度が低い。

図1に示すG2(画像は略)について考えてみましょう。

このグラフには、単一のコア、つまり2コアがあり、グラフ全体が含まれています。
このコアの密度は11/8 = 1.375に等しい。しかし、サブグラフB1は7つのエッジと5つの頂点を含み、密度7/5 = 1.4を与え、これは唯一のコアの密度よりも高い。
この例では、より密度の高い代替のグラフ分解を定義するよう動機づけています。このグラフような分解を局所的分解と呼びます。

私たちは次を満たすような分解に興味があります。
（i）内側サブグラフの密度が外側サブグラフの密度よりも高く、
（ii）最も内側のサブグラフは最も細いサブグラフに対応し、
（iii）分解を効率的に計算または近似することができる。

局所的に密集した部分グラフを定義することで目標を達成します。本質的には、頂点を追加したり削除して密度を上げることはできません。
これらの部分グラフは、外側の部分グラフに行くにつれて密度が減少し、最も内側の部分グラフが実際には最も細い部分グラフであるような階層に配置されることを示す。
この階層を発見するための2つの効率的なアルゴリズムを提供します。

最初のアルゴリズムは、Goldberg [15]によって与えられた最も密なサブグラフを発見するための正確なアルゴリズムを拡張する。
このアルゴリズムは、パラメータαに依存する特定のグラフ上の最小カット問題を解くことに基づいている。
Goldbergは、ある値α（バイナリサーチで見つかる）に対して、最小カットは最も細いサブグラフを回復することを示した。
我々の貢献の1つは、ゴールドバーグのアルゴリズムをより明らかにし、同様の構成がαを変化させることによってすべての局所的に密な部分グラフを発見することを可能にすることである。

我々の第2のアルゴリズムは、密集した部分グラフを近似するためのCharikarによる線形時間アルゴリズムを拡張する[13]。
このアルゴリズムは、最初に最小次数の頂点を繰り返し削除することによって頂点を順序付けし、次にその順序を考慮して最も細いサブグラフを選択する。
この考え方は、同じ順序を使用して、順序を考慮した最初の最も細いサブグラフを見つけ、最初のサブグラフを含む2番目に細かいサブグラフを繰り返し検索するなどして拡張します。
このアルゴリズムは線形時間で実行可能であり、第2因子近似保証を達成することを示す。

Charikarのアルゴリズムとk-core分解を発見するためのアルゴリズムは非常に似ています。それらは両方とも、最小次数の頂点を削除することによって頂点を順序付けます。この接続が深いことを示し、k-core分解が局所的に密な分解のための第2因子近似を提供することを示す。

一方、実際にはk-coreは局所的に密なサブグラフとは構造が異なり、k-coreは必ずしもグラフ密度とよく一致するとは限らないことを理論的に示します。

論文の残りは次のように編成されている。第2節では予備的表記法を用いる。
3章で局所的な部分グラフを紹介し、セクション4の部分グラフを発見するための現在のアルゴリズム、セクション5のkコア分解への接続について説明します。
6章で関連する作業を提示し、7章で実験を提示する。最後に、8章で議論した論文を締めくくる。

2018-04-26

Git LFSは別にリポジトリサーバー側で対応が必要なわけではなくて、LFSサーバーが必要なだけ

GitHubやbitbucketのLFS対応もなんかストレージの料金がすごい高いなぁとおもっていて、リポジトリをホストするサーバーで対応が必要とおもっていたのですが、調べてみるとどうやら違うようでした。

ydkk.hateblo.jp

LFSサーバーをAWS Lambdaに構築して、S3をストレージにする実装

仕組みとしてはLFS サーバーとして、ラージファイルを保存した/保存できるURLを提供する。
git lfsのコマンドがpull / pushの時にLFSサーバーと連携して、オブジェクト(LFS track対象のファイル)をLFSサーバーが返すURLにGET / PUTするという仕組みでした。

他にもLFSサーバーと連携しないstandalone transfer agentの仕組みなどがあるようです。
https://github.com/git-lfs/git-lfs/blob/master/docs/custom-transfers.md

LFSサーバーなしでS3をストレージにする実装としては、下記のようなものがありました。
github.com

なんか不思議な感じです。

GitHubやbitbucketもAPI トークンを登録するとか、AzureのBlog StorageのSAS トークンを登録することで、クラウド上で提供されているストレージをLFSのバックエンドとして使わせるとかできるはずなのになんでしないんだろうという感じです。
みんながほしいソリューションはそっちじゃなかろうかとおもうのです。

2018-04-11

TCP over websocket

仕事の関係でKeycloakとその下回りであるJBoss/WildFlyを調べていて面白い記事を見つけました。

https://nekop.hatenablog.com/entry/20131220/1387524669

EJB呼び出しなどは以前はRMI/IIOPのようなTCP/IP上のプロトコルを使っていたが、いまはWebSocket上で行っている(TCP over WebSocket)という記事です。これはWildFly8の頃で、現在の12ではまた別のプロトコルに代わっています。

これと並行してKeycloakでWebSocketを保護できるという話を見つけました。

https://github.com/windup/windup-keycloak-websocket-auth/tree/master/websocket-api

OAuth2のアクセストークンの期限切れをwebsocketに反映させるとかはできないけど、認証だけならアダプタ入れるだけでできるよという話です。
プロトコル的にはまずHTTP 1.1 GETと一緒にUpgrade要求をするので、その間にOAuth2の認可フローを差し込めるというのがプロトコル上の理解です。

上記のような話題からウェブサーバーとしてOpenID connect / OAuth2などと連携するVPN/トンネリング製品ができるなとおもっていたのですが、https://kaazing.com/ というのがまさにそういう製品のようです。

chisel(https://github.com/jpillora/chisel)というgoで作られた、やはり同様のOSSがあったのですが、保護までしてくれないようだったのですが、chiselもApacheのmod_wstunnel / mod_auth_openidcとかと組み合わせればいけそうな気がします。

すこしこのあたりに興味がわいてきました。