今回から7問。F以外の6完。Fはパッと見ただけで、読んでもいない。WTFで心が疲れていたので、Eまで通したらさっさと順位表を見てしまった。
A - Legendary Players
コピペできる形で出してくれてはいるが、整形がけっこう大変。\n を },\n{" に置換するとかそういう作業をする。最初はpair<string, int>の配列にしようと思っていたが、map<string, int>にできればもっと簡単で、同じ形で初期化できてくれと思いながら書いて、動いてくれた。3分かかってる。これは仕方ない。A問題はもっと簡単にしてくれ。
B - Measure
意味がわからないので言われた通りに実装する。そんなに時間はかからないからいいけど、こういう意味不明な問題はやめてくれ（ABC285Bよりはマシ）。
C - False Hope
「はじめに知ったほうの」の意味がわからない。どんな問題かわかってから見るとしっくりくる。どんな問題かわかるための文章なはずなんだけどなあ。問題は実装。next_permutationを使うまではいい。8本の列の列挙が面倒。手で書くというのもあるが、1箇所だけミスするとか考えるとやはり縦3本と横3本はループを使いたい。斜めは手で書いた（今見たら3回ずつチェックしてて草）。その1つの列の3要素について、早く知る2つを取り出して等しいか判定するのが最難関（制約から2個が等しいなら残りの1個はそれとは異なる）。ifを何回も書きたくないので、pairにして知る順番でソートした。手元で600msを超えていてびっくりした。vectorのインスタンスが100万個以上作られると遅くなるのだった。微妙に怖いので少し減らして400ms台にして提出したら117ms（言語アプデで速くなった？）。青コーダーが15分かかる問題をCに置くのはやめてくれ。
D - Minimum Width
これは二分探索してくださいと問題文に書いてある。スペースを入れるのが難しいが、現在の行にどこまで入れたか持っておいてそれが0でないなら1文字追加すればいい。はみ出したら次の行に移ってその単語を入れる（今気づいたけど現在の行が0文字のことない実装だったな（初期状態で0行目に幅分の文字が詰まってる実装にしてた））。二分探索の範囲を10^9よりちょっと大きいくらいにしていて、サンプルに助けられた。なんかMが大きいと思っていたので最悪1行1単語でいけるという前提で書いてた。
提出してWAで、少し見直してわからないのでEへ行った。Eを通して戻ってきて改めて読むと、次の行に単語を（幅に依存せず）置けることになっていた。二分探索の下限をLの最大値にしてAC。解説の「すべての単語の先頭にあらかじめ空白をつけておき」っていうのすごいなあ。それでちょうど1だけずれた答えが求まるのか。
E - Bus Stops
lcm(1, 2, 3, 4, 5, 6 ,7, 8)を求めると840。10^8くらいの計算回数なのでなんとか間に合う。840で割ったあまり毎に愚直計算して、かかる時間を求める。クエリは入力にこれを足すだけでいい。
F - Fighter Takahashi
開いて3秒くらい見ただけで、やってない。
（追記）bitDPというネタバレを見て考えたが、かなり難しい。時間をかけて考えて整理して実装。難しいので解説も見るけど、わかってることしか書いてない（あるいは書いてあるけど読めない）。10!通りは試せないけど、それまでに訪れた集合が同じなら順番は関係なくなる（手順の良し悪しは最終的な強さに対応し、取る薬の集合を決めたとき最善手順で行けるところまで行くと最終的な強さも訪れた頂点集合も同じになる）ので、10*2^10回の探索（計算量はO(N*log(N))）をすればいい。現在行ける頂点のうちs_iが小さいものから貪欲に挑む。これで損しない。かなり苦手な実装。
WAが一つだけ出て、全然わからなかった。まず、最初に薬を取らない探索をするときに薬番号を-1にして範囲外アクセスをしていたのを直すが変わらない。次に、強さが1倍になる薬を取って強さが変わらないときに更新されてないと思い不等号にイコールを付けて提出するが、よく考えると0と比較するんだから等しくなることはなく必要なかった。改めて考え直し、今のままでもよさそうだけどカッチリDPするため、お目当ての薬に到達できないときはスコアを0にして遷移しないようにしたが、結果は変わらなかった。翌日も悩んで、考える気力もなく時間を無駄にし続けた。他の人の提出を見て、自分と同じ場所がWAになっている人が見つからなかったが、Yesとだけ提出している人がいて自分のWAはYesが正しいのにNoを出力しているのだとわかった。しかしそんなわけないように思える。さて、薬はできるだけ後に取るのがいいが、今のやり方だと必ず探索の最初に取ることになっている（前の探索で行けるところまで行っているので）、というのは前から気づいていた。そこで、薬を取る前に他の頂点を探索してしまうと、薬がないため諦めてしまう（薬を取れば倒せるかもしれないのに）ということに気づいた。そこをどう修正するかもなかなか難しかったが、まあバグがわかれば直すだけ。やっとAC。
日曜日にプロセカのブログを書く予定だったが、午前中これをやって午後はぷよぷよの配信（ぷよぷよニューヒーローフェスティバル）を見ていて、夜になってやっと提出するがずっとWAのままで、ニコ生で涼宮ハルヒの消失をやっていたので見始めたらやっぱりクソ面白くて、今日改めてやってたら昼までかかって、それも思考の密度は極端に低くTwitterみてダラダラしたりソースコードを前に何も考えずただそこにいるだけだったり、もう最近の自分の時間のなさを象徴するようなものだった。改善案は特にないです。
G - Counting Shortest Paths
順位表を見てこっちに集中。「補グラフ 最短経路」でググるとAtCoderの解説が出てくるのでそれを読む。こういうグラフでBFSできるという話の存在をなんとなく知っていたのが大きい。未訪問の頂点を持っておくらしい。解説に書いてあることがすぐに理解できるわけではないが、できそうだという雰囲気は感じる。現在の頂点から行けない頂点の個数を稼ぐには辺を消費しないといけないので、未訪問の頂点を毎回全部見ても、訪問済みになるか辺を消費するかどちらかは達成されるのでO(N+M)になっていそう。書かれている通りに実装しようとも思ったが、計算量に自信が持てないのと、自力で計算量OKな方法を思いついていたことから、自分で考えた方法をとった。まず現在の頂点から行けない頂点に印を付ける（これは処理が終わったらいちいち消すことで全体でO(M)でできる）。未訪問の頂点のリストをなめて、行けないものは次の未訪問リストに追加、そうでないものは普通にBFSを進める。これで頂点1から各頂点への最短距離がわかった。最短パスの個数も一緒に求めるのはあきらめた。頂点たちを最短距離で分けて、距離hから距離h+1へ何通りあるか遷移させる。これは、辺が全部ある状態から削除したぶんを引けばいい。やったことある処理だ。サンプルが合わないが、BFSしながらパスの個数も求めようとしていた名残りの変数を使っていたからだった。また、最短距離で分けるとき、到達できない頂点を考えてなかったことに気づいてそこも修正した。これでAC。計算量もいい感じにできてよかった。
