c21coterie @ ウィキ

c21coterie @ ウィキ内検索 / 「2351～2360」で検索した結果

• 2351～2360
  2360　Sharp 2SAT http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2360 論理式が与えられるのでそれを真にする真偽値の組み合わせを求める問題。 基本的な考え方は考え始めて最初の50分で思いついたものの、実装が大変な問題でした。 基本的な考え方は論理式の連鎖が (X1,X4)(X4,X2)(X2,X5)(X5,X1)というループか (X6,X7)(X7,X8),,となる鎖かしかない。 鎖なら鎖を順にたどって組み合わせ数をメモ化で求めていきます。 ループならメモ化のスタート時がtrueだったかfalseだったかを覚えておきながら論理式のチェインでできる組み合わせ数を求め最後にTでおわるＦで終わるものだけを合計する。 というシンプルな発想です。 #include stdio....
• 会津大学オンラインジャッジコード記録
  ...341～2350 2351～2360 2361～2370 aoj2391～2340 aoj2400～2410 aoj2411～2420 aoj2431～2440 aoj2471～2480 aoj2481～2490 aoj2491～2500 aoj2501～2510 aoj10000全部 北京大学オンラインジャッジの問題を解いた履歴。 poj適当 poj適当２ UVa適当 UVa問題日本語意訳100～110 UVa100～110 カンニング履歴一覧 どうしても自力で解けなかった問題は公開されている答え（解き方の指針だけで詳細なコードまでは載ってない）を見たり、公開されているジャッジデータ（採点用データ）でテストしてから投稿したり、掲示板で質問したりして解きました。 リンク先はそうやってカンニングして解いた問題の一覧です。 アルゴリ...
• 2361～2370
  2361　Sort http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2361 ソートコストを題材にした問題。 解法 とりあえずグラフの問題としてダイクストラ法で解いてみましたが速度出てません。 もしかしたら何も考えない深さ優先探索の方が早いかもしれません。 #include stdio.h #include map #include string #include queue struct S{ std string str; int cost; bool operator (const S s)const{ if(cost!=s.cost)return cost s.cost; return str s.str; } }; int main(){ std map std strin...
• aoj2341～2350
  2350　A-B Problem http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2350 Ａ-Ｂで桁の繰り下がりを最大Ｋ回まで忘れた場合Ａ-Ｂの最大値は幾らになるか？ 解法 問題で指定されたとおりに実装します。 探索空間が狭いので全探索で答えが出ます。 この問題数万桁とかになったらどう解くか結構難しそうな問題になりそうです。 #include stdio.h #include string #include iostream std string ans=""; int borrow[13]={0}; void saiki(char a[20],char b[20],char c[20],int k,int count,int p){ if(p==0){ std ...
• オイラープロジェクト351～360
  問い351 http //projecteuler.net/problem=351 解法 この問題は点をベクトルA(1,0),ベクトルB(cos60,sin60)とすると全部の点を tA+sBとして表現できます。 となればｔとｓが約分できる点は他の点に遮られている点となります。 約分できる数の個数となればファイ関数の出番です。 n-φ(n)とすれば遮られた点の個数が出ます。 ０度 Θ ６０度の範囲だけ求めれば後は対象なので６倍します。 ちょっとした注意点として計算を簡単にするために原点からX軸と６０度、１２０度、、３００度の角度にある点は別口で計算しています。 早解きを目指したので計算部分のコードに少し混乱が見られますがまあ正しい答えを出すのでいいかと。 コード実行時間３分３０秒。 人生で三冊目の整数論の本を買った効果でてます。 #include ...
• 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). ...
• 2321～2330
  2330　Earth Invasion Diary of Miyabi-sensei http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2330 コピーのドラキュラの中からオリジナルのドラキュラを見つける問題。 偽物金貨の問題と同じなので割り算するだけ。 #include stdio.h int main(){ int n,c=0; scanf("%d", n); n--; while(n!=0){ n/=3; c++; } printf("%d\n",c); } 2331　A Way to Invite Friends http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2331 海に一緒に行く友達の...
