4完。ちょうどいい難易度の問題がたくさんあるセットは幸せだ。
No.671 1000000007
1000000007と聞いて身構えるが、数として受け取る必要はなく文字列として長さがわかればいい。1つ目のサンプルが1長いのかと思ってたら、いま見たら1短いのね。まあ制約でNが107のこともあるので差の絶対値で。
No.672 最長AB列
難しい。しばらく考えて次の問題も見てみたが、まあこちらに集中することにした。まず考えたのは、ABのうち少ないほうに注目すること。でも、シマがたくさんできてしまってどの塊に注目したらいいかわからない。しゃくとり法っぽい感じもしてくるが、先が見えないのでねえ。「もっと先まで読めば同じになるかも」を解決できない。
累積和を思いついて、解けそうだと思えてきた。Aなら+1、Bなら-1していって、累積和の差が0の区間のうち最長のものを求めればいい。区間全部を調べたらTLEなので、もうひと工夫が必要。解けそうになってからも少し悩む。
文字列の長さをNとして、累積和の各値は高々N*2+1通りしかない。例えば、ある値に5回なったとして、その5つの位置から2つ選んだ距離が最も長くなるものを求めていってそれらの最大をとればいい。5つを保存すると大変なので最小値と最大値を持って更新していけばいい（文章にすれば短いが思考時間はそこそこ長い）。累積和の初期値は0ではなくNにした。最小値はN、最大値は-1で初期化。
No.673 カブトムシ
Bはともかく、Cが64bit整数で乗算できないサイズなのは珍しい。計算してみると、CもBと同じく単に余りをとればよかった（それはそう？）。
Dも大きいので繰り返し2乗法のような方法を使う必要があるが、試しに3年後を計算してみると B*C^3+B*C^2+B*C。なんかを C-1 で割ったやつな気がする。割り算は（時間がかかるから）できないので、元の式に C-1 を掛けてみる。それっぽい。C（を1000000007で割った余り）が1のケースは場合分けする（毎年一定数増えるだけなので簡単）。あとはライブラリのinvとpowを使うだけ。
No.674 n連勤
重複しない区間を高々Q個持てればいい。順番に並べてO(log(Q))くらいでlower_boundができればよさそう。1回のクエリでたくさんの区間を消すことはあるけど、増える区間は全体で高々Q個なので、全体では消す個数もQで押さえられる。
なんかソート済みを保ちながら要素を追加削除できるやつ。まあstd::setか。定数倍が重いからあんまり使いたくないけど。座標圧縮も考えたがちょっとわからなかったのでまあsetを使う。区間は重複しないのでmapにした。そして、lower_boundで見つけた区間に対しては順方向に次の区間を見ていってどこまで覆うかという向きで考えていたので、新しい区間の頭と見つけた区間のお尻の比較でlower_boundしたい。なのでmapのキーはお尻の位置、mapの値は頭の位置とした。
色々なケースがあってややこしいが、区間が被ってなければ（ここでは、2つ以上の重複しない区間が合体して1つの区間になるケースも「被る」と言ってた）単に区間を追加すればいい。被るなら被った相手を全部消して、それらと新しい区間を合わせたものを追加する。区間を追加するときに、区間の長さの最大値を更新していく。
No.675 ドットちゃんたち
状況把握に時間がかかるが、まあわかってしまえば、累積和とか逆から見るとかでなんか解ける見た目だ。符号の向きとか全然わからないけど解く方法が絶対に存在してるやつだ。
向きを0,1,2,3で表し、回転させる関数を作る。移動はそのときの累積回転回数mod4で意味が変わるはずだから、入力を回転させて移動の累積和を保存する。累積回転数も保存する。色々考えたけど、符号を全通り試せば行けるんじゃね。実際サンプルが通ったので提出した。WAだった。
（追記）よーやくAC。符号というか、うん、逆から見るためにはたくさんの変数を保存しなくちゃならなくて面倒なので順方向に見てたのよね。それでp[n]-p[i]とかp[n]とかp[i]とかその符号反転とかバリエーションがすごくて、それだけならまだしも、試すべきパターン数がすごく多いことに気づいてなかったのでもうダメ。考え方としては、回転を床の回転と捉え、移動は床に書かれた座標で行う。生まれた場所は当時の床の座標に変換し、移動ベクトルを単に足して、最終的な床の向きを考慮して出力すればよい。
