クラウドエンジニアのノート

情報技術系全般，自分用メモを公開してます。

トップ > Python > PFN2020インターンの課題 解答

PFN2020インターンの課題 解答

Python OSS Github 就活

PFN2020インターンに応募した話

M1になり，そろそろ夏インターンを探さなきゃってことで，色々応募しました．

強化学習のインターンをやりたかったのですが，勉強不足を面接であっさり見抜かれてしまい，落ちてしまいました．

これを糧に，これから強化学習の勉強をしっかりしようと強く思いました．

現在はberkeleyの強化学習スライドをベースに，基礎的な部分の勉強をしています．いずれはそれをまとめた記事を公開しようと思ってます．

PFN2020課題

Github上で2020の課題が公開されたので大丈夫だとは思いますが，もし何か差し支えるようでしたら，ご連絡頂けますと幸いです．

こちらのリポジトリに解答例を載せましたので，ソースはこちらをご覧ください． github.com

また，問題文はこちらです github.com

PFNの課題というと，深層学習のイメージがありましたが，今回はかなり競プロっぽい内容でした． 最近はそういう流れなんですかね．

また，大問が3つあって，それぞれコーディング課題と，その正しさを検証する課題の2つセットで解答する必要があります．

もし数式が正しく表示されていなければ，ブラウザをリロードしてみてください．

Q1

3つの整数 x, y, d が与えられる。 3x3 行列の各要素を x または y で埋めるとき、行列式がちょうど d になるような 埋め方は何通りあるか数えよ。

問題の解法説明

まず最初に思いつくアプローチは全探索である．

しかし，3x3行列というのは各列を3次元ベクトルと見ると，平行六面体を表しており，行列式の値はその体積に相当する．つまり同じ向きのベクトルが存在すると体積は0になる．この性質を利用して計算量を減らした．

$d \neq 0$ の場合

  • 3次元ベクトルそれぞれが取ることができるx, yの組み合わせは$2^{3}=8$通り
  • そこから重複なく3つ選ぶ数は ${}_8 C_3 = 56$ 通り
  • また，ベクトルをそれぞれ入れ替えて行列式の符号が同じになるような組み合わせは3通り

つまり56通り検索し，見つかった数×3すれば良い．

$d == 0$の場合

  • 同じく56通り調べる（転置してベクトルが0になる場合）
  • 重複する選び方の数(=全通り - 重複しない数)を計算

行列式が0なので，見つかった数×6に重複する選び方の数を足せば良い．

プログラムの正しさの検証

q1_in.txt を総当りのプログラムとの出力の比較を行った．

境界条件としてdが正・負・0, x, yが同符号・異符号・0の場合のすべての組み合わせ(12通り)について検証を行った．

また，おまけとして，全通りでも制約すべての条件下で現実的な時間内に終わりそうだったため，q1_validation_extra.pyにてすべての場合の検証を行った．

進捗を見やすくするため，tqdmという外部ライブラリを使用した．（並列化してますが，それでも手元の6コアCPUで30分程度かかりました）

Q2

文字列 S1, S2, ... を以下で定める。

  • S1 = "a"
  • S2 = "b"
  • S3 = "c"

Sk = Sk-3 + Sk-2 + Sk-1 (k ≥ 4) (ここで、+ は文字列の結合を表す) 例えば、S4 = "abc", S5 = "bcabc" である。 3つの整数 k, p, q が与えられる。 Sk の p 文字目から q 文字目までに含まれる文字 "a", "b", "c" の個数をそれぞれ求 めよ。

問題の解法説明

まず最初に思いつくアプローチとしてDPがある．しかし試してみたところ，メモリが$k > 40$をこえたあたりで足りなくなった．

そこで，この漸化式の行列表現を考える．

Svec_{k} = \begin{pmatrix}a_k&b_k&c_k&sum_k \end{pmatrix}

とすると以下のように表現できる．

このとき，$a_k$とは，文字列$S_k$に含まれるaの個数である．

\begin{pmatrix}Svec_k\cr Svec_{k-1}\cr Svec_{k-2}\end{pmatrix}=A^{k-3}\begin{pmatrix}0&0&1&1\cr 0&1&0&1\cr 1&0&0&1\end{pmatrix}, (k>3)


このAを毎回累乗して求めても良いが，高速化のためにこのAを対角化してn乗を求めておく． すると$O(1)$で，文字列$S_k$に含まれるa, b, c の個数がわかる．

また，この行列は固有値に虚数を含むため誤差が生じる．しかし，$A^{50}$のときの誤差が $ [0.0144 +0.0016j, 0.0124+0.0014j, 0.0072+0.0013j] $ であるため，問題ないと言える．

（当時は2乗法を知らずn次行列を求めてますが，あまり美しい方法じゃないので，2乗法を使ったほうが良いと思います‥）

qiita.com

つぎに$[p, q]$だが，もし，$[p, q]$の範囲が，ある S_l, (l \leq k) の文字数と同じ場合，先程の行列の結果をそのまま返せば良い． つまり，そのような$S_l$を探せば良い．

$S_k$は S _ {k-3}+S _ {k-2}+S _ {k-1} の3つの文字列から構成されている． つまり，$[p, q]$は$S_k$の各構成要素を跨ぐ場合と，そうでない場合に分けることができる．

以上の性質を用いると以下のようなアルゴリズムを考えることができる．

区間が跨いでいる場合

  • それぞれを区間を跨がないように分割し，最後にそれぞれの結果を足す

区間が跨いでいない場合

  • $[p, q] = S_{l}$ ならば，行列計算の結果を返す
  • $[p, q] \neq S_l$ ならば，対応する部分の$S_m, (m < l)$を調べる

以上の手順を再帰的に繰り返すことによって調べることができる．

プログラムの正しさの検証

プログラムの境界条件と，それぞれが1回以上の文字連結で構成されている$k=7$でのすべてのケースについて検証を行った．
また，DPで解くプログラムの限界が$k<40$であるので，その条件に満たすq2_in.txt でも同様に出力の検証を行った．

Q3

長いので省略

問題の解法説明

まず考えられるアプローチとして，各距離をすべて保持する方法が考えられる．

単純に，ある$j$番目人を最も距離が大きいかつ一番左の$a_j$に座らせて，$a_j$から両端まで距離を更新して行けば良い．

しかし，この手法は$O(n^{2})$であり，制約の$n$が大きいため時間がかかる．そのため高速化を考える．

ある$j$番目の人が$a_j$に座ったとき，そこから$l$方向($0 < l < j$)と， $r$方向の区間($j < r \leq n$)のまだ誰も座っていない区間に分割する．

それぞれ分割された区間の中で，区間の左右から最も離れた位置が最も大きい場所に座れば良い．
つまり，分割された区間が$l$から$r$とすると($l$は0から)，その区間内で離れることができる最大の距離$dist$は$(l - r) // 2$であり， 座る位置のindexは$l + dist$として表現できる．また，$dist$が最も大きいものから（同じからlが小さい方）から選んでいけば良い．

この手順を再帰的に繰り返し適用していけば，すべての座る位置が求まる．
しかし，最初の分割だけ例外があり，端に誰も座っていないため2で割る必要がない．よって$dist = l - r$とした．

実装上の工夫として，$dist$の最も大きい値を効率的に探すためにheapqを用いた．

プログラムの正しさの検証

プログラムの境界条件（最初に端に座る，n=1など）の検証を行った．
また，$O(n^{2})$の方法が現実的な時間で終わるのが$k < 10000$なので，その条件を満たすq3_in.txt についても同様の検証を行った．