c21coterie @ ウィキ

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

• 会津大学オンラインジャッジコード記録
  ...071～1080 AOJ1081～1090 AOJ1091～1100 AOJ1100～1109 AOJ1110～1120 AOJ1121～1130 AOJ1131～1140 AOJ1141～1150 AOJ1151～1160 AOJ1161～1170 1170～1180 AOJ1200～1210 1221～1230 AOJ1231～1240 AOJ1241～1250 AOJ1300～1310 AOJ1500～1509 AOJ1510～1519 AOJ2000～2010 2011～2020 AOJ2021～2030 AOJ2031～2040 AOJ2071～2080 AOJ2081～2090 2100～2110 AOJ2111～2120 AOJ2151～2160 AOJ2161～2170 2181～2190 AOJ2191～22...
• AOJ1081～1090
  1082　http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082 特殊なルールで変換される携帯電話の変換結果候補の組み合わせ数を求める問題。 解法 トライアンドエラーで解いた問題。 連続した数字の長さがｎ文字だとして、ｎ-1文字目までの組み合わせからｎ文字目の組み合わせをボトムアップで求めることが出来ます。 n-1文字の末尾がイになる組み合わせだったら次はウになる組み合わせかアになる組み合わせにしか分岐しません。 memo[n][1](1は1文字のア)かmemo[n][3]に足されます。 ここまでは当たり前にできたのですが。 なんでn%5==1とn%3==1の時だけ１を足さないといけないのか理由が分かりません。 直感的にn%5==1になるとき+１が必要なのではと理由もわからず思いつき試してみたらうま...
• AOJ1091～1100
  問い1092　Make KND So Fat http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1092 甘味どころで体重が増えるようにお菓子を買う問題。 解法 範囲が狭いので何も考えない動的計画法で十分解けます。 #include stdio.h #include vector void calc(int s,int d,int m){ int memo[310]={0},k,w,p;; std vector int ws[101],ps[101]; for(int i=0;i s;i++){ scanf("%d", k); for(int j=0;j k;j++){ scanf("%d %d", w, p); ws[i].push_back(w); ps...
• AOJ1071～1080
  1072 Rearranging Seats http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1072 升目に並んだ座席で特殊なルールに従った席替えが出来るか出来ないかを答える問題。 理屈はわからないが直感的に縦*横が奇数だと席替え不可能な気がしたので直観に従ってコードを書いたらアセプト。 何か15パズルで答えに行きつける場合といきつけない場合と同じ理屈があるような気がする？ #include stdio.h int main(){ int r,c; while(1){ scanf("%d %d", r, c); if(r+c==0) break; printf("%s\n",(r*c) 1==1?"no" "yes"); } ...
• AOJ101～110
  101 Aizu PR http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0101 lang=jp 文章に記述ミスがあり、Hoshinaと書くところをHoshinoと書いてしまいました。 文章が与えられるのでミスを全て訂正した文章を出力してくださいという問題。 解法 string型に関する基本機能を理解しているか問われるだけの問題です。 #include iostream #include string int main(){ std string s; int n; char c; unsigned int pos; std cin n; std getline(std cin,s); for(int i=0;i n;i++){ std getline(std cin,s); pos=0; ...
• AOJ1～10
  0001 List of Top 3 Hills http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0001 lang=jp 山の高さをあらわす整数が10個与えられるので、その中から上位３つの山の高さを表示せよ。 基本機能であるソートを理解しているかどうかが問われる問題です。 基本機能を理解しているならそのまま実装しましょう。 #include stdio.h #include algorithm int main(){ int m[10],i; for(i=0;i 10;i++){scanf("%d", m[i]);} std sort(m,m+10); for(int i=9;i 6;i--)printf("%d\n",m[i]); } 0002 Di...
• AOJ1031～1040
  aoj1033　Kuru-Kuru Robot http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1033 この問題はそれほど難しくはないが練習問題としてはかなりめんどくさい問題でした。 まず線分が同一直線上にあり共有部分を持つ場合、コードを単純にするために線分を統合していく必要があります。 次に、線分の交点を求めグラフに翻訳します。 後はゴールまで優先順位付きキューと幅優先探索を組み合わせれば計算量的に言って楽です。 注意点はグラフの探索中ロボは前に移動した方向と今いるポイントを覚えていく必要がある点くらいです。 他の回答者の方も同じくらいのコードサイズなので私の答えは平均的なものです。 #include stdio.h #include vector #include set #include ...