• 2311～2320
  2311　Dessert Witch http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2311 簡単なＣＰＵ同士のオセロ対戦のシミュレーション問題。 簡単すぎて皆やる気が起きなかったのか私のコードがコードサイズ最小でアセプト。 これくらいの問題なら中学生プログラマでも解けそう。 本気でショートコードしたらどれくらい縮むか気になる問題。 #include stdio.h #include string.h char map [9][9]; char next[9][9]; char tMap[9][9]; int dxs[]={ 1, 1, 0,-1,-1,-1, 0, 1}; int dys[]={ 0, 1, 1, 1, 0,-1,-1,-1}; int nx,ny; void revers(int...
• 雑記・日記2
  ここはこのサイトの管理人こと堀江伸一さんの個人的な雑記、日記　勉強記録を雑多に集めたページです。 当サイトの小学生レベルの創作物に関する言い訳 勉強記録一覧 リンク　→会津大学オンラインジャッジコード記録 会津大学オンラインジャッジの解答コードでこちらへ来た方はリンク先へどうぞ、私のコードが掲載されています。 一応少数の問題でコード実行速度一位を取ったコードもあるのですこしは参考になるかもしれません(ご近所さんのある方はＡＯＪでコード実行速度一位とるなんて馬鹿でもできる笑いもの　ぷぷぷ　とか言ってました。世間的なＡＯＪの評価ってそんなものかもしれません)。 会津大学オンラインジャッジ復習 ここより以下は本当に個人的な雑記ですので気にしないでください。 もしも結婚できたら子供に言ってみたいこと ネットで好みのイラスト収集 新ギレン...
• 2251～2260
  2259　Programming Contest http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2259 たまに簡単すぎる問題があるのが不思議。 #include stdio.h int main(){ int n,m,s,b,a=0; scanf("%d %d", n, m); for(int i=0;i n;i++){ s=0; for(int j=0;j m;j++){ scanf("%d", b); s+=b; } a=a s?a s; } printf("%d\n",a); } 2260　(iwi) http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2260 名前を左右対称...
• オイラー1～10
  オイラープロジェクトという数学の練習問題を解くサイト。 プログラムで解いても数式で解いてもいいらしい。 http //projecteuler.net/about 問い２ フィナボッチ数のうち４００万以下の偶数の和を求める問題。 もしかしたら大きな数になるかと思ったら意外と小さい数になった。 フィナボッチ数の性質を考えたら当たり前か。 偶数項だけ見て小さい順にＡiとラベルを張っていくとAi=4*(Ai-1)+Ai-2という性質があることを利用して計算量を下げる。 出題側としてはこの数式の性質を考えてほしいのだろうと思うが、私はプログラムが書けただけで満足してしまってる。 #include stdio.h int main(){ __int64 sum=2,add=0,now=2,t; while(1){ t=now*4+add; if(t =4000000)b...
• AOJ231～240
  0231　Dangerous Bridge http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0231 橋の通行予定表から橋が壊れるほどの重量がかからないかを調べる問題。 解法 わたる順番と橋を渡り終える順番を時系列順に並べて一からシミュレートするだけです。 こういう簡単な問題は気楽に解ける分楽しいです。 １００マス計算宜しく、こういう簡単な問題を１００問並べた１００問プログラムとかあれば楽しいのですが。 #include stdio.h #include queue struct move{ int w,type,time;//wは重さ、0がわたり終わり1がわたり始め bool operator (const move m)const{ if(time!=m.time) return time...
• aoj2331～2340
  2333 My friends are small http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333 ナップザック問題のうち最大限入れられる組み合わせの数だけ計算する問題。 解法 組み合わせの集合を排他的に分けます。 おもちゃの重さを小さい順に並べ、入れないことに決めた一番最後に入れる一番小さなおもちゃを決めてそれを入れない場合をナップザック問題の手法で計算します。 入れないことに決めたおもちゃを最後に入れようとしてはいらない組み合わせだけ集計すれば答えが出ます。 入れないことに決めたおもちゃより軽いおもちゃは全部入れるとすると組み合わせの集合が綺麗に別れるので工夫点はそこだけです。 #include stdio.h #include vector #include string.h...
• aoj2391～2340
  2399　Save Your Privacy! http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2399 各人のもつ個人情報のリストと流出した個人情報のリストを突き合わせてだれが流出させたかをチェックする問題。 個人情報を01のビット配列に変換してBit演算でOrとって情報量が増えなかったらその人。 二人以上や一人も候補がなければ-1. 簡単です。 #include stdio.h #include bitset void search(int n){ std bitset 102 ps[102],ms; int m,p,ans,count=0; for(int i=1;i =n;i++){ ps[i].reset(); scanf("%d", m); for(int j=0;j...
