2017-01-01から1年間の記事一覧
木の直径のパスを一つ挙げるライブラリ 木の直径のパスを一つ挙げるやつをライブラリ化しました。これを解いている時に必要になって、自明なのに妙に実装に時間がかかったので作りました。この問題でverify済みです。中のアルゴリズムは非常に簡単で、次の通…
Educational Codeforces 035 div.2 F. Tree Destruction Problem - F - Codeforces 解法 まず直径をできるだけ残しておくべきであることがわかります。なぜなら、直径を残している間は、それ以外の辺を破壊していくときに、その辺を破壊したときに得られる最…
CS Academy 062 E. Tree Partition CS Academy 解法 なんらかの方法によって、各部分木の頂点集合とその補集合が即座にわかればよさそうです。しかし各ノードに部分木の頂点集合のsetを持たせるのはさすがに厳しいです。そこで、各頂点に乱数を割り振って、…
CS Academy 061 F. Xor the Graph CS Academy 解法 これを読んでいるとこの解法がかなり自然に見えます。まず明らかに同じ辺を3回以上使うメリットはありません。そのような構造は、パスの個数を増やすことなく、パスの長さを小さくできるからです。すべての…
平面上のロシアゲー（構築ゲー）を解くためのそこそこ一般的なテクについて この記事はCompetitive Programming Advent Calendar 2017の12月13日の記事です。 ロシアゲーとは 「ある条件を満たすものを何でもいいから一つ出力しなさい」という形式の問題のこ…
CS Academy 060 E. Flip the Edges CS Academy 感想 DPの書き方がよくわからなかったので、pekempeyさんより解説をいただきました。 解法 まず二度以上選ぶ辺は存在しないことが言えます。なぜなら、もし仮にそのような部分があるとき、そのような部分は反転…
この記事はCompetitive Programming Advent Calendar 2017の12月8日の記事です。 競プロにおけるオイラー路とその応用について 目次 ・はじめに ・オイラー路とは？ ・無向グラフのオイラー路 ・有向グラフのオイラー路 ・無向オイラー路の構築 ・有向オイラ…
CODE THANKS FESTIVAL 2017 参加記 CODE THANKS FESTIVAL 2017 - AtCoder 前日 前日はボードゲームの会に参加しました。会う予定の人は全員初対面だったため、もちろん緊張でヒザがガクガク震えていました。Tikeさん、TsutaJさん、フェリンさん、らてあさん…
Inverse of factorialsをO(N)で列挙する はじめに 素数 $p$ を法として、 $n$ 以下の階乗の逆元を $O(n)$ で列挙しちゃおうというアレを知っていますか？（僕は知りませんでした。。。）（コードが読みにくくなる割には）そんなに高速になるわけではないため…
CS Academy 058 E. Path Inversions CS Academy 解法 ある長さ $k$ のパスを固定して考えると、このパス上の転倒数の個数とこのパスを逆に進むようなパス上の転倒数の個数の和は、書かれている数に関わらず常に、${}_{k + 1} C _2$ となることがわかる。これ…
DDCC 2017 D. なめらかな木 D: なめらかな木 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 | AtCoder 解法 bitDPをする 実装 #include "bits/stdc++.h" using namespace std; const int MOD = 1000000007; int n; vector<int> g[55]; map<tuple<long long, int, int></tuple<long></int>…
Atcoder Grand Contest 009 E. Eternal Average E: Eternal Average - AtCoder Grand Contest 009 | AtCoder 感想 実装軽いのに考察が重すぎる...。 解法 最終的に残る数を$\ x\ $とする。$\ x\ $は連分数で書かれるような数になるが、このまま考えるとわか…
Atcoder Grand Contest 008 D. K-th K D: K-th K - AtCoder Grand Contest 008 | AtCoder 解法 位置が確定しているものを左から順に確定させ、その数の左側に置かなければいけない個数を空いている場所に左詰めで書いていく。これができない場合は不可能。位…
Atcoder Grand Contest 013 E. Placing Squares(追記) E: Placing Squares - AtCoder Grand Contest 013 | AtCoder 感想 愚直$\ DP\ $の高速化に失敗したので、解説放送を見て想定解を実装した。 解法 $\ 0\ $から$\ n\ $までの任意の位置に柵をおいて、その…
DDCC 2017 本戦 C. グラフいじり C: グラフいじり - DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 | AtCoder 感想 dfsの計算量を間違えていた。$\ O(m(n + m))\ $。これは$\ O(n^4)\ $なので、$\ TLE\ $する。仕方がないので無理やり…
Atcoder Grand Contest 013 E. Placing Squares E: Placing Squares - AtCoder Grand Contest 013 | AtCoder 感想 $\ O(n)\ $を高速化したかったけどできてない..... 想定解はまた今度考える。 解法 まず愚直に$\ DP\ $を書くと$\ O(n^2)\ $になる。この記事…
Atcoder Regular Contest 084 F. XorShift F: XorShift - AtCoder Regular Contest 084 | AtCoder 解法 基底とする数は与えられる$\ n\ $個の数だけとして考えて良い。これらを任意の個数使って、シフトさせたり$\ xor\ $をとったりして数を作る。ここで$\ x…
Atcoder Grand Contest 007 F. Shik and Copying String F: Shik and Copying String - AtCoder Grand Contest 007 | AtCoder 感想 考えることはシンプルなんだけど条件が難しい 解法 $\ T\ $の連続する文字の先頭文字と、それに対応する$\ S\ $の文字を決定…
Atcoder Grand Contest 010 E. Rearranging E: Rearranging - AtCoder Grand Contest 010 | AtCoder 感想 とにかく自力でACできて喜んでいたが、うさぎさんのコードを見ると圧倒的に簡潔でわかりやすかったので、大幅に真似て改良した。 AtCoder Grand Conte…
Atcoder Grand Contest 010 D. Decrementing D: Decrementing - AtCoder Grand Contest 010 | AtCoder 感想 奇数の$\ gcd\ $で割ったときに偶奇の個数が変わらないことがポイントだった。 解法 明らかに愚直に考えると厳しいので、とりあえず偶奇によって場…
Atcoder Grand Contest 006 D. Median Pyramid Hard D: Median Pyramid Hard - AtCoder Grand Contest 006 | AtCoder 感想 いいところまでは考えられたような気がしたけど結局解説を読んで。 てきとうに書いて投げたら通った。 最近は二分探索をあまりバグら…
Atcoder Grand Contest 002 D. Stamp Rally D: Stamp Rally - AtCoder Grand Contest 002 | AtCoder 解法 二分探索をまとめてやる感じのやつ。各$\ mid\ $の値に関するソートをしておくことで左から順に見ていける。$\ O(m {\log}^2 m)\ $。 実装 #include "…
Atcoder Grand Contest 007 C. Pushing Balls C: Pushing Balls - AtCoder Grand Contest 007 | AtCoder 感想 難しいよ 解法 解説動画がわかりやすい。各ボールの距離に関する数列を書いて実験すると、その次のステップ（の期待値）の数列も同様に等差数列に…
Atcoder Grand Contest 019 C. Fountain Walk 感想 500点くらいの問題 解法 一般性を失わずに左上にスタート、右下にゴールがあると仮定して、それらを頂点とする長方形を考える。このとき、明らかにこの長方形の外に出て遠回りする方が経路長が短くなるよう…
Atcoder Regular Contest 013 C. 笑いをとれるかな？ C: 笑いをとれるかな？ - AtCoder Regular Contest 013 | AtCoder 感想 友人が問題文の内容がおもしろいと言っていたのでやったみた。確かにおもしろかった。 解法 各座標軸を基準にみて端点同士の点より…
Atcoder Grand Contest 011 E. Increasing Numbers E: Increasing Numbers - AtCoder Grand Contest 011 | AtCoder 感想 数論の問題などでたまに見かけるレピュニットの性質をうまく利用した問題で少しおもしろかった。 解法 増加的な数を9個以下のレピュニ…
AOJ Prime Caves 感想 実装がめんどくさい 解法 どう見てもDPするだけ。$\ m \leq 10^6\ $なので、$\ 1000 * 1000\ $の正方形のマスを用意して考えればよい。すごく面倒だが、各数を投げるとその配列上での位置を返す関数を作る。これは各正方形の左上の数が…
Atcoder Grand Contest 004 F. Namori F: Namori - AtCoder Grand Contest 004 | AtCoder 感想 解にたどり着くまでに考えることがたくさんある。ケースに応じて適切なアルゴリズムに落とし込んでいくのが、おもしろい。 解法 まず連続する同色の頂点を反転さ…
Atcoder Grand Contest 014 E. Blue and Red Tree E: Blue and Red Tree - AtCoder Grand Contest 014 | AtCoder 感想 難しいがおもしろい。解説を読んで、少し人のコードを参考にして書いた。 解法 辺の色が異なる2つの木を重ね合せて考える。そのグラフ上…
行列ライブラリ 競プロ用に行列ライブラリを作った。特別に綺麗だとか高速だとかそういうことはないけれど、もし利用したい人がいれば、勝手に利用していただいても構いません。多分動きます。Typeは、値が小数になる場合と、逆行列が必要なときにdoubleにし…