• AOJ181～190
  0181 Persistence http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181 ｎ巻そろった本を1巻から順にｍ段の本棚に右下から詰めて入れます。 格段の本の幅が小さくなるようないれ方をした時、格段の本の幅の最大の幅がどれくらいとなるか答えよ。 本を詰める順番は1巻から順にし順番を違えないとする。 解法 i段目までｍ冊目までの本を入れた時、どのような入れ方をしたにせよ、そこまでの本の幅が最小となる入れ方のみを残します。 この考え方で動的計画法で解きます。 #include stdio.h #include algorithm void setData(int m,int n){ int memo[21][102],w=0; for(int i=0;i 21;i++){ ...
• AOJ1041～1050
  1045　Split Up! http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045 戦闘力が与えられるので戦闘力の合計が均等になるように２チームにわける問題。 普通に解くだけなら全探索にちょっと枝刈で簡単に解いたけど、高速化してみた。 saikiAとsaikiBと半分半分で計算すれば2^20の計算量が2*2＾10の計算量に落ちる。 #include stdio.h #include set int sum,herf,n,datas[21],t,ans,nHerf; std set int herfSum; std set int iterator it; void saikiB(int deep,int now){ if(deep n){ saikiB(deep+1,now+datas[...
• AOJ1061～1070
  1062 It s our delight!! http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1062 飲食店の時間帯別接客成績を計算する問題。 何故か8分を5分と読み間違える謎のミスをしてしまう。 簡単な問題なので丁寧に書くだけです。 #include stdio.h void calc(int n){ double okLDM[3]={0,0,0},allLDM[3]={0,0,0}; for(int i=0;i n;i++){ int hh,mm,mm2; char c; scanf("%d%c%d %d", hh, c, mm, mm2); int add; if(mm =mm2){ add=(mm2-mm) =8; }else{ add=(mm2+60-mm) =8; } if...
• AOJ1011～1020
  1011 Finding the Largest Carbon Compound Given Its Long http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1011 CとHで出来た炭素鎖からHを省き、できた鎖のCの両端を持った時両端が最も長くなる距離をｎとする。 長さがｎを超えないでCを最大までくっつけた時数字上何個までCを接続できるか答えよという問題。 解法 この問題は英語読解が出来なかったためYahoo知恵袋で問題の題意を質問して解きました。 題意が分かれば対称性を利用して解ける簡単な問題です。 #include stdio.h void calc(int perm[31]){ perm[0]=0; perm[1]=1; perm[2]=2; perm[3]=5; for(int i=4;...
• 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...
• AOJ1021～1030
  1021 Emacs-like Editor http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1021 Emacsエディタの簡易版をシミュレートする問題。 解法 テキストエディタって結構設計が大変なのですね。 簡単な問題とみて甘く見てました。 改行だけしかない空行、先頭行、末尾行などの取り扱いが意外と大変な問題でした。 一晩色々なパタンを考えてから提出、ポカミスを2度修正して合格となりました。 入力データの文章の最終行は\nがないようです。 後答えの最終行に\nをつけないと不正解になります。 #include stdio.h #include string #include iostream #define ss std string //グローバル変数まとめ unsigned i...
• 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...
• 会津大学オンラインジャッジ復習
  数年前より私のホビーアルゴリズマーとしての腕が上がったのか下がったのか？ 会津大学オンラインジャッジの問題をもう一度復習することで自分の腕の変化を試してみようというページです。 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 ...
• aoj1033挑戦中
  aoj1033　クルクルロボット http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1033 この問題はそれほど難しくはないが練習問題としてはかなりめんどくさい。 まず線分が平行で共有点を持つ場合、コードを単純にするために線分を統合していく。 次に、線分の交点を求めグラフに翻訳する。 後はゴールまで探索すれば計算量的に言って楽です。 ロボは前に移動した向きと今いるポイントを覚えていく必要がある点くらいですね。 #include stdio.h #include vector #include set #include math.h #include algorithm #include map #include queue struct P{ double x,y; bool operat...
• AOJ581～590
  0582 Triangle Types http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0582 三角形のデータが与えられるのでそれが三角形をなすなら、鈍角三角形か直角か鋭角か判断してカウントし最後にその数を出力せよ。 解法 中学校で習った三角形の公式通りに判定するだけです。 #include stdio.h #include algorithm int main(){ int as[3],ans[3]={0}; while(1){ scanf("%d %d %d", as[0], as[1], as[2]); std sort(as,as+3); if(as[0]+as[1] =as[2])break; int len =as[0]*as[0]+as[1]*as[1]; i...
