c21coterie @ ウィキ

c21coterie @ ウィキ内検索 / 「AOJ Problem Set from ALDS1 問30～34」で検索した結果

• 会津大学オンラインジャッジ復習
  ...ジです。 AOJitp1 AOJ Problem Set from ALDS1問　0～19 AOJ Problem Set from ALDS1 問20～24 AOJ Problem Set from ALDS1 問25～29 AOJ Problem Set from ALDS1 問30～34 AOJ Problem Set from ALDS1 問35～39 AOJ Problem Set from DSL 問0～問4 AOJProblem Set from CGL 問0～4 AOJProblem Set from CGL 問5～9 AOJ Problem Set from DPL 問0～4 AOJProblem Set from NTL 問0～4 AOJ再挑戦問0～4 AOJ再挑戦問...
• AOJ Problem Set from ALDS1問　0～19
  ...どんなんだろう？ AOJやっててよかったことは今のところ何もないので、評価値が下がろうが気にしない。 #include stdio.h #include string.h #include list const int LIMIT =((1 16)+33); std list int hashTable[LIMIT]; int h1(char *str){ int p,p1,num,result=0; char c; for(p=0;p strlen(str);p++){ c=str[p]; num=0; if(c== A )num=0; if(c== C )num=1; if(c== G )num=2; if(c== T )num=3; ...
• AOJ Problem Set from ALDS1 問30～34
  Graph I - Graph http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_A グラフのつながりを表示する問題。 #include stdio.h #include string.h const int LIMIT=101; int g[LIMIT][LIMIT]; int main(){ int n,u,k,v; scanf("%d", n); memset(g,0,sizeof(g)); for(int i=0;i n;i++){ scanf("%d %d", u, k); while(k--){ scanf("%d", v); g[u][v]=1; } } for(int i=1;i =n;i++){ for(int ...
• AOJ Problem Set from ALDS1 問35～39
  Graph II - Single Source Shortest Path I http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B ダイクストラ法を実装せよという問題。 データ量が小さいのでまあ手抜きで書きました。 #include stdio.h static const int MAX = 500; static const int INFTY = (1 21); main(){ int n, i, j,u,v,c,k; int d[MAX],M[MAX][MAX]; scanf("%d", n); for ( i = 0; i n; i++ ){ d[i]=INFTY; for ( j = 0; j n; j++ ){ ...
• AOJ Problem Set from ALDS1 問20～24
  Tree - Tree Walk http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_7_C lang=jp 2分木をデータから組み立て順番に訪問した結果を出力する問題。 #include stdio.h const int LIMIT=26; const int NIL=-1; struct node{ int p,right,left; }; node Tree[LIMIT]; void Preorder(int p){ if(p==-1)return; printf(" %d",p); Preorder(Tree[p].left); Preorder(Tree[p].right); } void Inorder(int p){ if(p==-1)return; Inord...
• AOJ Problem Set from DSL 問0～問4
  Set - Disjoint Set Union Find Tree http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A 集合をユニオン木で管理せよという問題。 コード実行速度6/26位　タイム　0.03秒。 一位が0.02秒で２位が0.03秒５人、まあ平凡タイム。 #include stdio.h #include map int parents[10001]; int parentSearch(int p){ return (parents[p]=(p==parents[p]?p parentSearch(parents[p]))); } void parentUpdate(int p,int top){ if(p!=parents[p]){ parentUpdate(parents...
