ABC179おつかれさまでした． 競プロ復帰から早1か月が経過しました．あれからレートはほとんど変化なしです(は？)
レート変化
524→549(+25)です．パフォは735で，一応Highestは更新しました．
緑までの道のりはまだまだ長いです．
A：Plural Form
文字列の末尾を見て”s”を付けるか”es”を付けるか判断するという問題です． 実際の英語とはちょっとルールが違いますが， 実際の英語に即して末尾を判断するとなると，それはもはやA問題の守備範囲ではありませんね()
文字列の扱い方だけ分かっていればやるだけです． ifで振ってあげてACしました．大体1分．
B：Go to Jail
サイコロを2個振る試行を$N$回行った結果が与えられ，ゾロ目が3回以上連続で出たかどうか判定する問題です． これについても問題のまま素直に実装してやればすぐですね． ゾロ目の連続記録が途切れた時にカウンターをリセットすることを忘れないように． ここまででちょうど6分．
C：A×B+C
問題は非常にシンプルですが，制約が$N\leq10^{6}$なので適当に実装すると即TLEして詰みます． 適当に$A, B, C$それぞれを全探索すると$O(N^{3})$なので，まず終わりません．
まず$C$については$A, B$を決めてしまえば一意に定まるので，$A, B$だけ考えれば十分です． さらに$A$に対して$B$は$\frac{N-1}{A}$個存在することになるので（$C\neq0$なので$\frac{N}{A}$ではない）， Aについて1～$N$まで全探索してやれば$O(N)$で解が導けます．
自分の提出コードの場合数え方が想定解と違いますが，発想は同じでした． ここまでで約28分． 緑に行くにはもっと早くC問題を突破する必要がありそうです・・・．
D：Leaping Tak
「D問題のDはDPのD」という言葉通り，DPをやる問題です． ・・・が，そのまま素直にDPすると$O(N^{2})$なので制約的にTLEまっしぐらです． 自分の場合DPをすることには気づいたのですが，計算量を$O(N^{2})$から落とす方法が分かりませんでした． 「もしかしたら通るんじゃね(無謀)」という考えのもととりあえずDPを普通に書いて提出しましたが， 予想通りTLEして撃沈しました(残当)．
解説では累積和を用いてDPを高速化する手法を用いていました．
イメージとしては上図のような感じです． 上の方法ではそれぞれ個別で足すので最悪$N$回の足し算が発生しますが， 下の方法では区間ごとにまとめて足してしまっているので，最悪でも$K$回の足し算しか発生しません． 区間の和については累積和をとりながらDPをすることで$O(1)$で取得できます． したがって下の手法を用いることで$O(KN)$まで計算量が削減され，時間内に処理が終了します． 移動できるマス数が区間で与えられているというのがミソでした． これ本番で思いつくの結構大変だなぁ・・・．
E：Sequence Sum
「余りの問題はループが発生していないか見よ」と聖書にもあります（ない）． というかこれどっかのABCと発想ほぼ同じ問題やんけぇぇぇ！！！ 何故ACできなかった？？？？精進の大切さを改めて感じました．
これです ↓ atcoder.jp
素直に漸化式に従って余りを順番に足していくと計算量は$O(N)$となりますが，これでは制約的に間に合いません．
鳩ノ巣原理から$A_n$には高々$M$個の値しか現れません． さらに漸化式から，数列$A_n$は一部がある一定周期でループします．
上図のようなイメージになります． 状態を
(i) ループに入る前の部分 (ii) ループの部分 (iii) 終了に伴いループしきれなかった部分
の3セクションに分解に分解すると，求める値は
(i)＋(ii)×ループ回数+(iii)
となり，$O(M)$で求まります．
本番中は(i)のセクションの存在を忘れており，ACできませんでした． うーんこれはACしたかった問題です．方針が一瞬で浮かんだだけに悔いが残ります．
最後に
ACはできなかったもののDとEの大まかな解法は本番中に一瞬で出てきたので， ある程度精進の成果は出ているのかなというように思います． この調子で頑張ろうと思います．
あとDとEの難易度逆転が最近多い気がするのは気のせいですかね？？ DとEは両方見る癖をつけたほうが良い気がします．
