型レベル自然数を使って型付き行列を作ってみた

#動機 研究で行列計算ライブラリを使っているのですが、numpyはなぜか異なる型の行列同士を足せてしまいます。 このせいでデバッグがめちゃくちゃ大変でした。 こんな単純な間違いはコンパイル時に弾いてくれればいいのにと思ったので、違った型の行列は足せ…

CTF入門記

11月の終わりからCTFをかじり始めました。この熱意がいつまでつづくのか分からないのですがとりあえずこの二週間くらいでやったことを書いてみようと思います。 動機 CTFは高校の先輩に一年ほど前から勧められていたのですが放置していました。最近寒いし何…

n番煎じのyesod入門ーとりあえずプロジェクトを作ってみる

yesodとは haskellで作られたweb frameworkです。 Yesod Web Framework for Haskell インストール 公式サイトのYesod quick start guideのとおりに cabal install yesod-platform yesod-bin すると依存関係がぶち壊れる可能性大なので cabal-devを使ってイン…

Haskellでインベーダーゲームを作ってみた

夏休みがあまりに暇なのでインベーダーゲームまがいの物を作ってみました。 ゲーム全体の状態を持つ変数をIORefで包み 一定時間毎に更新することでゲームの状態を変更・保持しています。 (IORefを使うとIOモナドの中で変数が更新できます。(実はよく分かっ…

Codeforces Round #176 div 2

久しぶりに(一年ぐらい)Codeforcesに出ました。 正解したのはA問題のみというひどい結果でした。 B問題はコーナーケースで落ち、C問題以降は 手も足も出ませんでした。 もう一度初心に帰って勉強する必要性を感じました。 A. IQ Test 問題概要 4x4の…

Marathon Match 78 の記録

最終的なアルゴリズム 左上(0,0)を出発点として、盤面上に一本の線を引いていく。 1マス進むことを一手として10手探索してはもっとも高い点数が 得られるものを最終的な解に追加していく。このとき輪っかができなくなるものは除外する。 探索と解の追加を…

HaskellとOpenGLを使って四角形を描画しテクスチャを貼り付ける

こんな感じになります↓ 結構苦労しました。誰かの役に立ってくれると嬉しいです。参考サイト いろいろなサンプルがある:Index of /GLUT/examples/RedBook 今回役に立ったのは Tex〜.hs 視野の設定:Lichu's_Base テクスチャの読み込み・設定:https://githu…

HaskellとOpenGLをつかって四角形を描画する

うまく動いたら雛形にでも使ってやってください。 参考サイト GLUTによる「手抜き」OpenGL入門 プログラミング/Haskell/HSDL - Flightless wing import Graphics.UI.GLUT import Graphics.Rendering.OpenGL.GLU import System.Exit import Data.IORef --タイ…

cabal install を使う前に

apt-cache search パッケージ名 とするとよいかも

AOJ 0090 Overlaps of Seals

問題の内容 10*10の正方形上に半径1の円をn個(n 最も多くの円の内部に含まれる正方形上の点はいくつの円に含まれるか。 (円の内部とは円周上も含む。) 解法 想定解法では任意の二つの円についてその交点を求め いくつの円に含まれるかを数えるらしい。 AOJ…

cabal install monadius したら結構ハマった

結局こんなことをやった cabal install OpenGLRaw --reinstall cabal install StateVar --reinstall cabal install Tensor --reinstall cabal install ObjectName --reinstall cabal install OpenGL --reinstall cabal install GLURaw --reinstall cabal ins…

JOI2012春合宿

一日目:125 二日目:11 三日目:10 四日目:70

Haskellで文字列圧縮(エンコーダーのみ)

仕組み 各文字の出現頻度を数えて一番多いものに"1"、二番目に"01"、三番目に"001"を割り振る。 ex "aaaaaaaaaaaa" -> "11111111111" その後6ビットずつに区切る ex "11111111111" -> ["111111","111111"] 2進数として読み、文字に変換する ex ["111111","11…

Haskellでheadコマンド

Haskellで作るものが思いつかないのでheadコマンドを実装してみた。 main = do cs <- getContents putStr $ unlines $ take 10 $ lines cs

std::setでデータ同士の間に順位付けができないと無視されてしまう件

#include <stdio.h> #include <set> using namespace std; struct Data{ int a,b; }; Data makeD(int aa,int bb){ Data d; d.a=aa,d.b=bb; return d; } bool operator < (const Data &d,const Data &e){ return d.a<e.a; } int main(){ set<Data> se; se.insert(makeD(0,1)); se.insert(makeD(0,2)); pri</e.a;></set></stdio.h>…

HaskellでBrainfuckの処理系を実装する

Brainfuckとは http://ja.wikipedia.org/wiki/Brainfuck プログラムの動かし方 runghc Brainfuck.hs Brainfuckのソースコード] 課題 '.' ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。 IOモナドを使いたくない(使えない)のでマシン…

情報オリンピックの過去問の入出力をチェックするのに便利だったコマンド

nkf -Lu -overwrite TEST.txt とやるとファイル中のCRLFが全てLFになって便利だった。

JOI2007 春合宿 1日目 2番

Factorial: 階乗

解法 nを素因数分解して p1^e1*p2^e2*p3^e3*......pr^erとなったとき、 m1!%p1^e1==0,m2!%p2^e2,m3!%p3^e3,.....となる 最小のm1,m2,m3...を求めて m1,m2,m3....の中で最も大きな値が答え #include <stdio.h> #include <vector> #include <map> using namespace std; typedef long </map></vector></stdio.h>…

AOJ 1203

問題文要約 記号を含む文字列が与えられるので、記号を除いて小文字を大文字に変換した後その文字列が含む回文を列挙せよ。ただしcXcとなる回文が存在した場合Xを出力してはならない。 解法 dp[i][j]=(i文字目からj文字目までが回文となっているかどうか) で…

AOJ 1204

解法 最後のnクロックの状態と次にpipelineに入れられる仕事の番号を使って拡張ダイクストラをする。int dist[21][1 //AOJ1204 #include <stdio.h> #include <vector> #include <string> #include <string.h> #include <queue> #include <map> #include <set> #define INF (1<<20) #define W 10 using namespace s</set></map></queue></string.h></string></vector></stdio.h>…

JOI2012本選5番

ダイクストラして最大全域木求めてLCAする全部入り問題。 #include <vector> #include <queue> #include <stdio.h> #include <algorithm> #include <string.h> #include <queue> #define MAX_V 100000+10 #define MAX_Q 100000+10 #define INF (1<<28) #define ROOT 1 using namespace std; struct Edge{ int to,c</queue></string.h></algorithm></stdio.h></queue></vector>…

JOI2012本選4番

講義資料 - いもす研 (imos laboratory) ↑参照。 累積和を使ったコード #include <stdio.h> int nails[5010][5010]; int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i</stdio.h>

JOI2012本選3番

時間がSにかぶるときだけ気をつけてdpすればOK。 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int n,S,T; int A[3010],B[3010]; int dp[3010][3010]; int rec(int store,int time){ if(store==n) return 0; else if(dp[store][time]!=-1) return dp</algorithm></string.h></stdio.h>…

JOI2012本選2番

dp[ap=Aの何枚目か][bp=Bの何枚目か]でDPした。 #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int dp[5010][5010]; int ac[5010],bc[5010]; int rec(int ap,int bp){ if(ap<0||bp<0) return 0; else if(dp[ap][bp]!=-1) return dp[ap][bp]; else{ in</algorithm></string.h></stdio.h>…

JOI2012本選1番

解説を聞いてから自分のやっていたことがRunLength圧縮と同じであると気づいた。 #include <stdio.h> #include <vector> using namespace std; char in[10000000+10]; int main(){ scanf("%s",in); vector<int> ch,sq; int c=in[0],s=1; for(int i=1;in[i]!=0&&in[i]!='\n';i++){ i</int></vector></stdio.h>…

JOI2012本選まとめ

↑の大会に参加してきました。 実力を限界まで発揮できたと思います。 合宿は問題を楽しむだけにしようと思います。

JOI2011本選5番

kについて二分探索した後、その判定を頑張ってO(n)で出来るようにする。 #include <stdio.h> #include <utility> #include <set> #include <algorithm> #include <vector> #define MAX_V 1000100 using namespace std; int n; int ai[MAX_V],can[MAX_V],bi2ai[MAX_V]; pair<int,int> bi[MAX_V]; int ok(int k) { </int,int></vector></algorithm></set></utility></stdio.h>…

SuperCon2011に参加しました

2011年8月22日(月) 〜 26日(金)にかけて大阪大学豊中キャンパスで SuperCon2011にチームMKとして参加してきました。 今回の課題は「https://www.cp.cmc.osaka-u.ac.jp/supercon/naklon.html」。 リンクをクリックして表示されるのはSIZE=8のもの…

Haskellで数式をパースする

使い方 :load で読み込んだ後 myEquation "1+2*3" import Text.ParserCombinators.Parsec myDigit :: Parser Char myDigit = oneOf ['0'..'9'] myNumberString :: Parser String myNumberString = do c<-myDigit do cs <- myNumberString return (c:cs) <|> …

HaskellでHTMLをパースする

使い方 hoge.hsに下のコードを保存する。 runghc "hoge.hs" "target.html" ※ダブルクオーテーションは必要 このままでは空行が大量に含まれているので runghc "hoge.hs" "target.html" | sed '/^ *$/d' すると良い --sed '/^ *$/d' import Text.ParserCombin…

ubuntu11.04でmp600を使う

環境:xubuntu11.04+canon mp600キヤノン:ダウンロード|ScanGear MP Ver.1.00 for Linux ここから共通ファイルとmp600用のファイルをrpm形式でダウンロードして キヤノンよりダウンロードした2つのファイルを~/canonに置いた。 sudo apt-get install alie…

JavaScriptでインベーダーゲームを作るーその1

JavaScriptの実行されるタイミングがよく分からない。

SuperCon2011予選

PriorityQueueを使って全ての地点までのk最短路を求めた後にメモ化再帰。 ソースコードの後半は指定されていたテンプレート+入力データのコピーだけ。 /* SuperCon 2011 予選問題C用テンプレート ・解答プログラムはこのテンプレートに従って作成すること…

SRM370 div1medium

通信範囲を1づつ大きくしながらメモ化再帰。 #include <algorithm> #include <vector> using namespace std; class ConnectTheCities { public: int n,dist,range; vector<int> pos; int cache[105][55]; int rec(int bP,int k) { //printf("bP=%d k=%d\n",bP,k); int &r=cache[bP][</int></vector></algorithm>…

ややこしすぎて、なんで通ったのか分からない。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <climits> #include <cfloat> using namespace std; int K,gN; int E[40]; int G[16][16]; dou…</cfloat></climits></map></set></cmath></cstring></cstdio></sstream></iostream></vector></string></algorithm>

SRM331 div1 medium

2^10は使わなかった。 #include <algorithm> #include <vector> using namespace std; class Shopping { public: int minNumber(int X, vector <int> values) { sort(values.begin(),values.end()); if(values[0]!=1) { return -1; } else { int r=1; int s; for(s=1;s</int></vector></algorithm>

SRM337 div1 medium

ALGORITHM NOTE ヒストグラム中の最大の長方形の面積 または Amazon.co.jp: プログラミングコンテストチャレンジブック: 秋葉 拓哉, 岩田 陽一, 北川 宜稔: 本 の280ページ、スタックの利用を参照。 #include <vector> #include <stack> using namespace std; typedef long</stack></vector>…

SRM367 div1medium

問題概要 あるデバイスに送らななければならないデータがその始まりのアドレスと大きさの形で渡される。 データはパケットに分けて送らなければならない。 そのパケットはメインデータとオーバーヘッド部分から成る。 このとき送らなければならない最小のバ…

SRM384 div1 medium

問題要約 ーーーーーーーーーーーー n人の人が円形に並んでいて、 時計回りの順にボールを任意の他の人に向かって投げる。 ボールがあたった人は円から離脱し、 番号iの人が投げたボールが当たる確率はprobably[i]である。 この時円形に並んでいる人が1人に…

SRM397 div1 medium

k乗和の公式を使う。 求め方は数学Bの教科書に載っている。 #include <algorithm> #include <string> #include <vector> #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <cmath> #include <set> #include <map> #include <climits> using namespace std; typedef long long LL; static const LL MOD=10000000…</climits></map></set></cmath></cstring></cstdio></sstream></iostream></vector></string></algorithm>

SRM508div1

なにそれオイシーの?

SRM388div1 medium

使うギターを全探索するだけ。 #include <algorithm> #include <string> #include <vector> #include <set> using namespace std; class GuitarConcert { public: vector<string> comp(vector<string> vs1,vector<string> vs2) { if(vs1.size()==vs2.size()) return (vs1</string></string></string></set></vector></string></algorithm>

SRM388div1 medium

分からなかった。 ビットを使って部分集合を求めると結構速いらしい。 このDPの計算量はそれぞれのビットについて (mask:0,sub:0),(mask:1,sub:0),(mask:1,sub:1) の場合があるので3^nなんだって。 2^n*2^nしか思いつかなかった。 #include <vector> using namespace</vector>…

SRM386div1 medium

凸な図形=三角形の集まりなので rec(どの座標を使ったか(=mask)、今どの座標か(=k))は kを含む三角形を(i,j,k)の面積をsとすると s+rec(maskにi,j,kを追加した物,k+1) の内最小化のものを返せば良い。あとはそれをメモ化再帰して終わり。 三角形の面積を求…

SRM329div1 medium

最大値の最小化なのでセオリー通りに二分探索。 #include <algorithm> #include <string> #include <vector> #include <sstream> using namespace std; class LogCutter { public: int n; vector<int> canCut; bool check(int L,int C,int mid) { int beforeCut=0; while(mid</int></sstream></vector></string></algorithm>

SRM410 div1 medium

#include <algorithm> #include <vector> #include <cstdio> #include <cstring> #include <climits> using namespace std; typedef long long LL; int n; LL k; int range[55][55][2][2]; LL cache[55][55][2]; class ContiguousCache { public: LL intersect(int a1,int a2,int b1,int b2) { if(a1<=b1 &</climits></cstring></cstdio></vector></algorithm>…

SRM439 div1 medium

メモ化再帰。 難しくて解説みた。 #include <string> #include <vector> #include <cstdio> #include <cstring> using namespace std; typedef long long LL; LL DP[(1<<13)][2][15][15]; class PalindromePhrases { public: int n; vector<string> words; bool isPalindome(string s) { for(int i=0;i</string></cstring></cstdio></vector></string>

Google Code Jam Qualification Round

満点で予選通過した。 Round1は中間テストの真っ最中だけど、頑張って出るかもしれない。

SRM479 div1 medium

二部探索+ダイクストラ。 #include <algorithm> #include <string> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; typedef long long LL; int n; LL limit; LL INF=((LL)1<<LL(50)); LL visited[500]; vector<int> F[500]; vector<int> T[500]; vector<int> P[500]; vector<int> D[…</int></int></int></ll(50));></utility></queue></sstream></vector></string></algorithm>