...

アルゴリズムは女の子#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 = ...

HTTFまとめ 解説放送のアーカイブ(YouTube) を見たまとめです 知らない知識を使わなくても999が取れたりするそう 山登り法は名前は知らなかったけど考えたりはできた（実装してないが） 最小単位での遷移、多くの遷移法を考える ランダムケースにランダムが使える！ 「前計算O(N 2 )各計算O(1)」や「前計算なし各計算O(N 2 )」を 更新頻度に応じて 使い分ける なるほどが深い 焼きなまし法ってなんだよ 勉強しよう 結果 変数を変更できる余地を残し、 いろいろいじったものを投げて、9553806647 しかしこれはつまりランダムにしたほうがよく、 サンプルをcatでなげるとランダムと同じくらいよくて96が出るらしく、 すでに抜かれてて泣いた

競プロをやる強プロのみなさん、いかがお過ごしですか！ JOIは今年が初めての参戦ですか？ 本選がどんな感じか不安ですか？ 遅延er界のこの僕が、この時期に、JOI2017本選の様子を思い出しながら書こうと思います！ 現地集合、受付 つくばのどっかに着きます。 周りは本選に向かっているのであろうJOIerがいたのだと思いますが、当然1人も知りませんでした！ つくばのなにかしらの施設に着きます。 すごい広い。 受付で名前とか言って、予選ランクAなら”なにかしら”をもらいます。 親erがいたので荷物にならないよう、そのまま持ち帰ってもらいました。 あとは謎の部屋で待ちます。 他の参加者もそこにいます。 荷物とかは基本そこに置きっぱなしにします。 時間がくるまでみんなパソコン触ったり蟻本触ったりTwitterしたり交流したり…してたけど僕は当然虚無をしていた。 時間がきたらプラクティス 説明を受けて、本選会場におもむろに連れて行かれます。 プラクティスは参考書持っていけます。 簡単な[要出典]コンテストが一応あります。 ログインの流れとか、IDE等の起動、準備、Hello,world.ぐらいまでできるようにしておきましょう。 運営スタッフに質問したり、知人erに相談したり、圧倒的なコミュ力を思う存分に発揮したりしてください。 運営にプラクティスコンテストの提出を急かされますが、1個も提出しなくてもいいので、本番で焦らないよう、しっかりゆっくり確認しましょう。 その後は講習 IN 待ち場所に使われた怪しい部屋 Twitterをします。（聞こうね！） “ニューラルネットワーク計算のアルゴリズム”ってタイトルだった。 たしか…多次元ベクトルをドカーンってしてバーンってなって、パンを作るって話だった気がする。プリンだっけ？ 移動 正直どこに移動したとかは知らないが、ホテル的なとこなのだろう。多分。 バス で移動だ。 隣の人に話しかけてもかまわない。 僕は貯めてたMPを存分に使って話しかけたぞ！ だけど「ABC」とか「太陽☀ですね」とか「太陽☀が降ってきました」とか言われてよくわからなかったぞ！ 競プロ用語は覚えとくだけ覚えてから行こうね！ 僕は仕方なくホテルに...

paizaスキルチェック Sランク問題を満点解法で埋めてきました。 現時点で14問あります。 難易度はそんなに高くありません。 結構バランスよくあります めっちゃむずいのとか、めんどいのとかから、 お前B行けみたいなやつまで 運ゲーですね、いくつかやってみてください 必要なのは プログラムがわかる 思い通りにかける 簡単なアルゴリズムがいくつかかける を少しでも満たしていれば、どれかは解ける プログラミングコンテストチャレンジブック、通称蟻本でいうところの 96ページぐらいまで把握しておけば全問正解も見えてきます 解けない問題あると気持ち悪いじゃないですかっ 今回はこんなんです。 おやすみ… 近々非競プロerプログラマのための競プロ入門を書こうと思う

一覧・参加感想記事 問題公式PDF AOJ 1-5問目 6問目 7問目←ここ これは解説なのか？ 7:積み荷の配置 これ本番中にできなかったの悔しいな…と思いつつ結構考慮しなければいけないケースが多くて実装時間かかった bitDP ですね。 蟻本にもタイル敷き詰めの問題がありましたが、 タイル敷き詰めを見たらbitDPだと思えるようになっておこうね（思っただけで終わった僕のようにならないように実装練習しようね） 解法 1行ずつ見ていく。 ある行を見ているとき、2行上は気にしなくていいね。 よって、横4マスのうち左3マスに左上が置かれているか、という情報を保持する。 状態数は1行に2^3 = 8個、1e4行で8e4通りなので十分間に合う。 ちょっと、そのうちちゃんとした図解作りかも知れないし作らないかもしれない。 英語間違ってるかも（弱）。 #include <iostream> #include <algorithm> using namespace std ; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--) #define RREP(i,n) RFOR(i,0,n) int bitcount[] = { 0 , 1 , 1 , 2 , 1 , 2 , 2 , 3 }; int h,n; bool b[ 4 ][ 10000 ]; int dp[ 2 ][ 1 << 3 ]; int main(){ cin >> h >> n; REP(i, n){ int x,y; cin >> x >> y; b[x][y] = true ; } REP(y, h- 1 ){ int *prev = dp[ 0 ]; int *now = dp[ 1 ]; ...

一覧・参加感想記事 問題公式PDF AOJ 1-5問目 6問目←ここ 7問目 6:トランポリン まず10で割っておいて、左右にいくつ動けるか計算しておきます。それをd[i]とします 行きを考えます。 iを0からカウントアップさせていきます。 今iにいるとしたら、i+d[i]まで行けますね。 これをcangoとしましょう。 そのとき、今までのcangoより大きくなければ、 今までで最大の場所から飛べばいいので、更新しなくてもいいです。 こうやって次にいけなくなるか、n-1にたどり着いたら終了です。 n-1にたどり着いていたら、同様に帰りも計算します。 計算量はO(N)です。 #include <iostream> #include <algorithm> using namespace std ; #define FOR(i,a,b) for(int i=(a);i<(b);i++) #define REP(i,n) FOR(i,0,n) #define RFOR(i,a,b) for(int i=(b)-1;i>=(a);i--) #define RREP(i,n) RFOR(i,0,n) const int _N = 3e5 + 100 ; int n; int d[_N]; int main(){ cin >> n; REP(i, n){ cin >> d[i]; d[i] /= 10 ; } // 行き int i= 0 , cango= 0 ; for (;i <= min(cango, n- 1 );i++){ cango = max(cango, i+d[i]); } if (cango<n){ cout << "no" << endl; return 0 ; } // 帰り i= 0 ;cango= 0 ; for (;i <= min(cango, ...