Rustコトハジメ

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

LeetCode

W180: D「Maximum Performance of a Team」a[i]の和かけるb[i]の最低値のtop k最大値

問題 長さnの数列a[i]とb[i]が与えられる。 k個のiを選んだ時、sum(a) * min(b)を最小化せよ。 制約: n=105, a=105, b=108, 1<=k<=n 解法 上位kだとよくあるのは優先度キューで上位k個を保持するというアルゴリズムだけどこれは違う。 sum(a)の上位k個を選ん…

W126: D「Minimum Cost To Merge Stones」区間DP。逆構築の手順からDPの式を導く

激ムズだと思うんだが。ディスカッション見てもわからないし、LeetCodeで今まで見た中で一番むずいと思う。kmjpさんが「9点にしては簡単だね」って言ってて、どうなってんだと愕然。 https://leetcode.com/contest/weekly-contest-126/problems/minimum-cost…

W136: D「Longest Duplicate Substring」単調性に注目してにぶたん

しばらくわからなかった。 https://leetcode.com/contest/weekly-contest-136/problems/longest-duplicate-substring/ 問題 長さnの文字列sが与えられる。 このうち、長さlの部分文字列が2回以上登場するとする。 lの最大値はいくつか? 制約: n=105 解法 ま…

W178: D「Minimum Cost to Make at Least One Valid Path in a Grid」最短路問題への帰着。Dijkstra Solution

問題 こんな感じのグリッドが与えられる。 矢印の向きを一回変えるのを1コストとして、最小手数でゴールにたどり着いてください。 制約: h,w=100 We have a grid like this and your goal is to make a path that flows from the upper-left to the bottom-r…

W141: D「Shorted Common Supersequence」LCSからまず考える

https://leetcode.com/contest/weekly-contest-141/problems/shortest-common-supersequence/ 問題 長さn,mの文字列s1,s2が与えられる。 文字列sであり、s1,s2を部分列として含むもののうち最短のものを構築せよ。 制約: n,m=1000 解法 sの長さはどう考えて…

W135: C「Minimum Score Triangulation of Polygon」三角形の切りとり方の工夫

6点なのにリアルわからなかった。絶望。 https://leetcode.com/contest/weekly-contest-135/problems/minimum-score-triangulation-of-polygon/ 問題 n角形が与えられる。それぞれの点については反時計方向にA[i]の値がつけられている。 このn角形をn-2個の…

W145: C「Longest Well Performing Interval」1,-1列の中で区間和がk以上の最長区間を探す

一般化してアルゴリズムを覚えておくと良いと思った。 https://leetcode.com/contest/weekly-contest-145/problems/longest-well-performing-interval/ 問題 0,1の列が与えられる。1がstrictに過半数以上を占めるのうち、最長の長さはいくつか? 制約: n=104…

W146: D「Maximum of Absolute Value Expression」絶対値がなぜ外せるか

AtCoderでも似たような問題を見たことがあるけど正直理解してなかった。 問題 数列A,Bが与えられる。 |A[i]-A[j]| + |B[i]-B[j]| + |i-j| の最大値を求めよ。 制約: n=4*104 解法 O(n2)解法はダメ。 こういう時の定石は、絶対値を外すために、 |a-b|はa-bかb…

W177: D「Largest Multiple of Three」余分なものを取り除く

https://leetcode.com/contest/weekly-contest-177/problems/largest-multiple-of-three/ 問題 0-9の数列が与えられる(長さn)。 この中から数字を選び、3の倍数となるような最大の数を作りなさい。 制約: n=105 解法 桁和が3の倍数は明らか。 そこでコンテ…

W150: D「Last Substring in Lexicographical Order」Suffix Array

Suffix Arrayを使うだけ問題です。verify 問題 長さnの文字列が与えられる。 このうち、辞書順でもっとも後ろにある部分文字列は何か? 制約: n=105 解法 Suffix Arrayのアルゴリズムでは、 SA[i] := 辞書順でi番目(0-indexed)の文字列は、前からSA[i]削除…

W153: D「Make Array Strictly Increasing」夏休み型DP

実装してないです。夏休み型DPではないかな? 問題 数列aと数列bが与えられる。 あなたは、i,jを選択肢、a[i]=b[j]という代入をいくらでも行うことが出来る。 これによってaを狭義単調増加にする最小手数を求めよ。 制約: n=2000 解法 LISは、しっぽだけが重…

W176: D「Construct Target Array With Multiple Sums」構築手順を逆に考える

問題 長さnの[1,1,1...]列からスタートして、 合計を計算する 数列のうち1つをその合計で置き換える という操作を繰り返して、特定の数列にたどり着けるか判定せよ 制約: n=5*104, ai=109 解法 順序は関係ないことは明らか。 ターゲットを[3,5,9]としよう。…

W175: D「Maximum Students Taking Exam 」二部グラフの最大独立集合。No Cheatingの小さい版

https://leetcode.com/contest/weekly-contest-175/problems/maximum-students-taking-exam/ 問題 mxnグリッドに椅子がいくつか置いてある。生徒は、斜め前と真横の計4箇所はカンニング出来る。 どの生徒もカンニング出来ぬように生徒を椅子に座らせる場合、…

W159: D「Maximum Profit in Job Scheduling」

方針は瞬見えするので、あとは実装をいかにバグりにくくするかの問題。 https://leetcode.com/contest/weekly-contest-159/problems/maximum-profit-in-job-scheduling/ 問題 セグメント[l,r), p が与えられる。これらのセグメントをオーバーラップしないよ…

