6完。今日の脳内BGMはアイノマテリアル。ほんとはBGM再生に使うリソースがもったいないけど、ABCだしリラックスしてやれる効果もあるし、まあいいでしょう。
A - Six Characters
(6/{Sの長さ})回だけ答えに追加していく。久しぶりに気持ちよく解けるA問題。ギリギリ1分切り。
B - At Most 3 (Judge ver.)
3重ループでいいのだが（1個と2個で作れるやつは各forの最初に同様の処理を書く）、「BでDP！？」と思ったままフリーズしてしまった。Dも読んでみたがよくわからず（え）。3*10^6まで入るvectorを用意し現れたかをチェック。Wまでに何個あるかを出力（最初W超えも全部数えててサンプル合わなかった）。
C - Poem Online Judge
問題文に意味を見出すと自然な設定を補完して間違える場合があるので、極力問題文をそのまま実装していく。unordered_setで初めての文字列かを判定する（if (!st.insert(s).second) continue;）。これで「オリジナル」だけを相手にできるので、今までの最高得点を超えていたら得点とインデックスを更新する（提出が遅いものが優先されるなら「最高得点以上なら」）（最高得点の初期値を0未満にしておく）。
D - At Most 3 (Contestant ver.)
W=10^6の答えを常に出力すればよい。難しそうなので、実は2個でできたりしないかなーなどと考える。しかし、300^2（多く見積もっている）が10^6に届かないので無理。ただ、300個から3個選ぶ方法は十分多そう。0が使えないけど、それは1個や2個選ぶことに対応するから大丈夫。2個で表すことを考えると、まあ大きいのと小さいのに分けて0から99と100から10000を100刻みで。個数に余裕があるし同様のことを3個でもできそうだ。100進法で3桁。10^6が必要なので1個足りないと思いきや、0から99ではなく1から100にすればよい（今考えると990000と10000でいけるわ（3つに分けた同じグループから複数選ぶ発想がなかった））。
E - Tahakashi and Animals
ループではなく線だった場合を考える。これは、動物iまで餌をあげる最小費用でDPできる。ということは、A_N円払う行動をするかどうかで場合分けすれば解けている。しない場合、動物1に餌をあげる方法は1通りしかない。動物2にも自動的に餌が行く。する場合もまあ同様（ループするところのケアが少しだけ必要）。DPの更新で少し混乱した（A_i円払うとき動物i+1までカバーされるのでそっちも更新する必要があるかと思ったがそんなことはなかったぜ）。2個前と1個前どっちを使うか両方試して小さいほうが最小費用。
Dより解かれててヤバい。確かにDも難しかったけどさあ。競プロer、DP得意すぎ問題。
F - Two Spanning Trees
えっ、そんなのできるのと思い、頂点数5の完全グラフを描いてみる。まずT_2を考えたが、なるほどできそうではあるし、辺が減れば別の手段が現れそう。2問ぶんあって大変そうだが、解けてみたら「確かにこれは1問だ」となるのかどうか。苦手なDFS木の様子を見てみる（どちらかの答えにはなっていることを期待）。ちょっと思い出すのに時間がかかったが、無向グラフのDFS木なので、使われない辺は全て祖先とつながっている（そうでないとしたら既にその頂点は（辺を逆にたどることで）探索されているはずなので）。T_1の答えになっている。さてT_2だが、さっき考えた全域木の形、DFSと対になるものと言えばBFS、ということで考えてみると、使わない辺が祖先とつながっていたら最短経路でなくなってしまうし多重辺もないので条件を満たしている。これは面白い（そのうえ教育的で、ABCとして理想的な問題だ）。
G - Intersection of Polygons
点が内部であるかの判定は、ぐるっと見て角度が360度変わったか結局戻って0度になったか。これ行ったか戻ったかの判定どうするんだろ。凸なので、各辺を見て三角形の面積が全部非負でいいか。とりあえず書く。サンプルが、Yesが多くなるよう書いたはずなのにそうなってない。サンプルの図もPが描かれてなくてよくわからない。ここで、Pに含まれる必要があると勘違いしていたことに気づく。さて、同じ多角形の共通部分だから何かいい性質があってもおかしくないが、わからない。共通部分の多角形の辺数がO(N)っぽいとは思う。これを見つけてしまって、自分で考える時間が短くてもったいなかった。
（追記）アイデアをTwitterで見て自分で実装を詰めた。やっていくうちに、内側というより直線に対してどっち側と捉えたほうがわかりやすいんだなと気づいた。辺の進行方向に対して左側が多角形の内部だ（進行方向という言葉は解説を見るまで出てこなかった）。各辺に対し、進行方向へのベクトルを時計回りに90度回転させたものとの内積で内部かどうかの位置を表す数値を得る。M通りのうちこれが最も小さくなるものが採用される（そうじゃない向きの位置は関係ない）。具体的に採用された辺を保存する必要がないことは実装してから気づいた。最小値だけ保存しておき、(a_i, b_i)の位置がそれ以下ならOK。これは思いつけば自分の知識だけでいけたので、思いつきたかったな（早々に思いついたとして実装間に合ったかは微妙だけど）。