• prolog勉強プロジェクトオイラー121～130
  ...ひとつで一位が狙えるAOJと違ってプロジェクトオイラーは整数論の知識が要求される。 整数論の知識がない私にはこの問題は今のところお手上げだったのだが。 海外のコードも結構いじましい努力してるな。 深さを制限して1～200まで探索して制限内である数Nを作れたら確定で探索をまとめている。 もっと賢い方法を期待してたけど、こういう小手先のテクニックでも結構速くなるらしい。 プロジェクトオイラーのほうはどうせ整数論の知識もない私のことだし、一位を目指すとか上位を目指すとかそういうことはしない、まあできないけど。 深さ制限探索してある数Nが作れたときそのNをそれまでにもっと低い回数で作れていたら探索しない。 ということでまあ何とか見れる速度になった。 海外のコードを参考にしたし、なぜそれでうまくいくかの原理もよくわかってない。 参考サイトでも探そう。 search(_,...
• prolog勉強プロジェクトオイラー31～40
  プロジェクトオイラーの問題をＰｒｏlogで解くページ。 作者　堀江 伸一 近況　問い３６のコードの無駄を修正。 こんなネットの裏の裏の一番端っこの誰からも注目されないＷｉｋｉに何を書いたって世の中に何の影響も与えないので結構好きかって書いてます。 Problem 31 「硬貨の和」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2031 イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 以下の方法で£2を作ることが可能である． 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p これらの硬貨を使...
• prolog勉強プロジェクトオイラー141～150
  プロジェクトオイラーの問題を堀江伸一さんがProlog言語でとくページ。 整数論の知識はないので早いコードはあまりかけない。 Problem 142 「完全平方数コレクション」 † x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x y z 0で, 最小の x + y + z を求めよ. http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20142 解法 最新のパソコンで1秒くらいで答えが出る方法。 x+y=s1 x-y=s2 y+z=s3 y-z=s4 x+z=s5 x-z=s6 として x-s1=-y x-s2=y y-s3=-z y-s4=z として s1+s2の半分を...
• 会津大学オンラインジャッジ英語問題日本語訳
  会津大学オンラインジャッジの英語問題。 問題を意訳したものを掲載。 個人的な意訳なので正確性については保証しませんが、私が解けた問題だけ掲載しておきます。 Problem F Computation of Minimum Length of Pipeline http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1014 グラフの問題。 ｎ個の源泉、ｍ個の都市、源泉と都市の間の距離、都市と都市の間の距離が与えらえる。 源泉から都市へ熱水を供給したい。 源泉から都市へ、都市から都市へとパイプラインを引き全ての都市に熱水を供給し最短距離でつなげよ。 サンプルとして提示されているinputデータの解説は以下の通り。 3 5(源泉の数、都市の数) 12 8 25 19 23(源泉1からi番目の都市ま...
• プロジェクトオイラー問い111～120
  Problem 112 「はずみ数の濃度について調べ上げよ」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20112 左から右までどの桁もその左の桁を上回らない数を増加数と呼ぶ. 例えば, 134468. 同様に, どの桁もその右の桁を上回らない数を減少数と呼ぶ. 例えば, 66420. 増加数でも減少数でもない正の整数を「活発な」数と呼ぶことにする. 例えば, 155349. 100以下の数に活発な数が無いのは明らかだが, 1000より下の数では半数を少し上回る数(525)が活発である. 実際, 活発な数の割合が50%に達する最少の数は538である. 驚くべきことに, 活発な数はますます一般的になり, 21780では活発な数の割合は90%に達する. 活発な数が数の割合が99%...
• prolog勉強プロジェクトオイラー1～10
  プロジェクトオイラーの問題を堀江伸一こと私がＰｒｏｌｏｇで解くページ。 プロジェクトオイラーの問題は問題番号が小さいものほど簡単で問題番号が大きいものは非常に難しくなります。 この辺は最初なので中学生プログラマでも挑戦できるレベルの問題が並ぶ。 Problem 1 「3と5の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 1000未満の３か５の倍数になっている自然数の合計を答えよ 解法 数式で解くのが正しいけれどサイトの趣旨、数学の問題をプログラムで特に合わせて末尾再帰で記述。 mod_n(N,N) - member(R,[3,5]), N mod R= =0, !. mod_n(_,0) -!. search(1000,Ans) -!,write...
• プロジェクトオイラー問い61～70
  問い61 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2061 三角数, 四角数, 五角数, 六角数, 七角数, 八角数に関する問題。 解法 問題をグラフに翻訳して深さ優先探索で解決です。 少し手の込んだ処理を書いてますがもしかしたらもっとシンプルになるかもしれません。 #include stdio.h #include vector #include map std map int,std vector int memo[9]; bool spents[9]={false,false,false,true,false,false,false,false,false}; void saiki(int start,int num,int deep,int...
• prolog勉強プロジェクトオイラー61～70
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ Problem 61 「巡回図形数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2061 三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される. 三角数P3,n=n(n+1)/2 1, 3, 6, 10, 15, ... 四角数P4,n=n^2 1, 4, 9, 16, 25, ... 五角数P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ... 六角数P6,n=n(2n-1) 1, 6, 15, 28, 45, ... 七角数P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ... 八角数P8,n=n(3n-2) 1, ...
• プロジェクトオイラー問５４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2054 Problem 54 「ポーカーハンド」 † ポーカーの勝敗を判定する問題。 詳細はリンク先を参照のこと。 解法 世界中で何回ポーカーの役判定のコードが書かれたのだろうかと思いをはせる問題です。 両者ともに素朴に役を判定して役に対応したスコアと役で使ったカードの数字を返し、 Aのほうがスコアが大きいなら勝利、同じならカードを比べてAの勝利か判定するだけ。 １を14として取り扱うと話が綺麗になります。 判定には巧みな手法があるそうなのでそれを調べるのもいいかもしれませんね。 ファイルは一行ごと１０枚のカードを現すリストと変換しています。 max(A,B,A) -A B,!. max(_,B,B) -!. ...
• prolog勉強プロジェクトオイラー21～30
  プロジェクトオイラーの問題をPrologで解くページ。 創価学会の皆さまから小学校の算数までしかできないと言われている堀江伸一さんがこのページのコードを書いているようです。 Problem 21 「階乗の数字和」 † http //projecteuler.net/problem=21 10000以下の友愛数の和を求めよという問題。 そのまま定義通り計算するだけです。 複数の関数で一つの関数を表現するＰｒｏlogて独特。 yakusuu_sum(1,_,1,Sum,Sum) -!. yakusuu_sum(N,M,1,Sum,Sum1) -N M*M,!,Sum1 is Sum*(N+1). yakusuu_sum(N,M,Multi,Sum,Result) - 0= =N mod M,!, N1 is N//M, Multi1 is Multi*M+1, ya...
• prolog勉強プロジェクトオイラー11～20
  小学校の算数までしかできないと巷で評判の堀江伸一さんが、プロジェクトオイラーの問題にprolog言語で挑戦してみました。 ローカルな言語が集まるプロジェクトオイラーですが流石にprologで解いてるのは私だけかな、チェックはしてないけど。 Problem 11 「格子内の最大の積」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2011 20*20の格子に数字が入ってるものが与えられる。 上下左右斜めの連続する4つの数字の積の最大値を求めよ。 解法 こういう問題はＰｒｏlogのありがたさが少しだけわかる。 失敗したらとりあえずエラー処理もいらずにバックトラックしてくれるというのはとても便利。 dyxs(1,0). dyxs(0,1). dyxs(1,1). ...
• プロジェクトオイラー問い51～60
  問い51 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2051 　*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる. 　56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である 　56003は, このような性質を持つ最小の素数である.　 　桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注 連続した桁でなくても良い) 解法 100万までの素数をvectorに格納し、各素数それぞれについて*文字にチェンジした全パタ...
• prolog勉強プロジェクトオイラー91～100
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 問い91 原点が特殊処理が必要なくらいで後は点OAのベクトルを90度回してOA (a,b)としgcd(a,b)でOA 割ったベクトルを求め、そのベクトルの定数倍地点になる点の数を数えればOK。 gcd(0, B, B). gcd(A, B, G) - A 0, R is B mod A, gcd(R, A, G). min(X,Y,X) -X Y,!. min(_,Y,Y) -!. point_count(_,0,1000) -!. point_count(L,D,Result) - Result is L//D. r90(0,_,1,0) -!. r90(_,0,0,1) -!. r90(DY,DX,DY1,DX1) - gcd(DY,DX,G), DY1 is DX//G, DX1 is D...
• プロジェクトオイラー問い101～110
  問い102　内部に原点を含む三角形はファイル内にいくつあるでしょう? http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20102 3つの異なる点が -1000 ≤ x, y ≤ 1000 かつ三角形となるように, デカルト平面上にランダムに与えられる. 以下の2つの三角形を考える. A(-340,495), B(-153,-910), C(835,-947) X(-175,41), Y(-421,-714), Z(574,-645) 三角形ABCが原点を内部に含み, XYZは原点を内部に含まないことが確かめられる. 27Kのテキストファイルtriangles.txt(右クリックしリンク先を保存して欲しい) にランダムな1000個の三角形が適当なフォーマットのもと含まれている. 内部に原点...
• プロジェクトオイラー問い91～100
  問い91 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2091 0 =x,y =50の格子点で直角三角形を作るとき点の一つを原点に固定した時何通りの三角形を作れるか？ 解法 直角になる地点が決まれば後はベクトルの直角の概念から条件を満たす残りの点は決まります。 それを素直に計算するだけです。 #include stdio.h #include algorithm int gcd ( int a, int b ){ int c; while ( a != 0 ) { c = a; a = b%a; b = c; } return b; } int main(){ int ans=0; for(int ax=0;ax =50;ax++){ for(int ...
• prolog勉強プロジェクトオイラー191～200
  プロジェクトオイラーの問題を堀江伸一こと私がProlog言語で解くページ。 兵庫県加古川市加古川町南備後79-16 名前　堀江伸一 Problem 191 「賞を貰える文字列」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20191 ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している. 3日連続で休む, または, 2回以上遅刻した生徒は褒賞金を得る権利を失う. n日間の各生徒の出席状況を3進の文字列で表す. 文字はL (late, 遅刻), O (on time, 出席), A (absent, 欠席) である. 4日間の場合, 81通りの3進の文字列が考えられる. そのうち賞を貰えるのは以下の43個の文字列である. 30日間の場合, 賞を貰える文字列は何通り...
• プロジェクトオイラー問６２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2062 Problem 62 「立方数置換」 † 立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である. 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. 解法 ３乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。 例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。 最初に5個Hitした辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• prolog勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• プロジェクトオイラー問４９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2049 Problem 49 「素数数列」 † 項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ. (i)3つの項はそれぞれ素数である. (ii)各項は他の項の置換で表される. 1, 2, 3桁の素数にはこのような性質を持った数列は存在しないが, 4桁の増加列にはもう1つ存在する. それではこの数列の3つの項を連結した12桁の数を求めよ. 解法 まずa1 =a2 =a3 =a4でa1～a4は0～9の数という条件を満たす [a1,a2,a3,a4]というリストを全探索する。 ある[a1,a2,a3,a4]を並べ替えたものを４桁の整数とみて、これが素数であるか判定し ...
• アルゴリズム勉強日記
  http //rose.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja リンク先は会津大学オンラインジャッジというプログラマ向け問題集を扱ったサイトです。 私はこのサイトでsinapusu2002という名前で登録しプログラムの問題集を解いてます。 私の成績 http //judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=sinapusu2002 極力自力で解こうとしていますが、どうしても解けない問題は検索して答えを見たり、掲示板で質問して解いてます。 その際のカンニング履歴を記録することにしました。 個人的なもので、自分一人が分かれば十分な記録です。 カンニング履歴 1 http //rose.u-aizu.ac.jp/onlinejudge/ProblemSet/d...
• プロジェクトオイラー問い41～50
  問い41 n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする. #下のリンク先にあるような数学的定義とは異なる 例えば2143は4桁Pandigital数であり, かつ素数である. n桁（この問題の定義では9桁以下）Pandigitalな素数の中で最大の数を答えよ. 解法 ９桁や８桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは８桁と９ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。 よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。 末尾の数字が２の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。 #include stdio.h #include stdlib.h bool...
• 会津大学オンラインジャッジカンニング履歴一覧
  http //rose.u-aizu.ac.jp/onlinejudge/index.jsp?lang=ja リンク先は会津大学オンラインジャッジというプログラマ向け問題集を扱ったサイトです。 私はこのサイトでsinapusu2002という名前で登録しプログラムの問題集を解いてます。 私の成績 http //judge.u-aizu.ac.jp/onlinejudge/user.jsp?id=sinapusu2002 極力自力で解こうとしていますが、どうしても解けない問題は検索して答えを見たり、掲示板で質問して解いてます。 その際のカンニング履歴を記録することにしました。 個人的なもので、自分一人が分かれば十分な記録です。 カンニング履歴 1 http //rose.u-aizu.ac.jp/onlinejudge/ProblemS...
• プロジェクトオイラー問３０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2030 Problem 30 「各桁の5乗」 † 驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない. 1634 = 1^4 + 6^4 + 3^4 + 4^4 8208 = 8^4 + 2^4 + 0^4 + 8^4 9474 = 9^4 + 4^4 + 7^4 + 4^4 ただし, 1=14は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である. 各桁を5乗した数の和が元の数と一致するような数の総和を求めよ. 解法 9^5*7 1000000以下なので7桁以上は検討する必要がありません。 0～9までを含んだ数を重複なく反辞書順に６個...
• プロジェクトオイラー問３４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2034 Problem 34 「桁の階乗」 † 145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる. 各桁の数の階乗の和が自分自身と一致するような数の和を求めよ. 注 1! = 1 と 2! = 2 は総和に含めてはならない. 解法 7桁までの長さで一桁ずつ昇順で保持した重複のない数字のリストを作ります。 リストの要素をPermとします。 Permを各桁とみて階乗の和Numを計算します。 Numを各桁のリストに戻してソートしList1とします。 List1とPermが同じならその数Numは条件を満たす数です。 条件を満たす数は重複する数があるのでsor...
• prolog勉強プロジェクトオイラー131～140
  プロジェクトオイラーという数学問題の載ったサイトの問題を堀江伸一こと私がProlog言語で解いていくページ。 Prologは配列と優先順位付キューがなく、std setの自前実相も使い出が悪いのでそれらがないと効率的に解けない問題をPrologで解くことは難しいです。 そういう場合C++に逃げたりしますが基本Prologでときます。 Problem 131 「素数と立法数の関係」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20131 いくつかの素数pでは, ある正の整数nが存在して, n^3+pn^2が立方数になる. 例えば, p = 19のときには, 8^3+19×8^2=12^3である. このような性質を持つ各素数について, nの値は一意に定まる. また, 100未満...
• プロジェクトオイラー問６３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2063 Problem 63 「べき乗の桁の個数」 † 5桁の数 16807 = 7＾5は自然数を5乗した数である. 同様に9桁の数 134217728 = 8＾9も自然数を9乗した数である. 自然数を n 乗して得られる n 桁の正整数は何個あるか? 10＾２は３桁10＾３は4桁。 １０よりも大きな数は桁数の増加のほうがｎの増加より早いので答えは１０以下の数のｎ乗です。 またa^ｎの桁数がｎより小さくなったらそれ以後桁数はｎに追いつきません。 よって答えは狭い範囲に定まります。 logを使えば計算は簡単です。 sum([],0) -!. sum([X|Xs],Result) -sum(Xs,Re),Resul...
• プロジェクトオイラー問３２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2032 Problem 32 「パンデジタル積」 † すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう 例えば5桁の数 15234 は1から5のパンデジタルである. 7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる. 掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ. HINT いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ. 解法 a*b=cとすると a =...
• プロジェクトオイラー問１１５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20115 Problem 115 「ブロックの組み合わせ方の数え上げ その2」 † 注意 これは Problem 114 をより難しくした問題である. 長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている. ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). 敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする. 例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である. m = 3 の時, n = 30 がこの敷き詰め計数関数が初...
• prolog勉強プロジェクトオイラー201～210
  プロジェクトオイラーの問題を堀江伸一子と私がProlog言語で解くページ。 最近スランプ気味。 Problem 201 「唯一の和を持つ部分集合」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20201 数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる. sum({1,3,6}) = 10, sum({1,3,8}) = 12, sum({1,3,10}) = 14, sum({1,3,11}) = 15, sum({1,6,8}) = 15, sum({1,6,10}) = 17, sum({1,6,11}) = 18, sum({...
• プロジェクトオイラー解説問191
  Problem 191 「賞を貰える文字列」 † 問題 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20191 ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している. 3日連続で休む, または, 2回以上遅刻した生徒は褒賞金を得る権利を失う. n日間の各生徒の出席状況を3進の文字列で表す. 文字はL (late, 遅刻), O (on time, 出席), A (absent, 欠席) である. 4日間の場合, 81通りの3進の文字列が考えられる. そのうち賞を貰えるのは以下の43個の文字列である. OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OL...
• prolog勉強プロジェクトオイラー151～160
  プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。 Problem 151 「規格寸法用紙 期待値問題」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20151 とある印刷屋では毎週16回の定期的な仕事がある. 毎回 A5 サイズの特殊な色校正用紙 (special colour-proofing paper) を1枚使う. 月曜日の朝になると, 主任はA1サイズの特殊紙が入った新しい封筒を開ける. 彼はA1の紙を半分に切る. するとA2の紙が2枚出来上がる. 片方を半分に切りA3の紙が2枚出来上がる. 以下繰り返し, A5の紙を得るまで繰り返し, 1枚をその週の最初の仕事に使う. 使われなかった紙は全て元の封筒に収める. さて, 各仕事の際に, 主...
• prolog勉強プロジェクトオイラー181～190
  problem 188 Problem 188 「ある数のハイパーべき乗」 † 数 a の正整数 b による ハイパーべき乗 (hyperexponentiation) または テトレーション (tetration) を a↑↑b と書き, 以下のように再帰的に定義する. a↑↑1 = a, a↑↑(k+1) = a(a↑↑k). 定義によれば 3↑↑2 = 33 = 27であり, 3↑↑3 = 327 = 7625597484987となる. また, 3↑↑4は大体103.6383346400240996*10^12となる. 1777↑↑1855の最後の8桁を求めよ. 解法 単純にMod演算の 1777のｎ上の末尾8桁は1777＾ｒでｒの値によりループします。 1250001でループするので累乗をループサイズで割った余りをとっても計算は同じです。 あとはmod演算をしな...
• プロジェクトオイラー問３１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2031 Problem 31 「硬貨の和」 † イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 以下の方法で£2を作ることが可能である． 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p これらの硬貨を使って£2を作る方法は何通りあるか? 解法 初めてこの問題にPrologで挑戦した時は破壊的代入も配列もstd mapもないPrologでどうやって動的計画法をするか悩みました。 基本がわかれば考え方は簡単。...
• プロジェクトオイラー解説問4
  Problem 4 「最大の回文積」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%204 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数の最大値を求めよ. 解法 組み合わせ数が少ないので全部検討しても十分間に合います。 a=100～999=900個 b=100～999=900個 としても 全部で81万個の数字の検討にしかなりません。 最近のパソコンでは処理回数が5億回で1秒かそれ以下ですので、81万回の検討程度なら瞬きする間に終わります。 c=a*b とします。 100*100=10000 =c =999*999=9...
• プロジェクトオイラー問１９
  http //projecteuler.net/problem=19 Problem 19 「日曜日の数え上げ」 † 次の情報が与えられている. 1900年1月1日は月曜日である. 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである. 2月は28日まであるが, うるう年のときは29日である. うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない. 20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか? 解法 問題のほうで日数計算に必要なデータが提示されているので、出題の意図を読んでそれをつかって計算するのが正しいと思いますが。 ツェラーの公式で手抜きしました。 zellers(Y,M,D,Result) - (M 3 ...
• poj適当２
  コード記述者　堀江伸一 世にあるプログラマ養成プロジェクトの一つとして北京大学主催のプログラマ向け練習問題サイトというものがあります。 3000問程度問題が掲載されており、国際的にみても登録者の多いサイトで国際的には有名なサイトでアルゴリズムを勉強するにはちょうどいいサイトです。 問題を解くコードを書いてサーバに送信するとテストデータを使って自動採点までしてくれるので独学にはお勧めのサイトです。 http //poj.org/problemlist ただ問題が英語か中国語で掲載されているため日本人には敷居が高いかもしれません。 そこでリンク先サイトが役に立ちます。 問題を日本語訳しており挑戦しやすくなっております。 http //wikiwiki.jp/pku/?FrontPage リンク先サイトでは翻訳者を募集しているのですが、私はこのサイトをいいサ...
• オイラープロジェクト141～150
  問い142 Problem 142 「完全平方数コレクション」 † x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x y z 0で, 最小の x + y + z を求めよ. 解法 答えが１００万近辺とか小さな数であることを祈って解いた問題。 他の人の解法を見ると私ひとり頭の悪い解法を取ってるらしい。 この問題はメモ化とかより式変形が大事だったようだ。 y=z+a1 x=z+a2とすると x-y=a2-a1=平方数となるのでこの条件を満たすa1とa2の組み合わせを最初の２重ループで求めます。 後はこの組み合わせとｚの組み合わせを全て試す２重ループで試しただけです。 ｚは式変形するとa1,a2の値から増加量が決まるのでｚの増加数を適切にとることで計算量を抑えます。 これで約１秒で答えが出ます。...
• プロジェクトオイラー問６１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2061 Problem 61 「巡回図形数」 † 三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される. 三角数P3,n=n(n+1)/21, 3, 6, 10, 15, ... 四角数P4,n=n21, 4, 9, 16, 25, ... 五角数P5,n=n(3n-1)/21, 5, 12, 22, 35, ... 六角数P6,n=n(2n-1)1, 6, 15, 28, 45, ... 七角数P7,n=n(5n-3)/21, 7, 18, 34, 55, ... 八角数P8,n=n(3n-2)1, 8, 21, 40, 65, ... 3つの4桁の数の順番付きの集合 (...
• PKJ適当
  ...と感心した次第。 AOJではミドルサイズの問題は出てもラージサイズの問題はほとんど出なかったからなあ、これからはラージサイズの問題を前提にしたコードを考えないとなあ。 #include stdio.h #include algorithm #include queue struct Num{ int num,p; }; class maxSorter { public bool operator() (const Num l, const Num r) const { return l.num r.num; } }; class minSorter { public bool operator() (const Num l, const Num r) const { return l.num r.num; } }; const int s...
• プロジェクトオイラー問８５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2085 Problem 85 「長方形の数え上げ」 † 注意深く数えると, 横が3, 縦が2の長方形の格子には, 18個の長方形が含まれている. ぴったり2,000,000個の長方形を含むような長方形の格子は存在しない. 一番近い解を持つような格子の面積を求めよ. 解法 ｗ＜＝Ｈとしても一般性を失いません。 ｗを定めたら条件を満たすｈは２次方程式の解となるのでその近辺の整数を探すだけです。 hanni(X,X1) - between(-2,2,D), X1 is X+D. calc([Sa,H1,W,S]) - between(1,3000,W), D is (8000*1000)//(W*W+W), D 0, H ...
• プロジェクトオイラー問７５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2075 Problem 75 「1通りの整数直角三角形」 † ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである. 他にも沢山の例が挙げられる. 12 cm (3,4,5) 24 cm (6,8,10) 30 cm (5,12,13) 36 cm (9,12,15) 40 cm (8,15,17) 48 cm (12,16,20) それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある. 120 ...
• poj適当
  ...と感心した次第。 AOJではミドルサイズの問題は出てもラージサイズの問題はほとんど出なかったからなあ、これからはラージサイズの問題を前提にしたコードを考えないとなあ。 #include stdio.h #include algorithm #include queue struct Num{ int num,p; }; class maxSorter { public bool operator() (const Num l, const Num r) const { return l.num r.num; } }; class minSorter { public bool operator() (const Num l, const Num r) const { return l.num r.num; } }; const int s...
• 2011年4月
  ...のだろう。 AOJには実力のあるプログラマがそんなにいないから正解率が低いにすぎない。 AOJに集まる人にとっては難問だった、程度にすぎないのかも。 私もこの問題に挑戦。 この問題世間的には簡単に分類されるのだろうけど、私には難しく答えが出せない。 正しい答えを出すところまではいってるはずなんだけど、実行時間が長すぎて不正解を喰らう。 コードを効率化する方法がわからない。 家の数が１０軒でも全探索で10！*45程度の計算量　３６０万*45回の計算量になる。 どうやって計算量を落とせばいいんだ？ algorithm stdio.h void setMap(int n); int main(){ int n; while(scanf("%d", n)!=EOF){ setMap(...
• プロジェクトオイラー問９９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2099 Problem 99 「最大のべき乗」 † 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 3^7 = 2187 であることが確かめられる. しかし, 632382^518061 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる). 各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ. 注 ファイル中の最初の二行は上の例である. 解法 Ｌｏｇを使っても十分答えが出るよう...
• @wiki全体から「AOJ Problem Set from ALDS1 問30～34」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索