はむこの勉強記録

http://bit.ly/2ktf20t の写し

Leetcode 600. Non-negative Integers without Consecutive Ones

docs.google.com

Leetcode 639. Decode Ways II

docs.google.com

Aho、重複ありなしで結構混乱する…

Leetcode 401-391 考察ラッシュ

399. Evaluate Division

概要:変数がn個あって、a/b=c型の方程式がmこある。変数間の比がq個聞かれるので答えて。

考察:すげーAtcoderで見たことある…気がした(単位の変換みたいな奴)。グラフDFSするだけ。

398. Random Pick Index

概要:数列が与えられる。重複要素が含まれる可能性がある。数列の値が与えられるので、それに対応する添字を均一ランダムに返せ。

考察:どれくらいランダムだよ…(いいえ)

397. Integer Replacement

概要:数字nが与えられる。偶数なら半ぶんにして、奇数なら1を足すか引くかする。1にするのに最小何回?

考察:おっ、わからん(あとで確認)

396. Rotate Function

概要:円環数列aが与えられる。arrange(|a|)>>iとaの内積が最大になるのはいつか?|a|<=100000

考察:隣り合ったソートを考えると、比較関数が作れる。しかしそもそも円環でのソートってどうするのが良いのかわからないので後で確認

395. Longest Substring with At Least K Repeating Characters

概要:読めない…

考察:???

391. Perfect Rectangle

概要:座標付き四角形がn個与えられる。これは長方形をぴったり分割したものか?

考察:すぐにはわからない。

Leetcode 490-456 考察ラッシュ

hamko.hatenadiary.jp

488. Zuma Game (Hard)

概要:文字列sが与えられる。文字集合Sを使って、以下の操作を繰り返す。操作「集合Sの要素xを取り出し、sのどこかに挿入する。sの中で、3個以上連続して同じ文字があればそれらを全て削除する」。この時、結果として考えられる最小値を求めよ。|s|<=20, |S|<=5, 文字種類5種類以下

考察:わからん

486. Predict the Winner

概要:ポイント性の2人ゲームをする。数列aが共有されている。人1から交互に手番が来る。操作「aの先頭か末尾の数字をpopしてその点数を得る」をaが終わるまで続ける。人1は負けないか?|a|<=20、a[i]<=1e7

考察:わからない。全探索できるけど、全探索情報から必勝法を見つける方法ってあるのだろうか?

483. Smallest Good Base

概要:整数nがbase bで全て1だった。最小のbを求めよ。

考察:3乗くらいまでを場合分けしてアドホックに調べて、4乗以降はbを下から全探索。

482. License Key Formatting

概要:文字列sの-を消して、全部大文字にして、k文字ずつに分解してください。

考察:えぇ…(やるだけすぎる)

481. Magical String

概要:Down vote多すぎるので見ていない

考察:いいえ

480. Sliding Window Median

概要:数列aが与えられる。[i:i+k)の中央値をiについて全列挙せよ。

考察:Wavelet Matrixのquantileで殴る。

477. Total Hamming Distance

概要:数の集合Sが与えられる。Sのペアを考えて、それらのハミング距離の総和を求めよ。

