Rustコトハジメ

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

yukicoder

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高速化 もっともふつうの考え方は、ある…

No.1008「Bench Craftsman」いもす法を等差数列に拡張する

コンテスト中にはまじでわからなかったが、解法を見たら明らかだった。しかし、コンテスト中に素でバグなく実装するのはまぁまぁむずいはず。そこでおれは、1次元いもす配列に等差数列を与える(通常は定数項のみ)ライブラリを実装し、二度と悲劇が起こらな…

No.1002「Twotone」木の重心分解

No.1002 Twotone - yukicoder 問題 n頂点の木がある。n-1本の辺には、1からkの数字が書いてある。 u,vパスのうち書いてある数字の種類がちょうど2個あるものを調べよ。 制約: n=105 解法 木の重心分解という概念がある。あるルートgと、サイズのn/2以下部分…

No.997「Jumping kangaroo」行列累乗

ぼんやりとしか見えずに、解けなかった。エディトリも理解不能だったが、はまやんさんのブログで理解した。 Jumping Kangaroo [yukicoder 997] - はまやんはまやんはまやん 問題 カンガルーが座標0にいる。 座標iWは白く塗られており、カンガルーは2つのiW,(…

No.995「タピオカオイシクナーレ」漸化式を解く

タコヤキオイシクナーレという問題を見たことがある気がします。タコヤキの方がおいしいと思いますが、問題としては良かったです。教育的です。 https://yukicoder.me/problems/no/995 問題 タピオカがN個ある。それぞれにbiの美味しさがある。 はじめ、ミル…

No.990「NxMマス計算(Kの倍数)」GCDはANDマスクのようなもの

https://yukicoder.me/problems/no/990 解けなかった・・・。 足し算の方はmod kで分類で終わりなので解けなかった掛け算の方だけ。 問題 NMマス計算を行う。 c[i][j] = a[i] * b[j] c[i][j]がKの倍数のマスの個数を求めよ。 制約: a,b,k=109, n,m=105 解法 …

No.951「1枚頼むともう1枚無料!」

No.951 【本日限定】1枚頼むともう1枚無料! - yukicoder コンテスト中にそれっぽいものは書いて、サンプルは全部通したんだけど穴があっていまいちうまく行かなかった問題。深めておいて損はない問題なので、時間をかけて解法を考えました。 問題 ピザがN…

No.949: 飲酒プログラミングコンテスト:教育的DP

実装が大変だった。解法自体は20分くらいではっきり見えた。 No.949 飲酒プログラミングコンテスト - yukicoder 問題 長さN+1のAi,Bjと長さNのDkが与えられる。(Ai,Biは広義降順) iとjを0,0から1つずつ上げていき、その都度Dk <= Ai+Bjを満たすDkを取り除…

No.948: 「Bomb VS Dush」

なぜDashじゃなくてDush?何か意味があるのか? No.948 Bomb vs Dush - yukicoder 問題 半径Rの円の上を半径rの円が角速度1で移動する。この時、一周してきてもとの円に「衝突」する時間と、それまでに通過した領域の面積を求めよ。 解法 AtCoderに出て少し…

No.947: 「ABC包囲網」たぶん浮動小数点でやろうとすると失敗する

ちょっとだけ手をつけてみたが、体調が猛烈に悪いため諦めます。 たぶん、方針が良くないです。 No.947 ABC包囲網 - yukicoder 問題 2次元平面上にN個の点が与えられる。(座標は整数) このうち、(0,0)を内部に含む組み合わせは何個あるか? 制約: N=103 …

No.946: 「箱箱箱」Grundy数を相互再帰で定義する

No.946 箱箱箱 - yukicoder 問題 箱がN個積まれています。それぞれAi個の球が入っています。 あなたは1ターンで、 箱をいくつか降ろして開封する 開封した箱のうち1つから、いくつか球を取り除く のどちらかが出来ます。 先手後手のどっちが勝ちますか? 解…

No.945: 「YKC饅頭」ポワロ、2つの解決法を示す

タイトルはオリエント急行殺人事件より。2つの考え方があります。 No.945 YKC饅頭 - yukicoder 問題 N個のマスとM個の操作(l,r,t)が与えられる。t=Y|K|C, 0<=l,r

No.994: 煎っぞ!

No.944 煎っぞ! - yukicoder 問題 長さNの数列Aがある。 今あなたは、隣合う2つの数字をマージすることが出来る。 数列のすべての要素を同じにする時の長さRの最大値を求めよ。 制約: N=105, Ai=102 解法 Ai=102がヒントになっている。 あるRにするとなった…

No.943: 「取り調べ」ビットDP

今の自分にとっては良い湯加減の問題でした。 No.943 取り調べ - yukicoder 問題 言わんとしてることはこういうことです。 N頂点の有向グラフが与えられる。 頂点iは、隣接しているすべての頂点に色が黒か灰に塗られた時に色を塗ることが出来る。 最初、すべ…

No.939: 「and or」桁DPの基礎問題

https://yukicoder.me/problems/no/939 問題 整数AとBが与えられる。 X and Y = A, X or Y = BとなるX<=Yの個数を数えよ。 解説 桁DPです。基本問題なので、しっかり書けるようにしておきたいです。前にも自作問題で考察しました。 rustforbeginners.hatenab…

No.933「おまわりさんこいつです」数字根

★1.5で出てたけど、あとになって★2に訂正された問題。無知識前提だと★3くらいはあると思うが。 No.933 おまわりさんこいつです - yukicoder 問題 数字がN個与えられる。 これらを全部足した上で、1桁になるまで桁和を計算し続けたあとの数字を求めよ。 数字…

No.929「よくあるボールを移動するやつ」

https://yukicoder.me/problems/no/929 プライオリティキューを使った典型問題です。ABCのDでも似たようなものが出たような記憶があります。 問題 N個の箱があり、ボールがBi個入っています。ボールの合計はN個です。 1回の操作で、ボールを1つ、隣の箱に移…