競プロ

タイルを永遠に置き続ける問題

CF後twitterで話してたのでまとめた。 楽しかった。togetter.com3*Nに対するエレガントな解答を募集しています。

DPの区間クエリ的なやつ

雑な記事。 競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。togetter.com

木と計算量 後編 〜全方位木DP〜

前編はこちら前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。全方位木DP、有向辺に関するDPだと思うのが分かりやすい。1. 青い矢印は普通の木DPで下から順に求まる2. 根から出る矢印は全部求まっ…

木と計算量 前編 〜O(N^2)とO(NK)の木DP〜

この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました(嘘)最近、木上のアルゴリズムの面白い計算量解析が2つ話題になったのでまとめておきます。 予備知識 まず、二乗の木 DP - (iwi) { 反省します - TopCoder部 に…

最大マッチングを貪欲する問題の証明典型テク

ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である(つまりxもyも小さい…

Mail.Ru Cup 2018 Round 1

久しぶりにCFに参加した。(開始10分後くらいに偶然TLを見て気づいた) A 問題文が難しい>< B まぁ。 C として、正しいかチェック。 D 累積xorをとって長さn+1の数列Xを作る。 Xから同じ数を2つ取ってきてその間を選ぶとxorが0になる。 つまり、とすると…

Knapsack And Queries - JAG夏合宿2018 day2 D

D - Knapsack And Queries 良く出来てるなぁ。queueをstack2つで実現できるっていう知る人ぞ知るテクがある。 純粋関数型データ構造界隈とかで有名らしい。どうやるかというと、 queueにpush 単にstack2にpushする queueからpop stack1が空でない:stack1か…

CodeForces #485 Div1 C AND Graph

Um_nik回のCが面白かったので。 あと、自分の解法が想定解と違ったっぽいので。 問題概要 ビットの二進数 が 個与えられる。 のとき頂点 に辺を張ったグラフの連結成分数を求めよ。制約 はdistinct

Xmas Contest 2017

Xmas Contest 2017 を開催しました。 ご参加いただいたみなさま、ありがとうございました。 楽しんでいただけたなら幸いです。(そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です) あと、アンケートに回答してくださったみなさまありがとう…

IOI2017

IOI2017を観戦しました。師匠が圧倒的な1位を取り、日本チーム自体も金3銀1と過去最高成績で激アツでした。 金3も1,4,5位で凄すぎる。 おめでとう&お疲れ様! 本番から1時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か…

KMPのK

snuke.hatenablog.com上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。 KMPは、上の記事で紹介したMP(Morris-Pratt)にKnuthパワーが加わったものです。 さらなる考察がされて、文字列検索の効率が向上した感じで…

最小費用流の負辺除去

つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくな…

根付き木のハッシュ

りんごさんがちゃんとしたハッシュについての記事を書いてくれたのでそちらを推奨しておきます。 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい? multisetのハッシュ、0になりやすいなぁ…

ハッシュの衝突

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。ハッシュを使う場合、以下の2通りではそれぞれ衝突確率がかなり異なる。(少し考えれば当たり…

ACC2016 24日目「色塗り2」解説

Advent Calendar Contest 2016 24日目の問題「色塗り2」を出題させていただいたので、その解説 問題はこちら。div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css…

IOIへの出題について - 解説編

div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css("margin-left","15px");});function tgl(id,btn){$("#"+id).slideToggle("fast");s=btn.src;btn.src=(s.charAt…

IOIへの出題について

※この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの2日目の記事です。 IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。 IOIとは IOIへの問題の応募 IOIに問題が採用された時の流れ IOI 2016に…

ICPC Tsukuba 2016 参加記

慶應義塾大学のチーム「Running」として参加し、3位の銅メダルでした。 メダルを取ることが出来たのは初めてで、とても嬉しいです。時系列順で感想を羅列していきます。 コンテスト前日 つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯…

Mo's algorithm の上位互換の話

最近 Mo's Algorithm - Codeforces をよく目にする気がします。 興味深いアルゴリズムではありますが、より良いアルゴリズムがあります。 追記:「上位互換」と煽っていますが、実装量・定数倍の面から、Moが使えるときはMoを使ったほうが良いでしょう Mo ま…

ICPC2016 国内予選 参加記

おそらく最後のICPCの国内予選です。 7完2位でした。 大きな戦略ミスと大きなハマりがなかったので良かった。 メンバーは去年と同じ(peryaudo,mine_studio) 今年はJOI本戦勢・JOI春合宿勢・CTF勢の1年生チーム(peryaudoを名乗っているチーム)がいて、…

Xmas Contest 2015

Xmas Contest 2015 お疲れ様でした!ご参加いただいた方、ありがとうございました。楽しんでいただけていたら幸いです。とりあえず、各問題の解法の概要を書いていきたいと思います。 A「Accumulation」 乱数生成が一番難しい、という問題。 f(x) = Ax + B …

AOJ 2635 「Snuke」

この記事はAOJ-ICPC Advent Calendar 2015の記事として書かれました。りんごさんセットのSnake解きました。解法を知っていれば簡単。 問題概要 通れるでしょうか? 解法 ネタバレのため、反転してます各辺について注目した時、(凸包)ー(凸包)という鉄アレイ…

競技プログラマのためのC++

この記事はCompetitive Programming Advent Calendar 2015の6日目の記事として書かれました。この記事は、C++初心者が頑張って編み出した、C++初心者の競技プログラマ向けの実装テクニックを紹介するものです。 筆者自身がC++に詳しいわけではないため、仕…

ICPC Tsukuba 2015 参加記

11/28昼 ・チームメイトと秋葉原で合流。 ・つくばエクスプレス、椅子が硬いとの噂で、コンクリート並みの硬さをイメージしていたけど、そんなことはなかった。普通の在来線という感じ。 ・駅で静岡チームに出会い、着いていく。 ・つくばカピオに着く。カピ…

Golden Week Contest 2015 解説

Golden Week Contest 2015 - Golden Week Contest 2015 | AtCoder というコンテストをAtCoderさんで開かせていただいていました。まずは、チーム/個人それぞれののtop10から。 チーム 順位 チーム名 点数 問題数 時間 全体順位 1 カラフルジャンボチキン 621…

sublimeのプラグイン作った

sublimeの競プロプラグインを作りました。snuke/LibraryPastegithub.com 適当にプラグインの作り方をググって、雰囲気を把握して、あとはAPI referenceを眺めながら作ったらできた。どう実装するのかわからないところが出てきたらサンプルをあさるのも吉っぽ…

ちょうどK個選ぶ部分和問題

JAG春コンのB問題の解法が面白かったので僕なりにまとめておこうと思います。この解説を参考にしました。 問題(要点を抜き出したバージョン) N 個の数が与えられる。その中からちょうど K 個選んで作れる和を列挙せよ。 制約 与えられる N 個の数の和を M …

文字列の周期性判定

以前の記事「文字列の頭良い感じの線形アルゴリズムたち」で、 この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、 その辺りの説明は他のサイトにお任せします。 と書いたところ、周期性の判定の方に関して「"他のサイト"なん…

自作問題リスト

自作問題をgoogle spreadsheetにまとめました。snuke問題 難易度表evimaさんが作っておられたのを見て、確かスプレッドシートに自作問題をまとめておくのはいいなぁと思い、作りました。evima's problemsりんごさんのもあります。

CodeFestival 2014 上海ツアー 参加記 〜コンテスト編〜

結果としては、 1位:snuke (GJ以外の8完) 2位:omeometo (HIJ以外の7完) 3位:アジアの人 (GHJ以外の7完) という感じで、優勝できました。やったー。 7完のままでも時間の差で勝っていたけど、8問目を残り30秒くらいで通して順位表を面白く出来て良…