競プロ

ARC116Eとxmas16Hの関係性

このツイートによると、ARC116E は xmas16H を少しいじると解けるらしいです。 かなりびっくりしたので証明をしようとしてみたら出来ました。これら2つの問題はいずれも整数 N, K と N 頂点の木が与えられます。 (xmasの方は重み付きですが、重みなしの問…

秋分コンテスト 準備/裏話編

解説/講評編の続きです。コンテスト運営の裏話などを記録しておきます。 メンバー紹介 イカれたお誕生日メンバーを紹介するぜ! kagamiz KCSの開発者にして、伝説の「帰ってきたお誕生日コンテスト」のwriterの1人でもある。KCSは偉大。今回は「帰ってきた…

秋分コンテスト 解説/講評編

秋分コンテスト秋分コンテストを開催しました! スタッフ:japlj,kagamiz,snuke,tozangezanあの伝説のジャッジシステムKCSが復活し、またこうして新たなお誕生日コンテストが開催されたことを喜ばしく思います(?)ただ復活しただけでなく新たな進化を遂げ…

二部マッチングでTLEに苦しんだ話

opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。 そのときに得た知見をまとめておきます。 頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。

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

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になりやすいなぁと思ったけど0になる確率がat most n/modなのか。 記事での根付き木のハッ…

ハッシュの衝突

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。ハッシュを使う場合、以下の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を眺めながら作ったらできた。どう実装するのかわからないところが出てきたらサンプルをあさるのも吉っぽ…