素数modで問題を解くためのアルゴリズムは色々有名なものがありますが、合成数modだとうまくいかないものも多いです。 このようなとき、素因数分解によって素数modの問題に分解することができれば、中国剰余定理を用いて元の問題の解を復元できることがあり…

3完しかできなくてひどい目に遭った… ふと思い返すと、ひどい目に遭ったときしかブログ書いてない気がする。 そんなことはどうでもよくて、Dは解けそうにないし面白い要素もないので、Eをずっと考えていた。 こっちは考えごたえがあってとても面白かったので…

基本マラソンはあまり真剣にやらないんですが、今回はできそうなことがありそうなのでちょっと時間をかけてみました。 暫定200位よりちょっと悪いくらいらしいので、私の実力にしてはよくやったほうだと思います。 私は焼きなましだとかビームサーチだとか、…

冒頭からネタバレですが、やたらとdiffが低かった割には想定解法が遅延セグメント木だったので、おったまげた人が多かったようです。私もコンテスト中は遅延セグメント木使いましたが、E問題ごときでそんなん想定解のはずないだろって思い込んでいたので、た…

再帰がハマってキレイに書ける問題は楽しいです。 Rustはスライスで自然に範囲を狭めていくような再帰が書けるのが嬉しいですね。 解法 AND,XOR,ORはそれぞれ&, ^, |で書くことにする。 数式のAND,XOR,ORの部分がなんか怪しいので、とりあえずを当てはめて真…

こんなん乗せられていいはずないだろ！ っていうのがセグ木(みたいな何か)に乗るの、好きです。 解説見て、これちゃんとした名前のついてるデータ構造だったのか～と思いました。 解法 問題を見たところこれに似てるなと感じた。 B - 買い物 2 (Shopping 2) …

記事で載せてる実装例とかほぼ全部Rustのコードなことからわかるように、私はRust使いです。(私の記事読んだことある人なんでほぼいないでしょうが) たまに、Rustで競プロやりたいけど環境構築の方法がよくわからん、みたいな人もいるので、お手軽環境構築し…

コンテスト名が長すぎる… 解法 取り得る区間の累積和の絶対値の総和を求めよと言われている。 まず配列について区間の累積和の求め方を考えると、までの累積和から、までの累積和を引けば求まる。 つまり、からまでの累積和をと置けば、 となる。 ところで、…

本番で解けなくてひどい目に…見た目で無理そうと判断して飛ばしたのがチンパンプレーだったという話で、あとで考えたらそう難しくなかったのが余計に痛すぎる。 Twitter見てたら遅延セグ木とかいもす法とか言ってる人が多いですが、差分更新したほうが簡単じ…

AtCoderでは2023年の言語アップデートでAMD64向けのアセンブリ言語（の中でもNASM）による提出ができるようになりました。 これで問題解いてみたいな～とは思っていたもののなかなか手が出ていませんでしたが、ABS程度ならいけるかと思い立って解いてみまし…