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で出ました このセグ木の使い方が少し教育的と感じたため、メモとして記述してみます。問題文 個のマスがある。コマを2つ持っていて、コマはそれぞれマス にある。 マス にどちらかのコマを移動させるというクエリを 個処理す…
私もこれを書いてみようと思います。A問題 Robot Racingatcoder.jp解法右のロボットをできるだけ早くゴールさせるには、左のロボットの座標を順に、 へ移動させておけば良い。これを「操作」と呼んでおくとする。 詰まりすぎて出来ない場合は、詰まりすぎて…
問題文https://codeforces.com/problemset/problem/1268/B 列からなる高さがそれぞれ のヒストグラムがある。 であり、広義単調減少になっている。 このようなヒストグラムから、 であるか であるような長方形を何個作ることが出来るかという問題。制約 解法…
問題atcoder.jp 高橋くんが、まだ辺が存在しない $N$ 頂点のグラフに、 \(M\) 回任意の頂点へ移動しながら有向辺を張っていく。はじめは頂点 $1$ にいる。 \(M\) 回の移動後にそのグラフが強連結になっているような移動の仕方の通りの数を求める問題。制約$1…
atcoder.jp$0$ か $1$ を末尾に挿入,末尾削除をする操作を $N$ 回行って、最終的に文字列 $S$ にする操作列の場合の数を求める問題。 $1 \leq N \leq 5000$ と大きい。解法実は、同じ長さの文字列であれば操作列の場合の数は全て同じになる。なぜなら、操作…
初期のコンピュータ テスト範囲(具体的な発言は避けておく)であるためLibre Office Writerというソフトで色々と書いていたんだけど、コピーでそのまま貼り付けられたから投稿する。 目的はコンピュータの歴史を理解することで、 なぜこういうものが生まれた…
嫌なくらいconfigure: error が出ることがある あるね。 library not found の時はだいたい、規定のライブラリをインストールするとうまく行きます。 ディレクトリが存在しないって時も同じ対処が出来ます。 エラー内容をグーグル先生で調べて、何をインスト…
タイトルそのまま ツイストペアケーブルをつけてみた。 CAT5eのやつ。 10年前のさらに30mもあるやつ。 別にそんな長い必要ないけど、まあつけてみてどうだろうなって思った。 クソ速い あ、まあそうだろうな。 でも、もう相当使い込んでいるやつだし、ちょっ…
一応、悩んでいる人も多いと思うため投稿。 この前、 Linux Mint 18.3 MATE をデュアルブートでインストールした。 しかし、とあるエラーのせいで2日くらいかかってしまった。 ubi-partman crashed とか PCIe Bus Error とか Linux Mintのインストールという…