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

ARC070 F「HonestOrUnkind」別解

HonestOrUnkind解いた。 面白かった、と思ってたけど想定解と違ったのでメモ。 想定解の方がシンプルで頭良い。正直者を1人特定するところが違った。まず人の組をN/2組作る。Nが奇数なら1人余る。 各組(x,y)について? x yを質問する。 'N'なら正嘘、嘘正、…

AGC013F「Two Faced Cards」別解(TLE)

Two Faced Cardsのコンテスト中に書いてた別解です。 O(N√N logN) なのでTLEして悲しいけど紹介しておきます。 (想定解も理解したけどadhocで面白かった) 下ごしらえ とりあえずC(とA,B)を0~Nに変換しておきます。 Ai<Biのカードは裏で使うメリットがな…

根付き木のハッシュ

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

ハッシュの衝突

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

Xmas Contest 2016 I解説

I問題の解説です。

Xmas Contest 2016 F解説

F問題の解説です。

Xmas Contest 2016 B解説

B問題のギャラリーと解説です。

Xmas Contest 2016 A解説

Aの解説です。

Xmas Contest 2016 H解説

H問題の解法と雑な証明です。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");…

Xmas Contest 2016

Xmas Contest 2016 にご参加いただいた皆様、ありがとうございました&お疲れ様でした。難易度が高すぎて順位表が大変なことになっていましたね。。 1問をじっくり考えるのに慣れていない方には少しつらいセットだったかもしれないです。 でも、なんだかん…

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位の銅メダルでした。 メダルを取ることが出来たのは初めてで、とても嬉しいです。時系列順で感想を羅列していきます。 コンテスト前日 つくばエクスプレスの車内で合流して、つくばのリンガーハットでご飯…

最小流量制限付き最大流

SRMで最小流量制限付き最大流が出ました。(SRM694Div1 Hard) どうやるのが正統派なやり方なのか、わかる方がいれば教えてほしいのですが、とりあえず自分がやった方法をメモしておきます。まず、下図のようなグラフのs→tの最大流が求めたいとする。 以下の…

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 2633 「Cellular Automaton」

りんごさんセットのCellular Aun解きました。面白いです。ヒントなしでは解けませんでした。 ヒント div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg").css("margin-l…

AOJ 2635 「Snuke」

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

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

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

ICPC Tsukuba 2015 参加記

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

Sorting game

謎のゲームを作った。 Sorting game swapしてソートするだけのゲーム。マージソート風にやるよりもクイックソート風にやった方が強いっぽい。 適当に似た色を選んでいく方法も割と強い。 マージソートのやり方 2個組、4個組、8個組までは気合。 このとき、各…

Golden Week Contest 2015 解説

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

sublimeのプラグイン作った

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

sublimeをカスタマイズした

Sublime Textが気に入ってずっと使ってるんですが、今更ながらsublimeのカスタマイズをした。なんかMicrosoftが新しいエディタを出したのに触発されてやった。とりあえずまず、Sublime Textの気に入ってる点と不満点を挙げます。(今朝の時点での) 気に入っ…

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

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

SRM 656

出ました。 250 N個のパンケーキがあり、i番目のパンケーキの幅はi+1で美味しさはd[i]です。以下のような操作をしてタワーを作ります。 残っているパンケーキをランダムに1つ選びます。(残っていなければ終了) そのパンケーキの幅がタワーの一番上のパン…

文字列の周期性判定

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

SAT solverでパズルを解いた話

SAT solverで「数独」「美術館」「ひとりにしてくれ」を解きました。Githubにあげました。めっちゃ楽しかったので準急に多謝だー。(JOI春合宿で講義をしてくれた) 準備 SAT solverをインストールしましょう。僕はminisatにしました。(なんか入れるのに苦…

Top100を当てるやつ

Topcoder algorithmのactive coderのレーティング top 100 日本のredcoder

今年の目標

・今年中に今年の目標を立てる。

自作問題リスト

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

今年の目標を振り返る

人生ゲーム 2014 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ 採点します。 algorithmのレート:6/6 思ったより上がった。 marathonの参加回数:1/6 機械学習系にも出ないと回数が増えないなー。 marathonのレート:3/6 3回しか出てないにし…

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

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

CodeFestival 2014 上海ツアー 参加記 〜ボードゲーム編〜

上海で遊んだボードゲームについて書きます 5本のきゅうり ルールと写真 amazonのサジェストに出てきて、思わず名前買いした。基本的にカードの引き運がかなり強いんだけど、そんなに単純なゲームではない。 弱い手札が来ても、周りの様子とかを伺いながら…

CodeFestival 2014 上海ツアー 参加記 〜画像編〜

上海についてから初めて見た上海の風景 普通 1日目の観光 クルーズの円卓で回すために撮ったyosupo デパートにて。日本感漂う。 背の低いファミマ 小籠包作り 空港でぼっち飯してるyosupo

CodeFestival 2014 上海ツアー 参加記

0日目 (焼肉・前泊) ・ディスプレイとボードゲームがamazonから届くのを待っていた。(注文していたはずが、注文確定していなかったらしく、お急ぎ便で注文し直した) ・届いた。マルチディスプレイ快適すぎる ・TLはimosさんの結婚と、変数名の話しで盛り上…

ザングース6タテ バトルビデオ

Pokemon Advent Calendar 2014 - Adventar Pokemon Advent Calendar 2014 - Adventar の記事です。中高時代にポケモンやってました。自分はマイナー厨だったので、マイナーなポケモンか、変な型のポケモンをたくさん作ってました。さっそくバトルビデオです…

文字列の頭良い感じの線形アルゴリズムたち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日で追記して行きます。これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算…

SRM637

久しぶりにwriterやってました。登場人物もやってました。 「Cat Snuke と Wolf Sothe がゲームをする」というテーマで統一されています。 Cat Snukeといえば、いまのtopcoderの画像カンガルーだから早く猫の着ぐるみ買わないと。 Div2 Easy 猫のSnukeと狼の…

夏季セミナー2014 長編参加記

さすがに1単語は少な過ぎたのでもっと書きます。 下の方に真面目そうなことを書いてみました。 1日目 田舎を自転車で走っていたら迷子になり、疲れた。 昼を食べずに参宮橋へ 参宮橋でhogloidを発見 一緒に松屋に入る プレミアムじゃない牛めしがなくて不…

夏季セミナー2014 参加記

さらにボキャブラリーが減ったので、1単語のみで参加記を書きます。万豚記

Interpolation

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

Original Language Contest

Original Language Contestを開きました。 参加して下さった方々、ありがとうございます。お疲れ様でした。 ゴルフコンペの方に参加して下さった方々もありがとうございました。結果は、 1位:ushさん 2位:MikeCATさん 3位:semiexpさん 4位:logicmach…

Indenter

まだ紹介してなかったので。Indenterというものを作りました。(さっきの記事のソースコード折り畳むのにも使った。)div.pg{display:none;}p{margin:0px;}.btn{vertical-align:text-top; margin:0px;margin-right:3px;}$(document).ready(function(){$(".pg…

Segtreeのテクニック

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

hogloidのジャッジシェルスクリプトを改造した

hogloidのジャッジシェルスクリプトを改造した。変更点は以下の通り 自動でtmpファイルを作成してくれる。 ソースファイル名を引数で指定できる。 ついでに第二引数でTimeLimitを指定できる。 入出力データの拡張子を気にしないようにした。(.txtとかでも大…