pekempeyのブログ

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

Educational Codeforces Round 25: F. String Compression

http://codeforces.com/contest/825/problem/F 解法 文字列の最小周期はKMP法のテーブルを用いて計算できる。kmp[i]は文字列 S の先頭 i 文字を切り出した文字列の prefix と suffix の最大共通部分である。たとえば aabaabaab という文字列ならば 6 である…

Educational Codeforces Round 25: G. Tree Queries

http://codeforces.com/contest/825/problem/G 解法 一番最初の黒頂点を根 r として考える。黒頂点に囲まれている部分を black-tree と呼ぶことにする。タイプ1 u-r パスを black-tree に併合すればいい。事前に r-u パス上の最小頂点を求めておくことで O(1…

prime counting function

以下の問題を解く際に「n 以下の素数の個数」を高速に求める必要が出てくる。http://codeforces.com/contest/665/problem/F素数列を\(p_0,p_1,\ldots\)とする。\(\phi(x,p_i)\)を\(x\)以下の正整数のうち\(p_0,p_1,\ldots,p_i\)を約数に持たないものの個数と…

yukicoder 546: オンリー・ワン

https://yukicoder.me/problems/no/546 解法 高速メビウス変換というものを紹介する。高速メビウス変換というのは以下のような処理である。 for (int i = 0; i < n; i++) { for (int j = 0; j < 1 << n; j++) { if (~j >> i & 1) { a[j | 1 << i] -= a[j]; }…

ICPC 2017 国内予選D: 弁当作り

問題の解説はせずに、グレイコードの紹介をする。iに対してi^i>>1を計算して列挙すると、隣接する値のハミング距離が 1 になる。これをグレイコードと呼ぶ。 0000 => 0000 0001 => 0001 0010 => 0011 0011 => 0010 0100 => 0110 0101 => 0111 0110 => 0101 0…

ICPC 2017 国内予選F: リボンたたみ

解法 LRどちらを行っても下から何番目にあるのかは変わらない。そのため、各レベルにおいて下から何番目であるのかを求めることは容易である。広げきった状態から一手前の状態を考える。一手前の状態で下半分にあった場合、Lをすれば当然右半分に移動し、Rを…

ICPC 2017 国内予選

うろ覚えだけどメモ。 参加まで チームメンバーに誘われたので参加することにした。ところで、いまいち参加方法がわからない。新潟大学が最後に出場したのは2011年らしく、あまり参考にならない。具体的には、コーチとか監督とかどうすればいいのかというこ…

ICPC 2017 国内予選E: 論理式圧縮機

解法 DP。dp[i]=出力が i となるような論理式の最小の長さとする。DPのインデックスはf(0000),f(0001),f(0010),...,f(1111)の出力結果を16ビットにまとめたものである。遷移にループが生じるため、最短経路的なDPを行う必要がある。bellman-ford的な手法によ…

Codeforces #419 (Div.1) C. Karen and Supermarket

http://codeforces.com/contest/815/problem/C 解法 最適解は以下のような形である(入力が木になっていることに注意)。ここまで分かると dp[頂点][使用した頂点数][根と繋がっているかどうか] という DP ができることが分かる。しかしこれは O(n^3) ではな…

Codeforces #419 (Div.1) B. Karen and Test

http://codeforces.com/contest/815/problem/B 解法 和の線形性(重ね合わせの原理)を用いて計算するとうまくいく。i 番目の要素以外を 0 として、i 番目の要素が与える影響を調べてみることにする。動的計画法により結果を得ることができるが、それでは O(…

HourRank 20: Birjik and Nicole's Tree Game

https://www.hackerrank.com/contests/hourrank-20/challenges/birjik-and-nicoles-tree-game 解法 黒頂点を post-order でソートする。この列を左から順に見ていき、隣接する 2 点の LCA を列に挿入することを繰り返す。これだけで LCA の閉包(?)が作れ…

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

DP

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

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