「aoj2400～2410」の編集履歴（バックアップ）一覧に戻る
aoj2400～2410 - (2013/01/28 (月) 02:02:26) のソース
*2401 Equation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401
等号で結ばれた論理式が与えられるので論理式が恒等式であるかいなかを判定する問題。
この問題３回もタイムリミッドを食らっ手疑心暗鬼になりました。
もしかして膨大な採点データを処理しているのかそんなに速度が要求されるのかと疑問を持ちました。
どうしても合格できないので採点用データを入手してそれを使って解いてみますと。
採点結果を検討した結果一回目の投稿時点からアルゴリズムも実装もミスは無いことが判明。
データの読み込み部分にミスがあっただけでした、、、貴重な楽々アセプト問題を無駄にしてしまった。
各変数のtrue falseをsaiki1関数で設定して全探索。
各設定で等式が成り立つかsaiki関数で再帰下降構文解析で論理式を評価した。
ちなみにもっと賢い方法はありそうだが私には思いつかなかった。
この手法でも十分な実行速度で上位ランク入りしたので満足。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
bool bPerm[12],isOK;
bool hitSymbols[12];
int p;
bool saiki(char com[1002],bool modeRe,int deep){
bool b;
char s;
while(com[p]!='\0'){
s=com[p];
if(s=='\0')break;
p++;
if('a'<=s&&s<='k'){
b=bPerm[s-'a'];
}else if(s=='T'){
b=true;
}else if(s=='F'){
b=false;
}else if(s=='*'){
b=saiki(com,true,deep+1)&&b;
}else if(s=='+'){
b=saiki(com,true,deep+1)||b;
}else if(s=='-'&&com[p]=='>'){
p++;
b=(saiki(com,true,deep+1)==false&&b==true)?false:true;
}else if(s=='-'){
b=!saiki(com,true,deep+1);
}else if(s=='('){
b=saiki(com,false,deep+1);
}else if(s==')'){
return b;
}
//printf("(%s %c %d)",b?"t":"f",s,deep);
if(modeRe==true){
return b;
}
}
return b;
}
void saiki1(char comL[1002],char comR[1002],int deep){
if(deep==11){
p=0;
bool b1=saiki(comL,false,0);
p=0;
//printf("\n\n");
bool b2=saiki(comR,false,0);
//printf("<%s %s>\n",b1?"t":"f",b2?"t":"f");
if(b1!=b2)isOK=false;
//isOK=false;
}else{
bPerm[deep]=true;
if(isOK==false)return;
saiki1(comL,comR,deep+1);
if(isOK==false)return;
if(hitSymbols[deep]==false)return;
bPerm[deep]=false;
saiki1(comL,comR,deep+1);
}
}
bool calc(){
char com[1002],comL[1002],comR[1002],c1,c2;
com[0]='\0';
scanf("%s",com);
if(com[0]=='#')return false;
sscanf(com,"%1001[^=]%c%1001s",comL,&c1,comR);
isOK=true;
//printf("<%c><%s>=<%s>",c1,comL,comR);
//出現文字の種類を網羅する
for(int i=0;i<12;i++)hitSymbols[i]=false;
for(int i=0;comL[i]!='\0';i++){
char c=comL[i];
if('a'<=c&&c<='k'){
hitSymbols[c-'a']=true;
}
}
for(int i=0;comR[i]!='\0';i++){
char c=comR[i];
if('a'<=c&&c<='k'){
hitSymbols[c-'a']=true;
}
}
saiki1(comL,comR,0);
printf("%s\n",isOK==true?"YES":"NO");
return true;
}
int main(){
while(calc());
}
*2403 The Enemy of My Enemy is My Friend
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2403
どの隣国と同盟を結ぶべきかを問うグラフの問題。
各国は軍事力を持ち隣国とは同盟を結べず同盟を結んだ国の隣国とも同盟を結べない。
この条件下で軍事力の合計が最大になる同盟をした時の値を求める問題。
動的計画法でギリギリアセプト。
これの上位版問題は解けなかったがこれはサイズが小さいのでギリギリ解けた。
３回もタイムリミットくらってしまった。
AOJで４３０問以上解いた現在残りの問題は苦手問題か難しいのばかり。
これからはWAやタイムリミットがどんどん増えるのは目に見えている。
成績はどんどん落ちていくだろう。
AOJでの自分の未来を考えると暗澹としてしまう。
まあ成績なんて数字でしかないのだ、実際数字だし。
それよりこの問題の賢い動的計画法ってなんだろうか？
ビット演算で隣国を表現し、一国ずつ同盟に入れる入れないを選択。
検討をしてない残りの国だけで構成された同盟を結べなくなった国のリストを基準に動的計画法でとく。
とりあえず（memo）に放り込んで解いた。
ビット演算で速度をごまかしてるだけでアルゴリズム面はいつも通り自前で考え出した最低のコードである(自力で解けないのが悔しいので問題を解くときは調べ物はめったにしな)。
やはり実質中卒の私はこのへんの問題が限界なのだろうか？
最近自分の限界を感じてばかりいる、、、
#include<stdio.h>
#include<map>
#include<string>
#include<iostream>
#include<vector>
#include<queue>
#define v std::vector
#define llmap std::map<long long int,int>
int calc(long long int f,v<long long int> cons,int n,int Bs[42]){
llmap memo[2];
long long int one=1;
//まずはどこの国とも連結してない国と同盟を結ぶ
for(long long int i=1;i<n;i++){
//printf("(%lld %lld)",cons[i],(long long int)1<<i);
if(cons[i]==(one<<i)){
f|=(one<<i);
Bs[0]+=Bs[i];
}
}
memo[0][f]=Bs[0];
llmap::iterator it;
long long int ans=Bs[0],nextP,p,no,mask=0;
int nextB;
for(int i=0;i<=n;i++)mask|=(one<<i);
for(int i=1;i<n;i++){
no=(one<<i);
int now =(i+1)%2;
int next=i%2;
memo[next].clear();
mask=(mask<<1);
for(it=memo[now].begin();it!=memo[now].end();it++){
p=((*it).first&mask);
nextB=(*it).second;
if(memo[next].find(p)==memo[next].end()){
memo[next][p]=nextB;
}else if(memo[next][p]<nextB){
memo[next][p]=nextB;
}
if((p&no)==0){
nextP=(p|cons[i])&mask;
nextB+=Bs[i];
if(memo[next].find(nextP)==memo[next].end()){
memo[next][nextP]=nextB;
}else if(memo[next][nextP]<nextB){
memo[next][nextP]=nextB;
}
}
ans=ans>nextB?ans:nextB;
}
}
printf("%d\n",ans);
}
void setData(int n){
std::string A,D;
int B,C;
std::map<std::string,int> nameToNo;
v<std::string> conNames[42];
v<long long int> cons;//つながりを40ビットで表す
int Bs[42];
for(int i=0;i<n;i++){
std::cin>>A>>Bs[i]>>C;
nameToNo[A]=i;
for(int j=0;j<C;j++){
std::cin>>D;
conNames[i].push_back(D);
}
}
long long int one=1;
for(long long int i=0;i<n;i++){
cons.push_back(0);
cons[i]=(one<<i);//自国
for(int j=0;j<conNames[i].size();j++){
//printf("(%d)",nameToNo[conNames[i][j]]);
cons[i]|=(one<<nameToNo[conNames[i][j]]);
}
//printf("%lld\n",cons[i]);
}
calc(cons[0],cons,n,Bs);
}
int main(){
int n;
while(1){
scanf("%d",&n);
if(n==0)break;
setData(n);
}
}
*2404 Dog Food
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2404
杭の打ちつけられた平面にロープでつながれた犬と餌がある。
杭は高くロープがひっかかるとして餌までの最短移動距離を求めよという問題。
解法
とりあえず一発でまっすぐいけるかどうか試し、駄目なら一本杭を経由して直接行けるか試しそれでも駄目なら２本杭を経由してを続けます。
移動する際、杭に絡まった糸の処理がありますがこれを２重再起で計算します。
結構難しい問題で実装に５時間もかかりました。
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string.h>
int n;
int xs[10],ys[10];
int fx,fy;
double ans,maxLen;
std::vector<int> getInDeltaPoints(int bx,int by,int dx,int dy,int nx,int ny){
std::vector<int> re;
int vxs[3],vys[3],dxs[3],dys[3];
vxs[0]=dx-bx;
vys[0]=dy-by;
vxs[1]=nx-dx;
vys[1]=ny-dy;
vxs[2]=bx-nx;
vys[2]=by-ny;
for(int i=0;i<=n;i++){
int p=0,m=0,zero=0;
dxs[0]=xs[i]-bx;
dys[0]=ys[i]-by;
dxs[1]=xs[i]-dx;
dys[1]=ys[i]-dy;
dxs[2]=xs[i]-nx;
dys[2]=ys[i]-ny;
for(int j=0;j<3;j++){
if(dxs[j]==0&&dys[j]==0)continue;
int g=vxs[j]*dys[j]-dxs[j]*vys[j];
if(g==0){
zero++;
}else if(g<0){
m++;
}else{
p++;
}
}
if(p==3||m==3)re.push_back(i);
if(zero==1&&(p==2||m==2))re.push_back(i);
}
return re;
}
void saiki(int bx,int by,int dx,int dy,int spents[10],double RopeLen,double moveLen);
void saiki2(int bx,int by,int dx,int dy,int gx,int gy,std::vector<int>& perm,int spents[10],double RopeLen,double moveLen){
if(RopeLen>maxLen)return;
if(ans!=-1&&ans<moveLen)return ;
if(getInDeltaPoints(bx,by,dx,dy,gx,gy).empty()==true){
double lastAdd=sqrt((bx-gx)*(bx-gx)+(by-gy)*(by-gy));
if(RopeLen+lastAdd>maxLen)return;
moveLen+=sqrt((dx-gx)*(dx-gx)+(dy-gy)*(dy-gy));
if(gx==fx&&gy==fy){
if(ans==-1||ans>moveLen)ans=moveLen;
}else{
saiki(bx,by,gx,gy,spents,RopeLen,moveLen);
}
return ;
}
for(unsigned int i=0;i<perm.size();i++){
int no=perm[i];
if(spents[no]==0&&getInDeltaPoints(bx,by,dx,dy,xs[no],ys[no]).empty()==true){
spents[no]=1;
double t=sqrt((bx-xs[no])*(bx-xs[no])+(by-ys[no])*(by-ys[no]));
saiki2(xs[no],ys[no],dx,dy,gx,gy,perm,spents,RopeLen+t,moveLen);
spents[no]=0;
}
}
}
void saiki(int bx,int by,int dx,int dy,int spents[10],double RopeLen,double moveLen){
std::vector<int> perm=getInDeltaPoints(bx,by,dx,dy,fx,fy);
saiki2(bx,by,dx,dy,fx,fy,perm,spents,RopeLen,moveLen);
for(int i=0;i<=n;i++){
if(spents[i]==0){
spents[i]=1;
perm=getInDeltaPoints(bx,by,dx,dy,xs[i],ys[i]);
saiki2(bx,by,dx,dy,xs[i],ys[i],perm,spents,RopeLen,moveLen);
spents[i]=0;
}
}
}
void calc(){
int dx,dy;
scanf("%d %d %d %d",&dx,&dy,&fx,&fy);
for(int i=0;i<n;i++)scanf("%d %d",&xs[i],&ys[i]);
xs[n]=0;
ys[n]=0;
int spents[10]={0};
ans=-1;
maxLen=sqrt(dx*dx+dy*dy);
saiki(0,0,dx,dy,spents,0,0);
if(ans==-1){
printf("-1\n");
}else{
printf("%.7lf\n",ans);
}
}
int main(){
while(1){
scanf("%d",&n);
if(n==0)break;
calc();
}
}
*2400 You Are the Judge
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2400
なにやら知らないうちに２４００番台の問題が追加されていた。
もちろん記念すべき１問目は伝統にのっとり肩慣らしの簡単問題である。
こんな簡単な問題でコード実行速度差が出てくるというのが何とも不思議である。
どうやったらこの問題を遅く実行できるのか想像がつかない。
#include <stdio.h>
#include <algorithm>
#include <vector>
struct team{
int a,b[11],no,p;//正答数、誤答数
bool operator<(const team& t)const{
if(a!=t.a)return a>t.a;
if(p!=t.p)return p<t.p;
return no<t.no;
}
team(){
for(int i=0;i<11;i++)b[i]=0;
a=p=0;
}
};
void calc(int t,int p,int r){
std::vector<team> teams;
team t1;
for(int i=0;i<t;i++){
t1.no=i+1;
teams.push_back(t1);
}
int tID,pID,time;
char com[20];
for(int i=0;i<r;i++){
scanf("%d %d %d %s",&tID,&pID,&time,com);
tID--;
if(com[0]=='C'){
teams[tID].a++;
teams[tID].p+=1200*teams[tID].b[pID]+time;
}else{
teams[tID].b[pID]++;
}
}
std::sort(teams.begin(),teams.end());
for(int i=0;i<t;i++){
printf("%d %d %d\n",teams[i].no,teams[i].a,teams[i].p);
}
}
int main(){
int t,p,r;
while(1){
scanf("%d %d %d",&t,&p,&r);
if(t==0&&p==0&&r==0)break;
calc(t,p,r);
}
}
*2406 Al dente
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2406
簡単すぎる問題なので特に解法なし。
こういう簡単すぎる問題でとりあえず正答数を稼ぐのってせこいかな。
まあレーティングにはならないな。
でもレーティングって人手が入ってるから、例えばジャッジデータをより完全にできるアドバイスなどを提出できるとあれポイントもらえるのよね。
#include<stdio.h>
int main(){
int n,t,e,x,ans=-1;
scanf("%d %d %d",&n,&t,&e);
for(int j=1;j<=n;j++){
scanf("%d",&x);
for(int i=t-e;i<=t+e;i++){
if(i%x==0)ans=j;
}
}
printf("%d\n",ans);
}
*2407 Simple Othello
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2407
ｘとoのならびをｎマス続いている部分を一文字に圧縮しても問題はない。
そして圧縮しデータでは一手進むごとにｘかoが一つずつ減っていく。
なのでoのほうが多いならｘが先手でxoxo,,,の順でｘとoが１つずつ減っていく
ｘの方が多いか同じ数ならoの方が先手でoxoxox,,,の順で減っていく。
後はこの単純な計算をコード化するだけです。
ほんの少しだけショートコードを狙ったが平凡にコードの短さで中の上だった。
この問題にはもう本物のショートコーダーが来てるからコードの短さで一位を取ることは不可能。
#include<stdio.h>
int main(){
int xc=0,oc=0;
char s[52],old='s';
scanf("%s",s);
for(int i=0;s[i]!='\0';i++){
if(old!=s[i]){
s[i]=='x'?xc++:s[i]=='o'?oc++:0;
old=s[i];
}
}
printf("%s\n",oc>=xc?"o":"x");
}
圧縮後ｘのほうが数が多いときだけｘが勝つは、文字列の両端がｘであると同じ意味なのでとりあえずショートコーディングにしてみた。
コードの短さ三位だが一位は６０バイトという想像もつかない世界なので私のコードはショートコーディングではないようだ。
#include<stdio.h>
int main(){
char s[52],i=0;
scanf("%s",s);
while(s[i++]);
printf("%c\n",(s[i-2]|s[0])=='x'?'x':'o');
}
*2408 Social
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2408
兎がボートにわかれて乗ったのだが仲の悪い組み合わせがある。
同じボートに中の悪い組み合わせが乗っていると不満を持つが何匹の兎が不満を持つか答える問題。
皆この問題が追加されたことにまだ気づいてないのか、ほとんどだれも来ていない。
新雪の上を歩くような気分でとりあえずコードの短さ１位をゲット。
すぐに抜かれるんだろうなあ。
簡単すぎる問題なので特に解法もなし。
#include<stdio.h>
#include<string.h>
int main(){
int n,k,m,b,no[51],p,q,r;//no[i]はi番目の兎が乗ってるボートの番号
bool outs[51];
memset(outs,false,sizeof(outs));
scanf("%d %d",&n,&k);
for(int i=0;i<k;i++){
scanf("%d",&m);
while(m--){
scanf("%d",&b);
no[b]=i;
}
}
scanf("%d",&r);
while(r--){
scanf("%d %d",&p,&q);
if(no[p]==no[q]){
outs[p]=outs[q]=true;//同じ船に乗っていた
}
}
int ans=0;
for(int i=1;i<=n;i++){
ans+=outs[i];
}
printf("%d\n",ans);
}
*2409 Power
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2409
教授が権力を発動して実験室を守る問題。
解法
こんな簡単な問題なのに何回かＷＡを食らった問題。
まず架空の部屋0番目までを0人の教授が守ってるとみなす。
次に1番の部屋を守れる教授の中で一番数字の大きな部屋biまで守れる教授を選び。
後はこの部屋まで一人で守ってるので(bi)+1までの部屋を守れる教授の中でいちばん大きな部屋を守れる教授を選んでいけば答えとなります。
#include<stdio.h>
#include<vector>
#include<algorithm>
struct S{
int r,l;
bool operator<(const S& s)const{
return l<s.l;
}
};
int main(){
int n,m;
std::vector<S> v;
S s;
scanf("%d %d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d %d",&s.l,&s.r);
v.push_back(s);
}
std::sort(v.begin(),v.end());
int left=0,maxR=0;
int ans=0,p=0;
while(p<m){
while(p<m&&v[p].l<=left+1){
s=v[p];
if(maxR<s.r)maxR=s.r;
p++;
}
ans++;
if(p==m||maxR==n)break;
if(maxR+1<v[p].l)break;
left=maxR;
}
if(maxR==n){
printf("%d\n",ans);
}else{
printf("Impossible\n");
}
}
*2410 Janken
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2410
じゃんけん勝負の人工知能を作る問題。
取り合えず相手のこれまでの手から相手の出す手の確率分布を作り出し、後はミニマックス戦略で行ってみた。
まあ３５０点という圧倒的有利な問題なので勝てない方がおかしい問題。
ランダムに出しても平均１０００点はいけるのではないだろうか？
#include<stdio.h>
#include<string.h>
#include<time.h>
#include <stdlib.h>
int main(){
char l[11],t;
int n,data[11][11],cpuCount[11];//cpuが今まで出した手を記録する
scanf("%d",&n);
for(int r=0;r<n;r++){
scanf("%s",l);
cpuCount[r+1]=1;
for(int c=0;c<n;c++){
t=l[c];
data[r+1][c+1]=t=='o'?3:t=='-'?1:0;
}
}
int ritu[11];
int cpu,my,check=0;
srand((unsigned int)time(NULL));
for(int i=0;i<1000;i++){
//1000ターン
memset(ritu,0,sizeof(ritu));
for(int j=1;j<=n;j++){
ritu[j]=ritu[j-1];
for(int k=1;k<=n;k++)ritu[j]+=cpuCount[j]*data[j][k];
}
int a=rand()%ritu[n];
my=1;
for(int j=1;j<=n;j++){
if(a<ritu[j]){
my=j;
break;
}
}
printf("%d\n",my);
fflush(stdout);
scanf("%d",&cpu);
cpuCount[cpu]+=1;
check+=data[my][cpu];
}
//printf("%d\n",check);
}
