Rustコトハジメ

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

tokio::fsはただspawn_blockingしてるだけ

tokio::fsはファイルシステムの操作をasyncにして提供するライブラリなのだが、ファイルシステムの操作はシステムコールを呼んでいるためブロッキングである。これをどうやって非同期に偽造してるかというと、 // 例としてread pub async fn read(path: impl…

Futureのselect!マクロ

async fn task_one() { /* ... */ } async fn task_two() { /* ... */ } async fn race_tasks() { let t1 = task_one().fuse(); let t2 = task_two().fuse(); pin_mut!(t1, t2); select! { () = t1 => println!("task one completed first"), () = t2 => pri…

なぜFuture::pollはPinをとるのか?

Futureトレイトはこのような形をしている。 trait Future { type Output; fn poll( // Note the change from `&mut self` to `Pin<&mut Self>`: self: Pin<&mut Self>, // and the change from `wake: fn()` to `cx: &mut Context<'_>`: cx: &mut Context<'_…

ECR50: F「Relatively Prime Powers」

かなり難しい数学問題。ラフな解法のみ。 問題 xを因数分解した時、指数部分のGCDが1である場合、この数をエレガントと呼ぶ。 2からnまでの数字の中でエレガントな数は何個あるか? 制約: n=1018 解法 まず、指数部分のGCDが2であるというのはどういう状況か…

オイラー関数関連

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

ABC160: F「Distributing Integer」TDPC木の全方位木版

問題 n頂点の木が与えられる。 頂点kを根として、そこから隣接する頂点に番号を書いていく方法は何通りあるか? 全kについて答えよ。 制約: n=105 解法 考え方は、 rustforbeginners.hatenablog.com とほぼ同じ。 CumRLのために dp値 部分木サイズのfact 部…

CFR629 (Div. 3): E「Tree Queries」

解法はわかっていたのに、最後のところでミスってAC出来なかった・・・。最近、見えてたんだけど解けなかったが多い。 https://codeforces.com/contest/1328/problem/E 問題 n頂点の木が与えられる。 m個のクエリk v1 v2 ... vkが与えられる。 各クエリにつ…

みんプロ2018 決勝: A「Uncommon」互いに素であることと約数包除の関係性を問う問題

問題 n個の整数a[i]が与えられる。 1からmまでの各整数xについて、 f(x) = xはa[i]の中でf(x)個と互いに素である を求めてください。 解法 a[i]と互いに素であることを言うには、a[i]の素因数を抽出して(せいぜい10個程度)、そのどれも持ってないことをい…

ECR50: C「Classy Numbers」桁DPを教義的な方法でやってみる

https://codeforces.com/contest/1036/problem/C 問題 L <= x <= Rのxの中で、10進数で表した時に1-9の数字が3個以下のものは何個あるか? 制約: L,R=1018 解法 明らかに桁DP。 桁DPを書くなら再帰で書くのが楽だと思う。 桁DPだと以前にやったことを繰り返…

典型DP: M「家」TSP + ダブリング

https://atcoder.jp/contests/tdpc/tasks/tdpc_house 問題 高さH、1つの階にある部屋は16個の建物がある。すべての階は同じ構造をしている。 あなたは(1,1)から(H,1)にたどり着きたいが、移動方法は以下の制約がある。 同じ部屋をたどることは出来ない 部屋i…

典型DP: N「木」経路数と倍率

https://atcoder.jp/contests/tdpc/tasks/tdpc_tree 問題 頂点nの木が与えられる。 この木を構築する手順のうち、常にグラフが連結であるものはいくつあるか? 制約: n=1000 解法 各点から始める場合で足し合わせて、最初に書く辺に重複があるから2で割るこ…

立体の経路数

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

ECR84: D「Infinite Path」順列内のサイクルをk飛ばしで調べる

全くピンとこなかった。 https://codeforces.com/contest/1327/problem/D 問題 長さnの順列pと、各順列に対する色c[i]が与えられる。 pk[i] = p[p[p[p.....[i]] で定義する順列を考える。 無限ループの中がすべて同じ色となるような最小のkはいくつか? 制約…

ECR84: E「Count The Blocks」よく見りゃただの数え上げ・・・

難しく考えすぎて破綻した。DPしか見えなかった。 https://codeforces.com/contest/1327/problem/E 問題 nが与えられる。長さnの数(先頭は0埋め)をすべて考える。 このうち、同じ数がi回連続する箇所の総数を、全iについて求めよ。 解法 挿入DPみたいな感…

典型DP: L「猫」ふつうのDP。3乗だが実際には通る

これより前の問題の方が遙かに難しいと思う。 https://atcoder.jp/contests/tdpc/tasks/tdpc_cat 問題 猫がn匹をこの順番に並べたい。 猫iと猫jを距離1以下に配置すると、あらかじめ与えられるf[i][j]が得点として得られる。 猫間の距離を工夫して得点を最大…

ECR51: F「The Shortest Statement」パス長の組み合わせ系

ダイクストラやワーシャルフロイドで距離を求めてから組み合わせて何かの解を出すというのはよくあります。 https://codeforces.com/contest/1051/problem/F 問題 n頂点m辺の無向重みつき連結グラフが与えられる。 q個のクエリui,viが与えられた時、ui,viの…

典型DP: K「ターゲット」セグメント化してLIS

自力でわかりそうでわからない問題だった。精神がやられる。 K - ターゲット 問題 中心(xi,0)、半径riの円がn個与えられる。 strictに包含関係にある円の列のうち、最大長はいくつか? 制約: n=105 解法 まず、y方向は関係ないため、セグメントの問題に帰着…

No.1013: 「○マス進む」せっかくなのでダブリングの抽象化をしようか

せっかくなのでダブリングの抽象化をしました。 https://yukicoder.me/problems/no/1013 問題 長さnの順列p[i] (1,2,3,4...,n)が与えられる。これを無限につなげたすごろくを行う。 初期位置が先頭から0番目からn-1番目のとき、k回サイコロを振ったあとの位…

No.1011: 「Infinite Stairs」多項式解法でも解いてみる

https://yukicoder.me/problems/no/1011 問題 最初に0段目にいて、一回の試行ごとにi+1,...,i+dにジャンプすることが出来る。 n回試行したあとにk段目にたどり着くパスは何通りあるか? 制約: n,d=300, k<=n*d 解法 DP高速化 もっともふつうの考え方は、ある…

典型DP: J「ボール」期待値の最善を選択する

https://atcoder.jp/contests/tdpc/tasks/tdpc_ball 問題 座標0から15にいくつかものが並んでいる。 あなたはボールを投げてこれらのものを全部破壊したい。 しかしあなたがボールを座標xに向かって投げると、x-1,x,x+1の地点に等間隔で落ちてしまう。 全部…

典型DP: H「ナップザック」局所的には桁DPみたいなもの

重さと色に制限があるナップザック。 https://atcoder.jp/contests/tdpc/tasks/tdpc_knapsack 問題 n個の商品があり、重さwi,色ci,価値viである。 重さをW以下、使った色の数をC以下となるようにした時、最大の価値和はいくつか? 制約: n=100, W=10000, C=5…

ECR53: D「Berland Fair」考察すると計算量はnlogn回系

以前に同じような話があったため、またたぶんnlogn系だと思って解いたけど、確信は持てなかった。 https://codeforces.com/contest/1073/problem/D 問題 長さnの円状に店が並んでいて、各々a[i]円の品を売っている(ストックは無限にある)。 あなたは最初T…

典型DP: G「辞書順」辞書順とは何かが問われている

https://tdpc.contest.atcoder.jp/tasks/tdpc_lexicographical まじでわからなかった。怪しい方針で進めておかしいことに気づき、解法ブログを読んだけど皆目わからずという状態。辞書順というものがそもそもピンと来てなかった模様。 そういえばこの前はこ…

ECR54: E「Vasha and a Tree」クエリ先読み + DFS

https://codeforces.com/contest/1076/problem/E 問題 n頂点の木が与えられます。ルートは1。頂点の値は0で初期化されています。 k-subtree of xとは、xを頂点としたサブツリーの中でxから距離kのものをいいます。 クエリがm個与えられます。クエリは、 di-s…

典型DP: F「準急」移動制限つきDPは終点から見て経路を絞る

https://tdpc.contest.atcoder.jp/tasks/tdpc_semiexp 難しすぎ。理解だけ書きます。 問題 n個の駅がある。 このうち、電車は1とnに止まることは決まっているが、その間は適宜飛ばしてもよい。 しかし、k個連続で止まることは許されない。 n個目の駅につくま…

ECR55: E「 Increasing Frequency」累積和の和は別の形で言い換えてみる

https://codeforces.com/contest/1082/problem/E 問題 長さnの数列と整数cが与えられる。 この中のうち、(l,r)をとり、 [0,l)の中のcの数 [l,r)の中の出現頻度最大 3 [r,n)の中のcの数 の和を最大化せよ。 制約: n=105 解法 l,rを全通り試すとそれだけでもO(…

典型DP: D「サイコロ」素因数分解で可能性を絞る + DP

素因数分解して、実はその構成要素が少ないという特殊性に着目した解って結構ある気がする。 D - サイコロ 問題 サイコロをn回振った時に積がDで割り切れる確率を計算せよ。 制約: n=100, D=1018 解法 誤答例としては、dp[i] := 積がi (mod D)となるような確…

CFR596: D「Power Products」素因数分解のマッチング問題

https://codeforces.com/contest/1247/problem/D 問題 長さnの数列aと正整数kが与えられる。 a[i],a[j]のペアであって、xkの形で表されるものの個数を求めよ。 制約: n=105, ai=105 解法 初手は素因数分解。素因数の次数和が全部kの倍数になるものを探せとい…

CFR596 (Div. 2): C「p-binary」初手は自明なのでその後

https://codeforces.com/contest/1247/problem/C 問題 初手でkpという定数分を引いて、それが実現可能か調べるという方針は自明。ここからがわからなかった。 c0 20 + c1 21 + ... + cm 2m = n-kp c0 + c1 + ... cm = k を解け。 制約: n=109, |p|=1000 解法…

CFR628 (Div. 2): E「Ehab's REAL Number Theory Problem」各数字をたかだか2つの素数に落とす

https://codeforces.com/contest/1325/problem/E 問題 長さnの数列aが与えられる。各要素はたかだか7個の約数しかもたない。 要素の積が平方数となるような最短の部分列長を求めよ。 制約: n=105, ai=106 解法 約数が7ということを利用したい。 まず明らかな…