LeetCode weekly contest 133に参加しました
ちょっとAtCoderの方が伸び悩んだり、変なのが湧いたりしてモチベが下がったので、一旦LeetCodeというのに手をつけてみました。
(あとでtenka1の問題は解くつもりです)
AtCoderとの違い
- これが一番大きいと思います。標準入力を読み取って回答を標準出力に出すのではなく、特定の関数が用意されて、それに合わせて適切な戻り値を返す形になります。Pythonで解く場合、関数の変数にintやList[str]など型ヒントがつくので推測は出来るかと思います
- 問題が英語です(中国語もある?)。ただ例も結構書かれているし、GCJなんかに比べるとはるかに読みやすいです
- 過去に開催されたコンテストを、一定の時間で解くVirtual Contestなんてのもあります
- 過去の問題でも、回答すると進捗(Progress)には反映されます
- 実際のコンテストに参加すると、参加賞として5コインは貰えるようです。それとは別にレーティングもあります
実際にコンテスト参加してみて
4問出題、1時間半で回答。で1問だけ解けました。問題の難易度はEasy, Easy, Medium, Hardの順だったのですが、2問目の方が3問目より難しかった気がします。先に3問目解いてたら解けたのかもしれません(が後述の問題あり)
1030. Matrix Cells in Distance Order(Easy)
全てのセルを、あるセルから近い順に列挙する問題です。
添付したgistの、上の様な形式で 問題が出され、下のように回答しました。->AC(15分)
問題文に「マンハッタン距離で」ということと、マンハッタン距離の定義自体書かれているので素直にソートすればいいだけなんですが、動作確認とかどうでもいいとこで時間かかりすぎっすね。
1029. Two City Scheduling(Easy)
2問目なのに問題番号が1番目より小さいのは仕様です。
2N人いてそれぞれ2つの都市に行くコストが与えられるので、コストが最小になるようにN人ずつ振り分けろという問題です。
一見単純そうにみえて、結構きつい問題でした。片方の都市に行くコストが小さい順にN人選んでもダメなんですよね。@naoya_tせんせーはDP使って解いてたようですが、本当にEasyなのか?
1031. Maximum Sum of Two Non-Overlapping Subarrays
ある数列Aが与えられて、L個とM個を被らないように選び(どっちが左という決まりはない)、和を最大化させる問題です。
累積和の問題なので解いていけばいいです。が、自分のとこだと累積和自体がうまく計算できてないです。課題です。
1032. Stream of Characters
時間内にたどり着けなかったのでよく読んでないですが、1文字ずつ与えて、それがある文字列に一致したらTrueを返せばいいんですかね?過去のクエリ文字を記憶して、それと一致かけないとダメな気がします。
まとめ
LeetCodeに参加してみました。AtCoderやってる人なら出来るんじゃないかなと思います。回答用に関数作るのはちと面倒。