• 2291～2300
  2296 Quest of Merchant http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2296 平面上の街から品物を買って市場で売るとき、市場データから最大利益を求めよという問題。 とりあえずsinapusu2002としてコード実行速度1位をゲット。 コードも一つも記述ミスなく一発で通った。 解法 いくつかの都市を回ることを決めた時どの順序で回っても、一番短い時間で都市を回るルート以外意味がないので最初にこれを無視します。 次にその都市巡回ルートのなかで一番安く商品を買える都市以外から商品を買わないことにします。 この条件で各ルートごとに動的計画法で最短時間と最大利益を計算します。 このルート一つ一つを一単位(市場から出発して都市を回って帰ってくるルートを１セット)としてナップザック法適用すれ...
• AOJ251～260
  0256 Points for a Perfect Scorer http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0256 集計するだけの問題。 解法 一番簡単な問題なので何も考えません。 #include stdio.h int main(){ int s=0,a; while(scanf("%d", a)!=EOF)s+=a; printf("%d\n",s); } 0257 Railway Ticket http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0257 改札機の動きを出力する問題。 解法 一番簡単な問題なのでそのまま実装します。 Ｃでコード短さ一位の人のコードはなるほど...
• AOJ221～230
  0221　FizzBuzz http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221 フィジーバズというゲームをシミュレーションして結果を報告する問題。 解法 高速化する方法もあるようですが、そのまま解いてみました。 ルールどおりに実装するだけです。 この問題の引っ掛けは一人になったあと、残った入力データを読むのを忘れないことだけです。 それさえ忘れなければ簡単な問題です。 #include stdio.h #include string #include list #include iostream void solve(int m,int n); int main() { int m,n; scanf("%d %d", m, n); while(m!=0 ||...
• プロジェクトオイラー問い1～10
  問い1 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 １０００未満で3の倍数又は５の倍数となる自然数の和を求める問題。 プログラムを書くまでもなく数式で一発です。 #include stdio.h int main(){ printf("%d",333*167*3+199*100*5-33*67*15); } 問い２ http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%202 フィボナッチ数列のうち４００万以下の偶数となる項の和を求める問題。 解法 フィボナッチ数列は最初奇数、奇数で始まり 奇数+奇数＝偶数 奇数+偶数＝奇数 ...
• オイラー11～20
  問い11 20*20の表の中から縦横斜め連続した４数を選びその積の最大値を探し出す問題。 動的計画法やメモ化を使おうと思ったら表の中に0が混じってるので0をうまく処理する方法を思いつかず全探索となった。 何か賢い方法あるのかな？ #include stdio.h #include math.h #include string.h int main(){ int map[20][20]={{ 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8}, {49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0}, {81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65}, {5...
• AOJ2151～2160
  2151　Brave Princess Revisited http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2151 限られた予算で護衛を雇いながら少しでも安全にお姫様を目的地まで送り届ける問題。 解法 私なりに考えた解法は以下の通りです。 予算の値が小さいことを利用して以下の手法で解きます。 memo[今いる街][残り予算]=この状態にいたったときの最小の刺客人数。 今いる街と残り予算の二つの組で一点と定義されるグラフに対し動的計画法を適用します。 後は少し高速化の魔法を振りかけてコード実行速度81位中2位タイの出来上がりです。 #include stdio.h #include string.h #include queue #include vector struct State...
