Leetcode 571-491 考察ラッシュ
概要
勉強になる問題は、565, 564, 560, 546, 542, 523, 503, 502, 516, 493, 498。
就活力と典型力を身に着けたい。
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で全列挙するという手もある）
