日記N+1

日記N+1

とりあえずKaTeX入れました
同志記事: http://boson.fock.space/2016/11/bloggerkatex.html

f^(x)=∑i=0n−1f(ζni)xi \hat{f}(x) = \sum^{n-1}_{i=0}f(\zeta_n^i)x^i

書きたい欲を満たした何か。1

最近なんとかFFTを理解して基本的なFFT問題をひとつAC
https://atc001.contest.atcoder.jp/submissions/2025702

そのうちFFTの勉強法記事書こうと思うんですが、
「一番わかりやすいFFT解説」か「FFTの勉強法紹介」にするか考えています
前者のような記事が存在しないと思っているので、個人的にその先駆者として君臨したいなというのがあります。

NNTも無事わかったのでJOI18ho後にでも書きます

最近のAC復習

ARC089でAtCoder青になった
CSAもはやく青復帰したい
「青になる道のり」みたいなのは別に書きません！
ecasdqinaが書いてくれるので待機しとこう

ARC089

C

ログが正しいものか見るやつ

yukicoder:627 ランダムウォークの軌跡に似てる

D

市松模様系
自明な言いかえして累積和とる
累積和は実家なので。

市松関係でおすすめのPCK17ho-6問目
AOJ:市松模様
本選で爆速で解けた思い出がある

つまり累積和も市松模様も実家というわけである

初黄パフォだった

過去コンテストは青パフォばっかりでした、険しさを感じます

CSA Round #66

https://csacademy.com/contest/round-66/

二部マッチング帰着しきれなった、くやしい！！！

SHコン

企業コンテスト
またも二部マッチングを落とした。
基本問題で蟻本のやつより簡単だった
終わった後Dやってみたんだけど1h33mかかった

最近僕が強く意識するべきなのは「実装しやすい考察をする」ことだなと思った

Eはまた今度。

ARC090

2完
Cは日本語読解コンテストだとして
Dの考察が雑すぎた。

「なんかダイクストラっぽく見ていって～」
と雑なことを考えた

「すべての辺を満足させたい」
「すべての辺を見れる探索をなにかすればいい」
といった考察を目指すべきだった
DFSという人が多いがBFSでもなんでもいい

E

解説見たらdp1とdp2を作ることはできていて、過不足なく数えるところができていなかった

多少時間がかかっても、「数え上げ問題は、対象が何を数えているものか日本語で書く」ことをしようと思った

時間がかかってACするのと、時間かけずに嘘解法書くのはどっちがいいかはっきりしているからね。

F、これはまた今度。

数学ガール借りてきた

数学ガール/乱択アルゴリズムを読み終え、すごく良かったので最初から読もうと思った

ちなみに試しに関係ない「数学のセンスをつける！」みたいな本読んでみたけど、数学嫌いの文系のための本みたいな感じで、自分に合わなかった

数学ガールとてもいいですね

いま母関数というのを新しく知ったんですが、
FFTやきたまさ法をするときによく使うので名前が知りたかったみたいなところがあり、すごく感動しました

やっぱ数学は出会いの連続だな！！

数学をいままで以上に好きになれたのは競プロのおかげかな

あとecasdqinaとロマ数いきたいにゃ！

テンプレートをだいぶ変えました

競プロのテンプレはvimrcと一緒に管理しています
https://github.com/LumaKernel/vimfiles/blob/master/snippets/cp-cpp/temp.snip

ハイライトだけ紹介！

cout と vector

template <typename T> ostream 
&operator<<(ostream &o, const vector<T> &v) {
	o << '{';
	EACH(i, v)
		o << v[i]
		<< (i != v.size()-1 ? ", " : "");
	o << "}";
	return o;
}

EACHは心の目で読んでください

はむこさんの提出を参考にほぼそのまま。2

dumpを可変長に


#ifdef DEBUG
#define dump(...) cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n";
#else
#define dump(...)
#endif
  
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type 
_ot(ostream &, tuple<T...> const &){}

template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type 
_ot(ostream & os, tuple<T...> const & t){
	os << (n==0?"":", ") << get<n>(t);
	_ot<n+1>(os, t);
}

template<class...T> ostream & operator<<(
	ostream & os,
	tuple<T...> const & t
){
	_ot<0>(os, t);
	return os;
}

tubo28という方の提出を参考にしました3

言いたいことはわかるけど難しい
cppreferenceをもっと読まないと…

おそらくc++14以上向けになっていると思うので、POJとか考えると各バージョン向けのテンプレを作りたくなりますね

このままだと空じゃかけない…

プレゼント

特別…ですよ？

はむこさんのwiki - 神への近道

はまやんさんのまとめ - 神からの贈り物

おしまい

JOI本選にもっていくテンプレをそろそろまとめようと思います！

エカスドの作問で手伝ったものの解説などを書いています、完成が楽しみですね！

  1. \hatを知らなくてggってたら疲れた ↩︎

  2. ちなみにこれ無断でやっていいのかなという考察はありますがテクは良さそうみたいには思いますがとりあえず本人に聞いてみようと思いますいつか。提出コード自体には著作権があるという話なはずです（それはそう） ↩︎

  3. 今確認したら片思われという超申し訳ないことになっていたので早急にふぉろばした ↩︎

