競プロ
このツイートによると、ARC116E は xmas16H を少しいじると解けるらしいです。 かなりびっくりしたので証明をしようとしてみたら出来ました。これら２つの問題はいずれも整数 N, K と N 頂点の木が与えられます。 （xmasの方は重み付きですが、重みなしの問…
解説/講評編の続きです。コンテスト運営の裏話などを記録しておきます。 メンバー紹介 イカれたお誕生日メンバーを紹介するぜ！ kagamiz KCSの開発者にして、伝説の「帰ってきたお誕生日コンテスト」のwriterの１人でもある。KCSは偉大。今回は「帰ってきた…
秋分コンテスト秋分コンテストを開催しました！ スタッフ：japlj,kagamiz,snuke,tozangezanあの伝説のジャッジシステムKCSが復活し、またこうして新たなお誕生日コンテストが開催されたことを喜ばしく思います（？）ただ復活しただけでなく新たな進化を遂げ…
opencupで二部マッチングを使う問題があって、自分のライブラリが遅くてTLEにハマりました。 そのときに得た知見をまとめておきます。 頂点は合計200,000個、辺は200,000本、TLは3秒で、writerや他の人は400msくらいで通ってたらしい。
CF後twitterで話してたのでまとめた。 楽しかった。togetter.com3*Nに対するエレガントな解答を募集しています。
雑な記事。 競プロテクをtweetしただけだといつか流れてどっか行くので、とりあえずまとめといた。togetter.com
前編はこちら前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。全方位木DP、有向辺に関するDPだと思うのが分かりやすい。1. 青い矢印は普通の木DPで下から順に求まる2. 根から出る矢印は全部求まっ…
この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました（嘘）最近、木上のアルゴリズムの面白い計算量解析が２つ話題になったのでまとめておきます。 予備知識 まず、https://web.archive.org/web/20150819082918/https:…
ARC092C - 2D Plane 2N Pointsの証明が話題になってたっぽいので問題を見てみたら、最大マッチング系貪欲の証明テクが詰まった問題だなぁと思ったので書いてみた。 問題概要 平面上に赤い点と青い点がある。 赤い点が青い点の左下である（つまりxもyも小さい…
久しぶりにCFに参加した。（開始10分後くらいに偶然TLを見て気づいた） A 問題文が難しい＞＜ B まぁ。 C として、正しいかチェック。 D 累積xorをとって長さn+1の数列Xを作る。 Xから同じ数を２つ取ってきてその間を選ぶとxorが0になる。 つまり、とすると…
D - Knapsack And Queries 良く出来てるなぁ。queueをstack２つで実現できるっていう知る人ぞ知るテクがある。 純粋関数型データ構造界隈とかで有名らしい。どうやるかというと、 queueにpush 単にstack2にpushする queueからpop stack1が空でない：stack1か…
Um_nik回のCが面白かったので。 あと、自分の解法が想定解と違ったっぽいので。 問題概要 ビットの二進数 が 個与えられる。 のとき頂点 に辺を張ったグラフの連結成分数を求めよ。制約 はdistinct
Xmas Contest 2017 を開催しました。 ご参加いただいたみなさま、ありがとうございました。 楽しんでいただけたなら幸いです。（そして毎年一緒に運営を手伝ってくれるじゃっぷるさんにも感謝です） あと、アンケートに回答してくださったみなさまありがとう…
IOI2017を観戦しました。師匠が圧倒的な１位を取り、日本チーム自体も金３銀１と過去最高成績で激アツでした。 金３も１，４，５位で凄すぎる。 おめでとう＆お疲れ様！ 本番から１時間遅れで問題を閲覧することができ、yandexにjudgeが立っていたので何問か…
snuke.hatenablog.com上の記事では記事中の注釈の通りMPを紹介したので、KMPとは何かを大雑把に解説しておきます。 KMPは、上の記事で紹介したMP（Morris-Pratt）にKnuthパワーが加わったものです。 さらなる考察がされて、文字列検索の効率が向上した感じで…
つい最近まで最小費用流の負辺除去、「なんか上手いことやれば出来ることもあるらしい」程度の認識だったんですが、ちゃんと考えてみたら自明やんってなったので書いておきます。 この記事を読めば多分、自明かどうかはともかくとして、かなり見通しがよくな…
りんごさん方式の記事 正当性を証明するにはユニークな多項式の形にしてmodを素数にしておけば、Schwartz–Zippel lemmaを使えて良いっぽい？ multisetのハッシュ、0になりやすいなぁと思ったけど0になる確率がat most n/modなのか。 記事での根付き木のハッ…
ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。ハッシュを使う場合、以下の２通りではそれぞれ衝突確率がかなり異なる。（少し考えれば当たり…
Advent Calendar Contest 2016 24日目の問題「色塗り２」を出題させていただいたので、その解説 問題はこちら。div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css…
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…
※この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの２日目の記事です。 IOIにあまり興味が無い方は、下の方の僕が出題した問題の方だけをお読み下さい。 IOIとは IOIへの問題の応募 IOIに問題が採用された時の流れ IOI 2016に…
慶應義塾大学のチーム「Running」として参加し、３位の銅メダルでした。 メダルを取ることが出来たのは初めてで、とても嬉しいです。時系列順で感想を羅列していきます。 コンテスト前日 つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯…
最近 http://www.codeforces.com/blog/entry/7383?#comment-161520 をよく目にする気がします。 興味深いアルゴリズムではありますが、より良いアルゴリズムがあります。 追記：「上位互換」と煽っていますが、実装量・定数倍の面から、Moが使えるときはMoを…
おそらく最後のICPCの国内予選です。 ７完２位でした。 大きな戦略ミスと大きなハマりがなかったので良かった。 メンバーは去年と同じ（peryaudo,mine_studio） 今年はJOI本戦勢・JOI春合宿勢・CTF勢の１年生チーム（peryaudoを名乗っているチーム）がいて、…
Xmas Contest 2015 お疲れ様でした！ご参加いただいた方、ありがとうございました。楽しんでいただけていたら幸いです。とりあえず、各問題の解法の概要を書いていきたいと思います。 A「Accumulation」 乱数生成が一番難しい、という問題。 f(x) = Ax + B …
この記事はAOJ-ICPC Advent Calendar 2015の記事として書かれました。りんごさんセットのSnake解きました。解法を知っていれば簡単。 問題概要 通れるでしょうか？ 解法 ネタバレのため、反転してます各辺について注目した時、(凸包)ー(凸包)という鉄アレイ…
この記事はCompetitive Programming Advent Calendar 2015の６日目の記事として書かれました。この記事は、C++初心者が頑張って編み出した、C++初心者の競技プログラマ向けの実装テクニックを紹介するものです。 筆者自身がC++に詳しいわけではないため、仕…
11/28昼 ・チームメイトと秋葉原で合流。 ・つくばエクスプレス、椅子が硬いとの噂で、コンクリート並みの硬さをイメージしていたけど、そんなことはなかった。普通の在来線という感じ。 ・駅で静岡チームに出会い、着いていく。 ・つくばカピオに着く。カピ…
Golden Week Contest 2015 - Golden Week Contest 2015 | AtCoder というコンテストをAtCoderさんで開かせていただいていました。まずは、チーム/個人それぞれののtop10から。 チーム 順位 チーム名 点数 問題数 時間 全体順位 1 カラフルジャンボチキン 621…
sublimeの競プロプラグインを作りました。snuke/LibraryPastegithub.com 適当にプラグインの作り方をググって、雰囲気を把握して、あとはAPI referenceを眺めながら作ったらできた。どう実装するのかわからないところが出てきたらサンプルをあさるのも吉っぽ…
