Rustコトハジメ

Rustで競技プログラミングをやる人の覚書のようなものです。

競技プログラミング

オイラー関数関連

x以下でxと素なものの個数 これはオイラー関数で求まる。xの素因数をp1,p2,..pkとして、x(1-1/p1)(1-1/p2)...(1-1/pk) 既約分数との関係(言い換え) これは、 1/x,2/x,...,x/xの中で「既約分数」の個数を求めてるのと同じこと。 x以下でxと素なものの和 例…

立体の経路数

平面の場合、HxWのグリッドを(1,1)から(H,W)まで行く経路数は、C(H+W,H)である。 これは、H+WのうちH個をxに書き換えるという意味ととらえると理解出来る。 しかしこの考え方だと、2次元から3次元、さらにn次元に拡張した時に通用しない。 そこでこれを(H+W)…

xor系の問題で扱われる性質

交換則: x xor y = y xor x 打ち消し: x xor y xor y = x 繰り上がり表現: x + y = x xor y + 2 x&y xorはmod 2と同じ: x xor y = x+y (mod 2)

高度合成数

まず約数の個数は、素因数分解した時に n = 2a + 3b + ... cnt = (a+1) * (b+1) ... である。 a[i]の値域に対して、最大で約数がどのくらいあるかを知っていると役立つことがある。自分より小さな数に、自分より約数の多い数が存在しない数のことを高度合成…

幾何の性質(内接円系)

https://codeforces.com/contest/1096/problem/C で出た。知識があるなら問題自体は難しくない。 円周角は中心角の半分 円周角はどこも等しい 内接四角形の対角の和は180 内接四角形の対辺の積の和は、対角線の積に等しい(トレミーの定理) 問題では1と2を…

重複あり組み合わせの図解

重複あり組み合わせ(nHr)というのはこういうことです。 n個のボタンがあります。あなたはこのうちの1つを選択して押すをr回行います。一回押すごとに、ボタンに書いてある数字は1上がります。終了後、ボタンに書いてる数字の組み合わせは何通りあるか? r…

素数の個数

xにはたかだかlog x程度の素因数しか含まれていない 種類を最大にしようとxを素因数分解した時、よくて2x3x5x7...だからこれは2x2x2x2...より大きくなり、log xより少ないことがわかる。 具体的にいうと、 105: 2x3x5x...x17=510510でたかだか7個程度 109: 2…

HL分解ライブラリのAPI

いつも忘れるので忘備録的に書いておきます。 HL分解では、出来るだけ長い直線のパスをとっていき、順にvid(virtual id)というのをつけていきます。このvidは直列化されるため、セグメント木などを使うことが出来ます。 HL分解では、あるパスu-vを指定した…

逆数の和

1+1/2+1/4+.. 1+1/2+1/4+...は2。Sとおいて二倍した2+1+1/2+1/4+...との差分ととればよい。 1乗 とてもゆっくり無限大に発散するが、大体logn程度である。 2乗 mathtrain.jp pi2/6に収束する。2で上限出来ると覚えておけば実用上問題がない。 2で上限出来る…

ユークリッドの互除法

ユークリッドの互除法に関する性質を列挙する。 GCD(x,y) = GCD(x+y,y) = GCD(x-y,y) GCD(x,y) = x <=> xはyの約数

LCMはOR、GCDはANDのようなもの

ORというのは各桁について、「大きい方をとっていく」という操作だと理解出来ます。またANDというのは、逆に「小さい方をとっていく」という操作だと理解出来ます。 素因数分解x=2p2 3p3 5p5 ...を[p2,p3,p5,...]のようにビット列と同様に見ると、 x,yのLCM…

組み合わせ問題を多項式で考える記事を自分なりに理解

maspypy.com 今日はコンテスト修業をやめて、数学野郎のmaspyさんの記事を読んだ。読むのには3時間くらいかかったので、再度読み直す時のためにおれの理解を書いておく。 何がポイントか このアプローチは、状態と遷移をベクトルで表している。ベクトルは、…

GCD系の問題で扱われる性質

GCD系の問題は多いですが、扱ってる性質はあまりないような気がします。見つけ次第列挙していきます。 N/xの種類はせいぜいsqrt(N)個である 109の約数の数は高々1344個である。735134400 A1とA2のGCDは、A1の約数とA2の約数のうちどれかである GCD(a,b) * LC…

グラフの問題で扱われる性質

競プロでよく扱われるグラフの性質についてまとめることにします。 二部グラフ 奇サイクルが存在しない 白黒で塗り分けることで判定可能 白頂点と黒頂点の数をW,Bとした時、M=WB 完全グラフ すべての頂点間に辺があるグラフのこと M=N(N-1)/2 木 次数3以上の…

【AtCoder】Restoring Road Network:真の最短路を見つける

エディトリがガバガバだと思いました。 D - Restoring Road Network 問題 n点のグラフについての全点最短距離が与えられる。 この最小距離を実現する最小のグラフを再構築しなさい。 制約: n=300 解法 まず、その全点最短距離が正常で、グラフが存在する場合…

【AtCoder】3N Number:方針は左右に分割するだけ。実装の工夫が必要

D - 3N Numbers 問題 長さ3nの数列aiが与えられる。 このうちn個を落とし、残った2nのうち、左nの和-右nの和を最大化しなさい。 制約: n=105 解法 どこかで切って、左のmax n個と右のmin n個を選ぶという方針は超典型。似たような話としては、ボールの色分け…