たぐ：

このブログの人気の投稿

YouTube Iridiumの紹介

イメージ
YouTubeであれがしたい ブロックをしたり, コメントを非表示にしたり. そんなあなたに, Iridiumをおすすめしたい. まえおき というか蛇足だ. 足を頭に書くってのは愚策だろうけどね, 他愛もない話をね. 前までは動画投稿をしていたんだけどね, 今は大学まで一旦休むことにしているんだ. ちょっと前までは “忙しくて” なんて言ってたけど, それは毛頭おかしな話だったんだ. 僕が動画を投稿していた頃は忙しい中, 合間を縫ってやっていたことだ. だいたい動画投稿している人間なんて忙しい人だらけだろう. だから僕は, 忙しいなんて嘯くのはやめたんだ. でも忙しくするのは大事なことだと思う. 本題 僕もコメントを隠すuserscriptを書こうとしたことがあるんだけど, 現在のYouTubeはSPAだからいかんせん作りにくい. どうやって更新を検知したらいいかもわからないし… それで他のスクリプトから学ぼうと思ったら, いたれりつくせりのuserscriptを発見した. まーそれはYouTube++てやつなんだけどそれの後継がIridium. スクショがこんな感じ. わーすごい! 神か? 神なのか??? さきにDLリンクを紹介. https://github.com/ParticleCore/Iridium/wiki/Download 自分の環境にあったものを選べばok. 機能の紹介 いろいろあるよ. コメントをデフォルトで隠すようにする ブロックして表示しないようにする 動画を別ページに移動しても表示し続ける（スマホアプリ版みたいな機能） 動画ページでスクロールしても動画を表示し続ける 他にもたくさんあるし, 細かい挙動を設定で変えられる. 広告は消されるが, 設定で登録しているひとだけ許可, などができる. わーすごい! ブロックはすこし使い方にくせがあるが, 動画のサムネイル時点でホバーをして左上に出てくるBlockを押せばいい. 動画を表示し続ける機能なんかは公式が対応すればいいのにとおもうほど… なんのためのSPAやねん. とりあえずブロック機能がほしかったから, 使いまくっている. 結局コイツがYouTubeの更新をどうやって検知してるかわからずじまいだけど… 設定...
つづきをよむ！

うくこん

大悪魔様の誕生日です. https://beta.atcoder.jp/contests/ukuku09 lumasdqina で luma + ecasdqinaででました A 見てない＞＜ エカスドが通した B なんか自明な貪欲があるのでそれと同値のものを数えるといい. C ダイクストラだなって思ったのでダイクストラしたらTLEして無限に申し訳なくなって, よく考えたら01BFSどころか1BFSだったのでそうしたら通った. D Manacherして色々考えてダメそうって思ったけど, 二分探索がきれいにハマった. E 考察してもうだめだと思うなどした. 楽しかった. 5位だったのでとてもうれしいね.
つづきをよむ！

TDPC - T フィボナッチ

まだ解いてなくて自分で解きたかったりしませんか大丈夫ですか救ってもらってもいいですか解法書きますよ大丈夫ですかではいきます 【追記】上の文字がおかしく見えるひとは違う世界に住んでいます h1を文字大きくするためだけに使うのはやめようねSEOが死にますよ TDPC - T フィボナッチ 覗いたらやってみたくなったのでやってみたら一苦労。 きたまさ法 というのを使います。蟻本作者由来のアルゴリズムらしいですね。 蟻本の最後の「こんなアルゴリズムもあるよ」にも乗っているらしいですね。らしい、というのは椅子から動きたくないからです。 意味不明な記事がおおかった 僕の頭が足りないのでしょうが、「あーここの記事の通り式変形してこれをfとおけば自明で、典型なので〜」みたいな記事で、（いやほかのTDPCの問題の記事は良かったんですが、） そんなんいいから、いい記事置いときます m項間漸化式の高速なアルゴリズム バタ子(btk)という方の記事です ここ見ながらノート作れば完璧です。 完璧ですが、最後の x_u = Σ(i=1, m) s_i × x_i x_v = Σ(i=1, m) t_j × x_j ならば x_(u+v) = Σ(i=1, m) Σ(i=1, m) s_i × t_j × x_(i + j) になる というのが少し苦しみました あと、この TDPC-Tは上記記事(すなわちきたまさ法で解ける問題)の特殊ケース であるということを念頭においてください。このことは僕のコードにも詳しくコメントを入れました。 しかし上記の式はとても重要で、 x_uとx_vが求まればx_(u+v)がO(m^2)で求まることを意味しています 記事の後ろに解説書くので同じくハマった人がいたら助けになればなと。(MathJaxとか知らない！) Typical DP Contest : T - フィボナッチ kmjpという方の記事 以下引用 yukicoderをちゃんとやっていれば余裕。 まとめには yukicoderをやっていたら、TDPCの最終問題があっさり解けるようになっていた。 と。 yukicoderにきたまさ法を使える問題があるようです。 No.214 素数サイ...
つづきをよむ！