競技プログラミングでは、フーリエ変換やゼータ変換などを使って畳みこみの計算を行うことがしばしばありますが、こういった○○変換で畳みこみの計算ができる直感的なお気持ちを最近ようやくわかった気になったので、その勝手な解釈を文章にまとめました。 読みにくいところやいい加減なところがありますが、ご容赦ください。 畳みこみについて 集合 上の 項演算 があって、 与えられた つの 次元ベクトル から、 となる新たな 次元ベクトル を作る操作を、ここでは「畳みこみ」と呼び、 で表します。 演算 として、 などの場合が競プロにしばしば登場します。 ただし、 はbitwise-AND、 はbitwise-OR、 はbitwise-XORを表します。 の場合は、 を次の手順で計算できます。 まず、 と それぞれに離散フーリエ変換を行って、 つの 次元ベクトル を得ます。 次に、 と の各点積、つまり、 を計

AtCoderで赤タッチしたのももう1.5年も前ですが書きます。覚えていないこと・抜け・漏れなどのオンパレードですがご容赦ください。 お前は誰 kobae964 - AtCoderです。2017年11月に初めてAtCoderでredになりました。 RedCoderになりました！！！！ pic.twitter.com/PcRWWu32qS— koba (@kobae964) 2017年11月11日 なんで今更これ書いたの 当時は面倒だったので書きませんでした。その後人々が変色時に記事を書いていくようになり、見かけた記事は大体全部読んでいました。 微笑ましいと思ったもののAtCoderの赤でそれをやった人を見たことがなかったので、せっかくなので書こうと思いました。すでに誰か書いていたらごめんなさい。 注意事項 筆者はAGCよりもARCの方が得意なため、AGCでの立ち回りは強い人に聞いてください

モチベーション Rustで標準入力から望みのデータを入力するのは意外と面倒で、標準ライブラリにあるものを使って素直に書こうとすると、結構コード量がかさみます。例えば、文字列を一行読み込むのに、 let s = { let mut s = String::new(); // バッファを確保 std::io::stdin().read_line(&mut s).unwrap(); // 一行読む。失敗を無視 s.trim_right().to_owned() // 改行コードが末尾にくっついてくるので削る };

はじめに 自分の経験から、Rustで競技プログラミングをやるときに役に立ちそうなことをまとめました Rustで競技プログラミングを始めた方がRust特有の引っかかりどころに引っかかることなく、 より問題の本質に集中できるようになれば幸いです 対象 プログラミング言語Rustをだいたい理解したけど競技プログラミングでRustを使うのは不安な人 環境構築 とりあえず RUST_BACKTRACE=1 を環境変数に設定しておく エディタはなんでも良いですが 入力補完 (rust-analyzer) 保存時か任意のタイミングで自動整形 (Rustfmt) 自動コンパイル & エラー箇所の表示 を導入しておくのをおすすめします。導入方法はググれば大丈夫だと思います rustup override rustup overrideを使うことでカレントディレクトリ以下で使うRustのバージョンを指定できま