Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

LeetCode Weekly Contest 156

LeetCodeはだるいので、実際には解かず、解法を考えるだけにします。もし間違ってたらTwitterなどで教えてください。

その中で特に典型だったり、解いてみたい問題だけ解くという使い方にします。

エディトリアルがないため、復習効率が悪すぎる。

https://leetcode.com/contest/weekly-contest-156

C

問題

a-zから成る文字列が与えられる。この中からk個の連続を取り除いていく。文字を取り除いた時、左右の文字列をconcatnateすることにする。(それによってまた新しいk連続が生まれる可能性がある)

この時、最後に残る文字列は何か?

制約: N=105, k=2-104

方針(案)

k以上の連続があった時に、それをとるという思考停止O(N2)アルゴリズムでも正しい解は出せそう。なぜかというと、その連続はいつかはとらなければいけないし、k以上連続があった時、どの部分をとるかというのは問題ではないため。(例えばk=3の時、aaaaaがあったとして、3通りの3連続のうちどれをとっても残るのはaaとなる)

そして、あるk連続をとった時に、それによって新しいk連続が生まれるとすれば、その直前だけである。例えばランレングス圧縮で表して、c1b1a3b2とした場合、a3をとったら、b1とb2が合体する。

これを素直に実装すれば良いのではないかと思った。リンクリストで管理して、マージしたらノード削除。トータルでO(N)のアルゴリズムとなる。

意味もなくややこしいので、もっと簡単なやり方があるかも知れない。

調べてみると、RustのLinkedListはO(1) removeがない。ノードを晒していないからだと思う。お気持ちで自作してみてもいいかも知れない。

D

問題

迷路の亜種。長さ2の蛇がN2迷路をゴールに突き進む。しかし蛇は、

  1. 右に1つ平行移動
  2. 下に1つ平行移動
  3. 尻尾を基点にして時計回り90度
  4. 尻尾を基点にして反時計回り90度

でしか動くことが出来ない。

この時、ゴールにたどり着く最小ステップはいくつか?

制約: N=100

方針(案)

蛇の向き状態は4種類。このうちゴールへは、右向きか下向きでしか到達出来ない。

各マスごとに蛇の向きの状態をもたせて、その最小ステップを計算していけばよいのではないか?

for step ..:
  for all マス:
    for all 向き状態:
      for all 蛇の動き:
        // 蛇を動かすシミュレーション

ふつうの迷路なら2Nステップでたどり着く。その倍とってたどり着けないならエラーでよさそう。なぜならば、蛇は単に一つ下のマスに移るだけでも一歩先に進んでからターンするという2度手間かかるから。これが上限なので2倍。

400x10000x4x4だから、ぎりぎり届くかも知れない。しかしこれだと簡単すぎるためHardではないような。