2016-01-01から1年間の記事一覧
// gist.github.com main(n)のnはint型のGlobal変数0に初期化される.
// gist.github.com Global変数は0で初期化される. scanf("")!=EOFと表現したい場合EOFマクロは<stdio.h>に入っているため<stdio.h>を除くとこの様に記述できない. 何も入力されない場合-1であることを利用(-1は全て1が立った状態)してbit反転の~で終了条件を作れる.</stdio.h></stdio.h>
// gist.github.com
// // サイドバーを製作した. gist.github.com
projecteuler.net e=[2;1,2,1,1,4,1,1,6,1,...,1,2k,1,...] という連分数展開の問題後ろから深さ優先探索で解く. from fractions import Fravtionsすると分数型が出来て便利 gist.github.com
逆ポーランド記法の問題 stackを用いる. gist.github.com C++で一行入力をするには string s,tmp; getline(cin,s);//文字列sに一行入力 //cin.eof()空だったらtrue stringstream ss(s); while(ss >> tmp){ //空白で区切られたモノに分割する //一つの単位がt…
チームの順位 | Aizu Online Judge AIZU ONLINE JUDGE: Code Review AIZU ONLINE JUDGE: Code Review
最大の整数と最小の整数の差 | Aizu Online Judge // gist.github.com stoll(string)はC++14 sort(),reverse()は文字列でも可能
血液型の分類 | Aizu Online Judge // gist.github.com int num; char comma; string s; cin>>num>>commma>>s; で違う方の一行入力を型ごとに変数に格納出来る. 入力が無い時はif(cin.eof())break;で終わらせる事ができる. string のi番目から始めたい時はst…
ポーカー | Aizu Online Judge 場合分けを頑張る // gist.github.com
玉 | Aizu Online Judge 再帰 // gist.github.com // gist.github.com AIZU ONLINE JUDGE: Code Review
projecteuler.net1 証明: 例えばa=4,b=2として下の図形を考える. まずa*bの長方形の格子点の個数を考える.すると(x軸の点5個)*(y軸の点3個)=15個である. これは(a+1)*(b+1)を計算している. 次に境界線上の点を数える. この直線上で格子点を通るのはgcd(a,b)+…
降順ソートの方法 sort(a,a+N); reverse(a,a+N); だと一手間多くなってしまうので sort(a,a+N,std::greater<int>()); とすると降順ソートが出来る.</int>
N-Queen問題の斜め無い版(N-飛車問題?,N-ルーク問題?)のアルゴリズムで考えられうる盤面を全て用意しそのマスに配置された数字の合計の中で最大のモノを探せばよい. サンプルの5*5盤面では1秒以内で出来たが15*15では時間がかかって出来なかった. もっと早…
projecteuler.net 単純な解放 奇数の判定はビット演算を計算する. n&1==1ならnは奇数, (not n&1)==1ならnは偶数 d.hatena.ne.jp ↑参考にしたい解答 // gist.github.com
projecteuler.net Pythonで分数型を用いたいときは fractions.Fraction(分子,分母)で出来る. 1. 500以下の全てのマスを素数か素数でないか区別する. 2. 次にマスが素数であれば"P"と鳴く確率は2/3, "N"と鳴く確率は1/3 マスが素数でなければ"P"と鳴く確率は1…
Pythonチュートリアル(Python2.x対応)で自分が知らなかったこと, なんとなくは知っていたけど使っていなかった知識で特に重要そうなものをメモしておく. dir()関数 >>>import sys >>>dir(sys) sysモジュールがどのような名前を定義しているのかを確認できる …
ゲーム理論の課題でA*探索を実装した. ↓コード // gist.github.com ↓実行結果 紙とペンを使って実行したもの同じになった. g:=世代 h:=盤面Aの各マスの盤面Goalへのマンハッタン距離の和 f:=h+g として[f,g,"前回に移動した向き",盤面]のデータ構造でPriorit…
【リストのメソッド】 append(x) extend(L): リストの末尾に与えられたリストL全アイテムを追加する insert(i,x): リストA[i]にxを挿入する pop([i]): A[i]を返す, A[i]はなくなる index(x): 最初にあるxのインデックスを返す count(x) sort() reverse()
docstring >>>def func(): """ aaaaaaaaaaaaaaaaaa """ print("hello") >>>func() hello >>>print(func.__doc__) aaaaaaaaaaaaaaaaaa
lambda 式 >>>def make_incrementor(n): return lambda x:x+n >>>f = make_incrementor(42) >>>f(0) 42 >>>f(1) 43
projecteuler.net 数独の問題 あるマスA[y][x] == 空白ならばそのマスが属する(i)横(ii)縦(iii)ブロックを探索しA[y][x]に入れるべき解の候補を探す. 解の候補の各々に対して再帰的な処理をする. 終了条件は, 答え→空白が無くなった ダメ→A[y][x]について解…
関数は「キーワード=値」の形で引数が取れる. // gist.github.com これにより「第二引数はデフォルトのままでいいけど第三引数に特別に値を入れたい」とかいう場合に役に立つと思う. 1つの引数は2回以上受け取れない.
Python3 エンジニア認定基礎ベータ試験に向けて『Python チュートリアル』の出題が多い章から順に気になったことを書く. 大学の図書館で借りることが出来たのはPython2.x 系のだったが, まあ大丈夫でしょう. 【気になったところ】 // gist.github.com デフォ…
難易度は20%と簡単だが, とにかく面倒くさかった. // gist.github.com ローマ数字から数字, 数字からローマ数字に変換できる関数とかはあるのかな? 【追記:すぐ】 問題文を読み落としていることに気づいた. ローマ数字は大きい方から順に書かれる. よって…
// gist.github.com d.hatena.ne.jp このブログを参考に書きました. とても参考になりました. 再帰のイメージを書いて見た. (limit = 1000) pで割り切れなくてもn//pでnを小さくしていけば結局同じなんですね.
type 以下の素数のリストをエラトステネスの篩で作る. その素数のみの積で表される数のうちlimit = 10**9を超えない数を数え上げれば良い. もっとも小さい素数は2であり2**n で始めてlimit を越えるのはn = 30であるので, 素数のリストから30個重複を許さな…
滅茶苦茶汚いコードだし理論もクソだったのでコードは載せない. 考え方は10<= n <= 150000000まで回してその一つ一つにn^2+1, ..., n^2+27を計算しそれぞれをMR法で素数か判定する. この時全体の時間を考えるとMR法で生成する乱数は少ない方が良い. 3回もや…
nが素数かを判定するプログラムです. フェルマーの小定理に基いて出来ています. フェルマーの小定理は a,n が互いに素のとき 「nが素数 → a^(n-1) modn = 1」 というものです. 対偶をとって 「a^(n-1) modn !=l 1 → nが素数でない(合成数)」 プログラムで書…
使うタイルの枚数をn, laminaeの輪郭の正方形の一辺の長さをa, 穴の正方形の長さをb とする. 100以下を考えるとすると b= 1のとき(穴が1*1マスのとき) a = 3, n = a**2 - b**2 =3**2 - 1**2 = 8 a = 5, n = 5**2 - 1**2 = 24 a = 7 ,n = 7**2 - 1**2 = 48 a …