• プロジェクトオイラー問８
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. 詳細はリンク先を参照してください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 まず１０００桁の数字を文字列リストとしてわたし、文字列リストを48引いて数字に戻します。 あとは文字列リストの先頭５桁の掛け算を試しながら大きいほうをTempAnsとして残して、先頭を一つずつ短くしながらsearchして、サイズ4になったら計算終了で値を返します。 max(A,B,A) -A B,!. max(_,B,B) -!. search([_,_,_,_],Ans,Ans) -!. search([A,B,C...
• プロジェクトオイラー関係
  プロジェクトオイラー問い1～10 プロジェクトオイラー問い11～20 プロジェクトオイラー問い21～30 プロジェクトオイラー問い31～40 プロジェクトオイラー問い41～50 プロジェクトオイラー問い51～60 プロジェクトオイラー問い61～70 プロジェクトオイラー問い71～80 プロジェクトオイラー問い81～90 プロジェクトオイラー問い91～100 プロジェクトオイラー問い101～110 プロジェクトオイラー問い111～120 プロジェクトオイラー問い121～130 雑記・日記2へ戻る。 掲載を後回しにしている問い 66,69,80
• 会津大学オンラインジャッジ復習
  数年前より私のホビーアルゴリズマーとしての腕が上がったのか下がったのか？ 会津大学オンラインジャッジの問題をもう一度復習することで自分の腕の変化を試してみようというページです。 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 ...
• AOJ11～20
  0011　Drawing Lots http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0011 lang=jp あみだくじを表現するデータが与えられるので、何番目のくじから始めたら何番目にたどり着くかを全て出力する問題です。 あみだくじの上端の紐を表す番号をつけた配列を用意し、これを上から読んで交換があればそれを入れ替えるだけで実装できます。 #include stdio.h #include algorithm int main(){ int d[32],w,h,i,l,R; scanf("%d %d", w, h); for(i=1;i =w;i++){ d[i]=i; } for(i=0;i h;i++){ scanf("%d,%d", l, R); std...
• AOJ51～60
  0051　Differential II http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0051 8 個の 0 から 9 までの数字を入力したとき、その 8 個の数字を並べ替えてできる、最大の整数と最小の整数の差を出力して終了するプログラムを作成してください。 数字を文字列とみてソートして手前と後ろから合計して差分をとるだけで計算できます。 #include stdio.h #include algorithm int main(){ int max,min,n,ten; char s[9]; scanf("%d", n); for(int i=0;i n;i++){ scanf("%s",s); std sort(s,s+8); ten=1; max=min...
• aoj2231～2240
  2233 Carrot Tour http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2233 兎が都市を回って人参をもらってくる問題。 解法 兎が前にいた都市今いる都市の組を点に見立ててグラフとして解きます。 人参の個数を一つずつインクリメントしながら人参ｎ個で前にいた都市a今いる都市ｂとして動的計画法で計算していけば答えが出ます。 もっと速度が出るかと思ったら意外と速度が出ませんでした。 #include stdio.h #include vector #include queue #include map #include math.h #include iostream struct rMove{ int oldCity,nowCity; long double len; }...
• AOJ551～560
  0551　Icicles http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0551 軒下に連なったつららがいつ全て折れるかを計算する問題です。 つららは隣のつららより長いつららのみ成長し、一定の長さになると折れます。 解法 この問題は あるつららが伸び始めるタイムが隣の先に延び始めたつららが折れるまで伸びないという点に注目点があります。 つまりあるつららが折れる時間は　隣のつららが折れた時間+L-初めの長さ。 という親子関係が全てのつららで成り立ちます。 これが判明すれば後はつららの折れるタイムを優先順位付きキューに入れれば実装は簡単です。 この発想法は実装の簡単さを優先しましたが、メモリを多めに使ってしまいます。 工夫すればメモリを節約できるようなので他の方のコードを参考にすることをお勧めします。...
• オイラープロジェクト231～240
  Problem 231 「二項係数の素因数分解」 † 二項係数 10C3 = 120 は 120 = 23 × 3 × 5 = 2 × 2 × 2 × 3 × 5, 2 + 2 + 2 + 3 + 5 = 14 を満たす. つまり, 10C3 を素因数分解した項の和は 14 となる. 20000000C15000000を素因数分解した項の和を求めよ. 解法 素因数分解の一意性を利用して解いてみました。 2000万！/(1500万!*500万！)で2000万と1500万と５００万を素因数から構成して差分を引けば答えが出ます。 手元のパソコンで30秒で答えが出ますが、私の場合整数論に関する授業を人生で一度も受けたことがないので解き方は基本全部自分で考えついた我流となっています。 おそらく効率が悪いコードでみる人からみたら失笑ものコードだと思います。 精進するしかあり...
• AOJ151～160
  0151　Grid http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0151 升目に01が与えられるので、その中で縦横斜めで最も1が長く連続している場所の長さを答えよという問題。 解法 memoに縦横斜めに分解して計算したら後は動的計画法で解けます。 memoに全部まとめたのでコードがコンパクトになった分少しわかりにくくなったかもしれません。 #include stdio.h #include string.h char row[258]; int memo[4][2][258];//0横,1上　2左斜め　３右斜め int dxs[]={-1,0,-1,1}; void search(int n){ int y,up,t,ans=0; memset(memo,0,4*2*258*4); for(int...
• aoj2221～2230
  2221　　KULASIS http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2221 成績表を不正に操作して最高の成績を求める問題。 この問題他の方は行列概念を使って解いてるらしい。 私は一段ずつ確定していく素朴な動的計画法でアセプト。 ある段までのスイッチの押しが決まったらそこより上の段は上の段の合計スコア以外計算に関係がない。 ことを利用してシンプルに解いたら、速度が出なかった。 考えたらどの段も1024通り全部が出てくる可能性があるから配列を使うべきでほとんどMapを使う意味がないと気付いたのはアセプトした後だったりしました。 #include stdio.h #include map #include algorithm struct myLine{ int num[5];//今操作中の...
• オイラープロジェクト51～60
  問い50 連続した素数の和として表される１００万以下の素数のうち和の長さが最長になる数を求めよという問題。 素数のみという条件が意外と手ごわい問題。 この条件がなければ簡単な尺取り虫アルゴリズムで片がつくんだけどな、、、 とりあえず力づくの全探索に近い手法で解いたけどかなり工夫の余地がありそうな問題。 #include stdio.h #include string.h #include vector const int up=1000001; bool so[up]; int memo[up]; std vector __int64 sosuu; void setSo(){ int i2; __int64 add=2; memset(so,true,sizeof(so)); sosuu.push_back(0); sosuu.push_back(2); for...
• 2011～2020
  2011　Gather the Maps! http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011 各人のスケジュールに合わせて宝の地図を手渡しで集めていく問題です。 この問題の解法は、ある日集まれる人全てを一か所に集めて、○○さんに全部渡した場合を全部を考えていきます。 集まったAさんに渡した場合、Bさんに渡した場合、、、の仮定を全部同時進行で計算していき最初に全部集まった人を発見したらそこで計算が終了となります。 誰がどの地図をどんな順番で持っていても最後に誰かに集めるなら途中経過でどんなふうに持っていても関係ないということが計算量を落とす秘訣です。 perm[最大人数]で各人のd日目の各人の地図の集まり具合を考慮します。 こうやってシンプルな解法を見つけると、昔の自分のコードがとても恥ずかしくなりますね...
• aoj2352挑戦中コード２
  aoj2352挑戦中コードの続き。 正答者のタイムにバラツキがない以上貪欲法で片が付いているのかな？ どう考えてもNP困難な問題に思えて高速化テクニックでごまかそうとしているのだが中々タイムが縮まらない。 std bitsetが遅すぎるだけなのだろうか？ stdio.h bitset map string std bitset 102 maskA; class bitSetSorter { public bool operator()( const std bitset 102 L, const std bitset 102 R ) const { //return L.to_string() R.to_string(); unsigned long Ls,Rs...
• AOJ1051～1060
  1052　Old Bridges http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1052 lang=jp 島を結ぶ吊り橋を渡って全部の財宝を回収しながら最初の島に戻ることができるかを判断する問題。 強度の低いつり橋から回収して試していくだけの一番簡単な部類の問題です。 この問題普通は0.0000秒のコード実行時間(早すぎて計測不可能)で解くのが普通なのですが一人だけ0.0032秒かつ大量のメモリーをつかって解いてる方がいました。 25！なわけはありませんしメモ化や動的計画法にしてはメモリを大量消費しています。 どのような手法で解いたのか逆に気になるところです。 #include stdio.h #include algorithm struct State{ int a,b; bool op...
• AOJ1151～1160
  aoj1156 Twirling Robot http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156 動的計画法で解ける簡単な問題。 普通に解くと少し遅いので優先順位付きキューとメモ化を使って気持ち高速化して解く。 平均的な速度とメモリ使用量で解けた。 方向転換の命令を使った場合使わなかった場合で後はキューが勝手にコスト順でソートしながら幅優先探索するだけ。 #include stdio.h #include queue struct point{ int x,y,a,cost; bool operator (const point p)const{ return cost p.cost; } }; bool calc(){ int map[31][31]; int arrowChange[5...
• 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の半分を...
• aoj2431～2440
  2435　Zero Division Checker 逆ポーランド記法で変数付きの式が与えられるので、変数が指定されたどの値の組み合わせになっても0除算エラーが起きないならcorrect、起きるならerrorを返せという問題。 解法 動的計画法で解きました。 式の結果はどこも0～255の範囲に定まるのでこの範囲で演算が行われるたびにあり得る演算結果の組を全部保管して次の演算へ進みます。 手元でテストデータを用意するのがめんどくさそうな問題だったので一発で通ったのはよかったよかった。 もし通らなかったらどれだけめんどくさいか考えたくもない問題だなこれ。 とりあえず通ったけどうーん本物のコンパイラはこれの１００倍大変なんだよなきっと？ #include stdio.h #include stack #include map #include string #...
• ニコニコ動画ユーザーは皆あわれ？
  ニコニコ動画ユーザーは皆哀れと近所の創価学会員が言っておりました。 http //www.nicovideo.jp/watch/sm12351431 こういう赤ちゃん動画をあげているお母さん（お父さん？）ニコニコユーザーも哀れなんでしょうか？ http //www.nicovideo.jp/watch/sm20697318 仲間と一緒にバイクで雪山登りにチャレンジ。 こういう楽しいことをしてるニコニコユーザーも哀れなんでしょうかね？ 閲覧数は伸びてないがこの手のリア充（日常生活が充実）してる動画をあげている人は結構いるようです。 皆哀れといわれても？とつきます。
• 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枚をその週の最初の仕事に使う. 使われなかった紙は全て元の封筒に収める. さて, 各仕事の際に, 主...
• AOJ261～270
  0261　Mayan Crucial Prediction http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0261 西暦をマヤ暦にマヤ暦を西暦に戻す問題。 解法 西暦をマヤ暦に戻すのは簡単でしたが、マヤ暦を西暦に戻すのは難しいですね。 手元のＧＣＣのtime_tが４バイトだったので値溢れが起きてtime.hで効率よくといきませんでした。 なので頭悪くひと月ごと引いていって計算しています。 ああ頭が悪い、、、 Ｃ＃使えば標準機能で西暦数万年とか扱えるのかな？ javascriptで解いても良かったかも。 #include stdio.h #include stdlib.h #include time.h #include iostream long long int GetDays...
• AOJ241～250
  0246　Bara-Bara Manju http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0246 解法 今のところ予測。 まず全部の数を数えて袋詰めにして残ったまんじゅうの数で動的計画法をおこなう。 1～9の重さのまんじゅうの個数をn１～ｎ9とする このときまず9の重さのまんじゅうを0～ｎ9まで使って10を作る組み合わせを全部検討し、これを作り終えたら残った9を全部廃棄する。 1～8の残ったまんじゅうの組み合わせが残りこの残り数を主キーとして動的計画法を立てる。 次は主キーを一つ一つ検証して8を0～最大数まで使うことにきめた場合で袋を作ッた場合を計算し同様に8を全部廃棄する。 これを１まで計算したらギリギリのメモリ使用量でクリアできるのではないか？ と思うがどうだろう？ 0241　Quat...
• オイラープロジェクト181～190
  問い181 問題文と２時間ほどにらめっこして到達した答え。 整数論の授業は人生で一度も受けたことがないのでまあ頑張ってアルゴリズムをひとりで考えてみた。 BWの組み合わせに番号を振って、黒白の石の数とセットを小さいほうからメモ化で積み上げていくコード。 memo[黒石の数][白石の数][この組でのBWのセットの最大値]であとはこれをメモ化を使いながら動的計画法でアセプト。 コード実行時間５秒。 まあまあだと思う。 必要のなさそうなループが一か所あるようなのでそこを削れれば今のコードより１０００倍くらい早くなるかも？ 調べて解くより自分で考えて解く方が楽しいというのはプログラマ（プロアマとわず）としては完全に欠点だな。 プログラマは自分で考えるより調べて応用できる方が重要だもの、俺はプロのプログラマにはなれない。 #include stdio.h #i...
• aoj2352挑戦中コード
  http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2352 リンク先問題を解こうとしたコードで問題が起こりました。 問題を解くコードをサーバに投稿すると。 サーバ側では投稿されたコードをＧＣＣでコンパイル。、 サーバ側で採点用データをきちんと処理できるか判断し、コードが採点用データをきちんと処理し問題をきちんと解いてるなら合格と返すサービスが提供されています。 一応私問題を解くコードを書き手元のＢＣＣでコンパイルするのに成功したのですが、サーバに送信すると下記のようなコンパイルエラーがかえってきて不正解となりました。 std bitsetをstd mapに使おうとした部分がエラーとなってるようです。 なぜこのようなエラーが出るのかエラーを出さないようにするにはコードをどう修正すれば良いかアドバイ...
• プロジェクトオイラー問い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に格納し、各素数それぞれについて*文字にチェンジした全パタ...
• aoj2501～2510
  2501　Grid Mori http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2501 土地購入を題材にした肩慣らし問題。 解法 競技プログラムのやり方に慣れるための導入問題なので特に考えることもなく解けます。 #include stdio.h int abs(int x,int y){ return x-y 0?x-y y-x; } int main(){ int n,a,b,c,d,ans=1000,t; scanf("%d %d %d %d %d", n, a, b, c, d); a--,b--,c--,d--; for(int i=1;i =n;i++){ t=abs(a%i,b%i)+abs(a/i,b/i)+abs(c%i,d%i)+abs(c/i,d/i); ...
• AOJ201～210
  0201　Wrought Gold Master http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0201 錬金術でアイテムの調合ができます。 複数のアイテムを調合して最も安く目的のアイテムを作ったときの値段を求める問題。 解法 アイテムを一つずつ確かめて、錬金で安く作れるならその値段に改定します。 改定した値段で更に調べなおして、値段が改定できなくなるまでループし続ければ答えがもとまります。 この方法でも十分速度はでますが、すべてのアイテムの最低値を求めており無駄があります。 もっと賢い方法として両手法という方法があるようです。 #include iostream #include map #include string #include vector using namespace...
• AOJ再挑戦51～55
  問51　Differential II http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0051 数字の文字列を並べ変えて最大の数と最小の数を作った時その差を計算する問題。 解法 並べ替えて手前と後ろから数字に直すだけです。 #include stdio.h #include algorithm int main(){ int n; char text[9]; scanf("%d", n); while(n--){ int max=0,min=0; scanf("%s",text); std sort(text,text+8); for(int i=0;i 8;i++) min=min*10+text[i]- 0 ; for(int i=7;i =0;i--)...
• AOJ2081～2090
  2086　! http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2086 ｎ進数で表記された数ｍがある。 ｍ！をｎ進数で表したとき末尾にある0の数を答えよ。 解法 unsigned long long intでｍを数字になおして、後はｎ進数で表したとき末尾が0になるのはｍ！のなかにｎの素因数が何個あるか数えれば答えが出ます。 #include stdio.h #include string.h #include iostream #include map void calcBase(int n,std map unsigned long long int,int base){ int ans=0; for(int i=2;i =n;i++){ int p=0; while(n%i==0...
• aoj2411～2420
  http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 リンク先問題はかなり難しい。 今のところ全く解法を思いついてない。 グラフとして見ると一千六百万本の辺をもつグラフみたいなものだな。 どう格闘しても計算量が落ちないのでとりあえず重さが均等に二分割になるように切っていけば近似解を出せると考えて試作品コードを書いたところで力尽きた。 どうやって解こうかな？ とりあえず切る位置を表すmemo[左側][右側]の4000*4000の配列を用意してい動的計画法で解けばいいのか？ 端から攻めていくかな？ とにかくこの手の問題は当たり前に言えることを探し当てて、最後は貪欲法に持って行ければ一番いいパタンだけど？ 一つ考えた。 右と左に切断した時、右の個数*右の重さの総計+左の個数*左の重さの総計が最...
• オイラープロジェクト151～160
  問い151 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20151 封筒の中身の期待値を求める問題。 シンプルに動的計画法で期待値を求めるだけです。 丁寧ですがコードサイズが膨らみました。 この問題簡単すぎますが他の人のコードを読んでると楽しい問題です。 問題をどんな構造で解くか。 色々なとらえ方があって楽しいですね。 #include stdio.h #include map #include string.h #include iostream #include time.h struct E{ __int64 paper[6]; bool operator (const E e)const{ for(int i=1;i =5;i++){ if(p...
• @wiki全体から「2351～2360」で調べる

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