多倍長整数でサボろうとしたのですが、TLEするな〜と思って思いとどまりました。 解法 各数値について、の位に何回寄与するか考える。 桁目の数値について考えると、 桁目から開始して桁目で終わる数値に、の位として寄与 桁目から開始して桁目で終わる数値…

競プロでは、どんなに非効率なコードを書いたとしても、要求された時間内に正しい答えが出せれば正義です。 なので、基本的には速いコードを書くことにそこまでこだわる必要はないです。 とは言っても速いコードを求めることは無意味ではなく、犯罪解法で計…

大きなC言語のコードをRustに移植しようとしたのですが、流石にいきなりRustっぽいコードに書き換えるのは難しかったです。 なので、とりあえずRustっぽくないコード（ポインタ使いまくり、libcクレート依存など）でテストが動く状態を作ってから、徐々にRus…

ただの備忘録です。 本題 mkfifoというのを使うといいらしいです。 回答プログラムがanswer、ジャッジプログラムがjudgeとして $ mkfifo fifo $ cargo run --bin judge < fifo | cargo run --bin answer teeを使えばログにも落とせます。便利。 $ cargo run …

本番めっちゃ詰まって困りました。 解法 をソートしておくと、どの文字列も隣の文字列とのLCPの長さが最大になる。 をソートしたあとの列について、隣の文字列とのLCPの長さを順にメモした配列をとしておく。 問題で求められているのはすべての文字列の組み…

最近、Online Dynamic Connectivityとか言われているデータ構造を実装しようと奮闘しています。 これを実装するのにEuler Tour Treeというのが必要なのですが、結構面白かったので備忘録です。 ちなみに、以下のスライドを参考にしているというか、なぞって…

素数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程度ならいけるかと思い立って解いてみまし…