Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

AtCoder Beginner Contest 141

4完。Eが怒涛のTLE地獄・・・。

各問題

A - Weather Prediction

if文をみっつ並べればよいです。対象が文字列なので、格好つけて配列を使って回したりすると逆に面倒くさいです。

こういう問題で一番怖いのはタイポだったりします。問題文からのコピペ推奨。

B - Tap Dance

問題の読み替えをするとちょっと楽になります。つまり、奇数文字目に'L'が入っているか、偶数文字目に'R'が入っている場合は"No"、そうでなければ"Yes"です。

ところで、なんで問題文をDDRに絡めずにタップダンスにしたのでしょうか?そこがちょっと不満です(え?

C - Attack Survival

愚直にシミュレートすると終わらなくなるのは明らかなので、これも視点をちょっと変えてみます。 最終的に、Q - 正解数がマイナスされるポイントなので、各参加者の正解数を保存しておいて、参加者ごとにQ - 正解数がKを下回っていれば"Yes"、K以上なら"No"となります。

D - Powerful Discount Tickets

大きい数を2で割るほうが効率がいいことは明らかです。なので、一番大きい数を2で割る→その結果一番に躍り出た数を2で割る、を延々(M回)繰り返せばいいです。 例えばc++ならpriority_queueを使えば簡単に実装できます。

E - Who Says a Pun?

4重ループ(重なり合わないような二つの範囲の始点と終点)を回してfindしてTLE地獄でした。

editorialをみると、Z-Algorithmとかローリングハッシュとかあって、あーそれ系の問題かー、となりました。要復習・・・。

F - Xor Sum 3

何かが見えたような気がしましたが、気のせいでした。

まとめ

Z-Algorithmとかローリングハッシュって何ヶ月か前にもみたなー、復習不足だなーという。復習大事。超大事。

水色パフォで、レートは微増ながら水色復帰はならずでした。

f:id:mdstoy:20190915232057p:plain