http://poj.org/problem?id=3252 パスカルの三角形をあらかじめ計算しておく。 まず、((数字の桁数) - 1)桁以下の2進数についてRound Numberを求める。 これは、iを桁数、jを0の個数として iCj - (i-1)C(j-1) の和を計算すればよい。次に(数字の桁数)桁の2進…

easy 和sとして、「和がsになる2つの数字の組合せ」を3つ取ってくる円順列を考えて、sがmax(7,K)から2N-5までの円順列の和を求めればよい。 #include <cstdio> #include <algorithm> #include <vector> #include <string> using namespace std; class FoxMakingDice{ public: long long c3(long </string></vector></algorithm></cstdio>…

ルールを変えたNimでAliceとBobのどちらが必勝かを判定する問題 ルール： 石が1個以上ある山がいくつかある。 プレイヤーは毎回、一つの山から石を1個以上とる。 山は順番に並んでおり、1個以上石が存在する山のうち一番左の山からしか石をとることはできな…

問題 http://poj.org/problem?id=1989 (翻訳)K種類の整数N個からなる整数列が与えられるので、その部分列とならない整数列のうち最短のものの長さを答えろ。 解法 整数列の先頭から、K種類の整数が一通り出るところまで進み、さらにその場所からまたK種類の…

問題 http://poj.org/problem?id=2719解法 4を抜かして数える は 4->5 5->6 6->7 7->8 8->9 と置き換えた9進数で数えることと同じと考える。 つまり、与えられた数の各位に4より大きい数があれば、その位の数から1を引き、できあがった数を9進数とみて10進数…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114解法 (x,y,z) = (1,1,1) を {x' = a1*x mod m1 {y' = a2*y mod m2 {z' = a3*z mod m3 で計算していくと、再び(1,1,1)になるという条件から xだけでみたとき、xが再び1になるまでの計算回…

PCK本選に向けての練習 1日1ACを目標にしている。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0211解法 d[i], v[i] のときの周回数を m[i] 回とし、周回時間 d[i]/v[i]*m[i]=T 時間とする(Tは一定の値) このとき (m[i]=) T*(v[i]/d[i]) …

問題 http://poj.org/problem?id=2390解法 単純な複利計算 やるだけ #include <cstdio> using namespace std; int main(){ int R, M, Y; double r, sum; scanf("%d %d %d", &R, &M, &Y); sum = (double)M; r = 1.0 + (double)R / 100.0; for(int i = 0; i < Y; i++){</cstdio>…

PCKに参加することになったので練習しています。 まだまだ先ですけどね問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0113解法 筆算をするようにやっていく。 余りを配列に記憶しておいて、 以前と同じ余りが存在している⇔循環している を…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0202以前問題を見たとき「あ、これ無理なやつだ」と思ったもの。 できるようになっていた。解法 素数の金額が作れるかを調べるのに動的計画法を用いる。 ↑この発想がむりだった。 k[i] := 品物iの…

問題 解法 代金をpとすると,実際に払う金額Pは p だから,全部ためしていくといい. #include <cstdio> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i</algorithm></cstdio>

問題(AOJ) 問題(POJ) 解法 エラトステネスの篩をつかうだけ。 #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char prime[1000000]; int a, d, n; int main(){ memset(prime, sizeof(prime), 0); prime[1] = 1; for(int i = 2; i <= 1000; i++){ if(pr</algorithm></cstring></cstdio>…

問題 解法 は0点の的に当たったとしてあつかえばいい。n回目に投げたダーツの得点をPnとすると、 P1 + p2 + P3 + p4 が成り立つようにしなければならない。このまま計算すると、計算量は O(N^4) となりN ここで、式を変形して、 P3 + P4 これを計算する 2つ…

問題 解法 1年1月1日から何日経過しているかを計算するといい。 この時、フェアフィールドの公式を使うと便利。 #include <cstdio> using namespace std; int dc(int y, int m, int d){ if(m <= 2){ y--; m += 12; } return 365*y+y/4-y/100+y/400+306*(m+1)/10+d-42</cstdio>…

問題 解法 全部足して、(k-1)で割ればいい。 #include <cstdio> using namespace std; int main(){ int k,t,s,i; while(scanf("%d",&k)&&k){ s = 0; for(i=0;i < k*(k-1)/2;++i){ scanf("%d", &t); s += t; } printf("%d\n",s/(k-1)); } return 0; }</cstdio>

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0158 ひさしぶりのHaskell たぶんlet式の意味を正確には把握していない main = do n <- getContents let vs = map (\cs -> (read cs :: Int)) $ words n putStr $ unlines $ map (\n -> show n) $…

問題 四つ子素数を見つける問題。 制限時間が1秒と短かったので、こんなのでテーブル作って貼り付けることにした。 別にこんなことしなくてもいいかもしれない。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 10000001; bool prime[MAX_N]; </algorithm></cstdio>…

Haskellで2分探索をつかい入力された値の平方根を求めるプログラムを作ってみた。 EPSで精度を変えられる。 inf = 1000000000 eps = 0.0000001 main = getContents >>= putStrLn . show . root 0.0 inf . read root l h n = let ave = (l + h) / 2.0 in if (…

haskellの練習のために、フィボナッチ数を計算するプログラムを作った。 nを入力すると第n番目のフィボナッチ数を返す。 O(n)で計算できるようにした。 モナドはあまり理解できていないが、かっこよさそうなので利用してみた。(>>=) f :: Int -> Int -> Int …

問題 略解法 線形合同法を使って疑似乱数を実際に生成しシミュレーションするだけでいい。実装 #include <cstdio> #include <algorithm> using namespace std; int A, B, C; int nX; const int MAX_N = 100; int N, num[MAX_N]; void rng(){ nX = ((A * nX) % C + B) % C; } int</algorithm></cstdio>…

問題 M(N, P) = Nより大きい2つの素数の和をとることで得られる数を，小さいほうから順に並べたとき，P 番目の数 M(N, P)を求めよ。 0 ≤ N ≤ 100,000 1 ≤ P ≤ 100解法 はじめにエラストテネスの篩で素数をたくさん求めておく。 Nより大きいP個の素数をみつけ…

完全数か不足数か過剰数かを判定する問題。約数の和をどうやって求めるかが重要。 n=100000000だからすべての数を調べるのは困難。調べたら、 √n = 10000 回のループで できるそうです。 1 if(n % i == 0){ S += i + n % i; if(i == n % i) S -= i; } これで…

3をかけていくだけの簡単なお仕事です。 #include <cstdio> using namespace std; const int MAX_N = 20; long long table[MAX_N + 1]; int main(){ int n; table[1] = 3; for(int i = 2; i <= MAX_N; i++) table[i] = table[i-1]*3; scanf("%d", &n); for(int i = 1</cstdio>…

硬貨の枚数を少なくしたい。 所持金をすべて払ったときのおつりを求め、そこから重複して払った硬貨の枚数を 引いていけばいい。たぶん一瞬で解が求まるから、８秒の時間制限も余裕。 #include <cstdio> #include <algorithm> using namespace std; int p; //代金 int coin[4]; </algorithm></cstdio>…