こどふぉ頻出です．大体やるだけなんだけどバグらせないようにしたいという記事です次の問題を考えます http://codeforces.com/contest/1467/problem/B 概要: 数列 $a$ が与えられるので「 $a_{i -1} a_{i + 1}$ または $a_{i - 1} > a_i 少し考えるとある値…
http://codeforces.com/contest/1472A: $2^{ctz(h)} * 2^{ctz(w)}$ 個に分かれます B: 次の順で判定します．sum が奇数なら no，1 が一個以上あれば yes，n が奇数なら no，あとは yes C: 思考停止メモ化したけど後ろから決めていけばいいです D: あくまで勝…
まず数列 $a$ の転倒数を求める問題を考えますより正確には $i a_j$ となるようなものの数を求める問題で，これは fenwick tree などのデータ構造を使って以下のように解けます fenwick_tree<long long> ft(MAX); long long ans = 0; rep(i, n) { ans += ft.sum(a[i] + </long>…
http://codeforces.com/contest/1437/problem/E の部分問題を考えます概要としては，ある整数列 $a$ が与えられ，「要素を一つ選び，任意の整数に置き換える」という操作を繰り返して $a$ を狭義単調増加な数列に変えるために必要な操作回数の最小値を求める…
D - Chordsまず円を直線上に展開することに気付くと，区間を $N$ 個とる問題になって区間 $dp$ っぽいことができそうな気持ちになります．連結成分を適当に分けてそれぞれ独立に数え上げることができればよさそうなことから自然に $dp(l, r) :=$ 区間 $[l, r…
E - Modulo Pairingまず $mod\ M$ の制約を無視して考えると，数直線状で交差する二つのペアや独立したペアをとっても得することはないのでペアをすべて入れ子状にしたものが最適解の一つになります．元の問題でこれが成り立つのはいずれのペアも $x + y = m…
C - Differ by 1 Bit動く回数は必ず $2^N - 1$ 回なので $a$ と $b$ の立っている $bit$ の個数の偶奇は異なることが必要です．$0...$ から $1...$ などにはきれいに移動できるので自然に分割統治をしたくなります．頂点 $S$ と $T$ が今見ている部分の半分…
G - Tapu & Tapi 2最終的にたぷちゃんとたぴちゃんの両方が存在するような連結成分が存在しなければOKなのでそれ以外の3つの状態をすべて持つことにします。$dp1[u] :=$ $u$ を含む連結成分にたぷちゃんもたぴちゃんも存在しないもので有効な状態にする最小…
参加しました。https://beta.atcoder.jp/contests/bitflyer2018-final開始前、wifiが接続できない感じで不安でしたが、近くにnuipさんがいたおかげで安心してコンテストに臨めました。コンテスト中、ほぼすべての時間を使ってFとGを解こうとしました。Fを解…
今年も神戸大学のチームとして、アルゴリズムのプロkimiyukiさん、マラソンマッチのプロkurenai3110さん、えんぴつ画を描くのが上手な僕KokiYmgch、の3人で出ました。僕はいま東京に住んでいるので朝7時に出発して神戸大学に向かいます。ワクワク！11時半に…
全方位木dpについてです。基本的にここにまとまっていて、僕自身もこの記事から学びました。本記事では、これよりもわかりやすく簡潔な実装します。名前が大げさですが、普通の木dpを少し拡張するだけです。上のサイトの例題 $1$ にもありますが、次のような…
木上のパスが含む辺の中で、その重みの最大値(最小値)を対数時間で求めるライブラリです。よく知られたダブリングというテクニックを使っています。ダブリングについてはここでは書きませんが、parmax[k][u] というのは、頂点 $u$ から根に向かってパスを $2…
二重頂点連結成分分解木のライブラリです。誰も使わないと思います。これの続きです。任意の無向グラフから二重頂点連結成分と関節点を頂点とする木を構築できます。それをやってくれるライブラリです。 //e2i[edge] -> index of the edge //tree index : [0…
二重頂点連結成分分解の実装です。追記：誤りがあったので大幅に変更しました。名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節…
二重辺連結成分分解の実装です。二重頂点連結成分分解についてはこちらの記事をご覧ください。無向グラフ上で、橋が存在しない部分グラフを一つの頂点につぶすと、橋を辺とする木ができます。以下は、それをそのまま実装しています。 struct LowLink { set<pair<int, int>> </pair<int,>…
H - Generalized Insertion Sort 解法 まず制約に注目すると、$25000 \geq n \log n$ にしか見えないので、そのような計算回数を実現するアルゴリズムを考えたい気持ちになります。木に関するアルゴリズムであって、計算量に $\log$ が現れるものは僕は現時…
CS Academy 解法 木を最小個数のパスで被覆する問題。選ぶパスは重複して良いことに注意します（もし重複を許さないなら、それはオイラー閉路を適切に構築してそれを出力する問題です）。とりあえず、葉は必ずパスの端点として選ぶ必要がありそうです。よっ…
E - Frequency他の人の実装を見るとなんだかあっさり実装されているので、より簡単な解法がありそうです。 解法 数列に出現する数 $x$ について、数列全体に $x$ 以上の数が何個あって、その一番左の数の $index$ が何であるのかがわかれば答えがわかりそう…
E - Prefix-free Game 解法 まず文字列は $0$ と $1$ しか含まないので、完全二分木で考えました（この考え方は、一般的な文字列においても使えるらしく $Trie$木と呼ばれているらしいです）。すると、木の頂点を順に塗りつぶしていく問題に変わります。ある…
F - XOR Tree 解法 $XOR$ の性質を使ってかなりきれいに解けます。まず、パスに関する操作が非常に扱いにくいため、なんとかしたい気持ちになります。$XOR$ の性質で重要なものとして、任意の数について、それ自身との $XOR$ は$0$ になるというものがありま…
I - Simple APSP Problem$2000$ 点の問題ですが、以下のアルゴリズムで使う発想ができれば、解くことができます。Hirschberg's Algorithmについて - Learning AlgorithmsEnglish version is available here. 解法 グリッドを適当に二つに分割することを考え…
二次元累積和のライブラリです。手で書いた方が早いレベルですが、何も考えずに求めたいときは貼ります。グリッド上で任意の長方形に含まれる数の総和を $O(HW)$ の初期化の後に $O(1)$ で求めます。antaさんがこれをRectangleSumと名付けて使っていた気がす…
はじめに 辺を構築していく問題を解くテクニックについて書きます。全然一般的には使えませんが、とりあえず以下の $2$ 問が似たような感じで解けます。C - 3 Steps F - Blackoutどちらの問題も距離を適切に定義してやると簡単に解けます（というか二問目は…
二部グラフのライブラリです。この問題で $verify$ しています。$DFS$ を実装するだけですが、持っておくと便利な時がたまにあります。二部グラフかどうかを判定したい無向グラフの隣接リストgを投げて使います。二部グラフではない場合は、-1が返ってきて、…
はじめに 彩色数を求めるアルゴリズムについて書きました。English version is available here. 彩色数とは 彩色数(chromatic number)とは、無向グラフにおいて、辺で繋がれた頂点同士が、互いに異なる色でなければいけないという制約のもとで、すべての頂点…
D - 辺彩色 解法 まず辺に色を塗っていく操作を、逆順から見ていきます。この発想は以下のような問題でも使えます。B - Splatter Paintingそうすると、一回塗った辺はもう変更することができないという操作に変えることができます。すると、各辺は条件を満た…
Problem - E - Codeforcespekempeyさんが書かれたコードから学びました。わかりやすすぎてありがたすぎます。 解法 まず、ある文字の集合を適切に並べると回文になるという条件は、出現回数が奇数である文字の種類が $1$ 個以下である、という条件に言い換え…
はじめに $Hirschberg's\ Algorithm$ に関する解説を丁寧に書きました。English version is available here. 問題 まず次の問題をご覧くださいCS Academy概要：各マスに数字が書かれたグリッドが与えられ、そのグリッド上で左上のマスから右下のマスまで最短…
追記 2018/01/22 ・重心を求めるアルゴリズムを変更して高速化しました。 ・最後に実践的な例題を置きました。 はじめに アリ本に載っているものよりも、（個人的に）わかりやすく整理した重心分解による分割統治法の一般形について書きます（アリ本でばっち…
問題 CS Academy 感想 変わった問題でおもしろいです。 解法 自明 $DP$ 解を書くと、やばいくらい $MLE$ します。$O(nm)$ のグリッドを用意するだけで $MLE$ するので注意です。空間計算量を落としたいので、$Hirschberg's\ algorithm$ (参考)という最高のア…
