5完水パフォ。Fそこまで簡単だったか？少し前に「淡々と」とよく書いていた気がするけど、みんなむずい。淡々とは解けない。実装以前のところで見慣れない考察に無限に時間を吸われる。調子悪い感じはないし、苦手セットが続いてるだけだと思うけど。まあ単に苦手な問題が出たってだけでも気分はめちゃくちゃ落ちるからね。無能さを教えてもらえるという意味では苦手セットのがラッキーなのかもしれんけど。
A - 369
A < B で非減少列を作るとして一般性を失わない。候補は3つで、外側の2つは常に整数だが真ん中のやつは整数じゃないかもしれない（作れれば全部違う列になる）。また、A == B のときは3通り作れるけど全部同じになってしまうので1通り。いやまあ解答コードのイメージはわりとすぐ浮かぶけど、細部を詰めるのがめちゃくちゃ大変。難しすぎる。
B - Piano 3
同じ鍵盤に同時に両手を置くことが禁止されてないのを確認する。あとはLR独立に同じ問題を解くだけ。初回は場所を記録するだけで、次からは疲労度を足してから記録する。
C - Count Arithmetic Subarrays
しゃくとりちょっと思ったけどね。まあ正面から行くのが無難。長い等差数列を作るには差が同じところが続く必要がありその辺りの区間はみんな等差数列になる。ということで差をとって長さN-1の列を作る。ここで、長さがNから1減ったこと、一つの差に短い等差数列がダブって対応しないか、といった不安がある。長さ2以上の等差数列のみを数えることにすれば大丈夫。実装上は、同じ差が現在何個連続しているかを管理して、それを足していく（掛け算は使わない）。現在の位置の差が最後となる長さ2以上の等差数列の個数を各位置について足すことになり、N（長さ1のぶん）を足せば答え。
（追記）しゃくとり法で解いてみた。各位置から始まる等差数列を数えることを考えると、しゃくとりできるとわかる。公差を持つとか考えるとかなり泥沼にはまりそうなので、やはりこの方針は避けるのが無難だった。ただ、短いコードにはなった。i1 - i0 <= 1 || a[i0 + 1] - a[i0] == a[i1] - a[i1 - 1] というのが数列を伸ばす条件で、これが見えるかの勝負。
D - Bonus EXP
倒せないから逃げるとかじゃなくて、経験値をたくさん得るために逃がすという設定。明らかにDP。これまでに倒した数の偶奇を状態に持ち、それまでに得た経験値の合計の最大を値に持つ。倒した数の偶奇が同じならそれから得られる経験値も同じになるからね。実装はちょっと手間取ってしまった。
E - Sightseeing Tour
グラフの問題として見ると、問題文の橋は辺のことで橋とは限らないのがややこしいなとか思ってた（勝手にややこしくなってろ）。複雑そうでうんざりするけど、Q個の問題というのを見ると、K本の橋の使い方を全部試してもK!*2^K通り（記憶では2^(K*2)通りだと思っていてめちゃくちゃすぎる）しかないので各頂点間の距離を前計算しておけばいけそう。前計算は、辺が多いのでダイクストラ法とかだと怪しいが、頂点が少ないのでワーシャルフロイドが使える。辺を使う順番を決めたら辺のどちら側に行くかも決めて、これで全部カバーできる。使った辺をまた戻るみたいな動きも許可されているので前計算した距離が使える。まず現在位置を（0-indexedで）頂点0に設定し、そこから次使う辺の入る側までの距離を足し、辺の長さを足す。これをK回繰り返し、最後に現在位置から頂点N-1までの距離を足す。ここを整理するのに時間がかかった。
DPで高速化できることは気づいていたが、これはABCという競技なので不要な高速化はしなかった。
逆向きの辺を張っていなくて1WA。両方必要なことは意識していたが、書くときには忘れていた。何を考えて書いてたんだろうね。
（追記）DPで高速化した。こっちの頂点から出てきたときの最短でDP。1LL < 60 と書いて結果が常に1になってやばかった。1回目の提出は2^K回のループを外し忘れて遅くなっていた。
F - Gather Coins
DPを1行ずつやっていくことを考える。復元がなければ遅延セグ木でいけそう。復元できるように永続的な情報を残すならmapかなあと思い、なかなかまとまらないけど時間もないので実装に入る。ここで、コインが1枚固定であることに気づく。A_i枚ではなく1枚であることで何が簡単になるのかわからなかった。実装し始めて、難しすぎておかしいと思い一旦捨てる。遅延セグ木を改めて考えてみると、二分探索で区間maxの更新が走る区間を求めておいてDPの遷移が横方向になる区間を記録しておけばできそうだと気づいた。いやあ安直に遅延セグ木に行って解ける気がしなかったんだよね（安直とは）。横に動く区間は、よく考えたら重なってしまう（最初の行で横方向にコインがいくつかあると、コインがあるたびに右端まで更新が走る）が、素直に並べて区間の右端は単調増加でそれで二分探索して見つかるのは左端が最も左のものなのでたぶん大丈夫。左へ1回動く毎に二分探索するのが無難。細かいミスが多く、終了後30分以上かけてAC。ゴール地点をW-1ではなくN-1にしていて1WA。ミスが多いのでもう少し電圧を上げたいところだが、上げられないからこうなってるんだよな。
解説のLISは天才かと思ったが、思いついても復元がやはり（自分にとって）大変ではある。今日実装する気力はなかった。
（追記）解説の方法で解き直し。座標の列を解説のようにソートすると、横方向の座標が広義単調増加になるように取ればそのようにコインが取れるし、コインを取る方法があればそのコインの座標だけ取り出した部分列は広義単調増加になっている。よって復元付きでLISを求めればいい。LISの復元はやったことなくて、遷移元がのちに変化してしまう可能性があってどうやるのかと思ったが、解説を見ると、そこを終端とするLISを考えて1個前の要素を（座標の列のインデックスで）保存しておけば普通にだどれる。これで取るべきコインを順番に列挙できて、ゴール地点を追加してから、順番にそこへ向かって適当に歩いていけばいい。やはり慣れていないと時間がかかる。
G - As far as possible
コンテスト中は読んだだけ。終了後に考えて、高橋君の最適行動はわりと自明で、青木君は貪欲に1つずつスコアが最も増えるものを選んでいってよさそうだけど証明できない。それでよかったとしてどうやって高速に求めるかもわからない。
（追記）解説を読んでupsolve。木DPできるという発想は出ないなあ。まあ言われてみればDPはできるし（特に反論がないだけで理解しているわけではなさそう）、そうなると（全体に足す感じになるので）差に注目する発想が出るのもわかる。Kが1増えたときにスコアがどのくらい増えるかをマージテクみたいにするのかと思いきや、木全体で一つのvectorに突っ込んでしまえる。そういう構造だったのか。自分でここまで到達できる気が全くしない。あまりにも遠い。この世には色々なことがありすぎる。最大値を頂点に記録し、他をvectorに突っ込む処理が必要で、自分は子への辺を2回走査した（1回目で最大値を求め2回目で最大値（の一つ）を除いてvectorに入れる）が、解説の実装例では1回しかやってなくて、最大値を更新するタイミングでそれまでの最大値を（最大値である可能性が今なくなったので）vectorに入れていた。コードを見てもよくわからなかったが、そのアイデアをつかんで自分で実装したらわりと簡単にできた。いやすごすぎるこの実装。最終的にけっこうシンプルなコードでACできてるけど、本当に難しい問題だった。
