コンテスト中AC:A〜E E - Ranges on Tree コンテスト中は確信が持てないまま通してしまいました。 解法に至った経緯をメモしておきます。 まず、問題文の意味がパッと見で理解できませんでした。そこで、入出力例を確認して、ざっくりと以下のような制約であ…

コンテスト中AC:A〜E B - Intenger Division 以前、このような自作関数を作っていました。 template<typename T> T Floor(T a, T b) { if ((a<0 && b<0) || (a>0 && b>0)) return a/b; else return (Abs(a)+Abs(b)-1)/Abs(b)*-1LL; } これを使うことで、Floor(X,10LL)で</typename>…

コンテスト中AC:A,C Bはコンテスト後自力AC。もう少しで解けそうでした。 A - Floor, Ceil - Decomposition 実際に10まで、xとfloor(x/2)×ceil(x/2)のどちらが大きいか手計算しました。 すると、 x≦4なら、x≧floor(x/2)×ceil(x/2) x≧5なら、x

解説AC 問題 公式解説 公式解説で解法だけみて、実装は自力でしてみようと思ったのですが、これも上手くいきませんでした。結局、実装も解説のものを確認しました。 LISの長さが3未満の保持方法 未確定の部分はinf、今回ならM+1としておけばよいようです。 …

解説AC 問題へのリンク 公式解説 単純に部分列を得るだけなら部分列DPなどが考えられますが、今回はすべての並び替えを得る必要があるので適用できません。 重複を含む並び替えの計算方法から考えてみます。 の選んだ個数をそれぞれとします。この時の並び替…

解説AC 問題へのリンク 公式解説 公式解説のメモ程度です。 の累積和をとおくと、与えられる情報は、 という風になり、 との一方が分かれば、もう一方がわかる という関係になる。 この関係をグラフ化し、とが連結ならYes。 ここまでが公式解説の内容です。 …

コンテスト中AC: A〜D A - Exponential or Quadratic D - AND and SUM 公式解説メモ 連立方程式の解き方 A - Exponential or Quadratic から、が64bit整数型に収まらなければ、直ちにYesです。 よって、64bit型を超えるまでは、実際に2を掛けていきます。そ…

コンテスト中にACしたものの、after_contestでTLEで、嘘解法でした。 この記事は公式解説を自分用にまとめたもので、新たな情報などは無いです。 ここでは、標高が低いところから高いところに行く坂を下り坂、逆を上り坂と言うことにします。 2個目の条件を…

コンテスト中AC:A〜E Eは嘘解法(Cも若干そうでしたが)だったので、ここでは省略します。 C - kasaka D - LR insertion C - kasaka 先頭から連続しているaの個数をhead、末尾から連続しているaの個数をtailとします。 先頭に付け加えるのに必要な個数は、tail…