読者です 読者をやめる 読者になる 読者になる

紙媒体で管理するとなくなりがちなのでブログで進捗などを管理することにしました
※殆どの記事は自分自身のためだけにかいています.他人に見せられるレベルには至っていません...

高速Fibonacci数の計算

これを使ってFibonacci数の計算を高速に行うことができる. (define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count);偶数だったら2回分の変換を1回で (fib-iter a b (+ (* p p) (* q q));p' (+ (* …

ABC027_B

島の人口を均等に分散すべく橋をかける問題 総人口/島の数で目標値を求め,その状態にしていったときに隣の島に流入、流出(マイナス流入)を加算していく. #include <bits/stdc++.h> using namespace std; int main() { int n,a[100],total=0; cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; to</n;i++){></bits/stdc++.h>…

ABC024_B

ドアの合計の開いた時間を求める問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = (int)1e5; int main() { int n,t,a[MAX_N]; cin>>n>>t; for(int i=0;i<n;i++)cin>>a[i]; int res=t;//最後に開く分 for(int i=1;i</n;i++)cin></bits/stdc++.h>

ABC032_B

集合setを用いる問題 集合への挿入は set<string> ss; ss.insert("aaa"); ss.insert("bbb"); ss.insert("aaa"); cout<<(int)ss.size()<<endl;//2 この時(int)でキャストしないと幾つかのテストケースでREをとってしまった. #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) int main() { set<string> ss; string s; int k; cin>>s>>k…</n;i++)></endl;//2></string>

ABC033_B

pairについて この問題では結局使わなかったけど調べたので書いとく. //市の名前と人口を入力 string s; int x; vector<pair<string, int> > city; for(int i=0;i<n;i++){ cin>>s>>x; city.push_back(make_pair(s,x)); } vector<pair<string, int>> city; int>>はint> > と書かないとcompilation errorを吐く.</pair<string,></n;i++){></pair<string,>

ABC035_B

文字列のカウント string str = "a1a2a3a4a5a6"; int cnt = count(str.begin(),str.end(),'a');//6 #include <bits/stdc++.h> using namespace std; struct Initializer { Initializer() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); } } in</bits/stdc++.h>…

便利ワザ3

早くなる. struct Initializer { Initializer() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(15); } } initializer;

ABC039_B

文字列を右90度に回転させる問題 #include <bits/stdc++.h> using namespace std; static const int MAX_N = 50; int main() { char a[MAX_N][MAX_N+1]; char b[MAX_N][MAX_N+1]; int n; cin>>n; //input for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ cin>>a[i][j]; } } //回転 for(int i=0;i</n;i++){></bits/stdc++.h>

ABC048_B

a以上b以下の数字のうちxで割り切れるものの数を答える. for文でループで解くのは一重ループだとしてもb = 10^18とか与えられるとキツイ. 上図で赤はxで割り切れる数 上段 = 中段 - 下段で考えた. aがxで割り切れた場合はaの1つ分を足す必要がある. #include <bits/stdc++.h></bits/stdc++.h>…

ABC051_B

counter変数の加算で右辺に条件式を持ってきてもよいことがわかった. ex) int cnt = 0; cnt += 0<=k && k<=10; //kが0<=k<=10ならばTrue=1が加算され,そうでなければFalse=0が加算される. #include <bits/stdc++.h> using namespace std; int main() { int k,s; int x,y,z; </bits/stdc++.h>…

便利ワザ2

定数 const int N = 1000; const int inf = (int)1e9 + 1; const ll big = (ll)1e18 + 1; const int P = 31; const int MOD = (int)1e9 + 7; const int MOD1 = (int)1e9 + 9; const int MAX_INT = (1 << 31) - 1; const double eps = 1e-6; const double pi …

ABC053_B

文字列反転の問題 文字列反転は次のようにする. string str = "abcde"; reverse(str.begin(),str.end());//"edcba" #include <bits/stdc++.h> using namespace std; int main() { string str; cin>>str; int start=0,end=0; for(int i=0;i</bits/stdc++.h>

ABC055_B

factorialを求める問題 大きい数値はll型を使う. int型(4byte)の範囲は20億くらいを目安にする. #include <bits/stdc++.h> using namespace std; #define ll long long int #define MOD (ll)1e9+7 #define MAX(X,Y) ((X)>(Y)?(X):(Y)) #define MIN(X,Y) ((X)<(Y)?(X):(Y)) i</bits/stdc++.h>…

ABC025_A

文字列についての問題 文字列の要素1つはchar型だと知った. ex) string str = "abcde"; cout<<typeid(str[1]).name()<<endl; //c よってsubstr(ポインタの位置,そこから何文字分?)を使って部分文字列を使った. #include <bits/stdc++.h> using namespace std; int main() { string s; int n; vector<string> ss; cin>>s>>n; sort(s.begin(),s.end()); for(int i=0;i<5;i++){ for(int…</string></typeid(str[1]).name()<<endl;>

