result:ooooo---
rateing:1914->1913
■A - Shampoo
v %= (a + b + c);
をすれば一周ですむ
■B - Hit and Blow
setをつかう
■C - Collision 2
y座標でグループ分けしたものをsortして
RLと並んでいる場所があればNG
■D - Moves on Binary Tree
2進数に変えて末尾に"add0"or"add1"or"pop_back"
10進数に直す時は、成約が絶対0になると教えてくれている場所は無視する
■E - Edge Deletion
ワーシャルフロイドを行う。
辺s-tが不要なのは、dist[s,x]+dist[x,t]<=dist[s,t]となるxが存在する時(xはs,tではない)
■F - Lottery
dp[i][j][k]:=i番目まで見た、j回くじを引いた、k種類
とするこれもコンテスト中に解けるべき
■G - Sqrt
とけてたのにね
dp[i]:=開始がiのときの答えとすると
dp[n] = dp[1]+dp[2]+.......dp[sqrt(x)]となる
もう少し眺めると
dp[i^2]からdp[(i+1)^2-1]は等しくなるのでうまいことやればいい。
sqrt()には誤差があるのでx*x<=nを満たす最大のxを求める関数を自作しているのだが
const int INF = 1e9;
long long ng = 3 * (long long)INF + 1;
とすべきところを
long long ng = 3 * INF + 1;
としていたため死亡(sqrtlを使えばいいらしい)。
Xの範囲を1e18で収めてくれ(普段この関数はng=INF+1で使っている)
10分じゃ焦ってデバッグ出来ませんでした。
■Ex - Builder Takahashi (Enhanced version)
SとGを結ぶ最短経路を１つ用意する
その最短経路に侵入する経路も同様に用意する
最短経路上から、最短経路と侵入経路を奇数回通って最短経路に戻ってくるような最短経路の経路数を求めればいい。
外枠を通るときの処理に注意。
