日記管理人 堀江伸一 〒675-0033-79-16
兵庫県加古川市加古川町南備後79-16
2011/3/1
会津大学オンラインジャッジの問題解答用テンプレ
<stdio.h>
<stdlib.h>
FILE *fin,*fout;
int sums[101];
int main()
{
fin=fopen("input.txt","r");
fout=fopen("output.txt","w");
fclose(fin);
fclose(fout);
}
2011/2/28
この問題は簡単、m個の数字の並びを。
a+(a+1)+(a+2)+,,,+(a+m)=b
となる連番と考えて分解すると
b-(1+2+3+,,,)=a(m+1)となるので
(b-(1+2+3+,,,+m))%(m+1)==0
を順番に計算するだけでよい。
平均的な高校生に出したら丁度好さそうな練習問題だな。
2011/2/27
<stdio.h>
<math.h>
void search(int s,int g,int n);
void setMap(int);
void setMap2(int s);
int b[1002],x[1002],y[1002];
double map[1002][1002];
double movesLen[1002];
bool moveOKs[1002];
int index[1002];
int m=100000000;
int main(){
int n;
scanf("%d",&n);
while(n!=0){
setMap(n);
scanf("%d",&n);
}
}
void setMap(int n)
{
n++;
for(int i=1;i<n;i++)
{
scanf("%d %d %d",&b[i],&x[i],&y[i]);
}
int vx,vy,len;
for(int i=1;i<1001;i++){
for(int j=1;j<1001;j++){
map[i][j]=m;
}
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j || i==0 || j==0){
map[i][j]=0;
}else
{
vx=x[b[i]]-x[b[j]];
vy=y[b[i]]-y[b[j]];
len=vx*vx+vy*vy;
if(len<=2500){
map[b[i]][b[j]]=map[b[j]][b[i]]=sqrt((double)len);
}
}
}
}
int m,s,g;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d %d",&s ,&g);
setMap2(s);
search(s,g,n);
}
}
void setMap2(int s){
for(int i=0;i<1001;i++){
movesLen[i]=m;
index[i]=0;
moveOKs[i]=true;
}
movesLen[s]=0;
}
void search(int s, int g,int n){
if(s==g){
printf("%d\n",s);
return ;
}
int min,p;
for(int j=1;j<n;j++){
min=m;
for(int k=1;k<n;k++)
{
if(moveOKs[k]==true && movesLen[k]<min)
{
min=movesLen[k];p=k;
}
}
moveOKs[p]=false;
if(min==m){
break;
}
for(int k=1;k<n;k++){
if((movesLen[p]+map[p][k])<movesLen[k]){
movesLen[k]=movesLen[p]+map[p][k];
index[k]=p;
}
}
}
int index2[1002];
int rootC=1;
p=g;
if(index[g]!=0){
index2[0]=g;
while(index[p]!=0){
index2[rootC]=index[p];
p=index[p];
rootC++;
}
for(int i=rootC-1;i>0;i--){
printf("%d ",index2[i]);
}
printf("%d\n",index2[0]);
}else{
printf("NA\n");
}
}
2011/2/21
まず、史跡を点でつなげるので出来上がるのはグラフ。
グラフにループがあった場合、ループ部分の線分を消しても史跡のつながりは確保される。
よって求めるべき答えは木構造。
ｎ-2本線が引かれｎ-1点まで木構造でつながったと仮定する。
2 この時、最後の点につなげるべき線分は、最後の点からでる一番短い線分になるのは明白。
このつなげた2点をA2と考え、それ以外の点をA２の補集合B2とし、A2とB2をつなぐ線分を切り離す。
こうなるとA２とB2は２と同じ状況になる。
A２を丸で囲み、この丸を一つの点と考えるとB2とA2をつなげる線はA2からB2への線分の中で最小のものとなる
。
A2から新しくひいた線分の先にある点をA2に加えてこれをA3,A3以外の点をB3とし以下同様の議論を繰り返す。
この議論が終わると全ての点が尽くされ全ての点が木構造で結ばれる。
この時の計算量は、ｍ本の線分がｎ点から出ているので一点頭平均a=m/n
一回めは大体a本の線分の中から最小の線分を探すので、a.
A2からはa*2本出ているので(a*2-1)
Aiからはa*i本線が出ているので役(a*i)-i;
より合計してa+(2*a-1)+(3*a-1)+,,,となる。
大雑把にいって
a*n^2＝ｍｎの計算量となる。
後はこれをコードにするだけ。
一見大学レベルの問題に見えるこの問題。
私のこの推論過程を読むとなるほど、帰納法だしこれは高校レベルの数学だと実感するはず。
という仮説を立てたものの少し自信がなかったりする。
とりあえずコードを書いてテストデータに食わしてみるか。
データを食わしてみたら上手くいった。
テストデータはかなりシビアに作られているので99％間違ってないだろうな。
以下コード。
ほぼ平均値のコードサイズ。
もっと短くできるようだけど、これをもっと短くする方法は僕には想像もつかない。
<stdio.h>
<set>
void solve(int n);
int map[101][101];
bool moveOK[101];
int MAX=100000000;
int main()
{
int n;
scanf("%d",&n);
while(n!=0){
solve(n);
scanf("%d",&n);
}
}
void solve(int n){
int m,a,b,t;
int minRoot=MAX,p1,p2,p;
scanf("%d",&m);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
map[i][j]=MAX;
}
moveOK[i]=true;
}
for(int i=0;i<m;i++){
scanf("%d,%d,%d",&a,&b,&t);
map[a][b]=t/100-1;
map[b][a]=t/100-1;
if(t<minRoot){
p1=a;p2=b;minRoot=t;
}
}
int sum=map[p1][p2];
moveOK[p1]=moveOK[p2]=false;
map[p1][p2]=map[p2][p1]=MAX;
std::set<int> points;
points.insert(p1);points.insert(p2);
std::set<int>::iterator it;
for(int i=2;i<n;i++){
it=points.begin();
minRoot=MAX;
while(it!=points.end()){
p=*it;
for(int i=0;i<n;i++){
if(map[p][i]<minRoot && moveOK[i]==true){
minRoot=map[p][i];
p1=p;
p2=i;
}
}
it++;
}
sum+=minRoot;
map[p1][p2]=map[p2][p1]=MAX;
moveOK[p2]=false;
points.insert(p2);
}
printf("%d\n",sum);
}
2011/2/20
21日更新
<stdio.h>
void solve(int,int);
void A(int,char);
void B(int);
void C(int,int);
void D(int,int);
char seats[103];//席は1番から100番まで使用する。0と101は番兵役
int main()
{
int n,m;
scanf("%d %d",&n,&m);
while(n!=0 && m!=0){
solve(n,m);
scanf("%d %d",&n,&m);
}
}
void solve(int n,int m)
{
n++;
for(int i=0;i<n;i++){
seats[i]='#';
}
seats[0]=seats[n]='e';
char c;
for(int i=0;i<m;i++){
scanf(" %c",&c);
if(c=='A'){
A(n,'A');
}else if(c=='B'){
B(n);
}else if(c=='C'){
C(n,i);
}else if(c=='D'){
D(n,i);
}
}
for(int i=1;i<n;i++){
printf("%c",seats[i]);
}
printf("\n");
}
void A(int n,char man)
{
int i=1;
while(seats[i]!='#') i++;
seats[i]=man;
}
void B(int n)
{
for(int i=n-1;i>0;i--){
if(seats[i+1]!='A' && seats[i-1]!='A' && seats[i]=='#'){
seats[i]='B';
return ;
}
}
A(n,'B');
}
void C(int n,int manCount)
{
if(manCount==0){
int m=n-1;
if(m%2==1){
seats[(m+1)/2]='C';
}else{
seats[m/2+1]='C';
}
}else{
int p=1;
while(1){
while(seats[p]=='#') p++;
if(seats[p+1]=='#'){
p++;
break;
}
if(seats[p-1]=='#'){
p--;
break;
}
p++;
}
seats[p]='C';
}
}
void D(int n,int manCount)
{
if(manCount==0){
seats[1]='D';
}else{
int lpoint=0,rpoint=1;
int lMax,rMax,spaceMax=0;
int t;
while(n>=rpoint){
if(seats[rpoint]=='#'){
rpoint++;
}else{
t=rpoint-lpoint-1;
if(n>rpoint && lpoint>0) t=(t+1)/2;
if(t>spaceMax){
lMax=lpoint;
rMax=rpoint;
spaceMax=t;
}
lpoint=rpoint;
rpoint++;
}
}
if(lMax==0 && seats[1]=='#'){
seats[1]='D';
}else if(rMax==n && seats[n-1]=='#'){
seats[n-1]='D';
}else if(spaceMax>0){
seats[(lMax+rMax)/2]='D';
}else{
A(n,'D');
}
}
}
2011/2/17
<stdio.h>
<math.h>
int search(int s,int g);
void setMap(int);
int b[1001],x[1001],y[1001];
double map[1001][1001];
double movesLen[1001];
bool moveOK[1001];
int m=100000000;
int main(){
int n;
scanf("%d",&n);
while(n!=0){
scanf("%d",&n);
}
}
void setMap(int n)
{
for(int i=0;i<n;i++)
{
scanf("%d %d %d",&b[i],&x[i],&y[i]);
}
int vx,vy,len;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=m;
}
movesLen[i]=m;
moveOKs[i]=true;
}
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
vx=x[i]-x[j];
vy=y[i]-y[j];
len=vx*vx+vy*vy;
if(len<=2500){
map[b[i]][b[j]]=map[b[j]][b[i]]=sqrt(len);
}
}
}
int m;
scanf("%d",&m);
for(int i=0;i<m;i++){
}
}
void search(int s,int g){
}
2011/2/17
会津大学オンラインジャッジのサイトにアクセスできない。
Botあおいちゃんを見る限りここ1時間以内で問題解いている人はいるので、サーバーが落ちてるわけではなさそう？
なぜ？
最近問題を解くのが習慣化してしまったから問題に挑戦できないと禁断症状が出てくる。
会津大学オンラインジャッジ。
さすがに170門も解くと気楽に解ける問題が減ってくる。
0～100までは、簡単問題中心。
まずはプログラムに慣れましょう
というレベル。
難しい問題が数問混ざってるだけ。
100～200はプログラムをおもちゃ代わりに簡単な問題解きましょう。
というレベルだな。
まだ初歩的な教科書通りのアルゴリズムで解ける世界。
僕はまだ100～200で修行の身といったところだな。
実務で使える。
レベルの問題があるレベルに到達するにいはまだまだ勉強がいるなあ。
2011/2/16
とりあえずの簡易データ。
7
9
1,2,8,8
1,3,4,4
1,7,3,3
2,6,1,1
3,4,5,5
4,5,2,2
5,6,7,7
5,7,1,1
6,7,2,2
2,5,10,10
点３から点２、点２から３への最短移動距離の合計がおかしい
<stdio.h>
void search(int s,int g);
int map[21][21];
int values[21];
int m=1000000000;
int n;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
map[i][j]=m;
}
values[i]=m;
}
int a,b,c,d;
for(int i=0;i<m;i++){
scanf("%d,%d,%d,%d",&a,&b,&c,&d);
map[a][b]=c;
map[b][a]=d;
}
int x1,x2,y1,y2;
printf("test\n");
scanf("%d,%d,%d,%d",&x1,&x2,&y1,&y2);
search(x1,x2);
}
void search(int s,int g){
int start=s;
int goal=g;
int min;
values[start]=0;
for(int k=1;k<=n;k++)
{
min=m;
for(int i=1;i<=n;i++)
{
if(min>values[i])
{
min=values[i];
}
}
if(min==m) break;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(values[j]>map[j][i]+values[i])
{
values[j]=map[j][i]+values[i];
}
}
}
}
for(int i=1;i<=n;i++){
printf("v[%d]=%d\n",i,values[i]);
}
}
2011/2/14
以下書きかけ
<stdio.h>
void solve(int n);
int times[21][21];//島のつながりと橋の時間を表す
int moves;
int moveCount;
int sum;
bool moveOKs[21];
int main()
{
int n;
scanf("%d",&n);
while(n!=0){
solve();
scanf("%d",&n);
}
}
void solve(int n)
{
int count,p1,p2;
moves=n-1;//移動する橋の数
moveCount=0;//移動した橋の数
int i1,i2,t;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
times[i][j]=0;
}
moveOKs[i]=true;//移動前ならtrue
}
for(int i=0;i<n-1;i++){
scanf("%d %d %d",&i1,&i2,&t);
times[i1][i2]=t;
times[i2][i1]=t;
}
//頂点になる橋は計算にいらないので削除する
for(int i=2;i<n;i++){
count=0;
for(int j=1;j<n;j++){
if(times[i][j]>0){
count++;
p1=i;
p2=j;
}
}
if(count==1){
times[p1][p2]=times[p2][p1]=0;
moves--;//移動しなくていい橋が一つ減る
}
}
}
void search(int islandNO,int n,int parentsNo){
//islandnoは今いる島、 parentsNoは前にいた島；
if(moveCount>=moves){
return ;
}
for(int i=1;i<=n;i++){
if(parentsNo!=i && times[islandNO][i]>0){
sum+=times[islandNO][i];
if(moveOKs[i]==true){
moveCount++;
moveOKs[i]=false;
}
search();
}
if(moveCount>=moves){
return ;
}else{
sum+=times[islandNO][i];
}
}
}
2011/2/14
７パズルを解くコード。
完成状態から探索を初めて、ダイクストラ法であるパターンに行きつくまで何手必要か。
をすべてのパタンで求めて解いた。
パズルが小さいから何とかなる方法で、もっと大きなパズルになるとこの手法は使えなくなる。
もっと根本的な手法が必要？
<stdio.h>
<map>
void moveOKStage(int,int);
void search(int);
void move(int,int,int,int);
int rs[9];
std::map<int,int>::iterator it;
std::map<int,int> next;
std::map<int,int> moveOK;
std::map<int,int> moves;
int main(){
int s,r,keta=1;
for(int i=8;i>=0;i--){
rs[i]=keta;
keta*=10;
}
search(123456780);
while(scanf("%d",&s)!=EOF){
s++;
s*=rs[0];
for(int i=1;i<8;i++){
scanf("%d",&r);
s+=(r+1)*rs[i];
if(r==0){
s+=i;
}
}
printf("%d\n",moves[s]);
}
}
void search(int start){
int s;
int cC=0;
moveOKStage(start,0);
int p;
moveOK.swap(next);
while(1){
next.clear();
cC++;
it=moveOK.begin();
while(it!=moveOK.end()){
s=(*it).second;
p=s%10;
move(p,p+1,s,cC);
move(p,p-1,s,cC);
move(p,p+4,s,cC);
move(p,p-4,s,cC);
it++;
}
if(next.size()<1){
break;
}
moveOK.swap(next);
}
}
void move(int p1,int p2,int s,int deep){
if(p1<0 || p1>7 || p2<0 || p2>7){
return ;
}
if((p1==3 && p2==4) || (p1==4 && p2==3)){
return ;
}
int u=s;
u=u+((u/rs[p2])%10)*(rs[p1]-rs[p2])-rs[p1]+rs[p2];
u=u-p1+p2;
moveOKStage(u,deep);
}
void moveOKStage(int u,int deep){
if(moves.count(u)==0){
moves[u]=deep;
next[u]=u;
}
}
2011/2/14
7パズルを解くコード。
コードの短縮と実行速度加速とメモリ使用量の低下のバランスを目指してみた。
こういう問題はビット演算で解くのが本質なのだけど、その方法を知らないので、7パズルの状態を8ケタの数字+空き枡のある位置の情報1ケタの数字、計9ケタとして実装してみた。
とりあえずコードを書いただけで未テスト。
、、、テスト中、、、
うーん、テストデータによる結果は時間切れ。
これは逆かな？
最初にダイクストラ法を使ってキューブの全状態の関係を求める方法を使えばいいのだろうか？
<stdio.h>
<map>
bool moveOKStage(int);
void search(int);
bool move(int,int,int);
int rs[9];
std::map<int,int>::iterator it;
std::map<int,int> next;
std::map<int,int> moveOK;
std::map<int,int> moves;
int main(){
int s,r,keta=1;
for(int i=8;i>=0;i--){
rs[i]=keta;
keta*=10;
}
while(scanf("%d",&s)!=EOF){
s++;
s*=rs[0];
for(int i=1;i<8;i++){
scanf("%d",&r);
s+=(r+1)*rs[i];
if(r==0){
s+=i;
}
}
printf("s=%d ",s);
search(s);
}
}
void search(int start){
bool cF=false;
moveOK.clear();
next.clear();
moves.clear();
int s;
int cC=0;
if(moveOKStage(start)==true){
printf("0\n");
return ;
}
int p;
moveOK.swap(next);
while(1){
next.clear();
cC++;
it=moveOK.begin();
while(it!=moveOK.end()){
s=(*it).second;
p=s%10;
cF=move(p,p+1,s)|move(p,p-1,s)|move(p,p+4,s)|move(p,p-4,s);
if(cF){
printf("%d\n",cC);
return ;
}
it++;
}
if(next.size()<1){
break;
}
moveOK.swap(next);
}
}
bool move(int p1,int p2,int s){
if(p1<0 || p1>7 || p2<0 || p2>7){
return false;
}
int u=s;
u=u+((u/rs[p2])%10)*(rs[p1]-rs[p2])-rs[p1]+rs[p2];
u=u-p1+p2;
return moveOKStage(u);
}
bool moveOKStage(int s){
if(s==123456780){
return true;
}
if(moves.count(s)==0){
moves[s]=1;
next[s]=s;
}
return false;
}
2011/2/14
strrev(一伸江堀)
平面板の上に回転するローラーを複数用意。
このローラにチェーンを巻きつけ、チェーンが一周するように張る。
チェーンには磁石を張り付け、チェーンの外周は一定間隔でコイルで編まれたホースで囲む。
これで電気を流せばモータにならないかしら？
2011/2/12
<stdio.h>
int main(){int a,b,c,d,s;scanf("%d %d %d %d",&a,&b,&c,&d);s=a+b+c+d;printf("%d\n%d\n",s/60,s%60);}
これ以上どうやってコードを短くするのか？
アマチュアプログラマである僕にとって謎だ。
後45文字も短くできるらしい？
ええええ？
謎すぎる。
後、欠片も汎用性がないコードを書いてしまったorz.
書いた後で気がついた。
A,B,Cからどれだけ選ぶかを
３重forループで回せばいいだけじゃん、そしたら計算量小さくなったし(爆)
なんという無駄コード（爆）
今日書いたコード。
<stdio.h>
<stdlib.h>
int money[51];
bool moveOK[26][18][11];
void search();
void solve();
void saiki(int wsum,int a,int b,int c);
int main(){
int n;
search();
scanf("%d",&n);
while(n!=0){
n=n/100;
printf("%d\n",money[n]);
scanf("%d",&n);
}
}
void solve(){
for(int i=0;i<51;i++){
int min=money[i];
for(int j=i;j<51;j++){
if(min>money[j]){
min=money[j];
}
}
money[i]=min;
}
}
void search(){
for(int i=0;i<26;i++){
for(int j=0;j<18;j++){
for(int k=0;k<11;k++){
moveOK[i][j][k]=true;
}
}
}
for(int i=0;i<51;i++){
money[i]=1000000;
}
saiki(0,0,0,0);
}
void saiki(int wsum,int a,int b,int c){
if(wsum>50){
return ;
}
if(moveOK[a][b][c]==false){
return ;
}else{
moveOK[a][b][c]=false;
}
int m=(a/5)*1520+(a%5)*380+(b/4)*1870+(b%4)*550+(c/3)*2244+(c%3)*850;
if(m<money[wsum]){
money[wsum]=m;
}
saiki(wsum+2,a+1,b,c);
saiki(wsum+3,a,b+1,c);
saiki(wsum+5,a,b,c+1);
}
2011/2/10
簡単な解法としては、mapを使いキーを重さ、値を宝の価値と定義する。
最初にmapに品物を入れる。
mapの要素を順番に取り出し、それに
ある品物を足す、足さないを順番に行い、新しい重さと価値でkeyに代入を行う。
このときKeyがもう埋まっているならより価値の大きい方でkeyの値を更新する。
keyがまだ存在しないならその値でkeyを更新する。
keyが重さの総和を超えたら、それは無視する。
全ての品物のチェックが終わった時
最後にイテレータを回して、mapの中で一番値の大きいものを探す？
という方法を考えついたのだけど、あっているかどうか少し自信がない。
問題はmapの中身が恐ろしい個数になる可能性がある点。
ジャッジ通るといいなあ。
2011/2/8
<stdio.h>
<map>
int main(){
int n;
}
void search(){
int map[9][9];
int NoCount[9];
int t;
std::map<int,int> err;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
NoCount[i]=0;
}
for(int j=0;j<9;j++){
scanf(" %d",&t);
if(NoCount[t]==0){
NoCount[t]=1;
}else{
err[i*9+j]=1;
}
map[i][j]=t;
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
NoCount[j]=0;
}
for(int j=0;j<9;j++){
t=map[j][i];
if(NoCount[t]==0){
NoCount[t]++;
}else{
err[i*9+j]=1;
}
}
}
for(int i=0;i<9;i+=3){
for(int j=0;j<9;j+=3){
for(int k=0;k<9;k++){
NoCount[k]=0;
}
for(int k=0;k<9;k++){
if(NoCount[map[i+k/3][j+k%3]]==0){
NoCount[map[i+k/3][j+k%3]]=1;
}else{
err[(i+k/3)*9+j+k%3]=1;
}
}
}
}
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(err.count(i*9+j)==1){
printf("*%d",map[i][j]);
}else{
printf(" %d",map[i][j]);
}
}
printf("\n");
}
}
2011/2/8
答えや考えかたは検索すれば良いコードが見つかるんだけど自分で解くのが大事かなと考えて、解いた後だけ参考程度に見てる。
解く前は、足元すくってくるような意地悪なデータがあったらどうしようとか、計算誤差が問題になる微妙な問題はどう解くかとか色々悩むのですが
解き終わった後にみるとこんな簡単な問題で悩んだりしてたのかと思ったり。
こういうのってプログラマとして少しは成長してるのかな？
さすがにこれだけ解いてるとただ解くだけでなく、実行速度一位とかコードの短さ一位とかに興味がわく。
変数一文字、改行削除してまで稼ぐコードの短さは興味がないので、コードの短さはそこそこでいいけど、実行速度上位はとりたくなるところ。
2011/2/4
SFネタ記録
音を発する機能を持った飛行ロボ。
歩兵用装備。
遠隔操作で飛ばし、足音や人の声、銃声等を発することができ、その地点に人がいると思わせる効果を持っている。
GPS誘導で目標地点まで移動するサイボーグ系のスピークマウス等もいる。
移動経路はネズミの脳まかせ、脳に端子が埋め込まれ、背中に装備一式を背負うことが可能で目的地まで移動してカメラ偵察、音声欺瞞を行う能力を持つ。
装備は太った鼠に見えるようカバーで覆われる。
最終更新：2011年03月01日 17:57
