Leetcode 572-640 考察ラッシュ
概要
就活対策と典型力を鍛えることを目標にして、Leetcode Problem number 572-640のMedium, Hardの考察ラッシュをした。今の僕にとって解く価値があるのは、640, 639, 632, 630, 629, 621, 600。目的は考察であり、解けたと思ったら実装はしない方針で。
https://leetcode.com/problemset/all/
640. Solve the Equation
概要：+-しかない1元方程式を解いて
解法：実装ゲーだけど、こういうのって良い実装方法あるのだろうか。x見つけて後ろまで+-先頭が来るまでbackしてstrtointして、xと定数項をひたすら数えまくる。
639. Decode Ways II
概要：小文字のみからなる文字列sを想定する。sを、数字のみからなる文字列に「'a'->1, …, ‘z’->26」と一文字ずつ変換する。更に、一部の文字が消失し、どの数字なのかわからなくなっている箇所もある。そのような数字列を作る文字列sは何通りあるか。
解法：Ahoっぽいけど…こんなのDPでやるしかなさそう。でもすぐには遷移式が出てこない。
638. Shopping Offers
概要：商品がn(<=6)個ある。商品セットi(<110)は、p_i円で売っている（例：商品1を3個、商品2を1個、商品3を4個で100円）。ちょうど商品をa_i(<=6)個買いたい。最小支払いを求めよ。
解法：無理ｗと思ったら制約がガバガバだった。高々状態が66、遷移が110*6なので、30792960でまあ0.1秒くらいで行けそう
637. Average of Levels in Binary Tree
概要：ノードに整数が載った二分木が与えられるので、各深さでノードの整数の平均値を出力してください。
解法：やるだけすぎる
635. Design Log Storage System
概要：2つのクエリを捌け。「時間tを登録」「時間粒度gで、時間xから時間yまでの間にあるtを全て報告」
解法：時間粒度別に全部setを作ってしまう。xを二分探索関数で調べて、その後はnextでyまで舐める。報告個数k, 登録個数nに対してO(g n log n + k)
632. Smallest Range (Hard)
概要:サイズn以下の数字リストがk個与えられる。区間[l, r]が正しいとは、全てのリストlに対して、ある要素x in lが存在して、x in [l, r]であることを言う。最小の範囲を求めよ（長さが短く、長さが同じなら要素番号が小さいもの）。なお、要素の数字は-100000から100000の範囲（M=2e5）である。
解法：lを固定すると、l以上の値yを取ってきて、[l, y]のリスト個数が何個あるか？はO(k)で求まる。また、これは単調増加なので、二分探索が可能。lを動かすと、O(k M log M)で解ける…が制約上かなりギリギリ。
630. Course Schedule III
概要：区間がn個与えられる。区間の長さと最大値はm以下である。区間をかぶらせずに最大何個区間を取れるか。n, m<10000
解法：典型っぽい！dp[i][j] = i個の区間を見た時に、最後にj日目が埋まっている時の最大区間数？しかしnが大きすぎるので無理。区間スケジューリング問題みたいなの、結構いつも困るんだよね。
629. K Inverse Pairs Array (Hard)
概要：n, kが与えられる。数列a=arrange(1,n)のpermutationの中に、i<j&&i>a[j]なる組がk個あるようなものは何通りあるか？n<1000
解法：全くわからん
623. Add One Row to Tree
概要：木が与えられる。深さdに整数値n付きノードを挿入せよ。
解法：やるだけすぎる。
621. Task Scheduler
概要：A-Zを、同じ文字が長さn以上近づかないように並び替えた時の最小長さを求めよ。ただし、NULLで水増しすることが許されている。
解法：とりあえず何から始めるかa-zは全探索したい。 後で考える
611. Valid Triangle Number
概要：長さa_iの辺がn個与えられる。3つ選んで三角形を作るための辺の選び方は何通りあるか？ n<1000
解法：3乗が通りそう。早くするなら、2つ決めるともう一個は二分探索で個数が求まるのでO(n2 log n)にもできる。
609. Find Duplicate File in System
概要：めんどそう
解法：やめて（やめます）
600. Non-negative Integers without Consecutive Ones (Hard)
概要：nが与えられる。n以下の非負整数の中で、二進数表記で1が連続しないものは何通りあるか？
解法：これはd=1000個埋め込めば、ステップ数n/d=106くらいになってO(n / d log n)で一応解けますね…（それでいいんですか）
593. Valid Square
概要：4点与えられます。これは正方形ですか？
解法：えぇ…（やるだけすぎる）
592. Fraction Addition and Subtraction
概要：分数の足し算引き算が文字列で与えられるので、計算してをしてください。
解法：えぇ…（形式楽だから普通に一個ずつ足し算&規約分数やるか、rational持ってくるか、pythonか何かの有理数ライブラリがある言語でやります…）
591. Tag Validator (Hard)
概要：だからやめてこういうの
解法：いいえ
583. Delete Operation for Two Strings
概要：2つ文字列が与えられるので、最長部分列の長さを求めてください。
解法：えぇ…（さすがに解けます）
576. Out of Boundary Paths
概要：盤面hxwがあり、(i, j)にボールがある。ボールに対する操作「4方向のどちらかに移動する」が可能である。操作回数N回以内で、ボールを盤面外に出すための操作列の場合の数を求めよ。（ボール盤面50x50以下、操作回数50以内）
解法：DP[i][j][h]=(i, j)にボールがいて残りh回操作可能である時の場合の数。初期値は盤面外のマスについて、DP[?][?][0]=1。
