スキル棚卸し:2021年度 冬

前回の記事はこちら。 katoufujibanana.hatenadiary.jp

この記事は、定期的に「今、自分が(システム開発で)どんなことができるかなー」というのを整理するための、完全に自分のための記事です。赤文字のところが今回の追加分、青文字のところが前回の記事から記載を省略した箇所です。

経歴

  • 都内 SIer(多分)の新卒5年目。もうすぐ6年目。
  • 設計と開発とテストと保守改善と、顧客折衝の経験あり。開発の比重重め。
    • 裏を返すと、要件定義が未経験。ただ、今はスクラムが流行りなのもあり、超小規模要件定義 → 超小規模開発 → 超小規模保守・改善、みたいな流れは経験あり。これを要件定義に数えてよいのかは悩ましいところ。

仕事で関わったシステム

  • ぜんぶ Web アプリ。サーバー立てて、ブラウザ開いてアクセスして、みたいな。
    • 業務的な特徴は、守秘義務などあるので触れない方向で。(ドメイン知識の話ができない!) 細かいアーキ構成も、身バレの危険性があるので触れない方向で。

趣味で作ったシステム

  • マーケット情報収集サーバー
    • 株などの情報を収集して保存する。HTTP リクエストを叩くと、収集したデータを取得できる。収集しているデータは以下の通り。
    • Google Apps Script にて実装。
      • データの永続化先は Google Spread Sheet。
  • 投資系数値計算 API サーバー
    • 今乗っている機能はこんな感じ
    • Node.js 製。Web サーバーを Express で立てて、数値(主に行列)計算は math.js を使用。
    • Heroku 上で稼働中。
  • ボラティリティスマイル表示アプリ → 日経225オプション価格リスク管理アプリ
    • 日経225オプションのボラティリティスマイルを表示する。取得できるデータの都合上、20分ディレイのデータを使用している。
    • Heston モデル、Cogarch モデル、Vasicek モデルのパラメータを表示する。
    • 保有するポジションの、グリークスと、マーケット変動時の P/L を表示するアプリ。ポジションの登録・更新機能もあり。
    • 日次の日経225の価格、値動き、RV、VI を表形式で表示する。
    • サーバー側は Express、クライアントは React を使用。
    • Heroku 上で稼働中。
  • 最適ポートフォリオ計算サーバー
    • マーケット情報収集サーバーから情報を取得して、投資系数値計算 API サーバーにデータを投げて、投資対象の商品の中から最適ポートフォリオを計算する。
    • Python 製。Gunicorn + Flask でサーバーを構築。GUI は無し。
    • Heroku 上で稼働中。
  • 競馬予想サーバー
    • 過去のレース結果から、次のレース結果の予想を出したり、予想結果をもとに期待リターンと分散がいい感じになる馬券の買い方を計算したりすることができる。
      • 馬券の買い方最適化は、複勝は Scipy の optimize を使用。
      • 複勝以外は、アルゴリズムを自作し Rust(PyO3)で実装したモジュールで。計算している。
    • Python 製。Gunicorn + Flask でサーバーを構築。
    • Heroku 上で稼働中。
    • 計算過程の微調整ができるようにするために、UI が必要かなと最近感じている。