便利ワザ

入力に対して出力を行うのをプログラムがやってくれる. mainの後ろに置く. // ios_base::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif

ABC046_A

種類を数える問題 集合(set)を用いる #include <bits/stdc++.h> using namespace std; int main() { int a,b,c; set<int> s; cin>>a>>b>>c; s.insert(a);//集合sにaを挿入 s.insert(b); s.insert(c); cout<</int></bits/stdc++.h>

標準ライブラリ一括インクルード

#include <bits/stdc++.h></bits/stdc++.h>

ABC050_A

文字列を分割して数値にする問題C++におけるsplit関数の実装 qiita.com #include <iostream> #include <cstdio> #include <string> #include <sstream> #include <vector> using namespace std; int stoi(std::string str){ int ret; std::stringstream ss; ss<<str; ss>>ret; return ret; } vector<string> split(const s</string></str;></vector></sstream></string></cstdio></iostream>…

ABC051_A

文字列の置換 www.geocities.jp #include<iostream> #include<string> using namespace std; // 文字列を置換する std::string Replace(std::string String, std::string From, std::string To ) { std::string::size_type Pos( String.find( From ) ); while( Pos != std::str</string></iostream>…

Newton法で平方根を求める

(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (imporve guess x) x))) (define (improve guess x) (average guess (/ x guess))) (define (average x y) (/ (+ x y) 2)) (define (good-enough? guess x) (< (abs (- (square gu…

C91の反省

C91の反省と忘備録 配布物 前日5日間くらいで仕上げたので完成度がかなり低かった 製本が上手く出来なかった(製本テープを使う,業者に依頼するなど必要) ゲームのクオリティが低い 自宅で印刷をする場合,かなりの時間と手間がかかる 設営 相方が寝過ごした場…

PEP8について

Python Enhancement Proposal #8 について参考になったことを適宜更新していく記事にする. はじめに — pep8-ja 1.0 ドキュメント legacy.python.org

Python

Pythonでimport thisとやると下のような文が出ることが分かった. 今日から「Effective Python」を読み始める. Beautiful is better than ugly. Explicit is better than implicit. Simple is better than complex. Complex is better than complicated. Flat…

遺伝的アルゴリズムで画像再現

遺伝的アルゴリズムを用いて画像を再現するというプロジェクトを行った. まだまだ検討箇所があるので現在の結果を貼っておく. 目標の画像 0世代 1000世代 ツイートは0~800世代くらい https://twitter.com/vockyX/status/816646900392656897 今後の活動 ・100…

POJ1003 Hangover

// gist.github.com main(n)のnはint型のGlobal変数0に初期化される.

POJ1004 Financial Management

// gist.github.com Global変数は0で初期化される. scanf("")!=EOFと表現したい場合EOFマクロは<stdio.h>に入っているため<stdio.h>を除くとこの様に記述できない. 何も入力されない場合-1であることを利用(-1は全て1が立った状態)してbit反転の~で終了条件を作れる.</stdio.h></stdio.h>

レポートの表紙

TeX

// gist.github.com

AOJ Categories

// // サイドバーを製作した. gist.github.com

Project Euler 65 Convergents of e

projecteuler.net e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...] という連分数展開の問題後ろから深さ優先探索で解く. from fractions import Fravtionsすると分数型が出来て便利 gist.github.com

AOJ0087 Strange Mathematical Expression

逆ポーランド記法の問題 stackを用いる. gist.github.com C++で一行入力をするには string s,tmp; getline(cin,s);//文字列sに一行入力 //cin.eof()空だったらtrue stringstream ss(s); while(ss >> tmp){ //空白で区切られたモノに分割する //一つの単位がt…

AOJ0061 Rank Checker

チームの順位 | Aizu Online Judge AIZU ONLINE JUDGE: Code Review AIZU ONLINE JUDGE: Code Review

AOJ0051 Differential II

最大の整数と最小の整数の差 | Aizu Online Judge // gist.github.com stoll(string)はC++14 sort(),reverse()は文字列でも可能

AOJ0049 Blood Groups

血液型の分類 | Aizu Online Judge // gist.github.com int num; char comma; string s; cin>>num>>commma>>s; で違う方の一行入力を型ごとに変数に格納出来る. 入力が無い時はif(cin.eof())break;で終わらせる事ができる. string のi番目から始めたい時はst…

AOJ0038 Poker Hand

ポーカー | Aizu Online Judge 場合分けを頑張る // gist.github.com

AOJ0033 Balls

玉 | Aizu Online Judge 再帰 // gist.github.com // gist.github.com AIZU ONLINE JUDGE: Code Review

Project Euler 504 Square on the Inside

projecteuler.net1 証明: 例えばa=4,b=2として下の図形を考える. まずa*bの長方形の格子点の個数を考える.すると(x軸の点5個)*(y軸の点3個)=15個である. これは(a+1)*(b+1)を計算している. 次に境界線上の点を数える. この直線上で格子点を通るのはgcd(a,b)+…

AOJ0018 Sorting Five Numbers

降順ソートの方法 sort(a,a+N); reverse(a,a+N); だと一手間多くなってしまうので sort(a,a+N,std::greater<int>()); とすると降順ソートが出来る.</int>

Project Euler 345 Matrix Sum

N-Queen問題の斜め無い版(N-飛車問題?,N-ルーク問題?)のアルゴリズムで考えられうる盤面を全て用意しそのマスに配置された数字の合計の中で最大のモノを探せばよい. サンプルの5*5盤面では1秒以内で出来たが15*15では時間がかかって出来なかった. もっと早…

Project Euler 145 How many reversible numbers are there below one-billion?

projecteuler.net 単純な解放 奇数の判定はビット演算を計算する. n&1==1ならnは奇数, (not n&1)==1ならnは偶数 d.hatena.ne.jp ↑参考にしたい解答 // gist.github.com

Project Euler 329 Prime Frog

PE

projecteuler.net Pythonで分数型を用いたいときは fractions.Fraction(分子,分母)で出来る. 1. 500以下の全てのマスを素数か素数でないか区別する. 2. 次にマスが素数であれば"P"と鳴く確率は2/3, "N"と鳴く確率は1/3 マスが素数でなければ"P"と鳴く確率は1…

Pythonチュートリアルまとめ

Pythonチュートリアル(Python2.x対応)で自分が知らなかったこと, なんとなくは知っていたけど使っていなかった知識で特に重要そうなものをメモしておく. dir()関数 >>>import sys >>>dir(sys) sysモジュールがどのような名前を定義しているのかを確認できる …

5puzzle

ゲーム理論の課題でA*探索を実装した. ↓コード // gist.github.com ↓実行結果 紙とペンを使って実行したもの同じになった. g:=世代 h:=盤面Aの各マスの盤面Goalへのマンハッタン距離の和 f:=h+g として[f,g,"前回に移動した向き",盤面]のデータ構造でPriorit…

Python(5)

【リストのメソッド】 append(x) extend(L): リストの末尾に与えられたリストL全アイテムを追加する insert(i,x): リストA[i]にxを挿入する pop([i]): A[i]を返す, A[i]はなくなる index(x): 最初にあるxのインデックスを返す count(x) sort() reverse()

Python(4)

docstring >>>def func(): """ aaaaaaaaaaaaaaaaaa """ print("hello") >>>func() hello >>>print(func.__doc__) aaaaaaaaaaaaaaaaaa

Python(3)

lambda 式 >>>def make_incrementor(n): return lambda x:x+n >>>f = make_incrementor(42) >>>f(0) 42 >>>f(1) 43

Project Euler 96 Su Doku

PE

projecteuler.net 数独の問題 あるマスA[y][x] == 空白ならばそのマスが属する(i)横(ii)縦(iii)ブロックを探索しA[y][x]に入れるべき解の候補を探す. 解の候補の各々に対して再帰的な処理をする. 終了条件は, 答え→空白が無くなった ダメ→A[y][x]について解…

Python(2)

関数は「キーワード=値」の形で引数が取れる. // gist.github.com これにより「第二引数はデフォルトのままでいいけど第三引数に特別に値を入れたい」とかいう場合に役に立つと思う. 1つの引数は2回以上受け取れない.

Python(1)

Python3 エンジニア認定基礎ベータ試験に向けて『Python チュートリアル』の出題が多い章から順に気になったことを書く. 大学の図書館で借りることが出来たのはPython2.x 系のだったが, まあ大丈夫でしょう. 【気になったところ】 // gist.github.com デフォ…

Project Euler 89

PE

難易度は20%と簡単だが, とにかく面倒くさかった. // gist.github.com ローマ数字から数字, 数字からローマ数字に変換できる関数とかはあるのかな? 【追記:すぐ】 問題文を読み落としていることに気づいた. ローマ数字は大きい方から順に書かれる. よって…

Project Euler 204 (2)

PE

// gist.github.com d.hatena.ne.jp このブログを参考に書きました. とても参考になりました. 再帰のイメージを書いて見た. (limit = 1000) pで割り切れなくてもn//pでnを小さくしていけば結局同じなんですね.