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が良かった。

波を眺めて和む

なんかこんなもの作ってしまいました。 Waves ・ある点から波が出る。 ・波が到達した点からさらに波が出る。 ・同じ点からは1つしか波は出ない。 ・波が無くなったらリセット。 Waves2 ・ある点から波が出る。 ・波が到達した点からさらに波が出る。 ・同…

トランプの並び替え

大富豪をやれば、その人が好きな ソートアルゴリズムが分かる よく「ソート」の例にトランプ(手札)の並び替えとかが出てきますが、 実際のところ、手札の並び替えにはどんなアルゴリズムを使うのが良いんでしょうか。 とりあえず、手札の枚数を N とします…

コメントアウトの小技

みんな知ってるもんなのかどうかよく分かんないけど、 C++とかのコードで、コメントアウトするとき、 /* hogehoge; */ ってやるじゃないですか。 それを /* hogehoge; //*/ ってしとくと、コメントアウトを解除するのが //* hogehoge; //*/ って感じで1文字…

KOJ 0017

これを解いてみた。 コーディングはしてませんが。 問題概要 500円の商品をa+b個売るのだがおつりを全く用意していない。 客はひとつずつ商品を買っていく。 a人は千円札しか持っていないが、b人は500円玉を持っている。 売る順番を工夫すればうまくやりくり…

Xmas Contest 2011

運良く20位になれました。わーい、奇跡だ・・・ A え、やるだけ?・・・・ ↓ うわなにこの問題形式!面白いんだけど! ↓ DFSで書く バグを埋め込んでたりして、6とかでもTLE。 ↓ ムズくね?(飛ばす) E 通してる人が多かったので。 はじめはまんまとフェイ…

NetBeans

このまえ頑張って日本語化したeclipseだが、あれからもエラーに悩まされた。 で、NetBeansにしてみると、使いやすいではないか。 というわけで、特にMacなら、NetBeansがいいよ!

eclipse mac OS X 3.6 日本語化

eclipse mac 3.6 の日本語化がうまくいかなかったのですが、 eclipse.iniに追加するやつのパスをフルパスにするとうまくいった。 全く、こういうの苦手だぁ・・・ まぁ、うまくいったのは東方の作業用BGMのおかげ。

Herbertと数学

数学が好き? Herbert をやりましょう! プログラミングが好き? Herbert をやりましょう!! パズルが好き? ニコリ依存症? Herbert をやりましょう!!! Advent Calendar からいらっしゃった方、こんにちは。 snuke と申します。(twitterは @the_nikaido…

JOI模擬予選的なもの

「JOI模擬予選的なもの」に参加して下さった皆さん、ありがとうございました! tester用に作った問題文です 忍者のセキュリティの仕様がhogeで画像が表示されなかったり、3番の問題文が途中で切れってしまったりと、大変でしたがなんとか無事終えることが出…

Prime smash!

夏期セミナーで流行ってたiPad用ゲーム iTunes App Store で見つかる iPad 対応 Panasonic Prime Smash! id:nikollsonさんとかがよく「素数切らせて」って言ってきましたw 超簡単に言うと、「合成数を切り、素数を取るゲーム」 なんでみんなあんなスコア出せ…

JOI夏期セミナー

コンピュータジオメトリを取って、ボロノイ図を生成するプログラム(90%の完成度)を作った。 で、いろいろうpる。 ↓是非デスクトップにして下さいw

^(PHP)^

^(PHP)^ ^(PHP)^ ^(PHP)^ ^(PHP)^ PHP星人だお!

HOJページ開設!!!

snukeの部屋-HOJ HP改装もだいたい終わったので、HOJページを開設してみました! 日記+講座っていうmasさんスタイルです。 それから、「Flash」を「others」に改名して粉遊びの作品を載せました。 あのゲームは恐ろしいです・・・よく出来てるんですよホント

IE+AA=IAEA

タイトルは軽く無視してもらって、 snukeの部屋 IEで見るとちょっとした注意が表示されるようにしました。 IE対策はこれでいいでしょう? それと、HOJページも設置しました!! まだ「内容がないよー」ですが・・・・・・・・・・・・・ あ、あと、昨日Flash…

My HP更新なり〜

snukeの部屋-game HSP GAME倉庫のところのレイアウト改善してみたの! ほんのわずかにjavascriptを使ってみた。

supercon サンプル入力に対する出力等

一応実行してみた。(もちろん改訂版で) problem_c_0.txt, 0.007889, 501, 707401 problem_c_1.txt, 0.029113, 2069, 8 problem_c_2.txt, 0.065828, 2126, 60924 problem_c_3.txt, 0.091591, 2151, 196013140 problem_c_4.txt, 0.103135, 2774, 1457871012 …

Supercon 実行時間・メモリ比較

入力データ supercon 2011 input — Gist メモリは、snuke.txtに対する 実メモリの使用量 プロセスの仮想メモリサイズ(kbytes単位) プロセスが使用している物理(スワップされていない)メモリサイズ(kbytes単位)の順で書いてあります。(psコマンドで調べ…

Supercon 予選落ちたΣ

supercon選外だとさ。 自分で試したサンプルデータに対してはことごとく正しい結果を返してたのに、 どうやら、たまに誤答を返すらしい。 悔しいからデバッグしてみたけど、 やらかしてたわ! しかしこのミスは気付きにくすぎる・・・ 今年はIOIもsuperconも…

supercon 2011

最短距離と経路の数を別々にやってる人が多いっぽい? 自分は同時にやった。 ソース /* SuperCon 2011 予選問題C用テンプレート ・解答プログラムはこのテンプレートに従って作成すること. ・解答プログラムは1つのファイルで,チーム名.c という名前にす…

改装中〜

snukeの部屋-gameのページのレイアウトを修正。 ちなみにタイトルのフォントは「Comic Sans MS」ってやつ。 手書き感のあるフォントでなかなか。 対応してないブラウザとかだと残念(?)なことになりそうだけど、対策をする気はない。