AOJ0049 Blood Groups
int num;
char comma;
string s;
cin>>num>>commma>>s;
で違う方の一行入力を型ごとに変数に格納出来る.
入力が無い時はif(cin.eof())break;で終わらせる事ができる.
string のi番目から始めたい時はstring.substr(i)
AIZU ONLINE JUDGE: Code Review
Project Euler 504 Square on the Inside
1<=a,b,c,d<=mに対して(a,0)(0,b)(-c,0)(0,-d)で囲まれた四角形内部の格子点の個数(境界を含まない)は
証明:
例えばa=4,b=2として下の図形を考える.
まずa*bの長方形の格子点の個数を考える.すると(x軸の点5個)*(y軸の点3個)=15個である.
これは(a+1)*(b+1)を計算している.
次に境界線上の点を数える. この直線上で格子点を通るのはgcd(a,b)+1個.
これらを同様に全てに適応すると
は重複して数えている点を1回分引いている. それだけだと原点が入らなくなるので+1
参考にしたページ
examist.jp
AOJ0018 Sorting Five Numbers
降順ソートの方法
sort(a,a+N);
reverse(a,a+N);
だと一手間多くなってしまうので
sort(a,a+N,std::greater<int>());
とすると降順ソートが出来る.
Project Euler 345 Matrix Sum
Project Euler 145 How many reversible numbers are there below one-billion?
単純な解放
奇数の判定はビット演算を計算する.
n&1==1ならnは奇数, (not n&1)==1ならnは偶数
↑参考にしたい解答
Project Euler 329 Prime Frog
Pythonで分数型を用いたいときは
fractions.Fraction(分子,分母)で出来る.
2. 次にマスが素数であれば"P"と鳴く確率は2/3, "N"と鳴く確率は1/3
マスが素数でなければ"P"と鳴く確率は1/3, "N"と鳴く確率は2/3
これを辞書に記憶しておく.
d=dict()
d[(5,"P")]=Fraction(2,3) d[(5,"N")]=Fraction(1,3)
d[(6,"P")]=Fraction(1,3) d[(6,"N")]=Fraction(2,3)みたいに
3. あるマスi に関してそのマスから始めたときに"string"と鳴く確率を求める
メモ化再帰を用いる.
マスが1なら右しかいけないのでPr=d[(1,string[0])]*func(i+1,string[1:])
マスが500なら左しかいけないのでPr=d[(500,string[0])]*func(i-1,string[1:])
マスが2~499なら左右どちらもいけるので
Pr=d[(i,string[0])]*( func(i+1,string[1:])*0.5 + func(i-1,string[1:])*0.5) )である
これはiマスでstrnigの先頭一文字目("P","N")の確率*(二文字目以降の確率)である.
2~499では左右どちらかに行くのに0.5の確率を考慮する.
Pythonチュートリアルまとめ
Pythonチュートリアル(Python2.x対応)で自分が知らなかったこと, なんとなくは知っていたけど使っていなかった知識で特に重要そうなものをメモしておく.
dir()関数
>>>import sys
>>>dir(sys)
sysモジュールがどのような名前を定義しているのかを確認できる
例外の処理
>>>while True:
try:
x = int(input())
break
except ValueError:
print("数字を入力しろ")
入力として数字を入力すればbreakでwhile文が終わるが, 例えば文字列を入力するとint()へ変換できずValueErrorが生じるtry文はエラーが生じた地点でexcept文へ移動しexcept 文のオプションValueErrorと今回出たエラー(ValueError)と比較一致していたら,except文を実行する.
except(RuntimeError, TypeError, detail)のようにエラー処理を複数指定できる.
クリーンアップ
def divide(x,y):
try:
result = x/y
except ZeroDevisionError:
print("ゼロで割った")
else:
print(result)
finally:
print("finally")
>>>division(2,1)
2 ←エラー処理でない∧ZeroDivisionErrorでもない(当たり前)のでelse文が実行
finally ←finallyが実行
>>>division(2,0)
ゼロで割った ←ZeroDivisionErrorが実行
finally ←finallyが実行
>>>division("2","0")
finally ←"2"/"0"は出来ないのでエラーが出てtry文から抜けて例外処理へ, ZeroDivisionErrorでないelseは実行されないfinallyへ
エラーの文がつらつら
ジェネレータ
def reverse(string):
for i in range(len(string)-1,-1,-1):
yield string[i]
>>>for c in reverse('vocky')
print(c,end="")
ykcov
これはreverse('vocky')で
'vocky'[4]
'vocky'[3]
'vocky'[2]
'vocky'[1]
'vocky'[0]
の順でcに入るということ
5puzzle
ゲーム理論の課題でA*探索を実装した.
↓コード
↓実行結果
紙とペンを使って実行したもの同じになった.
g:=世代 h:=盤面Aの各マスの盤面Goalへのマンハッタン距離の和 f:=h+g
として[f,g,"前回に移動した向き",盤面]のデータ構造でPriority-Queueを用いて求めた.
実装している中で幾つか重要なことに気づいた.
1. Python のPriority-Queueは小さいものから出ていく.
C++は大きいものからだったようなきがする. 大きい順に出したいときは-1倍して入れれば良い.
2. リストのスコープについて
このコードの実行結果は
こうなる. C++とかだと関数内だけにしか適用されないのでこのミスに1時間程気づかず痛い目を見た.
もとのリストに変更を加えずリストの要素をいじりたいときは B=list(A)のようにして新たなリストBをつくるとよい. B=Aとしてしまうと, BはAを参照するという意味になってしまいBも同じく変化してしまう.
ex)
>>>A=[1,2,3,4]
>>>B=A
>>>C=list(A)
>>>A[0]="a" #リストの要素をいじる
>>>A
["a",2,3,4]
>>>B
["a",2,3,4] #Aと同じ
>>>C
[1,2,3,4] #変化しない(オリジナルのA)
>>>A=[5,6,7,8] #新たなリストの定義, 要素をいじってるわけではない
>>>B
["a",2,3,4] #Bはそのまま
