読者です 読者をやめる 読者になる 読者になる

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

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秒くらいで通して順位表を面白く出来て良…

文字列の頭良い感じの線形アルゴリズムたち3

昨日の記事の続きです。 Z algorithm 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。 例えば、 aaabaaaab 921034210 こんな感じです。Z algorithmのテクニックはM…

文字列の頭良い感じの線形アルゴリズムたち2

昨日の記事の続きです。 Manacher 文字列が与えられた時、各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズムです。半径というのは、(全長+1)/2です。 例えば、 abaaababa 121412321 こんな感じです。…

文字列の頭良い感じの線形アルゴリズムたち

この記事はAdvent Calendar 2014の12/1の記事として書かれました。 はじめに KMP、Manachar、Z algorithm の3つについて書きたいと思います。 1アルゴリズム/1日で追記して行きます。これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算…

Interpolation

多項式補間に関して教えてもらったのでまとめておきます。何らかのN次関数P(x)があったとします。xが小さい場合は簡単に計算できる時、それを利用して大きなxに対しても求めたいです。連立方程式を解くと各項の係数が求められますが、O(N^3)掛かってしまいま…

Segtreeのテクニック

昨日のCF259Div1E問題で新しいテクニックを知ったのでメモします。とりあえずまず遅延伝播から書こう。 遅延伝播 以下のクエリを処理せよ Addクエリ:区間内の全要素に1を足す Sumクエリ:区間の和を求める という問題を考える。 ノードに [ 区間の和 ] を持…

Golden Week Contest

こんなコンテストやってました。 参加していただいた皆様、ありがとうございました。楽しんでもらえたなら幸いです。 コンテストに関する感想 結構前からとざんとこういう変なコンテストをやろうと話していて、この機会にやっとやることにしました。 一切プ…

シュタイナー木コンテスト

JOIのチューター企画のシュタイナー木コンテストのGUIでできるやつをアップしました。 zip版をダウンロードして、gui.jsをsuper_gui.jsで置換すると、山登り機能が使えます。(すなわち、edit vertexで頂点を動かす時にスコアが上がるようにしか動かせなくな…

UTPC 2013

なんか、3位でした。(+5点) 良問がたくさんあって楽しかったので書こう。*11時に目が覚めて11:25に起きる(この時点で結構ぎりぎり) *12:44頃につけそうな電車に乗った(この時点でかなりぎりぎり) *電車遅延(この時点でちょい遅刻) *乗り換えが必…

鏡の閉路

SRM602 Div1 Hardの解説記事に書いた「光の閉路が出来ていれば鏡の閉路も出来ている」の証明っぽいものを思いついたので書きます。各セルを鏡で二等辺直角三角形に分けて、光が通った三角形だけを取り出してみる。それらの概形は、三角形どうしは縦の辺とか…

Advent Calendar Contest 2013 解説など

Advent Calendar Contest 2013、終了しました。 参加していただき、ありがとうございました。 コンテスト結果→各問題の軽い解説→統計、という流れで書きます。 コンテスト結果 ペナルティシステムは多分あまり意味をなしていない気がするので、完答数でいき…

Advent Calendar Contest 2013

2014にやるのかは謎ですが、Advent Calendar Contest 2013をNPCA Judgeでやります! 期間は 12/4 20:50 ~ 12/25 22:00 で、4の倍数の日の 21:00 に1問ずつ問題が公開されます。(つまり全部で6問) 問題は、自分のCompetitive Advent Calendarの記事に関…