F以外の6完。
A - Buy a Pen
3回同じことを書くのは人間がすることではない。Redとかを問題文からコピペしてstringの配列を作り、for文で処理する(文字列が一致したところだけでかい数にする)。綴りミスを検出できないサンプルなので気を使った。でも2分以上かかってるからベタ書きのが早いです。マジで嫌い。
B - Right Triangle
3点をrotateさせながら内積を調べる。最初rotateじゃなくreverseと書いててサンプル合わなかった(スニペットにしてるsortを書いてから書き換えたんだけど、その操作はreverseの頻度が高すぎて手が勝手に)。
C - Sum = 0
一見難しそうだけど、LRの範囲内で合計が一番小さくなるものを考えると、一番大きくなるものとの間は全部作れる(1ずつ大きくしていけばいい)。一番小さいのを作って、合計が負である間、範囲内で足していく。最後に、条件を満たしているかチェックして出力。
D - Shortest Path 3
頂点の重みは、その頂点へ向かう辺の重みに足して表現する。ダイクストラやるだけ。最後に頂点1の重みを足して答え。
E - Count Arithmetic Subsequences
最初、dpとpを入れ替えながらやるいつもので書いてたけど過去の情報が必要なことに気づいて修正。dp[i][k][d]:=A_iが末尾となる長さk公差dの等差数列の個数。長さ1の等差数列はN個、長さ2の等差数列はループ内で1個ずつ数えて、長さ3以上のやつは普通にDPっぽくやる。公差はありえる範囲が広いのでmapを使う。mapの配列にした。慣れないのでなかなか実装が見えない。
(追記)末尾だけでなくその前も持てば公差が要らなくなる。実装してみたが、3乗ではなく4乗になることに実装するまで気づかなかった(提出するとmapを使う3乗より速い)。
F - Perfect Matching on a Tree
最大重み最大マッチングは見た目が怖いし完全グラフとか書いてあるけど、よく読むと木上で頂点のペアを作る問題。なるべく遠いものをペアにする。木の直径の図を描いて考える。中心というより、頂点数が半々になるところで切るとよさそう。ペアによる全てのパスがそこを通るなら、重み(の合計)はペアの作り方に依存しない。時間もないので実装してみる。提出してRE。頂点が奇数個のときの処理が間違ってたけどそこは関係ないよなあと思いながら再提出してRE。なんか半々にできそうな気がしてたけど、うにを考えれば半々にできるわけがなかった。じゃあ半分以上に初めてなったところでいいか。でも色々な部分木がある中でどれを選んでいいかわからない。
「半分以上に初めてなったところ」とか、まんま重心分解だけど気づかない。そもそもコンテスト中にも重心分解は少し探ったが、そのときは正しい答えが得られると思えなくてすぐ捨てた。
(追記)解説をじっくり読んだけど、ちゃんと解けていてすごかった。Nの偶奇で1頂点使わないこともあるのに、その上界は思いつかねえよ。その上界がNの偶奇に関わらず達成できるとか思いついても考えないよ。ペアのなすパスすべてがある頂点を通ると仮定して、その頂点から出ている辺が2個より多いときにどうペアを作るのが最適かわからないと思っていたが、言われてみれば解説で言う別々の部分木から2頂点を選べば最適だ(必ず通る頂点までの距離が寄与の最大であり、1頂点余るならその頂点自身を省く)。重心を選べば、一つの部分木が半分を超えて占めることはないので、解説のようにすれば最適なペアが作れる。また、これは重心の一つを選んだときの最適なだけでなく、さっきの上界も達成している。やばすぎる。どうすれば思いつけるかはわからないが、確かに解けている。
G - Count Substring Query
FGをざっと見て、(Fの見た目がやばいので)順位表を見て、Gへ。Gは簡単そうな見た目だったが、(たくさん解かれていて)ここまで簡単なんだと思った。
Suffix Arrayかなと思い考えるとできそう。単に二分探索することを考えると、高々T_iの長さぶんの比較をlog(N)回程度すればいいので、間に合う。SuffixがT_i以上になるところから、SuffixをT_iの長さ以下になるように切り詰めたものがT_iより大きくなるところまでの距離が答え。stringを切り出すと時間がかかるので仕方なく比較を自前で書こうとしていたが、compareというのがありそうだと思い出してそちらへ(T_iの長さぶんだけ切り出すのは思いつかなかった)。string::compareの使い方がわかってなくて、オフセットとサイズを指定する対象を逆に書いてしまった。それを正しく入れ替えたときに不等号を逆にするのを忘れてサンプルが合わなかった。何も工夫せず二分探索が間に合うの、素直な問題だ。
(追記)二分探索なしでできるのかあ。Z-algorithmとかだとこういうSもTたちも全部入れてっていうのやるけど、Suffix Arrayでもやっていいんだな(?)。logが付かないとはいえさすがに重く、二分探索したほうが実行時間は短かった。