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

本番全くわからなくて焦った… 解説読んでもあんまりピンと来なかったのですが、半日考え直してようやく理解できたので記事にします。 解法 無限に誰も排除されないことがあるけどどうしよう...となるので、とりあえずサンプル1がなんでこれでいいのかを解き…

ABC331Fでロリハをセグ木にのせろと言ってるようなもんじゃんっていう問題が出たわけですが、その場で解けず悲惨な目にあいました。 なので1点更新のロリハをライブラリ化したわけですが、最近Link Cut Treeのライブラリ化を試みていたりと地味に平衡二分木…

パッと見であんまりよくわからなかったけど、解けてみると面白かったので。 こんなんセグ木に載るんかーといった感じでした。 解法 早い話が、全体の累積和と、各商品種（で分類される種類）の累積和をそれぞれ用意することができれば、各クエリにで回答する…

それぞれ長さであるような配列に対して、といった形の演算を畳み込みと呼び、多項式の乗算の実装等に使えます。 で、そのライブラリのverify用の問題がyosupo judgeにあります(https://judge.yosupo.jp/problem/convolution_mod)。私はRust使いなのですが、…

Montgomery剰余乗算のアルゴリズムを用いると、乗算剰余を計算する際に純粋な除算・剰余算を省くことができる。 用途は色々あって、 128bit剰余算は非常に遅いので、そのような演算が必要な場合には高速化が期待できる SSEやAVX/AVX2には整数除算命令・剰余…

どう考えてもとてもめんどくさいことになりそうなので、機械的に解きたいと思ってやってみたら、案外間に合った。 解法 現在の速度や、速度が上限に達する時間が整数でなくなる瞬間があるのが面倒くさいポイントだが、おそらくたかだか小数点以下1ケタくらい…

ちょっと悩んでしまったが、良い感じにきれいに解けた。 解法 一般に、、とする。 によって構成される格子の1マスに注目して、これがいくつの長方形に含まれるかを考えると、これは となる。(縦の辺については、左側は通り、右側は通り、横の辺については、…

こういうO(1)で気合導出、みたいな問題はめちゃくちゃ苦手… 解法 早い話、ありうる部分列を列挙して重複を除去すれば答えが出る。制約が大きいので重複の仕方が爆発してダメそうに見えるが、重複している数字が1個しかないので、重複の仕方を上手く見つけて…

ネタ解法。理論的な根拠は一ミリもないので閲覧注意。 解法 55個しか出力しなくていいなら、埋め込みがしたくなる。事実、任意の5個の値の和が合成数であるような55項の数列から適当にN個選んできて新しく数列を作っても条件は満たすので、N=55のときの解を…

DP力が貧弱なので、EDPCの解き直しをしつつ、記録を残します。 結構自力で解けてないやつもあるので、解けてない問題は解け次第随時更新となります。 めっちゃネタバレ記事になる予定なので、これから自力で解こうという方はぜひブラウザバックを… A - Frog …

どうしても解けなかった。ただ、SIMDで無理やり高速化できれば通る予感がしていて、実際解説を見るとSIMD高速化で通せる可能性に言及されている。 そんな訳なので、大して経験もないSIMDで突っ張って通してみた。 解法 凝ったことは何もせず単に二重ループを…

フローの問題を履修しているときに出くわしましたが、解説とちょっとグラフの作り方が違ったので。 解法 葉であるマス目を頂点として同じ行or同じ列どうしの頂点を辺で接続し、フローグラフを構築する。 すると、Sourceを、Destinationをとしたときの最小カ…

結構シンプルなコードが書けて、説明としてもわかりやすいものになったと思うので残します。 本質的には公式解説などと何も変わりないので、新規性はないかも。 解法 手番の偶奇を考えるのは面倒なので、以下のようなDPを考える。 マスから先攻でゲームを開…

結構迷走しながら考察しましたが、何とか解けました。 解説見たらめちゃくちゃ賢い解法が書いてあってビビりましたが、自分の賢くない解法も残します。 解法 である各について、との間に辺を張った頂点の無向グラフの連結成分を考える。 まず、すべての連結…

計算量がよくわかりませんが、なぜかACできてしまったので書きます。(公式解説を見たら同じような解法が載ってました) 解法 問題の条件を言い換える。 まず、条件を満たすの組み合わせは、(であるような場合をさておくと)対称になるので、との関係はとりあえ…

公式解説では二分探索をうまく適用する賢い方法がとられていますが、私はそんなこと思いつくわけもなく… しかし、気合で数え上げることによってコンテスト中にACできたので解法残します。 解法 個以上リンゴが載っている皿のみ、小さいほうから考える。 もし…

ABCの解き直しをやっていて、ちょっと悩みましたがなんとか解き切りました。解説を見てみると、ちょっと効率の良い解法だったので一応残します。 解法 各島について西側からなめつつ、自身より西側のみを考える。自身より東側に仲の悪い島がある場合、その島…

コンテスト中に解法思いついたけど、計算量改善の実装が間に合わず無念の敗退… 結局、コンテスト後に自力ACに成功しました。しかし公式解説見てみると、解法が違う気がする。なので、一応解法残します。 嘘が含まれていたら教えてください。 解法 問題を、有…

導入 AHCではローカルテスタが用意されているので、手元で自身の実装の改善度合いを具体的な数値で見ることができます。 しかし、1個1個テストを回すのは面倒なので、当然、どうにかしてテストを簡単にできるようにしたいと思うでしょう。 そこで、一例とし…

早速本題 先週のABC237にて、順位455位、perf1860で、入青を達成しました。入水したのは昨年6月19日のようなので、入水時と同様、色変は半年以上ぶりということになります。 まだかなり水色とのボーダー上ですが、備忘録ということで。 入水したときから今ま…