ABCDEGの6完。Eまで調子よく解いて順位が低くFGが難しめということで、なんとか片方解けてよかった。
今日は、ずっと溜めていたABC315Gと新エディタコンAをやることができた（何日か熱っぽくて頭が働かなかったのとアニメゲームで忙しかったのとで）。内容はともかく、久しぶりにいいコンディションで臨めた。
A - Full Moon
1日目というのは、Mが1以上というだけで、忘れていい。普通にMからステップPでfor文を書く。割り算でもできるけどA問題だと考える時間がもったいない。
B - Overlapping sheets
愚直に塗り潰して数える。考察難度はそこそこあるが、実装はシンプルな2重forだけ、嬉しい。
C - Blue Spring
ソートしてしまっていい。パスを使う回数を1回ずつ増やしながらそのときの合計金額を求める。その最小が答え。
D - General Weighted Max Matching
グラフというより頂点を2個ずつ選んでいく感じ。DFSとかでもできそうな気がするけど、さすがに本番でbitDP以外を選ぶ勇気はない。dp[選んだ頂点の集合]=重みの総和の最大値、とする。遷移は、最後に選ぶ2頂点を全探索して貰うDP。思ったより簡単だった。簡単なら10分以内に通してほしいけど。
E - Sandwiches
簡単そうに見える。真ん中を固定してみると、左右にある各数の個数がわかればいいし、差分計算もできそう。手が止まることはなかったが、最終的な実装がなかなか見えず時間を消費した。左から見て差分計算していく。各数が左右に何個あるかを持つ。真ん中が違う数という条件がないときの個数は差分計算できる。3つ同じ数になる個数は普通に計算できる。思ったより重かった。現在の位置とその前の位置を見ていじるので2回計算をするが、同じ数だったときにも2回まとめてやって壊れていた。サンプルに助けられた。
（追記）解説の別解の「どちらかというと両端の要素に着目する解法」で解き直した。こういうのをやりたかった。まず、真ん中だけ違うという条件を外して考える。左を見て、同じ数までの距離の和がわかればいい。これ自分では、その数が直前に出た位置を覚えておいてまとめて更新とか考えてたけど、解説見たらシンプルに面積から引かれるぶんを持っておくだけでいいのね。3つ同じ数のやつは各数が何個あるかわかれば簡単に計算できる。
F - Octopus
サンプル1が1個の区間になっていなくて既にやばい。あまり考えたくはない。N+1個に分かれた区間毎にカウント？ソートして近い順に割り当てていいと思うので、近い順の順番が変わるO(N^2)回をO(log(N))で検出してそれぞれをO(1)で処理？このとき10分くらい残っていたが、できる気がしなかった。
（追記）解説を読む。切り替わる地点がO(N^2)個と知ればまあ。長さ0の区間はどうでもいいので考えなくていい。左端と右端の無限に続く区間も除外。それぞれの区間について、全て条件を満たすか全て満たさないかのどちらかなので1点だけ愚直に計算する。左端の区間が-(2^60)より左にあるケースに気づかずWA。直してAC。最初、順位が入れ替わるO(N^2)回を検出しようとしていたが、それだと各区間内でどこが条件を満たすか改めて調べないといけないので大変だった。
G - Typical Path Problem
簡単そうに見えるが、少し考えてわからないし、問題名も知識がないと解けなさそうで怖い。頂点B視点で考える。しばらく正面からやってみるが、無理そう。辺素パスとかでググってみるがわからず。同じ辺を使えないならフローは？同じ頂点も使っちゃダメだけど、頂点をの中にグラフを構築して辺にする方法がありそう？頂点を通るときに必ず通る辺を用意する。こういうのAtCoderでごくたまに考えるけど、工夫が実ってACにつながるの珍しい（嬉しい）。最大流の計算量がそのときはわからなかったので、最小費用流を使った。Cを経由してAに行くケースをはじけてなくて、またサンプルに助けられた。定数倍がめちゃくちゃ重いけどlogが1個付くだけだから大丈夫と思って提出して572ms。思ったより重い。
（追記）頂点の中に、つながってる辺の数だけ頂点作ってたけど、直接入口と出口につなげばよかった。これならそんなに重くない。
