波と思考

全部混ぜます

最近の学び 21/4/1

競プロについて

 復帰と言えるかは分からないが、久しぶりに競プロのいろんな知識を吸収して、実際に問題を解いた。

フーリエ解析

 これは競プロに活かすというより、普通に知りたかったので、書店で偶然見つけた「道具としてのフーリエ解析」という本を買った。入門書らしい。

 フーリエ級数、複素フーリエ級数フーリエ変換ラプラス変換と見ていった後、応用として離散フーリエ変換微分方程式の解き方、畳み込み積分線形応答理論などの概要を学んだ。高速フーリエ変換(FFT)以外の部分はまだ実際に自分で扱うまでに至っていないが、とても面白い内容だった。

 高速フーリエ変換(FFT)の記述は役に立った。これによって競プロでFFTを使えるようになった。競プロでのFFTの使用法は、フーリエ変換と畳み込み積分の関係を、整数個の離散的なデータに応用したという背景があるのだと思う。下の行列で表される式が本質的な部分だと思った。(ほぼ自分用)

 
    \begin{pmatrix}
      Y _ 0\\
      Y _ 2\\
      Y _ 4\\
      Y _ 6\\
      \vdots \\
      Y _ {n-2}\\
    \end{pmatrix}
    
=
  
    \begin{pmatrix}
      W _ {n/2}^ 0 & W _ {n/2}^ 0 & W _ {n/2}^ 0 & W _ {n/2}^ 0 & \cdots & W _ {n/2}^ 0 \\
      W _ {n/2}^ 0 & W _ {n/2}^ 1 & W _ {n/2}^ 2 & W _ {n/2}^ 3 & \cdots & W _ {n/2}^ {n/2-1} \\
      W _ {n/2}^ 0 & W _ {n/2}^ 2 & W _ {n/2}^ 4 & W _ {n/2}^ 6 & \cdots & W _ {n/2}^ {2(n/2-1)} \\
      W _ {n/2}^ 0 & W _ {n/2}^ 3 & W _ {n/2}^ 6 & W _ {n/2}^ 9 & \cdots & W _ {n/2}^ {3(n/2-1)} \\
      \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
      W _ {n/2}^ 0 & W _ {n/2}^ {n/2-1} & W _ {n/2}^ {2(n/2-1)} & W _ {n/2}^ {3(n/2-1)} & \cdots & W _ {n/2}^ {(n/2-1)(n/2-1)} \\
    \end{pmatrix}
    

  
    \begin{pmatrix}
      X _ 0+X _ {n/2}\\
      X _ 1+X _ {n/2+1}\\
      X _ 2+X _ {n/2+2}\\
      X _ 3+X _ {n/2+3}\\
      \vdots \\
      X _ {n/2-1}+X _ {n-1}\\
    \end{pmatrix}
   
\\
 
    \begin{pmatrix}
      Y _ 1\\
      Y _ 3\\
      Y _ 5\\
      Y _ 7\\
      \vdots \\
      Y _ {n-1}\\
    \end{pmatrix}
   
=
  
    \begin{pmatrix}
      W _ {n/2}^ 0 & W _ {n/2}^ 0 & W _ {n/2}^ 0 & W _ {n/2}^ 0 & \cdots & W _ {n/2}^ 0 \\
      W _ {n/2}^ 0 & W _ {n/2}^ 1 & W _ {n/2}^ 2 & W _ {n/2}^ 3 & \cdots & W _ {n/2}^ {n-1} \\
      W _ {n/2}^ 0 & W _ {n/2}^ 2 & W _ {n/2}^ 4 & W _ {n/2}^ 6 & \cdots & W _ {n/2}^ {2(n-1)} \\
      W _ {n/2}^ 0 & W _ {n/2}^ 3 & W _ {n/2}^ 6 & W _ {n/2}^ 9 & \cdots & W _ {n/2}^ {3(n-1)} \\
      \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
      W _ {n/2}^ 0 & W _ {n/2}^ {n-1} & W _ {n/2}^ {2(n-1)} & W _ {n/2}^ {3(n-1)} & \cdots & W _ {n/2}^ {(n-1)(n-1)} \\
    \end{pmatrix}
  

  
    \begin{pmatrix}
      W _ n^ 0(X _ 0-X _ {n/2})\\
      W _ n^ 1(X _ 1-X _ {n/2+1})\\
      W _ n^ 2(X _ 2-X _ {n/2+2})\\
      W _ n^ 3(X _ 3-X _ {n/2+3})\\
      \vdots \\
      W _ n^ {n/2-1}(X _ {n/2-1}-X _ {n-1})\\
    \end{pmatrix}
   

