AOJのコンテスト開催用にランダマイザを作ってみた
https://github.com/kyos1704/AOJ-contest-randamizer
作ったのはここにおいた
テキストベースだったりしてすごくあれだけど気にしてはいけない
こんなかんじで問題をセットしたかっただけ
Tex を Ubuntu 12.04 に導入
http://qiita.com/items/a468d4673d7bb7105dc7
ここを見てうごうご
http://mytexpert.sourceforge.jp/index.php?Listings#jbdf49f8
あとここらへんも参考にlistingsの導入も
デュアルディスプレイ 全画面表示と暗転
デュアルディスプレイ環境になりました
が
片方で全画面表示をすると、もう片方も暗転したりうごうごしたりして
なんじゃこりゃだったので調べてみた
http://d.hatena.ne.jp/omochi64/20110511/1305101730
デスクトップコンポジションとかいうのがDXライブラリを使っている?
のが問題らしい
各アプリケーションでプロパティ:互換性:無効化
でなんとかなるそうで
iptables に関して
http://www.asahi-net.or.jp/~aa4t-nngk/ipttut/index.html
コレ読んで設定をうごうごしてたけどよくわからない
それ以前にドライバなかったりとかしてそっちに時間をとられた(探したらあった
ネットワーク周りの知識は暗記っぽいの多くて辛い
SRM 574 の結果と感想
rating 808->835
med落ち過ぎでは・・・・・
easy通ってmed撃墜された
easyサンプル読んだほうがはやい・・・
medは貪欲っぽくしたら場合分け忘れてた
全探索について ~スタックオーバーフローこわいけど大丈夫!~
この記事は突っ込みどころがおそらく満載でお送りしますので間違ってたら是非突っ込んでください
立命館合宿中に、
再帰によるスタックオーバーフローで数回WAをもらいました。
全探索(深さ優先探索)は再帰で書くのが楽ですが、
スタックオーバーフローが起こりうるので
他の手段による全探索を書ける必要があります。
今回はAOJ1130 Red and Black を対象としてコードを作成します
・ICPC Domestic 2004 B
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1130
長すぎるんで大雑把に説明します
- 再帰関数の引数をメンバに持つ構造体を作る
- 作った構造体を保持できるstackを再帰関数に突っ込む
- stackがからになるまでのループを書く(この中に再帰関数の処理部分を突っ込む)
- ループの前にstackに初期状態を突っ込む
- ループの最初にstackから状態を取り出す処理を書く
- 再帰を呼び出していた部分でstackに突っ込む処理に変える
長すぎる本編
まず、main関数を書きます
int w,h; string map[40]; int main(){ while(cin>>w>>h,w){ int fx,fy; for(int i=0;i<h;i++){ cin>>map[i]; } for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ if(map[i][j]=='@'){ fx=i; fy=j; break; } } } int ans=solve(fx,fy); cout<<ans<<endl; } }
はい、書きました。
必要なデータは
mapと初期位置です。
solve関数に初期位置を渡したら、
答えが帰ってきて欲しい感じになりました。
solve関数を書きます
int vec[4][2]={{0,1},{0,-1},{-1,0},{1,0}}; int solve(int x,int y){ int ans=1; map[x][y]='#'; for(int i=0;i<4;i++){ if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w)){ if(map[x+vec[i][0]][y+vec[i][1]]=='.'){ ans+=solve(x+vec[i][0],y+vec[i][1]); } } } return ans; }
vecはn回目に移動する時の移動方向のベクトルですね。
経路探索で辺が与えられる時とかは、vec→edgeみたいに読み替えましょう。
時々配列外参照とかをしてしまうので、
if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w))
この部分でそれを防止して
if(map[x+vec[i][0]][y+vec[i][1]]=='.')
これで移動先に道があるかを確認して
再帰で呼び出します
なんてことはない深さ優先探索ですね。
(この問題ではまったく問題ないけれど)
呼び出し回数によってはこれでスタックオーバーフローを起こします
*ここからはこの問題でオーバーフローを起こしたと仮定します
もう一回solve関数を一から書き直すのはめんどくさい上に時間もかかります(コンテスト中ならなおさら)
よって、今書いたsolve関数を利用して書いていきます
今書いたsolve関数は
int solve(int x,int y){ //自分の位置のタイルの数を足す int ans=1; //移動できるところに移動して //移動先以降のタイルの枚数を足す for(int i=0;i<4;i++){ //ここから二行条件判定 if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w)){ if(map[x+vec[i][0]][y+vec[i][1]]=='.'){ //動いたタイルを調査済みにする map[x][y]='#'; ans+=solve(x+vec[i][0],y+vec[i][1]); } } } return ans; }
というふうになっています。
再帰を使わずに深さ優先探索を行う場合、
stackというデータ構造を使用します
stackとは、机の上に積み上がっていく本のようなデータ構造です
※説明がだるいのでWikipediaを参照してください
stackでどうして深さ優先探索になるかとかそういう説明はおそらく怖い人がしているので
そちらに説明を譲ります
ここで問題になるのは
どう書き換えればスタックオーバーフローせずに
書けるかということです。
まず、stackに突っ込むデータを整理します。
要するに再帰するときに渡している引数が必要です
struct s{ int x,y; };
書きました。
初期化めんどくさいのでコンストラクタぐらいは書きましょう
struct s{ s(int X,int Y){ x=X; y=Y; } int x,y; };
はい書きました。
solve関数の手術の準備は終わりました
再帰をしてはダメなので
solve関数内でsolve関数を呼び出さずに
結果を変えないように、solve関数を書き換えます
int solve(int x,int y){ int ans=1; for(~~~~){ if(~~~~){ if(~~~~){ map[x][y]='#'; //再帰ans+=solve(x+vec[i][0],y+vec[i][1]); } } } return ans; }
とりあえず再帰してた部分をコメントアウトしました
当然結果は変わりますので、
再帰している部分をどうにか再現しないといけません。
再帰が何やっているかっていうと、
引数の状態での探索をもう一度繰り返している。
ということです。
なのでstackにでも探索したい状態を放り込んでおいてやって
取り出した状態を探索してやると良い感じになります
ではstackに状態がなくなるまで探索を続けるという風にコードを変形します
探索するたびに答えの値が一増えているのでans=1をans++とかにしてやります
int solve(int x,int y){ stack<s> st; int ans=0; while(st.empty()!=true){ ans++; for(~~~~){ if(~~~~){ if(~~~~){ map[x][y]='#'; //再帰ans+=solve(x+vec[i][0],y+vec[i][1]); } } } } return ans; }
このままでは当然whileループの中には入らないので(状態がstackに入ってない)
初期状態をstackに積みます
積んだのは取り出さないと行けないので
状態を取り出す処理も書きます
int solve(int x,int y){ stack<s> st; //初期状態の追加 st.push(s(x,y)); int ans=0; while(st.empty()!=true){ s tmp=st.top();st.pop(); x=tmp.x;y=tmp.y; for~~~~~~~~~~~~~~~~~~ } return ans; }
あとは再帰をコメントアウトした部分を
探索待ちの状態をstackに積むというコードに書き換えます
int solve(int x,int y){ ~~~~~~~~~~~~~~~~~~ while(st.empty()!=true){ ans++; for(~~~~~~){ if((~~~~~~~~~~){ if(~~~~~~~~~~~~){ map[x][y]='#'; //再帰ans+=solve(x+vec[i][0],y+vec[i][1]); st.push(s(x+vec[i][0],y+vec[i][1])); } } } } return ans; }
これで通るはずです(ふぅ・・・
ね?簡単でしょう?(
P.S
stackをqueueに変更してやると
幅優先探索になります
取り出し処理のメソッドが違ったりとかしますが
変更点はほぼ一緒なので、
すぐに書けると思います
コード
int solve(int x,int y){ int ans=0; map[x][y]='#'; queue<s> q; q.push(s(x,y)); while(!q.empty()){ s n=q.front();q.pop(); x=n.x; y=n.y; ans++; for(int i=0;i<4;i++){ if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w)){ if(map[x+vec[i][0]][y+vec[i][1]]=='.'){ map[x+vec[i][0]][y+vec[i][1]]='#'; q.push(s(x+vec[i][0],y+vec[i][1])); } } } } return ans; }
問題リストリンク ※更新 2013-03-13
立命館合宿ついでにいろんな人にいいリストはないか聞いてみた
(Twitterで聞いてるんだから別にこんな時でなくても良くないかって突っ込みはなしで)
リンク貼っててまずかったら @kyos_1704_p かコメントかあたりで連絡してください
ジャンル別リスト
倒すべき探索問題リスト
fura(@fura_2)さん作成
http://spinda2.blog48.fc2.com/blog-entry-534.html
DPの練習として良さそうなやつ
きゅうり(@kyuridenamida)さん作成
http://d.hatena.ne.jp/kyuridenamida/20111009/1318091499
SegmentTreeの練習として良さそうなやつ
tozangezanさん作成
http://d.hatena.ne.jp/tozangezan/20111111/1320993464
セグメント木 問題集
hogloid(@hogloid)さん作成
http://hogloid.hatenablog.com/entry/20121227/1356608982
いろんなジャンルの問題のリスト
ICPC(非公式)難易度 解いてる人数 リスト
元データは↓
https://docs.google.com/spreadsheet/ccc?key=0Ank515IguQc4dGJDR3FYOGZGTXQ5VHhNa1JmMDB4U0E#gid=0
AOJ ジャンル分けメモ
otacks(@otaks21)さん作成
http://d.hatena.ne.jp/otaks/20111026/1319629788
頻出典型アルゴリズムの演習問題として良さげなやつ
きゅうり(@kyuridenamida)さん作成
http://d.hatena.ne.jp/kyuridenamida/20111009/1318087144
実装が嫌いな人のための問題集
DEGさん作成
難易度の割に実装量が少ない問題
http://d.hatena.ne.jp/DEGwer/20130313/1363161745
個人的良問リスト
hogloid(@hogloid)さん作成
http://hogloid.hatenablog.com/entry/2013/03/11/182224
割と難しいらしい
追記:
自力で解けるようなものはない、らしいです、↓
https://twitter.com/hogloid/status/311116428810010624