4完。水パフォをとったゴミとしてこれから生きていくことになるのがつらい。毎度のことながら、コンテスト終了後ちょっとした操作ミスなどでめちゃくちゃイライラする。
A - Takahashi san 2
s.substr(s.size() - 3)。Sの長さが3以上の制約であることを確認。簡単でいいね。
B - Unvarnished Report
まとめてできるかもしれんけど、最初にS=Tのケースを場合分けしておく。SとTの短い（長くない）ほうの長さまで比較して位置を求める。違うところがなかったら位置Nで見つかったことにして、1-indexedに直して出力。
C - Separated Lunch
全探索。選んだ部分集合とそれ以外のやつの大きいほうの最小値を求める。
D - Laser Marking
全探索。next_permutationで線を描く順番を決め、N個それぞれについてどちら側から入るか2通りを決める。面倒だったし、問題文を読むのが大変だった。他の問題もそうだけど、ストーリーがわかりにくい。
E - Sensor Optimization Dilemma 2
両方の機械を買うことができるので、N=1でもけっこう難しい。個数制限のないナップサックを、2種類しかないことを利用して高速化、できなかった。価値とコストどっちでDPするのか迷って考えづらかった。混乱して考えが進まなかった。10^7というのが絶妙。フローを考えたりもしたが、結局DP。トイレに行って指数探索でまとまった（何もできない状態だったのでもっと早く行くべきだった）。
2種類のナップサックを必要なだけ伸ばしていく（足りなかったらXを上限として2倍の長さにする）。合計金額がX以下なので、2倍かそこらのロスはあってもDPの長さもN個合計でO(X)になるはず。実際の金額はDPテーブルを二分探索して求める（Nが小さいのでここの計算量は問題にならない）。提出してWA。長さの初期値を2^16にしていたが、P_iやQ_iがこれより大きいことがあるのを忘れていた（DPでREが起こる）。直して1個だけTLE。P_iがでかいと、その1個を買うためにDPテーブルが不必要に伸びてしまう。そういうのがたくさんあると、ロスが2倍や4倍どころではなくなるので、確かにTLEしそうだ。時間もないので、間に合わせの対処としてP_iやQ_iがXより大きいときを場合分けしてみたが、結果は変わらずTLE。2倍にする処理を2回連続でしたらもうそいつはダメということにしてみたがそれはWA。確かに、そうやって高価な1個を買うのが最適というケースもありそうだ。
終了後、ちゃんとした方法を考える。大きいほうがQ_iとなるようにswapしておく。X円で高々100個しか買えないなら、そちらを買う個数を全探索して、もう片方は割り算で求まる。そうでないなら、今までの方法でロスが少なくなる（2^16が2倍に伸びれば10^5円にかかる）。これでAC。22分遅れ。100というかNだね。10^7を、2倍とかのロスはあっていいからN個でちゃんと分担しないといけない。ほんとよくできた問題だよ。
F - Shipping
ほんとは都度出荷したいけど、X日というクールタイムがあるからまとめて出荷という選択肢も出るという問題。K個までしかまとめてできないという条件もあってきつそう。DPしたいけど、次にいつ出荷（CPUの命令発行のイメージでdispatchと脳内で言っていた）できるかが色々あって厳しい。制約や実行時間制限を見ると、次元の大きいDPを思いつく。最初の出荷は注文のタイミングだし、クールタイムが終わるタイミングはいずれかの注文からX日が正整数回経ったときだ。最初のL個を出荷済みでクールタイムが終わるのが注文iからX*j日経った時点であるときの最小の不満度、でDP。不満度の計算は累積和を使えばできる。遷移が難しくて手が止まるけど、配るDPで過去の全てから遷移させればよい。現在の注文の時刻とクールタイムのを比較して遅いほうを採用する。サンプルが合わないが、K個までしかまとめられないのを忘れていた。過去の全てではなくK個前までだけを見るようにする。
終了後にやって1時間ちょっと。つまりEを飛ばしてFをやるのが（レーティング的な）最適解だったが、まあそれを選ぶのは無理だよな。終わってみればただのDPだけど、あらゆるステップに時間をかけていて、合計して1時間になっている。
G - Only One Product Name
各文字について、後ろに付けていい文字と前に付けていい文字のリストが与えられている。有向グラフっぽい。被覆とかでググってみても難しいんだよな。自己辺とかは、簡単に処理できそうだけど、丁寧にやるのがしんどそう。あきらめて解説見たけどわからん。
（追記）ユーザ解説を見てめちゃくちゃ時間をかけてどうにかACを取ることはできた。かなり理解が進んだが、中途半端な理解なので、何も書けない。こうやって慣れていくしかない。出入りの個数差だけで下限が指定できるの不思議だし、フローを逆方向へ流し戻せるの知らなかった。
