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…