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 国内予選

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

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

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