Rustコトハジメ

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

AtCoder

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

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

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

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

典型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で割るこ…

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

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

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

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

典型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…

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

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

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

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

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

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

E「Three Substring」ずらして全探索

https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_e 問題 長さA,B,Cの文字列SA,SB,SCが与えられる。 これらはある文字列Sの部分列のうち、いくつらかを?に置き換えたものである。 元の文字列の長さの最小値を求めよ。 制約: A,B,C=2000 解法 …

典型DP: O「文字列」挿入DP

https://tdpc.contest.atcoder.jp/tasks/tdpc_string 問題 アルファベット各文字cがたかだか10個(0<=freq[c]<=10)与えられる。 これらを 同じ文字は隣り合ってはならない という条件を満たした文字列はいくつあるか? 解法 参考: http://garnacha.techblog.j…

典型DP: N「イウィ」区間DPの基本形

https://atcoder.jp/contests/tdpc/tasks/tdpc_iwi 問題 iとwだけで構成された長さnの文字列が与えられる。 あなたは連続した文字列iwiを取り除くという操作を許されている。 最大で取り除ける文字数は何文字か? 制約: n=300 解法 なにかしらの結合で部分列…

教育DP: N「Slimes」区間DP。マージの逆向きを考えてDP式を作る

今見るとずいぶん簡単。 https://atcoder.jp/contests/dp/tasks/dp_n 問題 n体のスライムがいる。 隣合う2つのスライムを併合することが許されて、その時にa[i]の和がコストとして加算される。 全スライムを1体に併合する時に、最小コストはいくつか? 制約:…

ARC008: D 「タコヤキオイシクナール」二値のセグ木

D - タコヤキオイシクナール のちに rustforbeginners.hatenablog.com にオマージュされるという伝説の名問。ぶっちゃけ今の水準からすると簡単だが、面白いので書いておく。 問題 ベルトコンベアにn台の機械がある。機械iは、入力xに対してa[i] x+b[i]を出…

ABC158: E 「Divisible Substring」Zero-Sum Rangesに帰着する

https://atcoder.jp/contests/abc158/tasks/abc158_e 問題 n桁の数字が与えられる。 この中の区間[i,j)のうち、素数pで割り切れるものの個数はいくつか? 制約: n=105 解法 区間を考える時、累積和っぽいものを考えるのは定石。(ライツアウト系でもよくある…

AGC023: A 「Zero-Sum Ranges」累積和のペアを探す基本アルゴリズム

最近のABC-Eの基礎となってる問題らしいので、吟味したい。 問題 長さnの数列が与えられる。このうちの空でない部分列であって、和が0のものの個数は何個か? 制約: n=105 解法 累積和Sを求めて、[i,j)の和が、S[j]-S[i]で求まるようにすると、その累積和上…

ABC155: F「Perils in Parallel」01列のフリップは累積和で考える

https://atcoder.jp/contests/abc155/tasks/abc155_f いくつかの問題が組み合わさっているので、分解して考えます。 問題 長さnの01列aがある。 セグメントiは[li,ri]をフリップする。 長さnの全0列bにいくつかのセグメントを適用して、a=bとせよ。 制約: n=…

ABC150: F「Xor Shift」XOR上で差分列を探す

問題 長さnの数列a,bが与えられる。 b[i] = a[(i+k) % n] ^ x となるようなk,xのペアを列挙せよ。 制約: n=105 解法 とりあえずmodを解消するためにaaと並べて、その中で何かのパターンを探す問題だろうとアテをつける。 やりたいことは、 こんな感じで、bに…

ABC157: F「Yakiniku Optimization Problem」k個の円に包含されている点の候補を全列挙する

問題 平面上にたくさんの焼き肉(xi,yi,ci)が置いてある。 あるx,yに火を置いた時、焼き肉は、ci * dist*1で焼き上がる。 k個の焼き肉を焼くための最小時間はいくつか? 制約: n=60 解法 どのポイントに置いても、時間を伸ばせば焼ける肉の数は増えるはずなの…

ABC151: F「Enclose All」中心となりうる点を全探索

https://atcoder.jp/contests/abc151/tasks/abc151_f 幾何問題。 問題 n個の点が与えられる。 これらを包含する最小の円の半径を求めよ。 制約: n=50 解法 求める円を考えた時には、その円は、 3点の外接円である 2点を直径とする円である のどっちかである…

ABC154: F「Many Many Paths」Combinationの足し合わせ

F - Many Many Paths 問題 グリッド上で右と上しか動けない制約において、(0,0)から(r,c)に到達するパスをf(r,c)と置く。 sum[r1<=i<=r2][c1<=j<=c2]{ f(i,j) } を求めよ。 制約: r1,r2,c1,c2=106 解法 f(i,j) = C(i+j,i)は良い。 これを2乗オーダーで足し合…

ABC155: E「Payment」ナップザック型

これが桁DPかどうかということがツイッターで少し話題になってるけど、おれは桁DPとは言わないと思う。 E - Payment 問題 この国には、1,10,100,1000,...,10100円札しかない。 10進法で10n長の価格のものを買う時に、払う枚数とお釣りの枚数の合計の最小値は…

ABC155: D「Pairs 」

むずい。ついにこれがDになるまで高騰してしまったかという感じ。 かなりストレートフォワードな解法を書きましたが、TLEだらけになったのと、なぜか2WAしました。すごく間違ってるとは思わないです。 D - Pairs 問題 長さnの数列aが与えられる。 n(n-1)個あ…

ABC150: E「Change a Little Bit」

Eにしてはかなり難しく感じた。 E - Change a Little Bit 問題 長さnの01列S,Tがある時、そのコストf(S,T)を、 あるビットiを変更する時、その時のコストは、Ci*k (kはその時にビットが異なる個数) の総和の最小値で定義する。 あらゆるS,Tの組み合わせにつ…

ABC152: F「Tree and Contraints」包除原理

F - Tree and Constraints 問題 N頂点の木が与えられる。辺は白か黒で塗る。 M個の制約が与えられる。(ui,vi)は、ui-viパスの中に黒色の辺が含まれていることを示す。 すべての制約を満たす色付けは何通りあるか。 制約: N=50, M=20 解法 最初見た時はセグメ…

ドワ6予選: B「Fusing Slimes」確率の積み重ね

B - Fusing Slimes 問題 スライムがN体いて、位置はXiである。 i回目の試行では、[1,N-i]のスライムjを1つ選んで、右横にあるスライムの位置に動かして、合体させる。この時、Xi-Xjが移動距離となる。 移動距離の期待値に(N-1)!をかけたものを求めよ。 解法…

ABC149: E「HandShake」FFT or カラツバ

E - Handshake 問題 長さNのAiが与えられる。これが1ペア用意され、2Nの頂点に合計N2の辺が張られる。 ある辺i,jを選ぶと、得点Ai+Ajが手に入るとする。 M個の辺を選ぶ時、最大の得点はいくつでしょうか? 制約: N=105, M=N2, Ai=105 解法 値xが何個あるかを…

ABC149: F「Surrounded Nodes」全方位木DP

全方位木DPを使って実装してみた。 F - Surrounded Nodes 問題 木が与えられる。はじめ、ノードは白色に塗られている。 いくつかのノードを黒に塗った時、すべての黒ノードを繋いで作られるサブツリーのうち、白色ノードの数を穴空き度と呼ぶことにする。 サ…