コンテスト中AC:A〜D C - Calendar Validator 以下の3条件を満たす必要があります。 ・最後の行を除くすべての数について、自分の下の数が、自分の数+7 ・最後の列を除くすべての数について、自分の右隣の数が、自分の数+1 ・すべての行について、要素の数を…

コンテスト中AC:A〜D C - Triangles? で全探索可能です。 面積が正でない三角形は、面積が0の三角形です。 言い換えると、直線上に3点が並んでいる時、面積は0になります。 3点が直線上にある時、線分の傾きが同じになるので、 三角形の面積が0でない時、 が…

コンテスト中AC:A〜D C - Doukasen アルゴリズムとしては、 左端と右端の導火線のうち、燃え尽きる時間が早い方を燃え尽きさせ、そのかかった時間分、もう一方の導火線を短くすることを繰り返す。その際、左から進んだ距離を合計しておく。最後に、導火線が…

コンテスト中AC:A,B A - Gold and Silver を折線グラフで考えたとき、下に凸な頂点で金に交換、上に凸な頂点で銀に交換し、それ以外では何もしないのが最適です。 始点と終点は例外なので、のとき、以下のようにします。 1.金を持っているとき なら、まだ上…

コンテスト中AC:A〜E D - Between Two Arrays 以下のDPを考えます。 がである整数列の総数 遷移を考えると、のとき、をにできるので、 となります。 これをについて計算していると、 というワーストケースを例として計算量はは超えてくるので、計算量を改善…

解説なし 問題文の読み違えで、全ての要素が以上の部分列を求めると勘違いしており、解けませんでした。 部分列の問題では各が必ず末尾に付くような部分列を考えていくと、重複を避けて数え上げることができます。今回もその方法で解くことができます。 具体…

与えられた木を、頂点1を根とする根付き木とみなします。 辺で結ばれた頂点を考えます。頂点の方が根に近いものとします。 根からDFSをすると、での探索が終了した後にに戻ります。 を根とする部分木について、の子孫についてのが求まっているとします。 か…

コンテスト中AC:A〜D D - Online Games の制約が小さければ、以下のimos法で解けます。 ・人目について、配列のに+1、に-1する。 ・最後に、を2から最大日数まで順に+=する ・日目のログイン数は人である。 今回制約が大きいので配列保持することはできませ…