時間ギリギリで6完。ペナが痛い。
A - A to Z String 2
愚直やってもいいけど、A問題程度の難易度ならO(1)で。N個の塊がX-1個（ターゲットの文字よりも左にある文字の個数）の文字から何個取れるか。割り算。
B - 1D Pawn
こんなの読む気力ないよ。駒を配置してシミュレーション。あー、そのままやる手もあったか？
（追記）そのままやるのが楽だった。
C - Robot Takahashi
まず思ったのは、体重と子供大人の情報をペアにしてソート、累積和でスコア計算（バチャ中はもっと曖昧なモヤモヤ）。ただ、同じ体重がありえるのでやや面倒。楽な方法をもう少し考える。子供と大人に分けてvectorに突っ込み、ソートして境界候補で二分探索。これだとN通り（ほんとはN+1通り）なので、全部子供と判定するのと全部大人と判定するのを加える（どっちかは二分探索してるけど）。解けるのはすぐ解けるけど、どう考えるのが楽か自然かというのが全然わからず難しくて面白い。
D - Jumping Takahashi 2
むずそー。これ、適切に始点を決めたらどの（一つの）ジャンプ台を指定されてもそこへ行けるってことなんだね。N個のジャンプ台全てを通る経路が存在するってことかと最初思って、その読み方をなかなか否定してくれないので大変だった。結局読み方がわからず、こっちの意味ならこう書いてないだろという読みでそっちの解釈に。二分探索が思い浮かぶ。始点も全探索で、3乗にlogも付いちゃうけど、200で3秒ならまあ通りはしそう。BFS部分が2乗かかるんだよな。計算量落とせそうではあるけどさすがに短時間ではわからないのでそのまま書く。答えは最大で4*10^9になるので注意。
いやワーシャルフロイドは思いつかなかったな。
（追記）ワーシャルフロイドは定数倍が軽いという安心感、全部求まって楽（残るのが困難のない実装だけ）。kyopro_friendsさんのO(N^3)解も、確かにこれは距離になっているのでワーシャルフロイドが使えそう。
E - Addition and Multiplication 2
順番は関係ないので回数だけ。まず桁数最優先なので、桁数最大化を考える。最もコストが低いものだけを使えばいい。これで桁数がわかったので、あとは上位桁から順に大きい数に変更できないか試す。最低コストを各コストから引いて、9から順に変更コストを払えるか試していく。WAになって原因がわからなかったが、変更したらループから抜けるというのを忘れていた。breakを書き足してAC。
F - Teleporter Setting
難しそうだが、よく読むとけっこう単純。未定だったものを使うかどうかで場合分けする。使わない場合は共通（BFSを1回するだけ）。使う場合は、どっち向きで使うかで場合分けする。使わない場合のBFSを始点と終点からそれぞれやっておいて、未定のもう片方の頂点たちの中でコストの最小値を前計算。
これもWAの原因がわからなかったが、結ぶ先をどこにしようが関係なく行って戻ってくるというパターンを完全に見落としていた。負けを認めざるを得ない。今日全然証明できてないというのは感じてた。本当に他にはないかというのもわからなかったし。
G - Prefix Concatenation
問題を読んでACLのZ-algorithmを見に行くと、Twitterで致命的なネタバレを見ていたっぽいのでEFのデバッグを優先した。
（追記）ネタバレはZ-algorithmで、これを使うとすんなり解けた（実際は、色々手間取ってはいる）。Tについて普通に前からDPしていく。配るときに工夫しないと間に合わない。区間最小値更新と1点取得があればいいので、遅延セグ木が浮かぶが、普通のセグ木でいい。セグ木は、Tの最初の文字の前から最後の文字の後まで|T|+1の長さ。そこに至るまでの最小コストは、i文字目だったらiから末尾までの区間最小値でわかる。更新は、SとTのi文字目からの共通部分の長さだけiに足してそこへコストに1足した数でchminする。
S+Tをatcoder::z_algorithmに渡しているので、共通部分の長さがNを超えることがありサンプルが通らなかった。そういえば昨日は'@'とか別の文字をはさむことを考えていたが忘れていた。
