読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

University CodeSprint: A,B,C,D [Haskell]

Haskell 練習です。D問題は入力サイズが大きく TLE してしまいました。 E問題以降はさすがに間に合いそうにないです。

University CodeSprint: Counting On a Tree

https://www.hackerrank.com/contests/university-codesprint/challenges/counting-on-a-tree

NCR CodeSprint: Points and Fences

https://www.hackerrank.com/contests/ncr-codesprint/challenges/points-and-fences 問題概要 2次元平面の問題。以下の3種類のクエリを処理する。 add x1 y1 x2 y2: (x1,y1) (x2,y2) の長方形型のフェンスを設置する delete j: j番目のクエリで設置したフェ…

高速多項式除算

自分はそこまで多項式の扱いに詳しい訳ではないので、もっとシンプルで高速なアルゴリズムがあるかもしれません。でも、ひとつもアルゴリズムを知らないよりは知ってた方がいいかなと思って書きました。 概要 高速多項式乗算は競プロではよく使われる。FFT, …

ゼータ変換とメビウス変換

ゼータ変換$\zeta$とメビウス変換$\mu$はどちらも関数 $f:2^n \to R \quad(R: ring)$ に対する変換である。

CSAcademy 13

Dominant Point x 座標最大の点が解の候補である。この候補が dominates するかをチェックしよう。 Pokemon Fight 小さい値を貪欲にペアにすれば OK。 Balanced Min Pairing ソートして、a[0..n/2) と b[n/2..n)、 a[n/2..n) と b[0..n/2) をペアにする。a[i…

素数冪 mod における階乗の周期性

概要 素数 mod における階乗の周期性は Wilson の定理としてよく知られている。 Wilson の定理:$p$ が素数であるとき、かつそのときに限り $(p-1)! \equiv p-1\;(\mathrm{mod}\; p)$ $p!\equiv0$ は当然であるため、この記事では階乗は既約のものを扱う。す…

Left-Leaning Red-Black Tree

以下の記事でも書いたが、もう少しだけ補足。 ARC 030: D - グラフではない (Left-Leaning Red-Black Tree) - pekempeyのブログ

高速フーリエ変換 (FFT)

FFT

再帰型の FFT はやっぱり遅いので、非再帰型の FFT について調べた。『アルゴリズムイントロダクション 第 3 巻』の「多項式と FFT」を参考にしている。多項式の次数は自由度(係数の個数)の意味で使っている。

CodeChef October Challenge 2016

Chef and Keyboard Chef and Three Dogs 証明 Chef and Two String Fenwick Iterations Big Queries Power Sums Bear and Shuffled Points Sereja and Stones Tree Balancing

Week of Code 24

Apple and Orange Happy Ladybugs Simplified Chess Engine Xor Matrix Shashank and the Palindromic Academy Surveillance

ARC 030: D - グラフではない (Left-Leaning Red-Black Tree)

LLRB (left-leaning red-black tree) の join/split の情報が少なすぎるのでメモ。問題自体は大分前に解いた。 http://arc030.contest.atcoder.jp/tasks/arc030_4

Codeforces Round #375 (Div. 2)

http://codeforces.com/contest/723 The New Year: Meeting Friends 問題概要 解法 Text Document Analysis 問題概要 解法 Polycarp at the Radio 問題概要 解法。 Lakes in Berland 問題概要 解法 One-Way Reform 問題概要 解法 st-Spanning Tree 問題概要 …

AtCoder Grand Contest 005: D. ~K Perm Counting

http://agc005.contest.atcoder.jp/tasks/agc005_d

AtCoder Grand Contest 005: C. Tree Restoring

http://agc005.contest.atcoder.jp/tasks/agc005_c

AtCoder Grand Contest 005: B. Minimum Sum

http://agc005.contest.atcoder.jp/tasks/agc005_b

Codeforces Round #374 (Div. 2): ABCD

http://codeforces.com/contest/721 A: One-dimensional Japanese Crossword 問題概要 解法 B: Passwords 問題概要 解法 C: Journey 問題概要 解法 D: Maxim and Array 問題概要 解法

Dynamic connectivity contest: Bridges: The Final Battle

http://codeforces.com/gym/100551/problem/D 問題概要 辺の追加・削除のクエリが与えられる。クエリを処理する毎に橋の個数を出力せよ。 1≦N,K≦105

HackerRank World CodeSprint 7

Sock Merchant Two Characters Gridland Metro Summing Pieces Inverse RMQ Recording Episodes Similar Strings 似ているとは? 正規化 簡単な問題から解く 解法 https://www.hackerrank.com/contests/world-codesprint-7/challenges

AOJ 2450 Do use segment tree (HL Decomposition)

LC木解は以前書いたのですが、HL 分解の方もコードだけ置いておきます。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2450

Codeforces Round #373 (Div. 1) A. Efim and Strange Grade

A 問題に面倒な実装を持ってくるのやめて欲しい…。 http://codeforces.com/contest/718/problem/A 問題概要 小数点以下のすきな場所で四捨五入するという操作を t 回まで行えるので、操作によって得られる最大の値を求めよ。

Codeforces Round #373 (Div. 1): C. Sasha and Array

http://codeforces.com/problemset/problem/718/C 解法はよくある感じなので、発展的内容として Kitamasa 法について書こうと思います。セグメント木に関しては書きません。

CodeChef September Challenge 2016

Chef and digits of a number Faded Palindromes Chef and calculation Chef and Friends Dividing Machine JosephLand The New Restaurant Chef and Cut Chef has a Spaghetti Garden(解けず)

Codeforces Round #371 (Div. 1) C. Sonya and Problem Wihtout A Legend

タイトルの Wihtout はタイプミス…? http://codeforces.com/contest/713/problem/C 問題概要 数列が与えられる。要素を +1, -1 する操作ができる。数列を狭義単調増加にするのに必要な最小の操作回数を求めよ。

Codeforces Round #371 (Div. 1) D. Animal and Puzzle

http://codeforces.com/contest/713/problem/D 問題概要 (x1,y1)から(x2,y2)の長方形領域内にある最大正方形を求めるというクエリを順次処理せよ。

Codeforces Round #371 (Div. 1) B. Searching Rectangles

http://codeforces.com/contest/713/problem/B 問題概要 (1,1)から(n,n)の領域の中に長方形が 2 つある。この長方形の座標は整数であり、2つの長方形は共通部分を持たない。 (x1,y1)から(x2,y2)の領域の中に完全に含まれている長方形の数を数えるクエリを投…

天下一プログラマーコンテスト 2016 本戦: E - 串焼きパーティ

http://tenka1-2016-final-open.contest.atcoder.jp/tasks/tenka1_2016_final_e

Educational Codeforces Round 16: E. Generate a String

問題ページ 問題概要 現在の文字列の末尾に 'a' を追加(コスト x) 現在の文字列の末尾を削除(コスト x) 現在の文字列全体をコピーし、末尾に貼り付け(コスト y) という 3 種類の操作を使って長さ n の文字列を作る最小のコストを求めよ。 $1 \le n \le…

Dynamic connectivity contest: GraphAero

問題ページ とりあえず LC 木で解けるので解きました。ただこの方法だと D 問題が解けない。 問題概要 N 頂点 M 辺の無向グラフが与えられる。辺(u,v) を追加するというクエリが K 個与えられるので順次処理せよ。各クエリを処理した後、グラフ中にある橋の…

Dynamic connectivity contest: Disconnected Graph

問題ページ 問題概要 n 頂点 m 辺の無向グラフが与えられる。与えられた c 個の辺を削除したときグラフが連結かどうかを判定するクエリを k 個処理せよ。 1≦n≦10000 1≦m≦100000 1≦k≦100000 1≦c≦4

Dynamic connectivity contest: Bridges in a Tree

問題ページ 問題概要 木が与えられる。初期状態に辺 e1, e2 ,..., eK を加えたとき橋はいくつあるかという M 個のクエリを順次処理せよ。 2≦N≦100,000 1≦M≦100,000 ΣK≦100,000

Dynamic connectivity contest: Connect and Disconnect

こんなコンテストがあったんですね。 問題ページ 問題概要 辺の追加 辺の削除 連結成分の個数を求める という 3 種類のクエリが与えられるので順次処理せよ。

Educational Codeforces Round 16: F - String Set Queries

問題ページ 問題概要 文字列 s をリストに追加 文字列 s をリストから削除 文字列 s の中にリスト中の文字列がいくつ存在するか数える という 3 種類のクエリを順次処理せよ。オンラインクエリ。

CS Academy: Connected Tree Subgraphs

問題ページ

Codeforces AIM Tech Round 3 (Div. 1) C. Centroids

あまり筋の良い方法ではないです。 問題ページ

Codeforces AIM Tech Round 3 (Div. 1) B. Recover the String

問題ページ

Codeforces AIM Tech Round 3 (Div. 1) A. Letters Cyclic Shift

問題ページ

Educational Codeforces Round 16: D - Two Arithmetic Progressions

問題ページ

CS Academy: Random Nim Generator

問題ページ アダマール変換のことはよく分からないので、基本的な線形代数で説明します。

CS Academy: A Single One

問題ページ

Codeforces Round #368 (Div. 2)

Haskell の練習です。D は C++ のコードも載せておきます。 http://codeforces.com/contest/707 Brain's Photos 問題概要 解法 Bakery 問題概要 解法 Pythagorean Triples Persistent Bookcase

CodeChef August Challenge 2016

700点でした。

HackerRank Week of Code 22

ダメダメでした。最後の問題は解けてないので書いてません。

Codeforces Round #367 (Div. 2)

最後の問題が解けなかったのは残念。

Codeforces Round #365 (Div. 2) E. Mishka and Divisors

http://codeforces.com/contest/703/problem/E 問題自体は典型だけど TL 1000ms + オーバーフロー + K=1 のコーナーケースで苦しめられた。

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

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

AtCoder Grand Contest 002: D - Stamp Rally

http://agc002.contest.atcoder.jp/tasks/agc002_d

Educational Codeforces Round 15: A-E

つい最近 Haskell の練習を始めたので、一部の問題を Haskell で解き直しました。本番中はすべて C++ で解いています。 A. Maximum Increase B. Powers of Two C. Cellular Network D. Road to Post Office E. Analysis of Pathes in Functional Graph

Educational Codeforces Round 15: F. T-Shirts

http://codeforces.com/problemset/problem/702/F 別の解があるようです。それと嘘解法の可能性があるので、あまり鵜呑みにしないでください。

CSAcademy Round #9: 101 Palindromes

https://csacademy.com/contest/archive/#task/101-palindromes/