atcoder.jp おもしろ解法次数が 以上の頂点は取り除いても、最適解を構成できる。 次数が の頂点は、たかだか 個の部分木しか繋げられないので、 つ以上の部分木が余る。 そのため、次数が 以上の頂点が最適解に含まれる時、その部分木の中の次数が の頂点と…

atcoder.jp面白れー問題 解法 この問題は、全てのスイッチを0にする問題と、xorでスイッチの階差を取った時に全ての値を0にする問題が等しい。 この時、区間内の全ての要素を反転する処理は左端と右端を反転させる処理になる。この処理が でできるようになっ…

not-522.appspot.com 900が一番簡単だけどA: Flip and Rectangles大きさが一定でなくても良いので、市松模様になっていると、色を行で全て同じに出来るので、 全て黒にすることが出来る。厳密な証明は2x2の4マスで考えると出来る(はず)。 左右2マスの色の異…

not-522.appspot.com 難しいA: Coinsまず、 でソートすることを考えてみると、金のコインをあげる人は、銀のコインをあげる人よりも左に来ることがわかる。 もし、銀をあげる人が金をあげる人より左にいた場合、もらい方を交換することで、必ず正の差分が生…

3日経つと、問題の解法を忘れてしまっています。 AtCoder Virtual Contest A: Colorful Hats上限と下限の差が2以上だと矛盾するので、"No"と出力する。 差が0の場合は、全体の色が異なっているのか、少なくとも2匹は同じ色になっているかのどちらか。 そのた…

色々と考察が出来て嬉しい AtCoder Virtual Contest ↑リンクA: Awkward Response桁数がわかっていれば値 を 倍にした時に、必ず より大きくなるから、数字の大きさを考慮しなくて良くなる。 この時 だと 辞書順で小さいので "No", だと "Yes" と出るので単調…

atcoder.jp ACPCVC20200120のCで出ました このセグ木の使い方が少し教育的と感じたため、メモとして記述してみます。問題文 個のマスがある。コマを２つ持っていて、コマはそれぞれマス にある。 マス にどちらかのコマを移動させるというクエリを 個処理す…

私もこれを書いてみようと思います。A問題 Robot Racingatcoder.jp解法右のロボットをできるだけ早くゴールさせるには、左のロボットの座標を順に、 へ移動させておけば良い。これを「操作」と呼んでおくとする。 詰まりすぎて出来ない場合は、詰まりすぎて…