• AOJ1000～1010
  1001 Binary Tree Intersection And Union http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001 バイナリツリーを表す２つの符号からバイナリツリーを作り、両方のツリーの共通集合か和集合を計算して符号で返すという問題。 解法。 この問題は正答者数が多いので情報系の正式なカリキュラムの一部としてこの問題が出てる可能性が高そうです。 学がないので私は四苦八苦でした。 調べたらたぶん正式な方法が出てくるとは思うのですが一つ腕試しと思い自力で暗中模索してみました。 手探りで作った結果木構造を作る部分に無駄な処理がありスパゲッティ化しています。 いつか綺麗になおすかもしれません。 木構造が実は苦手なのを差し引いても、スパゲッティ化で自分の実力を思い知った問題でした。 ...
• AOJ121～130
  0121　Seven Puzzle http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121 7パズルの盤面が与えられます。 盤面を完成させるには最短で何手必要かを答える問題。 解法 最初に7パズルの全ての組み合わせを求めて何手で到達できるかを計算して求めます。 コードでは高速化のため7パズルの並びを右上から精査して並べたものを数字列とみなして管理します。 数字の並びに0の位置を末尾に付け加えて管理します。 #include stdio.h #include queue #include map int mod[]={100000000,10000000,1000000,100000,10000,1000,100,10}; int dxs[]={1,4,-1,-4}; int main()...
• AOJ91～100
  0091 Blur http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0091 計算量を抑える工夫を加えようとするとかなりめんどくさそうなりそうな気がするので後日にまわす。 0092　Square Searching http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092 .と*で出来た升目のデータが与えられます。 盤面の中らから、.の部分だけを使って出来る最大の長方形を見つけよという問題です。 解法 まず前の行から次の行へと何段.が連続してるか計算します。 後は、そのデータをもとに横方向に移動しながら正方形が作れるかをチェックするだけです。 今まで見つかった最大の正方形より小さい正方形はチェックしないようにしています。 悪く...
• AOJ81～90
  0081　A Symmetric Point http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081 平面上の直線Ｐ１Ｐ２と点Ｐ３が与えられるので、Ｐ１Ｐ２に対するＰ３の線対称な点を表示せよという問題。 教科書通りに線対称行列を書いてみましたがこの問題は色々な解法があると思います。 #include stdio.h #include math.h int main(){ double xs[3],ys[3],vx,vy,x,y,len,sin1,cos1,sin2,cos2; while(scanf("%lf,%lf,%lf,%lf,%lf,%lf", xs[0], ys[0], xs[1], ys[1], xs[2], ys[2])!=EOF){ vx=xs[1]-xs[0]; vy...
• AOJ1100～1109
  1105　Unable Count http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1105 n a bの３数が与えられるのでnまでの自然数をax+by(x,yは0以上の自然数)(a,bは多分1以上の自然数)の形であらわしたとき、この式で表せない数の個数を求めよという問題。 妙に言葉遊びで遊んでいる問題文は出題者の趣味？ 解法 とりあえずナップザック問題の応用で解いてみましたがメモリを馬鹿みたいに使ってます。 #include stdio.h #include iostream #include string.h int memo[1000*1000+1]; int main(){ int n,a,b; while(1){ int ans=0; std cin n a b; if(n==...
• 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...
• AOJ131～140
  0131　Doctor s Strange Particles http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0131 ライツアウトと同じルールで盤面が与えられるので、全ての光を消す手順を表示せよという問題。 解法 ライツアウトは最上段の組み合わせを試したら後の段は自動的に決まるので最上段だけ全パタンを試します。 最下段に到達した時光ってるマスが残ってなければそれが正解です。 #include stdio.h int map[10][10]; int ans[10][10]; int dxs[]={0,1,0,-1,0}; int dys[]={0,0,1,0,-1}; bool goal; void push(int x,int y){ int nx,ny; for(int i=0;i 5;i++)...
