programming

KMPのK

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

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

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

Sorting game

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

sublimeのプラグイン作った

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

sublimeをカスタマイズした

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

SAT solverでパズルを解いた話

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

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…

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

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

CodeForces、Topcoder化計画

gachizei_tcが 「CodeForcesはTopcoderと違って背景が白いからレートが上がらない」 とか言っていたので、ForceCoder - Chrome Web StoreCoderForcesの見た目をTopcoderっぽくする Chrome Extensionを作りました。やったね、レートが増えるよ! 不具合とかあ…

GCJ 2013 Qual

GCJ2013Qualでなんか14位でした。R1進出には無意味だと思いながらも提出したおかげですかね。 ムダに実装量を増やす要素があってうっとうしかったけど、問題自体は割と面白かったので感想を。 Problem A. Tic-Tac-Toe-Tomek やるだけ 絶対クソゲーだけど今度…

RUPC

立命館のプログラミング合宿に参加してました。 なんか花粉とかそういうののせいで頭痛いので軽く参加記。・行きのバスでjapljさんに遭遇するが、twitterで会話 ・なんかコロコロ(転がす式の鞄)がやたら軽い ・着くと「3人1組になって〜!」phaseだったけ…

Dijkstraの定数倍

ダイクストラは dijkstra(){ distをINFで初期化 dist[始点]は0 usedをfalseで初期化 優先順位つきキューに[0,始点]を突っ込む while(キューが空になるまで){ キューの先頭を取り出す dに距離を代入 vに頂点を代入 if(used[v] == true) continue used[v] = tr…

ぐらふ

「デバッグが大変で、紙に100頂点の木を書いたりしていました...疲れたw」 とか昔の記事に書いててわろすなので、グラフをビジュアライズさせるツールを使ってみた。 デフォルト 小さい容量に押し込んでくれる。(曲がった辺とか使ってくるあたりプロ) neat…

再帰関数を使わないゲーム

ちょっとハマったのでまたやってみた。 hogeのpiyo乗をO(log piyo)で求めるやつ。 簡単だと思ったら、案の定簡単だった。 再帰verとちょっとだけ方針が違う。 #include<cstdio> #include<algorithm> #include<cstdlib> #include<ctime> #define rep(i,n) for(int i = 0; i < n; i++) #define rre</ctime></cstdlib></algorithm></cstdio>…

再帰関数を使わずにlowlinkを求める。

全変数を保存しないで再帰をstack使って書き換える方法ってありますか— hogloid@へなちょこさん (@hogloid) 2013年2月3日@the_nikaidoes 深さが10^5,6になる再帰関数をstackで書きなおすとき、for文で回している変数や戻り値を含む関数内のすべての変数を保…

絵迷路ジェネレーター

絵迷路ジェネレーターというものを作りました。 解くと絵が浮かび上がるような迷路を、画像から自動で生成してくれるアプリです。 こんな感じ。昔同じような物を作ったのですが、経路は自分で作らなければいけなくてかなり使い勝手の悪い物でした。アルゴリ…

Xmas Contest 2012

hosさんのXmas Contest 2012にPerorinCoders(りんごさん、きゅうり)で出て1位でした。 EとGを解いたのでコードをのせときます。G Ruins2と同じような方法でO(N^3)で出来る。 #include<cstdio> #include<cmath> #include<cstdlib> #include<algorithm> #define fi first #define se second #defi</algorithm></cstdlib></cmath></cstdio>…

NPCA Contest

NPCA のアドバイザーをしておりました。 問題の修正等多くて申し訳ありませんでした。 次回からは改善していきたいと思います。(関わるかどうかは知りませんが・・・)Div1の解説と統計を書きたいと思います。 黒い板 1問目から難しいです。 貪欲っぽい臭い…

IOI 2012 day1

公式 JAPLJさんによる翻訳 解いてみました。 Odometer HOJerとかは得意系だと思うけど、Task 5が手強い。コードは省略でコードの概要だけ1. 一個ずつ交互に取っていって、無くなったら止まる。 2. 1.の後putしながら30回くらい往復する。 3. 石を一個ずつ真…

Project Euler

Project Euler始めました。まだ20問しか解いていないので、この期に始めようと思う人は共に競い合いましょう!新しい言語の習得を兼ねるために、僕はPythonで解いてます。 素数判定みたいなのはイマイチ書きやすくないけど、多倍長の問題でも全く問題なかっ…

supercon参加記 その2

優勝しました! 最初は頭が全く回ってなかったせいもあり、サンプルに騙されてたけど、頭回り出してからは順調に行った。 まずはCPUで正しく動くフローを書こうと思い、ポテンシャルを使ったダイクストラ解法で解いた。 最初に出来たプログラムで既に0.04sく…

supercon参加記 その1

結果がまだ分からないので、競技のことに関しては明日書くことにして、とりあえずその他雑多なことを書きます。 8/20 ・この日は特に面白いことはなかったかな〜、移動日みたいなもんだし。 ・朝のんびり出発 ・御堂筋線混んでた・・・ ・受付の時間は過ぎて…

プログラミン

なんか見つけた。 プログラミン | 文部科学省 んで、なんか作った。 Turing machine 変数とか条件分岐とかなくて微妙な感じだったけど、 ちょっとしたゲームとか作れるようにしてあるらしく、当たり判定とかがあったから作ってみた。 ハターンとかいうコマン…

競技プログラミングwiki

競技プログラミングwikiを作りました。 詳しくはwikiの方を見て下さい。 編集者募集中です!! 編集者になりたい人は連絡ください!

Ritsumeikan University Programming Camp 2012 (Day 1)

ここ最近やたらとコンテストが多いですね。まいってます。 RUPC2012っぽいものがあったので参加。nya_wolvesでした。id:tozangezanと二人でチームで参加しました。 A: K Cards tozanがFAを取っててぱない B: Spellcasters 簡単。 C: Live Schedule gezanがFA…

iconroad 3

simroad input maker - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ simroadをtwitterからひろったiconを元にした入力データを作って遊んでみた。その2 スコアはO3Jで。 Respect2Dさんの鍵垢 roxion1377 the_nikaidoes stac_task tokoharu_saku…

iconroad 2

simroad input maker - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ simroadをtwitterからひろったiconを元にした入力データを作って遊んでみた。その2 スコアはO3Jで。 多いので折り畳みました。画像は「続きを読む」で。 iwiwi japlj kyuride…

iconroad 1

simroad input maker - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ simroadをtwitterからひろったiconを元にした入力データを作って遊んでみた。その1 スコアはO3Jで。 ABC順です。 catupper chokudai hogloid hos_lyric hziwara imos meg_73 …

今日は

AtCoder (アットコーダー) で開かれたCTPCに出ました。 D,G,Iが良かった。