Rustコトハジメ

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

Codeforces

ECR50: F「Relatively Prime Powers」

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

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

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

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だと以前にやったことを繰り返…

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みたいな感…

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

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

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

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

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…

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(…

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ということを利用したい。 まず明らかな…

CFR628 (Div. 2): D「Ehab the Xorcist」

https://codeforces.com/contest/1325/problem/D 良問。mathforces 問題 xor(a) = u sum(a) = v を満たす数列aを構築せよ。 解法 まず、 x+y = x xor y + 2*(x&y) を考えると、「u>vはあり得ない」はいえる。 次に、mod 2で考えた時に、a+bとa xor bは一致す…

CFR628 (Div. 2): C「Ehab and Path-etic MEXs」木上のMEXは2以上にしかならない

https://codeforces.com/contest/1325/problem/C 木かパスグラフか(Roland論法) 問題 n頂点の木が与えられる。 n-1本の枝に0からn-2までの数字を書き、u-vパスのMEXの最大値を最小化せよ。 制約: n=105 解法 木であれば次数3以上のノードが存在する 存在し…

CFR554 (Div. 2): F「Neko Rules the Catniverse」

https://codeforces.com/contest/1152/problem/F1 問題 長さkの数列aを作りたい。ただし、 a[i]は1からnのどれか(重複はなし) 1<=a[i+1]<=a[i]+m を満たす。 制約: k=12,m=4,n=105 解法 やはり「挿入出来る箇所の個数を管理していく」という発想で行く。 1…

CFR627 (Div. 3): C「Frog Jumps」二分探索を実装すると泥沼

これもおれは異常解法をして実装がめちゃくちゃ大変になった。エディトリはエレ解。 https://codeforces.com/contest/1324/problem/C 問題 n+2個のマス目a[i]にRLが描かれていて、これはその地点にいるときにはR/L方向に[1,d]進むことしか出来ないことを意味…

CFR627 (Div. 3): B「Yet Another Palindrome Problem」回文となっている部分列を探す

自分の解法がめちゃくちゃ複雑で、エディトリの解法がエレガント。拍手! https://codeforces.com/contest/1324/problem/B 問題 長さnの数列が与えられる。数列の中の部分列(subsequence)に、長さ3以上の回文となるものは存在するか? 制約: n=5000, ai<=n…

CFR627 (Div. 3): F「Maximum White Subtree」全方位木DP

https://codeforces.com/contest/1324/problem/F 問題 頂点nの木が与えられる。頂点にはそれぞれ、白が黒が塗られている。 あるサブグラフについて、白い頂点と黒い頂点の数の差をf(G)とする。 ans(v) = max { f(G): Gはvを含む } を求めよ。 制約: n=105 解…

ECR69: D「Yet Another Subarray Problem」

丸一日かかった。 https://codeforces.com/contest/1197/problem/D 問題 数列と、kとmが与えられます。 部分列[l,r)の値は、sum(l,r) - k * ceil((r-l) / m)と計算出来ることにします。(長さ0の部分列は許容される) 部分列の値の最大値を求めよ。 解法 エ…

ECR68: E「Count The Rectangles」

https://codeforces.com/contest/1194/problem/E アイデアだけ書いておきます。 問題 水平、垂直の線分がたくさん与えられるから、その中で作られる長方形の個数を数えよ。 制約: n=5000 解法 n=5000なので二乗とlogくらいは許されそう エディトリの解法はセ…

ECR83: E「Array Shrinking」区間DP。消去したあとに何が出来るかが一意

https://codeforces.com/contest/1312/problem/E 問題 長さnの数列が与えられます。 あなたは、隣り合う2つの数字xをまとめて、1つのx+1に置き換えるという操作が出来ます。 最高で何回消せるでしょうか? 制約: n=500 解法 区間DPの考え方です。 イウィなど…

CFR626 (Div. 2): D「Present」桁ごとに決める。半分全列挙的な考え方で探索を行う(教育的な要素満載)

コンテスト中には解けなかったです。解けてる人もdiv.2では100人以下。難問ではないので、解けても良かったと反省。(解けてれば100位くらい) https://codeforces.com/contest/1323/problem/D 問題 長さnの数列aが与えられる。 xor { a[i] + a[j] for j > i…

CFR626 (Div. 2): B「Count Subrectangles」いもす法の等差数列拡張!?

https://codeforces.com/contest/1323/problem/B 結構難しいと思ったのだが、なんで2400人も解けてる?いもす法の等差数列拡張を使うのであれば、昨日のyuki-Fより難しいことになるのだが・・・。もしかしておれはやばいアプローチをしている!? 問題 長さn…

CodeCraft-20 (Div. 2): E「Team Building」埋まったポジションをビットで管理してDP

https://codeforces.com/contest/1316/problem/E 問題 n人の人がいて、それぞれ応援力aiと、ポジションjをした時の戦力s[i][j]が決められている。 p人のチームとk人の応援団を作り、応援力と戦力の和を最大化せよ。 制約: n=105, p=7 解法 aiについて降順で…

CodeCraft-20 (Div. 2): C「Primitive Primes」NTTではない。畳み込みのようすを線で結べばわかる

FFT、NTTすべて試して6タコして終了です。めちゃくちゃ時間吸われてD完遂出来なかった。(あと5分あれば・・・) 問題 n次の多項式aの係数と、m次の多項式bの係数が与えられる。 これをc[t]=sum(a[i]b[t-j])で畳み込んだ時、c[t]のうち素数pで割り切れないも…

CFR625 (Div.2): E「World of Darkraft: Battle for Azathoth」セグ木を使って二次元累積和の最大値を計算

https://codeforces.com/contest/1321/problem/E 概念的に二次元累積和を考えることは当然ですが、最善値を出せばよいという場合に高速化のしようがあるということで、汎用性の高い問題だと思いました。 問題 防御力xk,攻撃力yk,獲得ポイントzkのモンスター…

ECR56: G「Multidimensional Queries」絶対値の外し方を全探索

https://codeforces.com/contest/1093/problem/G 問題 k次元のベクトルがn本与えられる。 ベクトルの距離はマンハッタン距離で計算される。 あなたは以下のクエリに答えなければならない。 i番目のベクトルを置き換える 区間l,rの中で、もっとも遠い距離を計…

ECR56: D「Beautiful Graph」奇サイクルの存在チェックと二部グラフ

https://codeforces.com/contest/1093/problem/D 問題 n頂点m辺の無向グラフが与えられる。 この頂点に1 or 2 or 3を書いたあとに、各辺について、それが繋ぐ頂点u,vに書かれた和が奇数になるようにしたい。 そんな数字の書き方は何通りあるか? 制約: n=105…

CFR618 (Div. 2): E「Water Balance」区間平均を凸法の傾きと見る

https://codeforces.com/contest/1300/problem/E 問題 長さnの数列aiについて、あなたは、ある区間[l,r]をとってその平均を[l,r]に置き換える操作を無限回許される。 aiを辞書順で最小化せよ 制約: n=106 解法 まず、前から出来るだけ最小を作るように貪欲す…

ECR57: G「Lucky Tickets」多項式の掛け算 + ダブリング

見たことない。多項式の累乗は持っておいても良いかも知れない。 https://codeforces.com/contest/1096/problem/G 問題 長さnの数列を作りたい(leading 0はOK)。 ただし、前半n/2と後半n/2の和は同じにしたいのと、与えられたk個の数字しか使えない(0から…