c21coterie @ ウィキ

c21coterie @ ウィキ内検索 / 「aoj1033挑戦中」で検索した結果

• 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...
• 会津大学オンラインジャッジコード記録
  ...52挑戦中コード aoj1033挑戦中 未定 210 迷路の問題 雑記・日記2
• 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 ...
• 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],...
• 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...
• 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...
• 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...
• 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&...
• 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; ...
• AOJ1000～1010
  1001 Binary Tree Intersection And Union http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1001 バイナリツリーを表す２つの符号からバイナリツリーを作り、両方のツリーの共通集合か和集合を計算して符号で返すという問題。 解法。 この問題は正答者数が多いので情報系の正式なカリキュラムの一部としてこの問題が出てる可能性が高そうです。 学がないので私は四苦八苦でした。 調べたらたぶん正式な方法が出てくるとは思うのですが一つ腕試しと思い自力で暗中模索してみました。 手探りで作った結果木構造を作る部分に無駄な処理がありスパゲッティ化しています。 いつか綺麗になおすかもしれません。 木構造が実は苦手なのを差し引いても、スパゲッティ化で自分の実力を思い知った問題でした。 ...
• 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[...
• 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()...
• 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...
• 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...
• 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になるとき+１が必要なのではと理由もわからず思いつき試してみたらうま...
• 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;...
• 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"); } ...
• aoj2352挑戦中コード
  http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2352 リンク先問題を解こうとしたコードで問題が起こりました。 問題を解くコードをサーバに投稿すると。 サーバ側では投稿されたコードをＧＣＣでコンパイル。、 サーバ側で採点用データをきちんと処理できるか判断し、コードが採点用データをきちんと処理し問題をきちんと解いてるなら合格と返すサービスが提供されています。 一応私問題を解くコードを書き手元のＢＣＣでコンパイルするのに成功したのですが、サーバに送信すると下記のようなコンパイルエラーがかえってきて不正解となりました。 std bitsetをstd mapに使おうとした部分がエラーとなってるようです。 なぜこのようなエラーが出るのかエラーを出さないようにするにはコードをどう修正すれば良いかアドバイ...
• 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", ...
• poj適当
  北京大学ではプログラマ向け練習問題を多数掲載しています。 そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。 このサイトの問題を解いた記録を掲載しています。 プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。 とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。 poj2887 100万文字の文字列にさらに別の文字列を2000回以下insertし2000回以下ｎ文字目の文字を返す問題 文字の枝にどんどん文字列の枝を接続していくイメージで攻略。 考え方としては子供のころ遊んだブロック遊びと大差ないなあ。 賢ければ中学生でも解けるレベルか。 一度目は何も考えずstd strinの基本機能だけ...
• 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...
• 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"...
• 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++)...
• 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++){ ...
• 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==...
• aoj2491～2500
  堀江伸一 〒675-0033-79-16 aoj2491 sanpo http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2491 ねこのそらの散歩を題材にした問題。 解法 正答者数も少なく難しい問題です。 普通に探索しては小さなグラフでも間に合いません。 道を通った回数、今いる地点、残り時間の３種類を基準に点をプロットし、グラフとして素朴な動的計画法で解こうととすると点の数が膨大になります。 この問題はすこし変わった方法で解けそうです。 1番にタイムとそのタイムで得られる最大の価値の対応表を持った猫を待機させます。 その猫からどれかの道にむけて対応表を持たせて架空の探索猫を１匹先行させます。 探索猫は枝先でないならついた広場で待機し親猫となり、さらに子となる探索猫を一匹出します。 探索...
• AOJ再挑戦66～70
  会津大学オンラインジャッジを解くページ。 問66　Tic Tac Toe http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0066 チックタックトゥの勝敗判定をする問題。 自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。 この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。 短さ１位の人のコードは想像もつかないがAOJの外には１位の人より上がいるのがネットの世界。 すごいと思う。 AOJばっかりに閉じこもってないで少しは外に出ないとダメか。 コードの短さ6/542位うーん平凡。 コード解説 rはマトリックスです。 ｂに盤面データが保存されています、マス目に番号を付けると。 012 345 678 となったらチェック...
• 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...
• 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...
• 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...
• AOJ1110～1120
  1111　Cyber Guardian http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1111 パケットフィルタリングの実装をこれ以上できないほど簡素にした問題。 ｎ個のパケットルールとｍ個の通信許可の質問が与えられる。 パケットルールはpermit(通信ＯＫ)なアドレスと通信拒否すべきアドレス(deny)でＦｒｏｍからＴｏへ送信される場合をＯＫか拒否をあらわす。 後から提示されたルールほど優先順位が高いとして検査し、パケットルールで通信Ｏｋなアドレスト判明したら通信可としてそれを表示。 通信不可能なアドレスであることが判明したらそれは表示しない。 どのルールにも引っかからないアドレスは通信拒否とせよ。 通信可の通信データの数を表示しそのあと通信内容を到着順に表示せよ。 解法 この問題英語の読解...
• AOJ171～180
  0171　Dice Puzzle http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0171 サイコロを８個組み合わせて、2*2*2の大きなさいころを作るという問題。 サイコロの面にはアルファベットが書かれており、面同士を合わせる時サイの目に描かれている文字が同じアルファベット大文字と小文字である必要があります。 yとYやaとＡのような組み合わせのみ面を組み合わせることができます。 与えられたサイの情報から大きなさいころを組み立てられるか判別してください。 解法 良い解法思いつきませんでした。 さいを回転する関数を作り、さいころを回しては大きなさいころにサイを追加し深さ優先探索で全探索します。 探索中check関数で今まで組み立てた部分が条件を満たすか調べて枝がりをします。 もっと賢い解法もあると思う...
• 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...
• 会津大学オンラインジャッジ復習
  数年前より私のホビーアルゴリズマーとしての腕が上がったのか下がったのか？ 会津大学オンラインジャッジの問題をもう一度復習することで自分の腕の変化を試してみようというページです。 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 ...
• 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...
• AOJ1300～1310
  1304 英語が苦手な人には厳しい問題。 ｎ*ｎマスのマップが与えられる。 ＃がウイルス、.がウイルスの発生してないマス、@がウイルス除去車を表す。 ターン制でセルオートマトンで繁殖するウイルスがあり、それを除去するための除去車がマス目を移動する。 最小の移動手数でウイルスを削除するときのターン数を答えよ。 ルール ルールＡ　除去車はターン初めに移動すること、今いるマスにとどまることはできない、隣接８方向に移動できウイルスのいないマスにしか移動できない。 ルールＢ　移動後除去車のいるマスは保護機能によりウイルスは侵入できないが、他のセルを計算するときは除去車はウイルスとして扱う ルールＣ　ウイルスは、周囲8マス中３マスがウイルスならばそのマスで新たに発生する。 ルールＤ　ウイルスがいきているマスの周囲２マスにウイルスがいるならウイルスはそのマスに生存し続ける。 ...
• AOJ1200～1210
  1202　Mobile Phone Coverage http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1202 簡単な問題。 左端から少しずつ走査して足しこんでいけば解ける。 範囲境界線上のｘ座標を全て網羅しｙ軸と平行に画面を切り取って後は少しずつ面積を足していくだけである。 もう少し賢い方法もある気はするが自前で思いついた方法を優先。 解答番号をprintfし忘れて一度不正解を食らったのはここだけの秘密。 私の場合問題はきちんと解けてるが最後のprintfで書き忘れで不正解というパタンが多い。 多分問題が解けて油断してるんだと思う。 #include stdio.h #include vector #include algorithm #include set int IN=1; int ...
• aoj2471～2480
  aoj2476 Strange Currency System http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2476 与えられた通貨を組み合わせて色々な金額を作るとき、作れない最小金額を答えよ。 解法 ２４００番台の問題とは思えないほど簡単な問題なのに正答者数が少ない問題です。 問題が英文であること２４００番台は難しいというイメージがあっておそらく多くの人がこの問題が簡単であると気付いてないのだと思います。 通貨を小さい順にソートして小さい方から足し合わせていって作れない数字が判明したらそれが答えです。 #include stdio.h #include vector #include algorithm #include iostream int main(){ int n; scan...
• 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...
• 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...
• PKJ適当
  北京大学ではプログラマ向け練習問題を多数掲載しています。 そのサイト名は北京大学オンラインジャッジという名前でコードの自動採点までしてくれるすぐれもの。 このサイトの問題を解いた記録を掲載しています。 プログラマ向け問題は中学生でもとける問題から、理数系東大生でプログラムに自信がある人でも悩む難問、数学的に未解決な問題まで出題されることがあります。 とりあえず中学生でも解ける問題を優先して簡単そうな問題からちまちま解いてます。 poj2887 100万文字の文字列にさらに別の文字列を2000回以下insertし2000回以下ｎ文字目の文字を返す問題 文字の枝にどんどん文字列の枝を接続していくイメージで攻略。 考え方としては子供のころ遊んだブロック遊びと大差ないなあ。 賢ければ中学生でも解けるレベルか。 一度目は何も考えずstd strinの基本機能だけ...
• 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...
• 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...
• 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...
• 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); ...
• AOJ再挑戦31～35
  問31　Weight http //judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0031 lang=jp 天秤で重さを図るときの問題 解法 ２＾ｎで考えたらｎのビットがたってるものだけ出力。 あとはｎ/２で割ったあとｎが0でないならまだのせるものがあるのでスペースを出力。 #include stdio.h int main(){ int n; while(scanf("%d", n)!=EOF){ int a=1; while(n!=0){ if(n%2==1){ printf("%d",a); n/=2; if(n 0)printf(" "); }else{ n/=2; } a*=2; } printf("\n"); }...
• poj適当２
  コード記述者　堀江伸一 世にあるプログラマ養成プロジェクトの一つとして北京大学主催のプログラマ向け練習問題サイトというものがあります。 3000問程度問題が掲載されており、国際的にみても登録者の多いサイトで国際的には有名なサイトでアルゴリズムを勉強するにはちょうどいいサイトです。 問題を解くコードを書いてサーバに送信するとテストデータを使って自動採点までしてくれるので独学にはお勧めのサイトです。 http //poj.org/problemlist ただ問題が英語か中国語で掲載されているため日本人には敷居が高いかもしれません。 そこでリンク先サイトが役に立ちます。 問題を日本語訳しており挑戦しやすくなっております。 http //wikiwiki.jp/pku/?FrontPage リンク先サイトでは翻訳者を募集しているのですが、私はこのサイトをいいサ...
• @wiki全体から「aoj1033挑戦中」で調べる

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