経験言語とフレームワーク

  • Python(業務・趣味含めた経験年数:4年
    • Flask
      • jinja テンプレートを使う場合も、API サーバーとして立てて SPA が API を叩きに行く場合もあり。
    • dataset
    • SQLAlchemy
    • numpy
      • ほんの少しだけ使った程度。競プロとかに使えているレベルではないです。
    • Scipy
      • numpy と同じく、少しだけ触ったレベル。
    • Selenium witn Python
    • Beatiful Soup 4
    • uWSGI(Pythonフレームワークかというと、厳密には違うような気もしますが)
    • Gunicorn (同上)
  • JavaScript(業務・趣味含めた経験年数:4年
    • フロントエンド
      • React(業務では、まだ Hook がなかったころのものを。趣味では v16 以降も)
      • MobX
      • Redux
      • Ant Design
      • Blueprint(趣味開発にて)
      • jest
    • サーバーサイド(Node.js)
      • Express
      • Sequelize
        • デフォルト設定のままでは使用感に癖があるなという印象でした。カスタマイズすることができるので PJ に合わせて手を入れるとき吉かも?
      • jest
  • SCSS(業務・趣味含めた経験年数:4年
    • bootstrap.js
  • シェルスクリプト(業務・趣味含めた経験年数:3年)
    • よくよく考えたら、シェルも使ったことありましたね。
  • Java(業務での経験年数:1年
    • Spring Boot と Spring(これさえあれば、全部揃うといっても過言ではない)
    • JUnit
  • Rust(趣味での経験年数:9か月)
    • PyO3(Python 用の so ファイルや pyd ファイルを作れるライブラリ)
    • wasm-bindgen(wasm を作れるライブラリ)
  • HTML(業務・趣味含めた経験年数:?)
    • これは開発言語なんですかね? ベタで書くこともなく、ほぼほぼテンプレートエンジンに値をはめに行くとかなので、素の HTML を書くことはほぼないかも。

使用経験のあるミドルウェア

システム稼働環境

  • 業務では、AWS かユーザー企業様のオンプレ環境
    • ただし、AWS については社内インフラ部門みたいなのがいて、彼らに作ってもらったので、構築などは未経験。さらに EC2 立ててそこに置くみたいな使い方だったので、サーバーレスも未経験。趣味で少しだけ AWS Lambda に触れた程度です。
  • 趣味では Heroku, Google Apps Script

開発支援ツール

  • バージョン管理
  • CI/CD
    • GitLab CI/CD(趣味開発にて)
    • clasp(趣味開発にて)
  • タスク管理
    • JIRA
    • エクセル(業務にて)
    • txt ファイル(趣味開発にて)
  • ノーコード開発ツール
    • Adalo(趣味開発にて)
      • まるでこだわりのない CRUD アプリみたいなのならこれで十分ですね。

Tips:Σ[r=0...A] nCr を、n = 0, 1, ..., N で求める

元ネタはこちら。

atcoder.jp

写像12相からの包除原理とかいう、そこそこゴツめな知識を要求した後に、

 \displaystyle{\sum^{A}_{r=0} \ _n C_r,\ \sum^{A}_{r=0} \ _{n-1} C_r,\ \dots,\ \sum^{A}_{r=0} \ _A C_r}

をすべて求めることを要求されます。
実際には、 \ _{A-1}C_r, \ _{A-2}C_r, \dots の場合の総和も求める必要がありますが、 n \lt r の場合の  \ _{n}C_{r} 0 であるとすれば、総和は  2^{A-1}, 2^{A-2}, \dotsとなるので割愛です。

さて、素朴に  \displaystyle{\sum^{A}_{r=0} \ _n C_r} を求めようとすると、 \ _n C_r = \ _n C_{r-1} \times \frac{n + 1 - r}{r},\ _n C_0 = 1 を使って  O(A) で解くことができます。

これが  N - A + 1 個あるので、全体の計算量は  O(A(N-A+1)) になります。すくなくとも今回の制約ですと、最悪  2.5 \times 10^{13} 回程度の計算が必要となってしまいます。


それが解説曰く「 O(N) で計算できます」というので以下つらつら。

公式解説ではグリッドによる表現を用いていますが、当記事では漸化式的な説明をしようかと思います。

 \ _n C_r には  \ _n C_r = \ _{n-1} C_{r} + \ _{n-1} C_{r-1} が成り立ちます。ただし、便宜上  r \lt 0 の場合   \ _{n} C_{r} = 0 とします。

すると、 \displaystyle{\sum^{A}_{r=0} \ _n C_r = \sum^{A}_{r=0} \ _{n-1} C_r + \sum^{A}_{r=0} \ _{n-1} C_{r-1}} となります。

  \ _{n} C_{-1} = 0 であることに注意すると、
 \displaystyle{\sum^{A}_{r=0} \ _{n-1} C_{r-1} = \sum^{A-1}_{r=0} \ _{n-1} C_{r} = \sum^{A}_{r=0} \ _{n-1} C_{r} - \ _{n-1} C_{A} } となるため、
 \displaystyle{\sum^{A}_{r=0} \ _n C_r = 2 \times \sum^{A}_{r=0} \ _{n-1} C_r - \ _{n-1} C_{A}} となります。

なので、事前に
  \ _{A} C_{A}, \ _{A+1} C_{A},\ \dots , \ _{n-1} C_{A} と、
 \displaystyle{\sum^{A}_{r=0} \ _{A}C_r} を求めておくことで漸化式的に解いていくことができます。

DP:桁 DP

練習問題としてはこことか、こことか。

atcoder.jp

atcoder.jp


一般に桁 DP でぐぐると、「桁を一個一個みていく DP だよ!」みたいな記事を見かけがちですが、冒頭の問題のように「 N 以下の」といった条件がある場合、文面通り桁だけ見ていくと条件を満たしているかどうか判定するの難しくないですか?

と思っていたら、比較的シンプルでわかりやすい解き方があったので、Python 化しました。解き方の元ネタは、2つ目の方の問題の解説記事です。ありがたや...。

# n: 桁数 + 1
# s: 状態数
# m: 探索対象の値の最大値
# m_str: str(m)

dp = [
    [[0] * s for _  in range(2)]
    for _ 
    in range(n)
]
# dp[i][j][k]
# i: 上から i 桁目まで桁を確定した(i 桁目の i は 1-indexed に注意)
# j: m 以下であることが確定しているかどうか(1 の場合、m 以下であることが確定)
# k: 状態
dp[0][0][0] = 1

for i in range(n):
    for j in range(2):
        for k in range(s):
            mi = int(m_str[i])
            for x in range(10):
                # 問題の指定に従い i, k, x から next_s 求める
                # ここは問題ごとに書き換え。
                next_s = (i + k + x) % s 
                if x < mi:
                    dp[i + 1][1][next_s] += dp[i][j][k]
                elif x == mi:
                    dp[i + 1][j][next_s] += dp[i][j][k]
                else:
                    if j == 1:
                        dp[i + 1][j][next_s] += dp[i][j][k]


どんな原理で動いているかというと、最後の  x \lt m_{i} のあたりの分岐が鍵です。

  •  x \lt m_{i} の場合
    •  m 以下になることが確定するので、遷移先の  j はどちらも  1 (= m 以下で確定)になる。
  •  x = m_{i} の場合
    • すでに  m 以下であることが確定済みならばそのまま  m 以下が確定。
    • 逆にそうでなければ  m 以下かどうか確定しないので、遷移先は同じく  m 以下が確定していない方(つまり  j = 0 の方)へ。
  •  x \gt m_{i} の場合
    • すでに  m 以下であることが確定済みならば、 x \gt m_{i} でも全体としては  m 以下であることは確定したままなので、 j=1 の方で遷移。
    • 逆に未確定であるときに、 x \gt m_{i} であるような  x を選ぶと、 m より大きくなることが確定するので考慮不要となるので捨てる。

あとは、最後に dp[N] の値をいい感じに変換したものを出力すれば大丈夫のはずです。全桁で 0 を選んだ場合を取り除かないといけなかったりするので、そこにはご注意ください。

Tips:k 種類の文字をそれぞれ最大 n1, n2, ..., nk 個使って並び替えてできる文字列の個数数え上げ

元ネタはこちらの問題です。

atcoder.jp


問題とにらめっこしていると、以下のように読み替えることができます。

 k 種類の文字  c_{1}, c_{2}, \dots, c_{k} が存在する。
このとき、以下の条件をすべて満たす文字列  S の個数を数え上げよ。
 S は空文字列ではない。
 S c_{1}, c_{2}, \dots, c_{k} 以外の文字を含まない。
 S に含まれる  c_{i} の個数は、高々  n_{i} 個である。※  i \in \{1,2, \dots k \}

これもにらめっこしていると、以下の式で求められることがわかります。

 \displaystyle{\sum^{n_{1}}_{j_1 = 0} \sum^{n_{2}}_{j_2 = 0} \dots \sum^{n_{k}}_{j_k = 0}} \frac{(j_{1} + j_{2} + \dots + j_{k})!}{j_{1}! \ j_{2}! \dots j_{k}!} \ - 1

愚直に全通り計算しようとすると、 (n_{1} + 1) \times (n_{2} + 1) \times \dots \times (n_{k} + 1) 回の計算が必要になります。冒頭の問題ですと  n_{1} + n_{2} + \dots + n_{k} \leq 5000,  k \leq 26 のため、最大  2.42 \times 10^{59} 回程度の計算が必要になりそうです。たぶん。

で、これをさらににらみ続けたり、解説を読んだりすると dp を使って計算量が減らせることがわかります。減らした後の計算回数は   \displaystyle{\sum^{k}_{i = 1} (n_{i} \times \sum^{i}_{j = 1} n_{j} )} 回です。   \displaystyle{\sum^{k}_{i = 1} (n_{i} \times \sum^{i}_{j = 1} n_{j} )} \leq \displaystyle{\sum^{k}_{i = 1} (n_{i} \times \sum^{k}_{j = 1} n_{j} )} なので  5000 \times 5000 で上から抑えられます。

わりと、今後も登場してきそうな形の式に思えるので、覚えておいて損はないかもしれません。

Tips:順列を引数にとり、返り値が自然数な関数の最大値・最小値を求める

元ネタはこちらです。

atcoder.jp

↑ のページにもありますが、こういった問題でも使えるテクニックとのこと。

E - Permutation

E - Traveling Salesman among Aerial Cities


さて、考えたい問題は以下のような問題です。

ある自然数  n が存在し、 (1,2,3,4, \dots, n) を並び替えた順列すべてを要素に持つ集合を  P とする。
このとき、関数  f \colon P \rightarrow \mathbb{N} が与えられるので、 max(\{f(p) | p \in P \}) を求めよ。

 max min になったりするバリエーションもあります。

 P の要素数 N! なので、素直にすべての値を求めて最大値・最小値を求めると、計算量が  O(N!) になってしまいます。 N=10, 11 くらいが限界ですね。


運がいいと  O(2^{N}) 程度に計算量を減らせるというのが本記事 & 元ネタの内容です。

以下が成り立つとき、計算量を減らすことができます。
ちょっと準備のため色々記号を用意しますが、お付き合いください。

  • ある列  p に対し  p[\colon i] を「 p の先頭から  i 番目までの要素だけの列」とします。

    •  p = (1, 4, 2, 8, 5, 7) のとき、
    •  p[\colon 0] = ()
    •  p[\colon 1] = (1)
    •  p[\colon 2] = (1, 4)
    •  \quad \vdots
    •  p[\colon 6] = (1, 4, 2, 8, 5, 7)
  • また、ある列  p に対し  p[i] を「 p i 番目の要素」とします。

    •  p = (1, 4, 2, 8, 5, 7) のとき、
    •  p[1] = 1
    •  p[2] = 4
    •  \quad \vdots
    •  p[6] = 7
      • Python の記法とは異なるので、スクリプトに落とす際はお気を付けください。
  •  P^{*} = \{p[\colon i] | i \in \{0, 1, 2, \dots, n\} , p \in P \}

    • 明らかに、 P \subset P^{*} です。
  •  f^{*} \colon P^{*} \rightarrow \mathbb{N} が存在し、 \forall p \in P, f^{*}(p) = f(p)

  • ある列  p に対し、列に登場する要素のみで作られた集合を  set(p) と書くことにします。

    •  p_{1} = (1, 4, 2, 8, 5, 7),\ p_{2} = (1, 2, 4, 5, 7, 8) のとき、 set(p_{1}) = set(p_{2}) です。
  • ある列  p の要素数 len(p) と書くことにします。

    •  p = (1, 4, 2, 8, 5, 7) のとき、 len(p) = 6 です。

このとき、以下を満たすような関数  d \colon \{s | s = set(p^{*}), p^{*} \in P^{*}\}  \times \{1, 2, \dots, n\} \rightarrow \mathbb{N} が存在する場合、計算量を減らすことができます。

 \forall p^{*} \in P^{*},\ len(p^{*}) = 0 \lor f^{*}(p^{*}) = f^{*}(p^{*}[\colon len(p^{*}) - 1]) + d(set(p^{*}[\colon len(p^{*}) - 1]), p^{*}[len(p^{*})])

  len(p^{*}) = 0 は、 p^{*}[\colon -1] が登場しないようにするための飾りです。

 d が存在するということが結構都合のいいことを言っていて、このおかげでサイズ  2^{N} の dp テーブルで、遷移数  N の dp を解くと、 f の最大値・最小値を求めることができます。

典型知識らしいです。本当に?

実は、巡回セールスマン問題がこのテクニック(の亜種)を使っています。巡回セールスマン問題の場合は、以下のように  d の定義と  d f^{*} の間で成り立つ式を変形させます。

 d \colon \{s | s = set(p^{*}), p^{*} \in P^{*}\}  \times \{1, 2, \dots, n\} \times \{1, 2, \dots, n\} \rightarrow \mathbb{N}  f^{*}(p^{*}) = f^{*}(p^{*}[\colon len(p^{*}) - 1]) + d(set(p^{*}[\colon len(p^{*}) - 1]),  p^{*}[len(p^{*})-1],  p^{*}[len(p^{*})])

katoufujibanana.hatenadiary.jp

Tips:半分全列挙

典型問題はこちらです。

atcoder.jp

ちょっとひねった問題はこちら。

atcoder.jp


半分全列挙が使える問題は(完全に個人的な感想ですが)どんな問題なのか、わかりづらくないですか? 私だけでしょうか。
すこーし考えてみたので本ブログにメモっておきます。

ある有限集合  S が存在し、 S の部分集合を引数に取る関数  f \colon X \rightarrow Y が存在する。ただし  X S のべき集合  2^{S} である。
このとき、 f(x) がある条件を満たすような  x \in X の個数や、条件を満たす  f(x) のうち最も hoge なものを求めよ

素朴に解くなら計算量  O(2^{|S|}) です。
冒頭の問題では  |S| = 40 なので、計算量  2^{40} \fallingdotseq 1.1 \times 10^{12} となり無事 TLE です。

半分全列挙では集合を2つにわけます。
分けた後でそれぞれを素朴に解けば  |S| = 40 でも計算量  2 \times 2^{20} \fallingdotseq 2.1 \times 10^{6} です。
ここまでならまだ実行時間に間に合いそうです。

このあと2つに分けた集合のそれぞれの  f(x) の値を組み合わせていくことを考えます。組み合わせる演算を  g: Y_{1} \times Y_{2} \rightarrow Y としたとき、以下が成り立つとよいです。よくわかっていないですが、たぶん成り立つ必要がある?

  •  y_{1} = f(x_{1})
  •  y_{2} = f(x_{2})

のとき、

  •  g(y_{1}, y_{2})= f(x_{1} \cup x_{2})

 x_{1} \cap x_{2} = \phi であることに注意してください。
なお、 Y_{1}, Y_{2} は以下のような集合です。

 S_{1} \cup S_{2} = S \ \land \ S_{1} \cap S_{2} = \phi となるような集合  S_{1}, S_{2} において、

  •  X_{1} = 2^{S_{1}}
  •  X_{2} = 2^{S_{2}}
  •  Y_{1} = \{f(x_{1}) \ | \ x_{1} \in X_{1} \}
  •  Y_{2} = \{f(x_{2}) \ | \ x_{2} \in X_{2} \}

すべての  y_{1}, y_{2} の組み合わせを検討すると計算量が約  |Y_{1}| \times | Y_{2} | となります。
 Y の値に重複が多ければ計算量が減らせるかもしれませんが、逆に重複がない場合は  |Y_{1}| \times | Y_{2} | =2^{|S|} となり TLE です。

冒頭の問題ですと、

  •  Y に全順序構造があること
    • このとき、 Y の部分集合の  Y_{1}, Y_{2} も全順序構造を持ちます
  •  y_{1} \in Y_{1} y_{2a}, y_{2b} \in Y_{2} について、  y_{2a} \leq y_{2b} のとき、 g(y_{1}, y_{2a}) \leq  g(y_{1}, y_{2b})

を利用してソート後に二分探索を使って個数や最大のものを高速に求められるというテクニックを使っています。

全順序じゃなくても成り立つのかなと思いましたが、その場合二分探索できないような気も。あと  g を構成できるかどうかもわからないので、ここら辺は話半分に聞いていただきつつ。

できる限り抽象化してみましたが、私の基礎体力のなさだと条件を満たすのが実数と和演算くらいしか思いつきませんでした。他のおしゃれな例をご存じな方いたら教えていただけると嬉しいです。

ゲーム理論:ゼロサムゲームにおけるパレート最適解

ゲーム理論です。ポエムです。

表題の通り、ゼロサムゲームにおけるパレート最適解が何かについての記事です。たぶん簡単な内容なので、広く一般に知れ渡っているような気もしますものの。

パレート最適解については、過去に記事を書いているのでそちらもご参照ください。


まずは、ゼロサムゲームについて。ゼロサムゲームはどの戦略の組を全プレイヤーが選択しても、各プレイヤーの利得の総和が  0 であるようなゲームです。

こう言ってしまうと簡単に聞こえますが、これだけでも、

  • 各プレイヤーの利得同士について、「和」の演算が定義されている
    • 零元が存在する
    • 総和が  0 となるので、逆元も存在する
  • 各プレイヤーのそれぞれの利得  O_{i} は順序構造を持つ。(戦略型ゲームで必須

が要請されます。

もしかしたら見落としがあるかもしれませんが、これだけで  O_1, O_2, \dots, O_N \mathbb{N} \mathbb{R} もしくはそれに類する(?)集合になってしまうかと思います。
本当かな? 数学に詳しい人どなたか教えてください。


ちょっと手を抜きますが、  O_1, O_2, \dots, O_N \mathbb{N} \mathbb{R} であるとき、

ゼロサムゲームにおける、すべての戦略の組み合わせはパレート最適である

が成り立ちます。

証明はそんな難しくはないと思います。パレート支配・被支配の関係があると、どちらかが総和がゼロでないことが示せるので対偶とって証明完了です。たぶん。