W158 D:「Maximum Equal Frequency」

データ構造を持ってたどる系。 https://leetcode.com/contest/weekly-contest-158/problems/maximum-equal-frequency/ 問題 長さnの数列が与えられる。このうち、長さLのprefixをとり、その中からたった1つの要素を削除する。この時、prefixの中に存在する数…

W160 D: 「Tiling a Rectangle with the Fewest Squares」

https://leetcode.com/contest/weekly-contest-160/problems/tiling-a-rectangle-with-the-fewest-squares/ 問題 nxmの領域を正方形で埋めたい。最小で何個の正方形を使えばよいか? 制約: n,m=13 解法 バックトラッキングして探索すればよい。 まだ使ってな…

W161: D 「Check If It Is a Good Array」

https://leetcode.com/contest/weekly-contest-161/problems/check-if-it-is-a-good-array/ 問題 長さnの数列が与えられるから、その中の部分列に対して、それぞれ適当な数をかけたあとに全部足して1にすることが出来るか判定せよ。 解法 作り方を考えます。…

W162: D「Maximum Score Words Formed by Letters」

https://leetcode.com/problems/maximum-score-words-formed-by-letters/ 問題 n個のワード (n=14) m個の文字 各アルファベットの得点 >= 0 が与えられる。あなたは文字を使っていくつかのワードを作り、含まれてる文字の総得点を最大化したい。 解法 第一感…

W163: D「Minimum Moves to Move a Box to Their Target Location」

わかったような気がするので解法だけメモる https://leetcode.com/contest/weekly-contest-163/problems/minimum-moves-to-move-a-box-to-their-target-location/ 問題 mxn迷路がある。プレイヤーははじめsにいて、boxをtに運んでいきたい。しかしプレイヤー…

W174: D「Jump Game V」

https://leetcode.com/contest/weekly-contest-174/problems/jump-game-v/ 問題 長さnの数列aと整数dが与えられる。 インデックスiからjは、forall a[i+1,j] < a[i] かつ j-i<=dの時にジャンプ出来る。i,jを逆にしても同様。 出発地点を選べるとして、訪れる…

W165: D「Palindrome Partitioning III」

Hard(6)のわりには苦戦。 問題 長さnの文字列と整数kが与えられる。 この中でcnt文字を任意に変更し、その後文字列をk分割した時に、すべての部分文字列が回文になってるようにしたい。 min{cnt}を求めよ。 制約: n=100 解法 解法がなかなか思いつかなかった…

W166: D「Minimum Number of Flips to Convert Binary Matrix to Zero Matrix」

https://leetcode.com/contest/weekly-contest-166/problems/minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix/ 問題 01で埋められたmxn行列が与えられる。あなたはi,jに対して操作する時、そのマスと、存在する隣接マスを01フリップする。…

W168: D「Maximum Candies You Can Get from Boxes」

https://leetcode.com/contest/weekly-contest-168/problems/maximum-candies-you-can-get-from-boxes/ 問題 これは好き。 頂点数nの木が与えられる。 各頂点には、 open: bool keys: [usize](鍵があると、open=falseの頂点にたどり着いた時に、そこを開け…

W173: D「Minimum Difficulty of a Job Schedule」

https://leetcode.com/contest/weekly-contest-173/problems/minimum-difficulty-of-a-job-schedule/ 問題 数列Aをd個に分割したい(d-1本の分割線を入れる。1つのグループは長さ1以上) この時の評価値を各グループの最大値の和とする。これを最小化せよ。 …

B18: D「Reverse Subarray To Maximize Array Value」

https://leetcode.com/contest/biweekly-contest-18/problems/reverse-subarray-to-maximize-array-value/ 問題 32bitの整数列が与えられる。この値をsum(abs(a[i]-a[i+1]))と定義する。 整数列の部分列を前後反転させて、この値を最大化せよ。 解法 こうい…

W170: D「Minimum Insertion Steps to Make a String Palindrome」

https://leetcode.com/contest/weekly-contest-170/problems/minimum-insertion-steps-to-make-a-string-palindrome/ 問題 文字列sが与えられる。この文字列に対して任意の文字の挿入を何度か行い、回文にしたい。 最小回数は何回か? 制約: |s|=500 解法 ど…

B17: D「Distinct Echo Substrings」ロリハ

問題 文字列sが与えられる。この中に、XX(Xは文字列)の形になってる箇所を見つけ、Xの種類数を答えよ。 制約: |s|=2000 解法 |s|=2000なのでロリハを使って2乗コードで落としに行くのが第一感。テストが甘いのか、それで通ります。 実装 impl Solution { p…

W171: D「Minimum Distance to Type a Word Using Two Fingers」

https://leetcode.com/contest/weekly-contest-171/problems/minimum-distance-to-type-a-word-using-two-fingers/ 問題 キーボードが与えられて、文字間の移動には距離が定められている。 あなたは右手と左手の一本ずつ合計2本の指でタイピングをするが、与…

W172: D「Minimum Number of Taps to Open to Water a Garden」

https://leetcode.com/contest/weekly-contest-172/problems/minimum-number-of-taps-to-open-to-water-a-garden/ 問題 0からnまでの座標上にセグメントがn個ある。 すべての点を被覆する最小個数のセグメントを求めよ。 制約: n=104, セグメント長=100 解法…