\\

 FFTは理論が分かってしまえば意外と実装は難しくない。コードを自分で書けるくらいまで理解した。さらに、FFTで使う複素数をあるMOD上の原始根で考えた数論変換(NTT)も少しコードを変えるだけで実装することができた。ただ、整数の余りを扱うため実行時間が長めになるのであまり使わないかもしれない。

 FFTが分かったのでいくつか問題を解いた。

https://atcoder.jp/contests/atc001/submissions/20749536

https://atcoder.jp/contests/agc047/submissions/21444461

この他にも、20万桁の整数どうしの掛け算とかをまともな時間で解く方法も分かった。

フロー

 高校生の間ずっと放っておいたフローアルゴリズムに少し手を出した。とりあえず最大流の求め方を学んだ。

 まず、フローとカットがどのようなものかを理解した。そして一番単純な(?)最大流アルゴリズムであるFord-Fulkersonのアルゴリズムと共に最大フロー最小カット定理というものを学んだ。今後も都度確認しながら定着させたい。

 それから、最大フローを求めるアルゴリズムを学んだ。Ford-Fulkersonのアルゴリズムでも求められるのだが、計算量が大きい。より少ない計算量で解けるEdmonds-Karpアルゴリズムの概要を把握した。これは結構理解しやすかったが、Dinic法の方がより計算量が小さいため、概要の把握程度にとどめてDinic法の理解を試みた。Dinic法もよく考えると理解できた。Dinic 法とその時間計算量 - みさわめも ←ここが分かりやすかった。

 最後にアルゴリズムの実装をした。Ford-Fulkersonは適当に済ませて、Dinic法を丁寧に実装した。Aizu Online Judgeに投げたらちゃんと通ってくれた。

 最大二部マッチングはフローに帰着できるが、Dinic法だと普通のフローよりも少し計算量が減るらしい。嬉しい。

掃き出し法

 大学の手続で謎の数学の冊子が配布された。教科書のように数学の学習内容がぎっしり詰まっているが、教科書にしてはレイアウトが簡素すぎる。表紙は白地に「数理科学基礎共通資料ナントカカントカ」と書いてあるだけ、裏面は真っ白だった。

 とにかくこの冊子には大学でやりそうな数学の内容がいろいろ書いてあったので、高校では未習だが有用で面白そうな行列の範囲を読むことにした。特に競プロで使える掃き出し法には興味があった。行列は最後の章だったので、行列を学ぶ前に学ぶべきだとされている章を読んでから読み始めた。読んでみると、行列で線形写像を表現できるなど興味深い内容がたくさんあり、掃き出し法も丁寧に解説されていた。

 掃き出し法の概要が分かったところで問題を解いた。連立一次方程式を解くのとは少し異なりビット列にXORを施していく使い方なのだが、確かに掃き出し法の考え方が効く。

https://atcoder.jp/contests/abc141/submissions/21434741

https://atcoder.jp/contests/agc045/submissions/21442895

こうして高校の頃はなんか難しそうだなと思って学んでいなかった掃き出し法を、ついに自分で扱えるようになれた。

感想

 競プロをしていると大学の数学とかで学んだ内容を即座に実際に応用できたりするから、その内容を学ぶ意味が生まれて、それが内容の理解の定着に繋がることもあるのでは?という幻想がある。

 今後は最小費用流をやりたいな。

 別に興味があるのは競プロだけではないが、学問分野は大学でやるだろうということで。ただ地学は高校で取らなかったので高校教科書レベルから頭に入れておきたいという気持ちがある。

追記

 VS Codeを使い始めた。今まではなんか導入方法が分からなくて使ってなかったが、改めてうまくやったら動いた。

 あとPythonのコーディングができる環境を整えた。大学とかで機械学習などをする機会があるかもしれないので。競プロにはほとんど使わないだろうけれど、基本的なコーディングができるようになるまで競プロの問題で鍛えておこうかな。