全体の感想

3完でパフォ1034。灰色勢としてかつてない出来！
そして茶色になった。

初めて難しめ（？）のC問題を解けた。精進の結果が初めて出たので割と嬉しい。これが競プロの醍醐味なんだろうけど、ここに至るまでがなかなか辛くて敷居が高いなと思ってしまったり。

Bで一度WA,　Cで一度TLEを出してペナルティを食らったのが悔やまれる。

A - Double Helix

愚直に解いてif文まみれに。解ければ何でもいいよね。Aだし（おい）。

Bはいつもどおりな感じだったがテンパっててWAを出してしまい絶望。当方初心者でC以降を解けることがまだ少ない。２完勢とのスピード勝負でやばいと思った。

落ち着いてデバッガーで動きを見てみると、コーナーケース？（ACGTのみからなる文字列）でのバグを発見。絶望した結果かえって落ち着いていた。すぐに直してAC。

問題文はちゃんと読んだのに、変数の範囲10⁵を見てなかった。初回提出は無事TLE。萎えた。

質問は最大で10⁵個ある。１個１個の質問に対し最大10⁵回探索する必要がある。計算量は10¹⁰くらいとなりどう考えても無理(たぶん)。正確な計算量に関してはまだ初心者なので勘弁して下さい＾＾。

10⁷~10⁸くらいまでが行けるラインらしい。

質問の個数に関してはアルゴリズムではどうしようもないので、無視。問題は探索である。質問の各ループ中にO(logN)かO(1)の計算量（本当か？）で'AC'が何個かを探索をしないといけない。

各質問では被る範囲があるからまずはそこに目をつけてみる。 →うまくいかない。

次に、２重for文の中から内側のfor文を外部に取り出すことを考えてみる。どういうことかと言うと、1からQまでの各質問のforループの中にある探索部分のforループを、外に出したいということ。

for(int i=0; i<Q; ++i){
    for(int j=0; j<N; ++i){
    
    }
}

つまり、上のこれを下のようにする。

for(int j=0; j<N; ++i){

}

for(int i=0; i<Q; ++i){

}

そうすれば、当たり前だが２重for文は１重for文になり、計算量の問題はなくなる。こういう考え方はわりと典型だと思う。いもす法もこういう形（本当か？）。

最初に、文字列S全体に関し'AC'を探し、場所を配列等に記録していく。その配列をつかってO(1)で各質問内において'AC'の数を探索出来ないだろうか。考えてみる。→累積和じゃん！！

これは感想だし他にも解説あるだろうしで累積和については飛ばします。

というか、累積和のこの使い方でもまあまあむずいのに、今回の問題は累積和を使うに至るまでが難しすぎる。これ本当にC問題妥当なんだろうか。今回は運良く思いついたけど、次もそうなるとは限らない。 C問題まじで恐ろしい・・・。

速度に不安があったので一応PyPyで提出。

問題文見てどうみてもDPだろと決めつけて（適当）、最終的には4次元DPにたどり着いた。解説放送で4次元DP使ってたから多分想定解もそうなのかな？

自分がやろうとした4次元DPはこんな感じ。

dp[ i ][ j ][ k ][ l ]
i:一個前の文字
j:現在の文字
k:一文字目からスタートした場合の現在の文字数
l:条件を満たす文字列かどうか（1か0か）

そして、科学の叡智が集積したこの特異点にて遂に――、 4次元ゴミが爆誕した。

~fin~

冗談はともかく、もちろん見当はずれだった。しばらく体調崩しててACコードまだ書いてない。すぐに書かないと。