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

pekempeyのブログ

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

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 では見れないのでご了承ください。

HourRank 19 screencast

Google Drive 上に screencast を置いといた。コードを書いてる最中にかなり手が止まってて面白い。 https://drive.google.com/open?id=0B-_lUQRjdBisWXBMWFBNNDlmbEU全く関係ないけど前回のABC057のscreencastも置いておいた。 https://drive.google.com/op…

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

DP

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

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 も似たような理由でうまいくのではと思い解析に挑戦してみました。スプレー木と同じポテンシャルの設定で解析できたのでメモしておきます。特に何かを参考にしたわけではないので間違っていたらごめんなさい。ポ…

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 個与…

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

http://codeforces.com/contest/763/problem/C 問題概要 n 個の数が与えられる。これを並び替えて mod m 上での等差数列にできるかどうか判定せよ。可能なら初項と公差を示せ。

Codeforces Round #395 (Div. 1) B. Timofey and rectangles

http://codeforces.com/contest/763/problem/B 問題概要 N 個の長方形が与えられる。長方形の四隅は格子点上にあり、辺は軸に平行、辺の長さは奇数である。長方形同士は重ならない。長方形を 4 色で塗り分けたい。ただし接している長方形の色は異なる必要が…

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

http://codeforces.com/contest/763/problem/A 問題概要 木が与えられる。各頂点には色がついている。頂点をひとつ選び削除したとき、分離されたどの部分木も単色であるような削除の仕方を答えよ。

CodeChef January Lunchtime 2017: Segment Queries

https://www.codechef.com/problems/SEGMENTQ

Treap の解析

手抜きです。

NJPC2017 G - 交換法則

非想定っぽいなとは思った。G: 交換法則 - NJPC2017 | AtCoder

NJPC2017 H - 白黒ツリー

想定解よりは複雑だけど、HL分解の方が応用が効くので書いておきます。H: 白黒ツリー - NJPC2017 | AtCoder

Educational Codeforces Round 17: D. Maximum Path (Simpath)

非想定解法です。普通に解いた方が明らかに楽です。http://codeforces.com/problemset/problem/762/D

±RMQによるLCAの実装

構築 O(n) 質問 O(1) のやつ。AOJ の以下の問題で verify した。 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C 基本的には euler-tour + sparse table RMQ。euler-tour したときの深さ列が ±1 で変化することを利用して高速化する。 …

8VC Vecture Cup 2017 - Elimination Round

E問題のコーナーケースに気づけなかったのが痛い。 (2017/01/16 15:01: どことは言わないけど、E問題の証明が間違ってたので訂正) http://codeforces.com/contest/755 A. PolandBall and Hypothesis B. PolandBall and Game C. PolandBall and Forest D. P…

AtCoder Regular Contest 067: F - Yakiniku Restaurants

http://arc067.contest.atcoder.jp/tasks/arc067_d

Codeforces Round #391: A問題からF問題

http://codeforces.com/contest/757 A. Gotta Catch Em' All! B. Bash's Big Day C. Felicity is Coming! D. Felicity's Big Secret Revealed E. Bash Plays with Functions F. Team Rocket Rises Again

高度合成数一覧

高度合成数計算機 高度合成数計算機を作りました。javascriptでは数値が double で管理されるらしいので正しく計算できない可能性がありますが、高度合成数が変化する境界を入れない限りは大丈夫だと思います。入力フォーマットのチェックはしてないのであし…

Ad Infinitum 17: The Axis of Awesome

変なことを言ってたらごめんなさい。 https://www.hackerrank.com/contests/infinitum17/challenges/the-axis-of-awesome

Ad Infinitum 17

https://www.hackerrank.com/contests/infinitum17/challenges Primitive Problem The Matchstick Experiment V-Cutting Tool Birthday Triplets Divisor Exploration II Number of M-Coprime Arrays

CodeChef: Subtree swapping

codechef の practice ってあまり使わないので知らなかったんですが、コンテストから practice に問題が公開されるまで大分時間がかかるんですね。復習しづらい。 https://www.codechef.com/problems/SBSWAP オイラーツアーの切り貼りは、以下の記事で説明し…

Good Bye 2016 A問題からE問題

黄色コーダーで終わりました。個人的には結構強くなったと思うんですが、数値だけ見ると去年の自分と大差ないですね。というか去年の自分が思ってるより強いですね。 http://codeforces.com/contest/611 A. New Year and Hurry B. New Year and North Pole C…

Week of Code 27: How Many Substrings?

どうせ平方分割だろうと思って editorial を覗いてみたら、想像以上に解法が面白かった。editorial を読んでもよく分からなかったので、簡単に解法に至る流れを書き留めておく。 間違ったこと書いていたらごめんなさい。 https://www.hackerrank.com/contest…

Codeforces Round #388 (Div. 2)

http://codeforces.com/contest/749

Codeforces Round #387 (Div. 2) A..F

http://codeforces.com/contest/747

AtCoder Regular Contest 066: D - Xor Sum

DP

寝坊したので不参加。 http://arc066.contest.atcoder.jp/tasks/arc066_b 関係あるかどうか微妙なのだが、この問題と問題設定が似ている問題がCodeforcesにある。Codeforcesの方の問題はcarry型の桁DPで"殴れる"(想定解は異なるものである)。 http://codef…

yukicoder No.465 PPPPPPPPPPPPPPPPAPPPPPPPP

かなり怪しい記事なのであまり信用しないでください。editorialの論文を読みましょう。 http://yukicoder.me/problems/no/465