各問題

A - Double Helix

単純にif, else ifを並べました。

1分台(1:43)でAC出たのでよし、と思っていたのですが、これでもちょうど300番目だった模様。厳しい。

N <= 10 なので、全部見ればいいわ楽勝楽勝と思っていたら、まさかのWA。最後の一個だけがWAだったので、境界値バグかなと思ってよく見たらそのとおり、入力が一文字のみときが見事にすっぽ抜けてました。on_

まず、各クエリごとに文字列を全部捜査するというゴミみたいなロジックを書いて無事TLEをもらいました。次に、文字列捜査部分を、"AC"をreplaceAllでぶっこ抜いてもとの文字列との長さの比較で答えを出すというロジックに変えて、引き続きTLEをもらいました。

そういうことじゃないから俺！

で、これは"AC"を探すのは最初に一回だけやっておけということだなということにようやく気づき、"AC"が出現した位置を最初に覚えるようにして、各クエリごとに、"AC"が出現した位置が範囲内に含まれるかどうかを「全部」確認するように書き換えたところ、三度TLEをもらいました。

ちょっと考えて、全部チェックしなくても範囲外の部分だけわかればいいよね、ということに気づき、ようやくACがとれました。

解説によると、これは累積和を使うとよかったんですね・・・。

せっかくなので累積和を求める解法で解き直してみました。

私が最初に通したコードとくらべて、笑えるくらいシンプルかつ速く動作するコードになりました。

解説にあるような、末尾がこれこれだとそれ以上は続かない、みたいなのがおぼろげにはわかったのですが、そもそもちゃんとわかってないし、わかったとしてDPを実装もできなさそうなので今の所だめです。

f:id:mdstoy:20190324235616p:plain

ぐいっと伸びているように見えるけど、これは二日連続開催だからですねｗ