• AOJをPrologで挑戦
  aojの0000～0003までをPrologで書いてみた。 ＡＯＪはPrologに対応しておらず答え合わせはできないのでコードの正確性は不明。 入出力も適当に書いてある。 基本的な考え方だけあってれば自分的に正解みたいな感じとなっている。 main -between(1,9,A), between(1,9,B), C is A * B, format( ~d*~d=~d~n ,[A,B,C]),fail. siwake([],M,[],[]) -!. siwake([X|Rest],M,[X|Downs],Ups) -M X,siwake(Rest,M,Downs,Ups). siwake([X|Rest],M,Downs,[X|Ups]) -X= M,siwake(Rest,M,Downs,Ups). q_sort([],[]) -!. q_sort([M|Rest],...
• 雑記・日記2
  ここはこのサイトの管理人こと堀江伸一さんの個人的な雑記、日記　勉強記録を雑多に集めたページです。 当サイトの小学生レベルの創作物に関する言い訳 勉強記録一覧 リンク　→会津大学オンラインジャッジコード記録 会津大学オンラインジャッジの解答コードでこちらへ来た方はリンク先へどうぞ、私のコードが掲載されています。 一応少数の問題でコード実行速度一位を取ったコードもあるのですこしは参考になるかもしれません(ご近所さんのある方はＡＯＪでコード実行速度一位とるなんて馬鹿でもできる笑いもの　ぷぷぷ　とか言ってました。世間的なＡＯＪの評価ってそんなものかもしれません)。 会津大学オンラインジャッジ復習 ここより以下は本当に個人的な雑記ですので気にしないでください。 もしも結婚できたら子供に言ってみたいこと ネットで好みのイラスト収集 新ギレン...
• aoj10000全部
  10000番台は競技プログラムの問題を初めて解く方のためのチュートリアル問題しかありません。 中学生プログラマでも解ける問題だけで構成されているのが特徴です。 10000　Hello World http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10000 ヘローワールドを出力する問題。 #include stdio.h int main(){ printf("Hello World\n"); } 10001 X Cubic http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=10001 x^3を表示する問題。 #include stdio.h int main(){ int x; scanf("%d&...
• AOJ141～150
  0141　Spiral Pattern http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0141 指定されたサイズの升目にスパイラルパタンを画くという問題。 升目で描きます。 解法 この問題は、曲がるまでに進むマス数を数列化することができれば非常に簡単になるそうです。 私の場合は盤面のパタンを順番に生成するという方法をとりました。 盤面を生成する方法は非常に多くの人がはまるよくない方法だそうです。 #include stdio.h void solve(int); char map[101][101]; int dx[4]={0,1,0,-1}; int dy[4]={-1,0,1,0}; int move; int main() { int d,n; scanf("%d"...
• オイラー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...
• 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...
• AOJ161～170
  0161　Sport Meet http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0161 スポーツ大会の合計タイムから1位のチーム2位のチーム、びりより一つ上のチームを表示せよという問題。 簡単な問題です。 解法 100万チームのデータを毎回確保するのは処理速度的にどうかと思うので最初に確保しておくくらいです。 後はデータを読み込んでソートするだけで答えが出ます。 #include stdio.h #include set #include algorithm struct team{ int no,time; bool operator (const team t)const { return time t.time; } }; team teams[1000002]; void setD...
• AOJ171～180
  0171　Dice Puzzle http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171 サイコロを８個組み合わせて、2*2*2の大きなさいころを作るという問題。 サイコロの面にはアルファベットが書かれており、面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字である必要があります。 yとYやaとＡのような組み合わせのみ面を組み合わせることができます。 与えられたサイの情報から大きなさいころを組み立てられるか判別してください。 解法 良い解法思いつきませんでした。 さいを回転する関数を作り、さいころを回しては大きなさいころにサイを追加し深さ優先探索で全探索します。 探索中check関数で今まで組み立てた部分が条件を満たすか調べて枝がりをします。 もっと賢い解法もあると思う...
• AOJ1500～1509
  問い1500　ID http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1500 条件を満たすＩＤが幾通りあるか答える問題。 解法 *の数も少なくメモ化で一発です。 #include stdio.h #include string.h char id[100001]; int memo[100001][10]; int main(){ int n,m,a; int base2[10]={0,2,4,6,8,1,3,5,7,9}; bool oks[10]={0,0,0,0,0,0,0,0,0,0}; scanf("%d %s", n,id); scanf("%d", m); for(int i=0;i m;i++){ scanf("%d", ...
• AOJ1121～1130
  1127　Building a Space Station http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1127 宇宙空間に浮かんでいるｎ個(１００個)以内の球状のユニットを最小の長さの通路でつなぐ問題。 ユニットのデータはx,y,z,rで与えらる座標と半径である。 球同士が共通部分を持つ場合長さ0の辺でつなぐことが出来る。 長さをグラフに翻訳したら後はプリム法で解くだけです。 昔プリム法を知らずに自力で同じ手法を考案して(車輪の再発明)して似た問題を解いたことがあるので感慨深い問題です。 #include stdio.h #include math.h #include algorithm #include string.h #include queue struct E{ int n...
• AOJ1131～1140
  1132　Circle and Points http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1132 平面上の点の座標が与えられるので一つの半径１の円で囲むことが出来る点の最大数を答える問題。 解法 回転行列の概念を使って交点を求めます。 後は交点を中心に円を描いたとき何個の点を囲めるかを確かめるだけです。 どうしようＡＯＪの問題を５７３問解いたけど、残りの問題どれをみても解法を思いつかないのばっかりだ、、、 #include stdio.h #include math.h #include vector void calc(double x1,double y1,double x2,double y2,std vector double pxs,std vector double...
• AOJ1231～1240
  1240 Unreliable Message http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1240 文字列を受け取ると一定のルールで変換して次の人に渡す人たちが6人いる。 各人が文字列を受け取った順番と変換後の文字列が渡されるので元の文字列を計算せよ。 簡単な問題です。 各人の変換ルールの逆変換を作って変換経路の文字列を逆にたどるだけで解けます。 こういう簡単な問題でちまちま正答数を稼ぐのは小銭を稼ぐような楽しさがあるかも。 #include stdio.h #include string #include iostream #include algorithm std string J(std string str){ int len=str.length(); if(len...
• AOJ1161～1170
  問い1162　Discrete Speed http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1162 摩擦のない国でスタートの都市からゴールの都市まで到達する最短時間を答える問題。 解法 前にいた都市、今いる都市、今のスピードの3つの状態であらわされる点と、スピードを+1～-1まで加速して次の都市へ行く行為を線とみなして、グラフの問題として見ました。 とりえあずダイクストラ法でといてみましたがメモリ使用量は多いし、速度は出てないしであまりうまい解法でなかったようです。 賢い解法は貪欲法かもしれません。 #include stdio.h #include queue #include string.h struct Car{ double time,speed; int ol...
• aoj2281～2290
  2281　Swap Cipher http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2281 暗号化された文書を復元する問題。 解法 一番簡単な部類の問題なので何も考えずに実装します。 一度全部読んで逆操作で復元しましたが、手前からリニアに読みこんで処理する方法でコンパクトなアルゴリズムを考えつきませんでした。 #include stdio.h #include algorithm void calc(int n){ char text[110]; int as[101],bs[101]; scanf("%s",text); for(int i=0;i n;i++)scanf("%d %d", as[i], bs[i]); for(int i=n-1;i =...
• AOJ1241～1250
  1244　Molecular Formula http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1244 簡略化された原子の重さと化学式が与えられるので化学式の重さの総計を答える問題。 再帰下降構文解析で解きます。 英文字がきたら、2文字読めるか1文字読めるか試します。 その次が数字ならその数字分重さを掛けて、数字でないなら重さを単純に足します。 開きカッコがきたら関数を読んでネスト、閉じかっこか文字列の終わりに到達したら関数はリターンします。 #include stdio.h #include map #include string #include iostream std map std string,int memo; int p; std string A,text;//原子...
• AOJ1141～1150
  1145　The Genome Database of All Space Life http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1145 lang=jp 圧縮された宇宙生物DNAデータを展開しi文字目にあるDNA記号を返す問題。 まずは１００万文字と少ない文字数なので再帰下降構文解析をやって愚直に求めるコードを書いてみた。 高速に動くコードをテストするための自前採点用データ製作機としての役割としてつくっただけでコードは単なる踏み台。 それを改良してと考えたらほんの6行コードを足しただけで高速化できた。 数行つけたしただけで高速化するなんてプログラムってちょっと面白い。 #include stdio.h int p,i,count; char s[101]; bool last; void s...
• 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...
• プロジェクトオイラー問い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 フィボナッチ数列のうち４００万以下の偶数となる項の和を求める問題。 解法 フィボナッチ数列は最初奇数、奇数で始まり 奇数+奇数＝偶数 奇数+偶数＝奇数 ...
• AOJ再挑戦101～105
  問101　Aizu PR http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0101 文字列の置き換えを実装する問題。 解法 一行丸ごと読み込んであとはstrstrで探して文字を置き換えるだけです。 文字数が同じだからこそできる手抜きテクニックです。 #include stdio.h #include string.h int main(){ int n; char c; scanf("%d%c", n, c); while(n--){ char text[1001],*ptr; scanf("%[^\n]%c",text, c); for(ptr=strstr(text,"Hoshino");ptr!=NULL;ptr=strstr(pt...
• AOJ再挑戦96～100
  問96　Sum of 4 Integers II http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0096 a+b+c+d=n nは4000以下の自然数 a,b,c,dは0～1000までの数で数ｎを作る方法は何通りあるか？ 解法 昔の自分のほうがかしこいコードを書いてたのでこちらを掲載。 今書いてみたほうは、計算量800万回。 それに対してこちらの計算量は１万回。 昔のほうが賢いコード書いてるな私。 aで作れる数は0～1000までが一通り。 それにｂを足すと1000～2000までの数が作れてその組み合わせをab[n]とする。 a+b+c=n3としてn3はn3-1000～n3までのab[n3-1000～n3]までの和となる。 ｄを足しても同様。 #include stdio.h #inc...
• AOJ再挑戦81～85
  問81　A Symmetric Point http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0081 線対称な点を計算せよという問題。 解法 数学の歴史に変換や特定の条件を満たす点を求めるための計算式のリストをひたすら作るというものがありました。 線対称な点を求めるというのもその一つで行列演算にしたがえばいいだけです。 まあ線対称くらいなら行列演算してもいいけれど。 点によっては（19世紀の幾何の話を探るとあるのだけれど）ｘ座標一つを求める式が30行くらいになる問題とかざら。 それくらいになると公式をプログラムに翻訳するだけでもバグが入りそうで怖い。 #include stdio.h int main(){ double x1,y1,x2,y2,x3,y3,dx2,dy2,dx3,dy3,ab...
• プロジェクトオイラー関係
  プロジェクトオイラー問い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
• AOJ1110～1120
  1111　Cyber Guardian http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1111 パケットフィルタリングの実装をこれ以上できないほど簡素にした問題。 ｎ個のパケットルールとｍ個の通信許可の質問が与えられる。 パケットルールはpermit(通信ＯＫ)なアドレスと通信拒否すべきアドレス(deny)でＦｒｏｍからＴｏへ送信される場合をＯＫか拒否をあらわす。 後から提示されたルールほど優先順位が高いとして検査し、パケットルールで通信Ｏｋなアドレスト判明したら通信可としてそれを表示。 通信不可能なアドレスであることが判明したらそれは表示しない。 どのルールにも引っかからないアドレスは通信拒否とせよ。 通信可の通信データの数を表示しそのあと通信内容を到着順に表示せよ。 解法 この問題英語の読解...
• AOJ1510～1519
  1510　Independent Research http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1510 ３次元セルオートマトンの初期データと変化ルールが与えられるので一定ターン経過後の状態を出力せよという問題。 解法 一番のりで解いた問題。 周囲２７マスの状態を関数で取得すれば計算が簡単になります。 サイズが小さい問題なので何も考えることなく素朴に解きました。 大きなサイズになるとビット演算とか色々使うと思います。 #include stdio.h #include string.h int map[8][8][8]; int cellCount(int x,int y,int z){ int count=0; for(int i=-1;i =1;i++){ for(int j=-1...
• aoj2481～2490
  2489　Palindromic Number http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2489 与えれた整数ｎに最も近い回文数を答えよという問題。 複数ある場合低い方を答えとせよ。 解法 簡単な問題なので全部生成してstd setから探すだけです。 #include stdio.h #include set int main(){ std set int memo; std set int iterator it; memo.insert(0); memo.insert(10001); for(int i=1;i =9;i++){ memo.insert(i); memo.insert(i*10+i); for(int j=0;j =9;j++){ memo.insert(i...
• AOJ191～200
  0191　Baby Tree http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191 植物に色々な種類の肥料をやって、一番成長する肥料のやり方を探しその時できる植物のサイズをこたえる問題。 解法 動的計画法で各ターンごとに計算していくだけです。 #include stdio.h #include string.h double fertilizer[102][102]; void calc(int n,int m){ for(int i=0;i n;i++){ for(int j=0;j n;j++){ scanf("%lf", fertilizer[i][j]); } } double memo[2][101]; for(int i=0;i n;i++){ memo[0][i...
• @wiki全体から「AOJ1081～1090」で調べる

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