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

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

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

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

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

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

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

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

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

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

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

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

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

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

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