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

pekempeyのブログ

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

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

赤コーダーになりました。http://codeforces.com/contest/790

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

本当にどうでもいい内容です。

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

寝坊したので不参加。 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

Kth Max Subarray(改: Suffix Tree)

https://www.codechef.com/DEC16/problems/KTHMAX

遅延セグメント木の可視化

キーボードが無性に叩きたくなったので、可視化のコードを書きました。 https://pekempey.github.io/lazy_propagation_segment_tree/lazy_propagation_segment_tree.html

Codeforces Round #382 (Div. 1) C: Ostap and Tree

http://codeforces.com/contest/736/problem/C 問題概要 木が与えられる。頂点を黒か白で塗りつぶす。どの白頂点も距離K以内に黒頂点があるような塗りつぶし方は何通りあるか。 1≦n≦100 0≦k≦min(20,n-1)

Codeforces Round #382 (Div. 1) D. Permutations

問題文が誤解を生みかねない感じがしたので、もとの問題文を変更して問題概要を書きました。 問題概要 完全二部マッチングの問題である。i 番目の辺を削除したときの完全二部マッチングの総数の偶奇を出力せよ。 与えられるグラフは奇数個の完全マッチングを…

CodeForces Round #382 (Div. 1): B. Taxes

http://codeforces.com/contest/736/problem/B 問題概要 $n$円の収入に対して、$n$未満の最大の約数だけ税金がかかる。後の説明のために税金額を$f(n)$と書くことにする。 Mr. Funt は税金の額をごまかすために、$n$をいくつかの整数$n_1,n_2,\ldots,n_k$に…

Codeforces Round #381 (Div. 1): B. Alyona and a Tree

http://codeforces.com/contest/739/problem/B

square869120Contest #3: G - フィボナッチ数の総和

http://s8pc-3.contest.atcoder.jp/tasks/s8pc_3_g

yukicoder 443: GCD of Permutation

http://yukicoder.me/problems/no/443