2011/5/11
僕は4流プログラマとしての実力しかない。
工学系の機械設計のような数万を超える関係式を設定するような問題は手も出ないし
バイオ系のような間接的なデータに高度な数学を適用して細胞内部でおこったことや状態を推測するような高度なコードはかけない。
昨今のゲームのすさまじい作りこみを見ると心が折れるほどの能力差を感じる。
事務系や業務系として働くにはそういった方面の知識がない。
金融商品を作ってるような天才や秀才とも縁がない。
漫画だったら駄目駄目ずくしでもそれでも何か大切なものを持ってたりするものだが、現実ではそんなものついぞ目にかかったこともない、。
業界経験もない。
4流プログラマとしてどう働く道を見つけるか?
ということなのである。
2011/5/9
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0509
この問題。
シーツの周計を求めるとはどういうことだろう?
シーツの外枠に沿って歩く人がいて一周したときの歩数でシーツの集計を数えるなら外周を数えたことになるだろうか?
シーツを1として、以下のような
00000
01110
01010
01010
01110
00000
場合シーツの外周を求めるとは?
0の所全てを歩くことになるわけだ。
すると、外周に沿って動く状態遷移マシーンを定義してあげて一度通ったポイントは記録しておけばいいのかな?
マシーンは
1 上下左右の1の数を数えて加算していく。
2 上下左右斜めの0のポイントを探して移動する?
外周に沿って動くということを定義するのが大変そうだなこの方法だと?
近傍点のみを判断基準にすると込み入った場所をスルーしてしまう可能性に対処できない。
しかもこの方法だと最悪6000*10000程度の点を記録することになるな。
もっと賢い方法は何だろう?
シートを一枚ずつ追加していく。
今までのシート外周点に関する情報を元に一枚追加した後の外周情報を使う?
2011/5/8
<stdio.h>
<algorithm>
<string.h>
<set>
void setMap(int,int);
struct setCourse{
int size;
int d;
bool subjects[21];
int sum;
bool operator<(const setCourse sc)const{
if(d<sc.d) return true;
if(d>sc.d) return false;
for(int i=0;i<size;i++){
if(subjects[i]<sc.subjects[i]) return true;
if(subjects[i]>sc.subjects[i]) return false;
}
return false;
}
void setData(bool* ss,int s,int deep,int tsum){
size=s;
memcpy(subjects,ss,s);
d=deep;
sum=tsum;
}
};
int main(){
int n,u;
scanf("%d %d",&n,&u);
while(n!=0 || u!=0)
{
setMap(n,u);
scanf("%d %d",&n,&u);
}
}
void setMap(int n,int u){
int m;
int tempSubC[21];
int subC[21];
int subMs[21];
int subSet[21][21];
for(int i=0;i<n;i++){
scanf("%d %d",&subC[i],&subMs[i]);
tempSubC[i]=subC[i];
for(int j=0;j<subMs[i];j++){
scanf("%d",&subSet[i][j]);
}
}
std::sort(tempSubC,tempSubC+n);
int tsum=0,ansMin=0;
for(int i=n-1;i>-1;i--){
tsum+=tempSubC[i];
if(tsum>=u){
ansMin=n-i;
break;
}
}
bool tempSet[21];
for(int i=0;i<n;i++){
tempSet[i]=(i<ansMin ? true:false);
//printf("%d ",tempSet[i]);
}
std::set<setCourse> scs;
setCourse sc;
bool pushOK;
do{
pushOK=true;
tsum=0;
for(int i=0;i<n;i++)
{
if(tempSet[i]==true)
{
tsum+=subC[i];
for(int j=0;j<subMs[i];j++)
{
if(tempSet[subSet[i][j]]==false)
{
pushOK=false;
break;
}
}
}
if(pushOK==false) break;
}
if(pushOK==true){
if(tsum>=u){
printf("%d\n",ansMin);
return ;
}
sc.setData(tempSet,n,ansMin,tsum);
scs.insert(sc);
}
}while(std::prev_permutation(tempSet, tempSet+n));
std::set<setCourse>::iterator it;
it=scs.begin();
while(it!=scs.end()){
sc=(*it);
for(int i=0;i<n;i++)
{
pushOK=true;
if(sc.subjects[i]==false)
{
for(int j=0;j<subMs[i];j++){
if(sc.subjects[subSet[i][j]]==false){
pushOK=false;
break;
}
}
if(pushOK==true){
sc.subjects[i]=true;
sc.sum+=subC[i];
sc.d++;
if(sc.sum>=u){
printf("%d\n",sc.d);
return ;
}
scs.insert(sc);
sc.d--;
sc.sum-=subC[i];
sc.subjects[i]=false;
}
}
}
it++;
}
}
<stdio.h>
<set>
void setMap(int n,int type);
struct point{
int x,y;
bool operator<(const point p)const{
if(x!=p.x) return x<p.x;
if(y!=p.y) return y<p.y;
return false;
}
};
int main()
{
int n,type;
scanf("%d %d",&n,&type);
while(n!=0 || type!=0){
setMap(n,type);
scanf("%d %d",&n,&type);
}
}
void setMap(int n,int type){
int x1,y1,x2,y2;
std::set<point> area;
point p;
for(int i=0;i<n;i++){
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
for(int i=x1+1;i<x2-1;i++){
p.x=i;
p.y=y1;
area.insert(p);
p.y=y2-1;
area.insert(p);
}
for(int i=y1;i<y2;i++){
p.y=i;
p.x=x1;
area.insert(p);
p.y=i;
p.x=x2-1;
area.insert(p);
}
}
std::set<point>::iterator it;
printf("%d\n",area.size());
if(type==2){
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
int count=0;
it=area.begin();
while(it!=area.end()){
for(int i=0;i<4;i++){
p.x=(*it).x+dx[i];
p.y=(*it).y+dy[i];
if(area.find(p)==area.end()){
count++;
}
}
it++;
}
printf("%d\n",count);
}
}
2011/5/6
<stdio.h>
void setMap();
void saiki(int deep);
char peaces[9][5];
char rows[3][4];
char cols[3][4];
char sa='A'-'a';
bool useds[9];
int ans;
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
setMap();
}
}
void setMap(){
for(int i=0;i<9;i++){
scanf("%s",peaces[i]);
useds[i]=false;
}
ans=0;
saiki(0);
printf("%d\n",ans);
}
void saiki(int deep){
if(deep==9){
ans++;
}
int x,y;
x=deep%3;
y=deep/3;
bool peaceOK;
for(int i=0;i<9;i++){
if(useds[i]==true) continue;
for(int j=0;j<4;j++){
peaceOK=true;
if(y>0){
if(!(rows[y-1][x]==peaces[i][j]+sa || rows[y-1][x]==peaces[i][j]-sa)){
peaceOK=false;
}
}
if(x>0){
if(!(cols[x-1][y]==peaces[i][(j+3)%4]+sa || cols[x-1][y]==peaces[i][(j+3)%4]-sa)){
peaceOK=false;
}
}
rows[y][x]=peaces[i][(j+2)%4];
cols[x][y]=peaces[i][(j+1)%4];
if(peaceOK==true){
useds[i]=true;
saiki(deep+1);
useds[i]=false;
}
}
}
}
2011/5/6
この時、深さ優先探索で履修単位を基準にメモ化をしておくと計算量が抑えられる。
探索の途中で過去に通ったのと同じ履修単位の組み合わせになったら、そこで探索を打ち切るという方法である。
もっと簡単で賢い方法があるのではないか?
深さ優先探索はお馬鹿な方法なのではないか?
という疑問があるためにこの問題は難しくなる。
深さ優先探索+メモ化探索でチャレンジ、見事玉砕。
この問題の統計データを見るにほとんどがタイムリミットエクスパッション、時間切れ、私もその中の一人と。
うーん、どうやって解けばいいのかな?
見方を変えてみよう。
単位の取り方は全体で2^20通りの組み合わせ。
これで、可能な単位の取り方不可能な単位の取り方というものを考えていけばいいのである。
2^20は約104万通り*実現可能な組み合わせかのチェックを導入する。
これなら計算量も小さくなんとかなるだろう。
と考え玉砕。
何が悪かったんだろ?
計算量を更に落とすにはどうすればいいんだろう?
<stdio.h>
<math.h>
void setMap(int,int);
int subC[21];
int subMs[21];
int subSet[21][21];
int main(){
int n,u;
scanf("%d %d",&n,&u);
while(n!=0 || u!=0)
{
setMap(n,u);
scanf("%d %d",&n,&u);
}
}
void setMap(int n,int u){
int m;
for(int i=0;i<n;i++){
scanf("%d %d",&subC[i],&subMs[i]);
for(int j=0;j<subMs[i];j++){
scanf("%d",&subSet[i][j]);
}
}
int p=0,q,d,ans=200;
int end=(int)pow(2,(double)(n)),sum;
bool subOK[21];
int nowSubSet[21];
while(p<end){
q=p;
p++;
d=0;
sum=0;
for(int i=0;i<n;i++){
if(q&1==1){
subOK[i]=true;
sum+=subC[i];
nowSubSet[d]=i;
d++;
if(ans<d) break;
}else{
subOK[i]=false;
}
q=q>>1;
}
if(ans<=d || u>sum){
continue;
}
int temp;
bool okFlag=true;
for(int i=0;i<d;i++){
temp=nowSubSet[i];
for(int j=0;j<subMs[temp];j++){
if(subOK[subSet[temp][j]]==false){
okFlag=false;
break;
}
}
if(okFlag==false) break;
}
if(okFlag==true && d<ans){
ans=d;
}
}
printf("%d\n",ans);
}
以下玉砕コード。
<stdio.h>
<set>
<vector>
<algorithm>
void setMap();
int saiki(int deep,int sum);
struct setCourse{
int size;
int d;
bool subjects[21];
bool operator<(const setCourse sc)const{
for(int i=0;i<size;i++){
if(subjects[i]<sc.subjects[i]) return true;
if(subjects[i]>sc.subjects[i]) return false;
}
return false;
}
void setData(bool* ss,int s,int deep){
size=s;
for(int i=0;i<s;i++) subjects[i]=ss[i];
d=deep;
}
};
int n,u;
std::set<setCourse> scs;
bool subjectOK[21];
int subjectC[21];
std::vector<int> subjectSet[21];
int ans;
std::set<setCourse>::iterator sit;
int main(){
scanf("%d %d",&n,&u);
while(n!=0 || u!=0)
{
setMap();
scanf("%d %d",&n,&u);
}
}
void setMap(){
scs.clear();
int m,t;
ans=200;
for(int i=0;i<n;i++){
subjectOK[i]=false;
scanf("%d %d",&subjectC[i],&m);
subjectSet[i].clear();
for(int j=0;j<m;j++){
scanf("%d",&t);
subjectSet[i].push_back(t);
}
}
printf("%d\n",saiki(0,0));
}
int saiki(int deep,int sum){
if(sum>=u){
ans=deep<ans ? deep:ans;
return deep;
}
setCourse sc;
sc.setData(subjectOK,n,0);
sit=scs.find(sc);
if(sit!=scs.end()) return (*sit).d;
std::vector<int>::iterator it;
bool nextOK;
int d=200;
for(int i=0;i<n;i++){
if(subjectOK[i]==true) continue;
nextOK=true;
it=subjectSet[i].begin();
while(it!=subjectSet[i].end()){
if(subjectOK[(*it)]==false){
nextOK=false;
break;
}
it++;
}
if(nextOK==false) continue;
subjectOK[i]=true;
d=std::min(d,saiki(deep+1,sum+subjectC[i]));
subjectOK[i]=false;
}
sc.setData(subjectOK,n,d);
scs.insert(sc);
return d;
}
2011/5/6
<stdio.h>
<set>
<algorithm>;
void setMap();
void saiki(int no,int sum);
int map[101][101];
std::set<int> connects;
int n,m,ans;
bool endFlag;
int main()
{
scanf("%d %d",&n,&m);
while(n!=0 || m!=0){
setMap();
scanf("%d %d",&n,&m);
}
}
void setMap(){
connects.clear();
endFlag=false;
ans=2000000000;
for(int i=0;i<n+m;i++){
for(int j=0;j<m;j++)map[i][j]=0;
}
for(int i=0;i<n;i++)connects.insert(i);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&map[i][j]);
}
}
for(int i=0;i<m-1;i++){
for(int j=i+1;j<m;j++){
scanf("%d",&map[i+n][j]);
map[j+n][i]=map[i+n][j];
}
}
saiki(0,0);
printf("%d\n",ans);
}
void saiki(int no,int sum){
connects.insert(no);
if(connects.size()==(unsigned int)(n+m)){
endFlag=true;
ans=std::min(sum,ans);
return;
}
std::set<int>::iterator it;
it=connects.begin();
int t=10000,nextNo=-1;
while(it!=connects.end()){
for(int i=0;i<m;i++){
if(connects.find(i+n)==connects.end() && map[*it][i]>0){
if(t>map[*it][i]){
t=map[*it][i];
nextNo=i+n;
}
}
}
it++;
}
if(nextNo>0){
saiki(nextNo,sum+t);
if(endFlag==true) return;
}
}
2011/5/4
この問題の難しいところは回答者リストのランキング。
私のコードは実行速度0.0017秒でメモリ800kb使用という普通の解き方。
メモリ使用量ほぼ0、コード実行速度0.0000という人がいること。
どうやって計算量抑えたんだ?
メモリ使用量低減は状態遷移マシーンで解いて落としたのだと思う。
計算量はどうしたんだろ、かなり謎である?
この問題計算量を落とせばメモリが増え、メモリを抑えると計算量が増えるイメージあるんだけどな。
難しそう。
とりあえず私のコード。
<stdio.h>
<string.h>
int main()
{
char t1[4001],t2[4001];
int memo[2][4001];
int len1,len2;
int num;
while(scanf("%s",t1)!=EOF){
scanf("%s",t2);
len1=strlen(t1);
len2=strlen(t2);
num=0;
for(int i=0;i<len1;i++)memo[0][i]=0;
for(int i=1;i<=len2;i++){
memo[i%2][0]= t2[i-1]==t1[0] ? 1:0;
for(int j=1;j<len1;j++){
if(t2[i-1]==t1[j]){
memo[i%2][j]=memo[(i+1)%2][j-1]+1;
num=memo[i%2][j]>num ? memo[i%2][j]:num;
}else{
memo[i%2][j]=0;
}
}
}
printf("%d\n",num);
}
}
2011/5/3
<stdio.h>
<algorithm>
void setSo();
void calc(int,int);
bool so [1000001];
bool sums[1000001];
int main(){
int n,x;
setSo();
scanf("%d %d",&n,&x);
while(n!=0 && x!=0){
calc(n,x);
scanf("%d %d",&n,&x);
}
}
void calc(int n,int x){
int foods[31];
for(int i=0;i<n;i++){
scanf("%d",&foods[i]);
}
std::sort(foods,foods+n);
int p,max=0;
sums[0]=true;
for(int i=1;i<=x;i++){
sums[i]=false;
p=0;
while(foods[p]<=i && p<n){
if(sums[i-foods[p]]==true){
sums[i]=true;
break;
}
p++;
}
if(sums[i]==true && so[i]==true){
max=i;
}
}
if(max>0){
printf("%d\n",max);
}else{
printf("NA\n");
}
}
void setSo(){
for(int i=2;i<1000001;i++)
so[i]=i%2;
int k;
for(int i=3;i<1000001;i+=2){
if(so[i]==true){
k=i*2;
for(int j=i*3;j<1000001;j+=(k)){
so[j]=false;
}
}
}
so[0]=true;
so[1]=false;
so[2]=true;
}
2010/5/3
<stdio.h>
<algorithm>
int calcTuriSen(int s);
void setMap(int n);
int main()
{
int n;
scanf("%d",&n);
while(n!=0){
setMap(n);
scanf("%d",&n);
if(n==0) break;
printf("\n");
}
}
void setMap(int n){
int d[4],ans[4];
int sum,coinSum;
int ansSum=1000;
for(int i=0;i<4;i++) scanf("%d",&d[i]);
for(int i=0;i<=d[0];i++){
for(int j=0;j<=d[1];j++){
for(int k=0;k<=d[2];k++){
for(int l=0;l<=d[3];l++){
sum=(i*10+j*50+k*100+l*500);
if(sum-n>=0){
coinSum=-(i+j+k+l);
coinSum+=calcTuriSen(sum-n);
if(coinSum<ansSum){
ansSum=coinSum;
ans[0]=i;
ans[1]=j;
ans[2]=k;
ans[3]=l;
}
}
}
}
}
}
int coins[]={10,50,100,500};
for(int i=0;i<4;i++){
if(ans[i]>0){
printf("%d %d\n",coins[i],ans[i]);
}
}
}
int calcTuriSen(int s){
int ans=0;
ans=s/500;
s%=500;
ans+=s/100;
s%=100;
ans+=s/50;
s%=50;
ans+=s/10;
s%=10;
ans+=s/5;
s%=5;
ans+=s;
return ans;
}
2011/4/30
<stdio.h>
int map[503][503];
void setMap(int h,int w){
char t;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
scanf(" %c",&t);
if(t=='.'){
map[i][j]=1;
}else{
map[i][j]=0;
}
}
}
for(int i=0;i<=h;i++)map[i][0]=map[i][w+1]=0;
for(int i=0;i<=w;i++)map[0][i]=0;
int lp,rp,cp,sum=0,max=0;
for(int i=1;i<=h;i++){
for(int j=1;j<=w;j++){
if(map[i][j]!=0) map[i][j]=map[i-1][j]+1;
}
for(int j=1;j<=w;j++){
if(map[i][j]!=0){
cp=map[i][j];
lp=rp=1;
while(map[i][j-lp]>=cp) lp++;
while(map[i][j+rp]>=cp) rp++;
sum=cp*(rp+lp-1);
max=max<sum ? sum:max;
}
}
}
printf("%d\n",max);
}
int main()
{
int w,h;
scanf("%d %d",&h,&w);
while(h!=0 && w!=0){
setMap(h,w);
scanf("%d %d",&h,&w);
}
}
2011/4/25
<stdio.h>
<list>
<algorithm>
<set>
int calcLen(std::list<int> homePerm,int n);
void setMap(int n);
int map[10][10];
int ans;
int main(){
int n;
while(scanf("%d",&n)!=EOF){
setMap(n);
}
}
int calcLen(std::list<int> homePerm,int n){
int hp[10];
int lens[10];
int i=0;
std::list<int>::iterator it;
it=homePerm.begin();
while(it!=homePerm.end()){
hp[i]=(*it);
it++;
i++;
}
for(int i=0;i<n;i++) lens[i]=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++)
{
lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
}
}
return lens[n-1];
}
void saiki(std::list<int> homePerm,int n,int deep){
if(n==deep){
if(ans==-1){
ans=calcLen(homePerm,deep);
}else{
ans=std::min(ans,calcLen(homePerm,deep));
}
return ;
}
int tempAns=-1;
std::list<int> homePermCand[11][100];
int ansCount[11];
for(int i=0;i<11;i++) ansCount[i]=0;
std::list<int>::iterator it;
std::list<int>::iterator it2;
int t;
bool endFlag=false;
int tempPerm[11];
it=homePerm.begin();
for(int i=0;it!=homePerm.end();i++){
tempPerm[i]=(*it);
it++;
}
bool skipFlag;
for(int k=0;k<n;k++)
{
skipFlag=false;
for(int l=0;l<deep;l++){
if(k==tempPerm[l]) skipFlag=true;
}
if(skipFlag==true) continue;
it=homePerm.begin();
endFlag=false;
while(endFlag==false)
{
it2=homePerm.insert(it,k);
t=calcLen(homePerm,deep);
if(tempAns==-1){
tempAns=t;
homePermCand[k][ansCount[k]]=homePerm;
ansCount[k]++;
}else if(tempAns==t){
homePermCand[k][ansCount[k]]=homePerm;
ansCount[k]++;
}else if(tempAns>t){
tempAns=t;
homePermCand[k][0]=homePerm;
ansCount[k]=1;
}
homePerm.erase(it2);
if(it==homePerm.end()){
endFlag=true;
}else{
it++;
}
}
}
for(int k=0;k<deep;k++){
for(int i=0;i<ansCount[k];i++){
saiki(homePermCand[k][i],n,deep+1);
}
}
}
void setMap(int n){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//データの読み込み
scanf("%d",&map[i][j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//より遠ざけたい人を基準に
map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
}
}
ans=-1;
std::list<int> homePerm;
homePerm.clear();
if(n==1){
printf("0\n");
}else{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i!=j){
homePerm.clear();
homePerm.push_back(i);
homePerm.push_back(j);
saiki(homePerm,n,2);
}
}
}
printf("%d\n",ans);
}
}
2011/4/13
といっても世間的にはそんなに難しくはない問題なのかも。
本当に実力のある人は北京大学のオンラインジャッジとか、Google主催のオンラインジャッジ(ネット上でプログラマ向けの大会や問題集を扱ってるサイト)にいるから世間的にはたいしたことないのだろう。
AOJには実力のあるプログラマがそんなにいないから正解率が低いにすぎない。
AOJに集まる人にとっては難問だった、程度にすぎないのかも。
私もこの問題に挑戦。
この問題世間的には簡単に分類されるのだろうけど、私には難しく答えが出せない。
正しい答えを出すところまではいってるはずなんだけど、実行時間が長すぎて不正解を喰らう。
コードを効率化する方法がわからない。
家の数が10軒でも全探索で10!*45程度の計算量 360万*45回の計算量になる。
どうやって計算量を落とせばいいんだ?
<algorithm>
<stdio.h>
void setMap(int n);
int main(){
int n;
while(scanf("%d",&n)!=EOF){
setMap(n);
}
}
void setMap(int n){
int map[10][10];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//データの読み込み
scanf("%d",&map[i][j]);
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//より遠ざけたい人を基準に
map[i][j]=map[j][i]=std::max(map[i][j],map[j][i]);
}
}
int lens[10];//ある並びで家が並んだ時の各人の家の位置
int *hp=new int[n];/各人の家の並び順
int min=2100000000;//21億
for(int i=0;i<n;i++) hp[i]=i;
do{
for(int i=0;i<n;i++) lens[i]=0;
//各人の家が特定の並び順になった時、家をぎちぎちに詰めた場合の最短の長さを求める処理
for(int i=0;i<n;i++)
{
for(int j=0;j<i;j++){
lens[i]=std::max(lens[i],lens[j]+map[hp[i]][hp[j]]);
}
}
min=std::min(lens[n-1],min);
}while(std::next_permutation(hp, hp+n));//家の全ての並び順を求める
printf("%d\n",min);//答え
delete [] hp;
}
2011/4/4
良いサイトである。
設計図をきちんと引いてゲームを作るとどれだけうれしいかが実感できる導入。
多人数で開発を分担できるプログラム開発とは何かが分かる設計。
ゲーム作りのみならず、プログラムを書く時cppファイルをどう分けていくかというアプリ開発の基本が身に付く感じ。
しかも段階を追って学習できるので、C++の基礎が終わっている人なら一人でも学習できる親切設計。
学習に必要な時間も決して長くはない。
解説が高校生でもわかるほどにやさしい。
これで無料!
驚くばかりにいい感じのサイトである。
名前 堀江伸一
住所 兵庫県加古川市加古川町南備後79-16
2011/4/5
http://dixq.net/rp/
今日は敵を表示させてみようまでコードを書く。
うーん理解しながら勉強すると時間がかかるなあ。
前半結構手間の多い処理記述が中心だけど、全ては後半楽をするための処理。
なのだ。
最終更新:2011年05月10日 13:18