ABC122 感想
ABC122
3月24日（日）21:00~21:40分に開催されたABC122に参加しました。この記事はその記録兼復習です。
また、私のコードはGitHubにあります。参考にどうぞ。
A - Double Helix
どうでもいいけど今回は塩基のお話でA,T,G,Cが出てきた。Uがいなかったのはかわいそうですね。
この問題は入力の内容で出力を変化させるだけの簡単な問題なので適当にswitch文でAC
B - ATCoder
与えられた文字列中で、ATGCのみで構成されている文字列（以下AGCT文字列）の長さの最大値を求める問題。for文を二重にして（外側は判定対象文字列の始点を走査、内側は判定対象文字列中を始点から最後まで走査）、AGCT文字列の長さを記録、最大値を更新していくという流れでAC。 コンテストの前にSSHで大きさの違うコンソールを扱ったせいかcatがバグってsubmitするコードがうまく表示されず、1分くらい遅れました。僕は普段NeoVimで書いて、catしたやつをコピペしてるんですが、他の人はどうやってるのか少し気になりますね。
C - GeT AC
自分の中ではここからようやく本番です。
与えられた文字列の、各問で指定された範囲の部分文字列中に"AC"が何個現れるかと言うのを各問ごとに求める問題。一見するとすべての問についてBのように一つづつ数えていけば良いようにも見える。しかし、問題数が105までと結構多いので愚直にやってもTLEとなると予想。というわけで計算量を落とす工夫をするわけだが、この問題が、与えられた文字列の指定された範囲の中で探せばいいということに着目する。そうするとABC120-C（多分これだったと思う）で出てきた考えのようにlからrのACの個数 = rまでのACの個数 - lまでのACの個数とすればいい。
このことに気づけば、はじめにDPで文字列の長さまでメモをして、各問はそのメモを使って単純に引き算してみればAC。
ちなみにこの考え方は累積和と呼ばれるものらしいです。
D - We Like AGC
コンテスト中に解けなかったので記事書いてる途中で解きました。
N文字の文字列のうち、0回または1回の隣接文字の入れ替えをして"AGC"という文字列を含まないものの個数を109+7で割った余りを求める問題です。
この問題の肝は、i文字目を置くときにはi-1,i-2,i-3文字目だけを気にすれば良いという点です。具体的に違反になるのは
| i-3 | i-2 | i-1 | i |
|---|---|---|---|
| A | G | C | ? |
| A | C | G | ? |
| G | A | C | ? |
| ? | A | G | C |
| ? | A | C | G |
| ? | G | A | C |
| A | ? | G | C |
| A | ? | C | C |
です。一部被りがありますが、数えているわけでは無いので問題ありません。
以上のことを踏まえると、dp[i][j][k][l]を長さiでj=最後尾から2文字後ろの文字,k=1文字後ろの文字,l=i最後尾の文字としたときの文字列の数と定義して、
if 違反していない dp[i+1][k][l][m] += dp[i][j][k][l]
という漸化式が成り立ち、答えはdp[n][j][k][l]のj,k,lを4文字でループしたときの総和となります。
感想
二回連続でCまで解けたことが嬉しかったです。またCの解法を考えるときに、累積和を使いそうだなということがすぐ思いついたなど精進の効果を少しづつではあるが感じられました。D問題も回答までは至らずとも、考え方は途中までは合っていたのでこれからも精進していきたいですね。 反省点としては、A、Bを解くときに余計なことで時間を食ってしまったことです。catがバグるなんて思わないだろ普通は。
