World Codesprint 10: Node-Point Mappings

https://www.hackerrank.com/contests/world-codesprint-10/challenges/node-point-mappings 解法 一番左の点(複数あるなら下にある方)を根に対応させる。根を中心に偏角ソートし、たとえば部分木のサイズが [4, 5, 3] となっていたら下図のように領域を分…

World Codesprint 10: Maximum Disjoint Subtree Product

https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximum-disjoint-subtree-product 解法 全方位木 DP の知名度も高まってきたので説明は省略する。以前に作成した全方位木 DP のライブラリを使用した。 #include <iostream> #include <cstdio> #include <vector></vector></cstdio></iostream>…

World Codesprint 10: Permutation Happiness

https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness 解法 DP。1~n の順列に n+1 を挿入するイメージで更新していく。山の頂上(極大点)の個数を状態として持つと良い。dp[i: 順列のサイズ][j: 頂上の個数] とする…

GCJ 2017 Qual

A 問題 +- の列があって、連続する K マスを反転するのを繰り返して全部 + にする問題。まったく同じ問題が蟻本にある。 B 問題 10 進表記で数字が昇順になるような N 以下の最大の整数を求める問題。なるべく上位桁は動かさない方がいいということ、ある桁…

Splay Tree の可視化

Chrome と Firefox では少なくとも見れます。重くて見れない方はごめんなさい。https://pekempey.github.io/splay_tree/splay_tree.html

Link-Cut Treeの可視化(失敗作)

Link-Cut Treeをうまく可視化できないか考えてました。exposeの可視化を目標としていましたが、うまい可視化が思いつかなかったので、あまり役に立たない可視化だけ公開します。察しのいい人なら実装まで想像がつくと思いますが、二分木のmerge/splitに慣れ…

Mo's Algorithmの可視化

SVG で描いてみた。処理落ちしたらごめんなさい(結構重い気がする)。https://pekempey.github.io/mo_algorithm/mo.htmlInternet Explorer では見れないのでご了承ください。

AtCoder Grand Contest 012 C: Tautonym Puzzle

http://agc012.contest.atcoder.jp/tasks/agc012_c 解法 空の列も良い文字列だとみなす。順列 A, B があって、AとBを連結したもの(A+Bと表す)のパターン数が X だったとする。 A←A+[foo], B←B+[foo] とすると A+B のパターン数は 2X になる。 A←A+[foo], B←[…

AtCoder Grand Contest 012 B: Splatter Painting

http://agc012.contest.atcoder.jp/tasks/agc012_b 解法 di が小さいのが鍵に見える。dp[v][i] を「頂点 v から距離 i の範囲を dp[v][i] で塗りつぶせ」と考えると上手くいく。命令を小さい距離へどんどん伝搬していくイメージ。 補足 ある頂点から距離 d …

AtCoder Grand Contest 012 A: AtCoder Group Contest

http://agc012.contest.atcoder.jp/tasks/agc012_a 解法 入力を昇順にソートして考える。適当な戦略を取ってみる。先頭から3つずつペアにしていくのはどうだろう。 _o__o__o__o_ 000111222333oになっているのが中央値。これは改善ができる。 _o__o___o_o_ 00…

CSAcademy Special MVC

editorial読んで概要はすぐに理解できたけど、cactus上のDPを整理するのに手間取った。この回難しすぎる。https://csacademy.com/contest/archive/#task/special-mvc/

Educational Codeforces #18: C. Divide by Three

http://codeforces.com/contest/792/problem/C

Educational Codeforces #18: E. Colored Balls

http://codeforces.com/contest/792/problem/E

Codeforces #405 Div.1 ABC

赤コーダーになりました。

Codeforces #404 E. Anton and Permutation

http://codeforces.com/contest/785/problem/E

Codeforces #404 D. Anton and School - 2

http://codeforces.com/contest/785/problem/D

CSAcademy #20 Palindromic Concatenation

https://csacademy.com/contest/round-20/#task/palindromic-concatenation

「みんなのプロコン」D - 工場

C: 検索 - 「みんなのプロコン」 | AtCoder

Query Sums on Strings O(K^2Q)

https://www.hackerrank.com/contests/university-codesprint-2/challenges/querying-sums-on-strings

Codeforces #399 ABCDE

A. Oath of the Night's Watch B. Code For 1 C. Jon Snow and his Favrourite Number D. Jon and Orbs E. Game of Stones

右方向の和を求めるBIT

本当にどうでもいい内容です。以下のように書けば sum(a[0..k]) が求められます。1-indexedのBITを0-indexedとして使うために最初にk++しています。 const int N = 1e5; int bit[N + 1]; void bitadd(int k, int v) { for (k++; k <= N; k += k & -k) { bit[…

Codeforces Round #397 F. Sourvenirs

高速化できたので追記しました。http://codeforces.com/contest/765/problem/F

Codeforces Round #397 ABCDE

A. Neverending competitions 問題概要 解法 B. Code obfuscation 問題概要 解法 C. Table Tennis Game 2 D. Artsem and Saunders E. Tree Folding

Codeforces Round #396 (Div. 2) A,B,D,E

C 問題は読めなかったので省略します。http://codeforces.com/contest/766 A. Mahmoud and Longest Uncommon Subsequence B. Mahmoud and a Triangle D. Mahmoud and a Dictionary E. Mahmoud and a xor trip

ポテンシャル解析

ならし計算量を解析するテクニックとしてポテンシャル解析というものがある。 ポテンシャル解析とは何かを簡単に説明し、いくつかの簡単な解析例を示す。

経路圧縮のみを用いた union-find の計算量解析

union-find の高速化テクニックとして経路圧縮は有名である。しかし、その計算量解析は有名ではないと思う。そこで、この記事では経路圧縮のみを用いた union-find の計算量解析を行う。計算量解析にはポテンシャル解析を用いるため、予備知識としてポテンシ…

Codeforces Round #395 (Div. 1) D. Timofey and a flat tree

http://codeforces.com/contest/763/problem/D 問題概要 木が与えられる。ある頂点を根としてみたとき n 個の部分木がある。もっとも部分木の形状の種類が多くなるような根の選び方を求めよ。部分木の形状が等しい、というのは根付き木として同型であるとい…

Codeforces Round #395 (Div. 1) C. Timofey and remoduling (modsqrt)

http://codeforces.com/contest/763/problem/C

mod 平方根

素数 mod p で となる を見つけるアルゴリズムです。Cipolla のアルゴリズムというのを紹介します。平方剰余に詳しくない方はまず補足を読んで下さい。Cipolla's algorithm - Wikipedia

Codeforces Round #395 (Div. 1) E. Timofey and our friends animals

snuke さんの以下の記事を読んでいればやるだけ?snuke.hatenablog.comhttp://codeforces.com/contest/763/problem/E 問題概要 n 頂点のグラフが与えられる。頂点番号が[l,r]であるものだけを取り出したとき、連結成分がいくつあるか、というクエリが Q 個与…