考察:bit独立でsum(#0*#1)

474. Ones and Zeroes

概要:二値文字列集合Sが与えられる。Sの部分集合Tを、'0'をm個、'1'をn個で構成できるとする。|T|を最大化せよ。|S|<=600, n, m<=100

考察:二次元ナップザックなのでDP[i][j][h] = i個見て、j個0を使って、h個1を使った時の最大個数。

473. Matchsticks to Square

概要:長さa_iの棒がn個与えられる。正方形を作れるか?n<=15, a_i<=1e9

考察:4つに分ける方法は19C4くらいなので全探索

468. Validate IP Address

概要:Down voteがひどいのでやらない

考察:いいえ。

467. Unique Substrings in Wraparound String

概要:円環アルファベット文字列a[0:26)=[‘a’:‘z’]を想定する。文字列sが与えられる。sには、aの相違連続部分列が何個含まれるか?|s|<=10000

考察:すぐにはわからない…。前処理で、各文字について、どこまで連続できるかを持っておく。長さを全探索して、連続限界以下かつ各文字について新出ならばカウント。

良い典型

466. Count The Repetitions

概要:文字列s1, s2が与えられる。n1, n2が与えられる。s2mn2がs1*n1の部分文字列であるという。最大のmを求めよ。

考察:全然わからない。二分探索したい気持ちにはなるけど…

464. Can I Win

概要:n言ったら勝ちゲームをする。kまで言えるが、数字の再利用は許されない。勝者はどちらか。k<=20, n<=300

考察:わからない…ゲーム系弱いんだよなあ…k<=20なので、状態は220*300である。メモリが大きいPCならばギリギリ全探索できる。

460. LFU Cache (Hard)

概要:LFU Cache(k)を実装せよ。

考察:読解がキツイのでいいや

457. Circular Array Loop

概要:長さnの円環すごろくがある。i番目には数字a[i]が書いてあり、ここに止まるとa[i]だけ前後に進む。ループはあるか?時間O(n), 空間O(1)で書け。

考察:空間O(n)なら、全てから初めて遷移を試すだけ。あとはめんどいのでSCCしちゃうという手もある。空間O(1)はよくわからない。

456. 132 Pattern

概要:数列aが与えられる。a[i]<a[k]<a[j] (i<j<k)なるi, j, kは存在するか?

考察:jを全探索したい。すると、①[0:k)の最小値<a[k] ②(k,n)の中でa[k]未満の最大値を持ってくればいい。こういうのはWavelet MatrixでO(log n)でできるので、O(n log n)でできる…が、普通どうやればいいのかわからない。

Leetcode 571-491 考察ラッシュ

概要

勉強になる問題は、565, 564, 560, 546, 542, 523, 503, 502, 516, 493, 498。

就活力と典型力を身に着けたい。

hamko.hatenadiary.jp

567. Permutation in String

概要:文字列s1, s2が与えられる。s2の連続部分列として、s1のpermutationは含まれるか?

考察:長さと数さえ合っていれば良いので、imosで前処理しておけばO(26n)

565. Array Nesting

概要:数列a=[0:n-1]のpermutationが1つ与えられる。s[k] = {si[k]} (i in [1, inf))である。s[k]の最大サイズは?

考察:複数の連結成分になっている可能性がある。サニーグラフなので、ループを検出して、ループ内頂点からそれ以外の点へDFS…???

564. Find the Closest Palindrome (Hard)

概要:整数nが与えられる。10進数で回文になっている数字文字列のうち、nに最も絶対差が小さいものは?

考察:nが18を超えないなら、109の全探索が一応できる。100に一番近いのは99と101で、桁が変わることはある。うーん、桁DPっぽいけどよくわからない。

560. Subarray Sum Equals K

概要:数列aと、整数kが与えられる。aの連続部分列のうち、和がkのものは何通りあるか?

考察:imos+値域に展開でできる気がするが、あまり確かではない。

556. Next Greater Element III

概要:32bit正整数nが与えられる。nの10進数表記の桁を入れ替えて、新たに32bit正整数を作ることを考えた時の、最大値を求めよ。

考察:結局10桁くらいしかないので、next_permutation

554. Brick Wall

概要:高さh、横幅wのレンガの壁がある。高さiのレンガは、数列a_iの横幅のレンガが横に並んだものである。レンガをなるべく切らずに、壁を切るときに切る必要のあるレンガ数は?

考察:imosしてcounterに突っ込むだけなのでO(hw)くらいで求まる。

553. Optimal Division

概要:Bad評価がつきまくってるので読んでない

考察:いいえ

552. Student Attendance Record II

概要:ALPからなる長さnの文字列を想定する。Aが1個以下かつLが2個以下の文字列を数え上げよ。

考察:DP[i][j][h] = ちょうどi文字見た時、Aがj個以下で、Lがh個以下の場合の数。j, hは大きくなるとメモリも計算量も足りないので、適当に2, 3くらいで抑えておく。

547. Friend Circles

概要:NxN対象行列Mは、M[i][j]=1の時に直接の友人であることを表す。M[i][j]=0かつあるhが存在してM[i][h]=1かつM[h][j]の時、iとjは間接的な友人と表現する。友人でグループ化した時、なんグループできるか?

考察:Union Findって知ってる?

546. Remove Boxes

概要:要素が[1, n]の数列aが与えられる。操作「連続して同じ数字である範囲a[i:j]を削除」を行うことで、(j-i+1)2ポイントもらえる。数列を空配列にするための最大ポイントを求めよ。n<=100

考察:わからん…

542. 01 Matrix

概要:二値HxW行列が与えられる。各要素から最も近い0までの距離を求めよ。n=HW<=10000

考察:1があったら、0のところを全部なめて距離を更新する、でO(n2)になる。最悪ケースは01の数が同じ場合なので、50002くらいに抑えられるのでまあ行けそう。0の部分から、0ステップずつBFSすればO(n)になりそう。 これおすすめ

540. Single Element in a Sorted Array

概要:以下の問題を、時間O(log n)以下、空間O(1)以下で解け!ソートされた数列aが与えられる。aは、同一要素が2個ずつ出る…と言いたいが、ひとつの要素だけ1回しか出現しない。そのような1個しか出現しない要素は何か?

考察:さすがにね??(ソートされているので初めから2個ずつ見ていって、違ったら出す)

539. Minimum Time Difference

概要:時刻がHH:MMの形式で、数列に格納されている(長さ20000以下)。時刻の差分の最小値は?

考察:時刻をmin.にしてソートして、隣との差を見る+最後と最初の差を見る。

537. Complex Number Multiplication

概要:複素数が2つ与えられるので、かけて

考察:にゃーん(わんわん)

529. Minesweeper

概要:マインスリーパのクリックをシミュレーションして

考察:なんでこんなことをしなければならないのか?(反逆)

524. Longest Word in Dictionary through Deleting

概要:文字列sと、文字列集合dが与えられる。sとd[i]の最長部分列長がd[i].size()であるような文字列のうち、もっともサイズが大きい物を答えよ。

考察:やるだけすぎる。

523. Continuous Subarray Sum

概要:非負数列aと、整数kが与えられる。sum a[i:j] = n kなるi<=j, nのペアは存在するか?n<=10000

考察:折れ線グラフモデルで考える。累積和がmod kで一致するものが一つでもあればOK これおすすめ

522. Longest Uncommon Subsequence II

概要:やたらdislikeが多いので読みません

考察:いいえ

518. Coin Change 2

概要:長さnの数列aが与えられる。aから重複を認めて数字をいくつでも取ってきて良くて、これらの和がamountになるような場合の数を求めよ。n<=500, amount<=5000

考察:まあamountに関するDPですね

517. Super Washing Machines (hard)

概要:数列aが与えられる。1回の操作は、範囲内に収まる整数kを選んで、操作「a[i]–, a[a+k]++」もしくは「a[i]–, a[a-k]++」のどちらかが可能である。数列の要素を全て同じにするのに必要な最小回数は?

考察:流すとか言ってるけど結局一個下げて一個上げる以上のことはしてないよね??diffを絶対値で取って/2にするだけ。

516. Longest Palindromic Subsequence

概要:文字列sが与えられる。sの部分列の中で最長の回文の長さは?|s|<=1000

考察:出力の場合分け、偶数と奇数がある。回文の中心を探索する。偶数の場合、分けた時の前と後のreverseの最長部分列x2が答え。奇数の場合、偶数+1が答え。これでO(n2 log n)で計算できる。

勉強したこと:回文には中心がある!なので、中心探索という手がある。というか部分列判定ってよくやるけど、しゃくとりのほうがいいですね(しゃくとり早いけど微妙にバグる)

515. Find Largest Value in Each Tree Row

概要:整数付き木構造が与えられる。各深さでの最大値を求めよ

考察:なめてんのか

514. Freedom Trail (Hard)

概要:円環文字列aが与えられる。文字列xは初め空である。操作「a <<= 1」もしくは「a[0]をxに追記」を最小何回行うことでx=keyにすることができるか?

考察:わかんない…

513. Find Bottom Left Tree Value

概要:二分木構造が与えられる。最も深いノードの中で最左のノードは何か?

考察:やっとこういうタイプで少し意味のあるものが出てきた…左からDFS探索して、各深さで最初に出てきたものを記憶していく。

508. Most Frequent Subtree Sum

概要:整数付き二分木が与えられる。部分木の和の最頻値は?

考察:やるだけ。部分木和は木DPで簡単に求まりますね?あとはmapでカウント。

503. Next Greater Element II

概要:円環数列aが与えられる。各iについてa[i+j]>a[i]なる最小のjにおけるi+jを全列挙せよ(ない場合は-1)。|a|<=10000

考察:各数字から、逆方向に、自分より小さいければ伝播自分を伝播させていく。

これ面白い。

502. IPO (Hard)

概要:n個のプロジェクト候補がある。i番目のプロジェクトは、初期資金として資産がc[i]が必要で、p[i]円儲かる。今、資産はw円持っている。時間の関係上、k個のプロジェクトを選ばねばならない。最終的な資産を最大化せよ。n<50000

考察:capitalは増える一方なので、とりあえずcでソートしたい。今取れる範囲で、貪欲に最大のprofitを選べばよい。同じプロジェクトを何回も行うことはできない制限から(これ書いてなくない?)、必要なクエリは「p[0:i]の最大値と最大indexをget」「p[i]を-INFにする」があればよい。これはSegment Treeで実現可能。

これ、実問題としては面白い(勉強したことは…?という感じだが)

疑問:最大値と最大indexってどうやってgetするの?

498. Diagonal Traverse

概要:行列MxNを右斜め->左斜め->…で、一次元配列に直してくれ

考察:やめて(と言いつつこういうのはぱぱっとできないとね)。実装ゲー。こういうのってどうやるのが良いんだろう。

あとでちょっと考える

495. Teemo Attacking

概要:英語が読めないしシミュレーションっぽいのでいいや

考察:(読めてないのであれなのですが、どうせ最後を管理するんでしょ)

494. Target Sum

概要:数列aが与えられる。添字集合Sについて、操作S「a[S]*=-1」を行ったあと、sum(a)=kとなったという。Sのとり方は何パターンあるか?|a|<=20, sum a <= 1000

考察:dp[i][j] = i番目まで見て、合計がjであるような場合の数。jが負になるので注意

493. Reverse Pairs (hard)

概要:数列aが与えられる。i<jかつa[i]>2*a[j]なる(i, j)を数え上げよ。|a|<=50000

考察:僕はiを固定して、Wavelet Matrixで殴る。

ペアの数え上げ、こんなんばっかだな。 数列aが与えられる。クエリ(i, j, k)は「[i:j]内でk以上の数を報告」ってどうするのが普通?

491. Increasing Subsequences

概要:数列aが与えられる。非減少部分列を全列挙せよ。|a|<15

考察:DFSしましょうね(めんどければbitmaskで全列挙するという手もある)

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)個買いたい。最小支払いを求めよ。

解法:無理wと思ったら制約がガバガバだった。高々状態が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。