【AtCoder】井井井:総和を求める系。式変形が重要

D - 井井井 / ### 問題 n本のx罫線とm本のy罫線が与えられるから、中にある全長方形の面積総和を求めなさい。 制約: n,m=105 解法 超ナイーブに考えると、O(n2m2)で永遠に終わらん。 第一感、こういう系統はまず「その小さな長方形が総和について何回カウン…

【AtCoder】Managerie:前2つを決めると自動的に決まる

D - Menagerie 問題 長さNの円環状に羊と狼が並んでいます。i番目の動物に「あなたの隣の2匹は同じ種類ですか?」と問います。羊は常に本当の事を良い、狼は常に嘘をいいます。つまり、羊がoというのであれば、両側は羊羊か狼狼であり、xというのであれば、…

【AtCoder】An Ordinary Game:最終形に着目する

atcoder.jp 問題 文字列sが与えられる。隣り合った文字は異なる。 終端以外の文字を取り除く。この時、取り除いたあとにも、隣り合った文字が異なるようにしないといけない。 先手後手で文字を取り除いていくとき、どちらが勝つか? 解法 Grundy数を考えるの…

【AtCoder】Travel by Car:ワーシャルフロイド法の応用

E - Travel by Car 問題 N個の町があり、M本の道路が繋がっている。道路はAi,Biをつなぎ、長さはCiである。 車の燃料タンクはlであり、距離1進むごとに1消費する。町では、燃料タンクを満タンにすることが出来る。 車がsiからtiにたどり着くために必要な給油…

【AtCoder】Rem of Sum is Num:インデックス差を累積和に埋め込む。ウェーブレット行列で解ける

E - Rem of Sum is Num 問題 長さNのAiと整数Kが与えられる。 この中の部分列で、長さが和%Kに等しいものの個数を求めよ 解法 例題で考えます。K=4 [1,4,2,3,5]という配列のうち、[4,2]が該当しますが、これは、累積和をとって、[0,1,5,7,10,15]とすると、7-…

【AtCoder】ABC146

Cは109を9桁と勘違いして、3タコしたが、順位的にはあまり意味がなかった模様。Dは入次数最大までしか色を使わなくていいということは明らかだが、コードを書くのに戸惑った。再帰で色を塗っていったり、求められてる形式で出力するのがただめんどくさいだけ…

【AtCoder】DISCO presents ディスカバリーチャンネル コードコンテスト2020 予選

ファック。Cが解けなかった。 自分の解法でなぜTLEするのかよくわからず、時間が溶けてそのまま3000人中2200位で終わった。 他の人の解法を見ると、横方向でスイープして、上下方向に伝搬させるというアルゴリズムで解けそう。思いつかなかったおれが悪いと…

【AtCoder】Common Subsequence:ユニークネスはしっぽで決める

E - Common Subsequence 問題 長さN,Mの数列Si,Tiが与えられる。 これらの等しい部分列の個数を数え上げよ。 制約: N,M=103 解法 どうやれば独立に数え上げられるか考えると、Si=Tiで、i,jまで使ったものの個数なら独立とわかる。この考え方は大変頻出。 あ…

【AtCoder】Roadwork:その工事現場で止まるとしたらいつ出発したか?イベントソートでやってみよう

E - Roadwork 問題 Q人の人がDiにX=0を出発して、時間ごとに1右に進む。 Xiでは、時間[Si,Ti)の間、工事が行われる。工事はN個計画されている。 工事に遭遇した時、人は歩むのをやめるとして、それぞれの人がどこまで歩けるか計算せよ。もし無限に歩ける場合…

【AtCoder】Cell Distance:マンハッタン距離総和問題。ある距離は何度カウントされるか?

E - Cell Distance 問題 n*mのマス目にk個の駒を置く。 駒の置き方全通りについて、各駒のマンハッタン距離の総和の総和を求めよ。 解法 典型問題。こういう問題や数え上げ系は、ある小さな要素が全体にどのくらい貢献するか?を考えるのが基本。というか競…

【yukicoder】数列圧縮:Treapの勝利

No.930 数列圧縮 - yukicoder 問題 長さNの順列が与えられる。 隣り合う数がx

【AtCoder】guruguru:遅延セグを使った別解を考える

E - guruguru 問題 長さNのaiが与えられます。1<=ai<=m 初期にa1にいてaiからai+1に移る時、 xに移ってから、1つずつ上げる 1つずつ上げる の2通りがありうる。ただし、mの次は1である(mod mということ) トータルのコストを最小化せよ。 制限: N,m=105 解…

【AtCoder】Ball Coloring

E - Ball Coloring 最大値だと大きい方と小さい方をいくつか集めてきてビット全探索すれば終わりそうですが、最小値だと700っぽくなる。解説の理解自体に2時間くらいかかりました。 問題 N個のペア(xi,yi) (xi<=yi)が与えられます。 それぞれを赤と青で塗り…

【数学的考察】Sum(nCk) = 2^n

この前おもむろに実装しておいたサブマスクを列挙する関数 impl Iterator for SubMasks { type Item = i64; fn next(&mut self) -> Option<Self::Item> { let old = self.smask; if old == 0 { return None } self.smask = (self.smask-1) & self.mask; return Some(old)</self::item>…