...

codeFlyer2018本選参加してきた 予選は4完. 本選は行けるとこまで走って溶けそうなやつを食べようと思っていたので, そうしたけど, 青なので運がほしいね. 結果はABCの3完. Eを考察した. うーん, 逆ポーランドみたいに木にしてダブリング頑張って+のとこで0になるやばいのとか頑張ったけれども, 答えが全て0になった. 本番終わり, メインの懇親会. たっぷり1時間ぐらい壁さんとお話しました, かわいい. 人間さんとも喋りました, 言葉が通じるってすてき.

アルゴリズムは女の子#1 アルゴリズムの気持ちがわかりたい. アルゴリズム覚えるだけが増えているので少しメモを書いていきます. お品書き 趣旨は 実装を速攻で書けるように , です. OJ作ったならば実装道場みたいなの作りたいですね. FFT KMP Manacher Z-algorithm ようこそ精進道場へ Warshall-Floyd なんとなくDPなのはわかりますがほぼ暗記するだけみたいなところありますね. k以下の頂点しかない場合の全点対最短路だと考えると, といった感じでしょうか. 間違えないので書きません. FFT これだけで記事一つになりそう… 実際実装するなら毎回導出している時間はないですね. というわけで実装を暗記する,ということも必要ですね. long doubleだと心配なので,NTT, CRTでの復元は使えるようになっておきたいです. 任意modはよくわからないです. 基本 complex<double> で書いてみます. 原始根には e x p ( 2 π i / n ) exp(2 \pi i / n) e x p ( 2 π i / n ) を使います. 高校数学の複素数さえわかればガウス平面で図形的に直行性を感じることができます(また(有限)等比級数の和の公式からも示せます) NTTを考えるにしても,この環が見えているとだいぶ理解しやすいと思います! // a.size() is 2 ^ k vector < comp > fft ( vector < comp > a , bool inverse = false ) { int n = a . size ( ) ; if ( n == 1 ) return a ; vector < comp > a0 ( n / 2 ) , a1 ( n / 2 ) ; for ( int i = 0 ; i < n / 2 ; i ++ ) a0 [ i ] = a [ i * 2 ] , a1 [ i ] = a [ i * 2 + 1 ] ; a0 = fft ( a0 ) ; a1 = ...

APIO 2018, Practice roundをやりました. 全巻下のデ乗せときます. 問題PDF確保してるのでそのうちペタるかも. A. A + B 概要 : 二つの小数を足す. 解法 : やる. コード: # include <bits/stdc++.h> using namespace std ; using ll = long long ; int main ( ) { ios :: sync_with_stdio ( false ) , cin . tie ( 0 ) ; double a , b ; cin >> a >> b ; cout << fixed << setprecision ( 5 ) << a + b << endl ; } B. Zero-complexity Transposition 概要 : 配列をreverseする. 解法 : 配列をreverseする. コード: # include <bits/stdc++.h> using namespace std ; using ll = long long ; int main ( ) { ios :: sync_with_stdio ( false ) , cin . tie ( 0 ) ; int n ; cin >> n ; vector < ll > v ( n ) ; for ( auto & e : v ) cin >> e ; reverse ( begin ( v ) , end ( v ) ) ; for ( auto & e : v ) cout << e << " " ; cout << endl ; } C. Wedding cake 概要 n個の有限小数 小数第 a i a_i a i ​ 桁まである.最後は0でない. 合計が1. 解法 max ⁡ (...