LeetCode Weekly Contest 133
- masashinakata
- 934
- 1
- 0
- 0
気分と体調いまいちで1問合格は嬉しい #LeetCode# I have solved Matrix Cells in Distance Order. Come and join the fun! leetcode.com/contest/weekly…
2019-04-21 12:40:132問正解。嬉しい #LeetCode# I have solved Two City Scheduling. Come and join the fun! leetcode.com/contest/weekly…
2019-04-21 12:59:17Q1.マンハッタン距離で昇順ソートする Q2.なんだこれEasyなのにDPか Q3.全区間重ならせずに試すだけ 先に累積和を取っておく Q4.Trie木に逆に登録しておいてクエリ履歴をあてはめてみる
2019-04-21 13:00:17#AC葵 #GCJ GCJ kick start Round B 2019. Building Palindromes [0,i]の範囲の各英字の出現数で累積和を取ってから、[l,r]を抽出しましょう。回文は、出現数が奇数の物が1個以下なら生成可能という話は頻出なので覚えましょう
2019-04-21 13:00:18#AC葵 #GCJ GCJ kick start Round B 2019. Diverse Subarray 恐らく多くの人はlargeは解けないだろうという見切り発車が重要で、それにより順位が挙げられます(最悪) smallならO(N^2)が可能なので、各左端について右端を全探索して、その結果の最大値を取ってしまえばACです
2019-04-21 13:02:05LeetCode Weekly Contest 133、数週間ぶりに全完したやったー。A: BFS B: コストの差でsort C: あらかじめ[i, i+L]の合計、 [j, j+M]の合計を計算しておく(O(n)でできる) D: Trie木。現在のノードへのポインタ(複数)を保持しておいて、query のたびに各ポインタをアップデートする
2019-04-21 13:02:13#AC葵 #leet weekly-contest-133.A 1030.Matrix Cells in Distance Order Outputの意味が分からなくてしばらく停止していました。これが無ければ2桁行けたのでは・・・? Outputはr0,c0に近い順の座標なだけでしたので、array<int,3>をvectorにいれた後sortが安全です
2019-04-21 13:06:25LeetCode133は3完でした A. 全セルで距離を求めて距離でソート B. dp[i, a, b] = i以降でAがa、Bがb残ってるときの最小コスト C. 全チェック。合計は累積和で出す Dは解けそうで解けぬ
2019-04-21 13:06:36#AC葵 #leet weekly-contest-133.B 1029.Two City Scheduling N個ずつに分割すれば良いんですね。先日のどこかのCFコンテストみたいに、a-bでsortしましょう。Easyなので何も考えずにminを取りすぎてWAでした。なにやってるんでしょうね・・・
2019-04-21 13:07:56#AC葵 #leet weekly-contest-133.C 1031. Maximum Sum of Two Non-Overlapping Subarrays L+M<<=A.length<=1000 なので、計算量削減のために累積和を追加しながら、 区間Lが先に来ると仮定して左端決め打ち→Mの左端決め打ちをやって、swap(L,M)で再試行して、それらの内の最大値を求めたら押しまい
2019-04-21 13:10:03