KMPのK

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

丸くなってしまったtwitterアイコンを戻す方法

なんか、twitterとtweetdeckのアイコンが突然丸くなった。 四角を想定して作られたアイコンの四隅が切り取られるのはアレなので、CSSをいじって直した。 twitter社はなにを思ってこんなことをしてしまったんだろう・・・? 直し方 まず、CSSをカスタマイズで…

Google Code Jam 2017 Round 3

通過しました。 初のGCJ決勝進出です。 GCJは現時点での第一目標だったのでとても嬉しい。 次はTCOかぁ、きっつい。今回はどれも解法がすらすらと分かったので、GCJと相性が良いのかもしれない。 (けど謎の問題(sortアルゴリズムを推測せよとか、乱択とか…

最小費用流の負辺除去

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

ARC075 F 「Mirrored」 速い解法

ARC075Fとりあえず桁数を1~18まで全部試します。 例えば6桁なら、 D = fedcba - abcdef = 99999*(f-a) +9990*(e-b) + 900*(d-c)となるようなa~f(0≦a~f≦9, a≠0)の個数を数えれば良いです。 (f-a),(e-b),(d-c)みたいに端から決めていくんですが、 解説ではD…

ICPCのライブラリPDFの生成

ICPCのWFまたは多くのアジア地区予選では持ち込めるライブラリのページ数が決まっています。 また、PDFの右上にページ番号、左上に大学名を入れろという指定がついてきます。 PDF化するコマンド sublimeに印刷機能がなかったし、ページ番号と大学名を入れる…

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

ハッシュの衝突

ローリングハッシュや木の同型判定など、競プロでハッシュを使う機会はあるけど、衝突確率とか必要な値域についてあまり考えたことがなかったので計算してみた。ハッシュを使う場合、以下の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の最大流が求めたいとする。 以下のように変換する。(蟻本に載ってる図と同様) 超頂点S,Tを作り、u→vにL以上R…

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 解説

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