会津大学オンラインジャッジを解くページ。
問66 Tic Tac Toe
自分で考えられる限りの短縮を図ったものの平凡なショートコーディングになった。
この問題昔掲示板でヒントはもらって書いたのだけど、今回はその時より短くなっている。
短さ１位の人のコードは想像もつかないがAOJの外には１位の人より上がいるのがネットの世界。
すごいと思う。
AOJばっかりに閉じこもってないで少しは外に出ないとダメか。
コードの短さ6/542位うーん平凡。
コード解説
rはマトリックスです。
ｂに盤面データが保存されています、マス目に番号を付けると。
012
345
678
となったらチェックすべきは
012
345
678
036
147
258
048
246
の8通り。
全部 ｐ、ｐ+ｄ、ｐ+２ｄと表せます。
そして(チェックすべき３マスに入ってる文字のビットOr)に18でマスクをとると。
ooo＝2
か
xxx＝16
それ以外は全部18になります。
％３をとれば、ｘｘｘなら1、oooなら２、それ以外なら0を返す検出器が作れます。
あとは0を入れたｔと8か所のbitORをとるだけです。
#include<stdio.h>
int main(){
char *r="0001223613432311",b[10],i,t,p,d;
while(scanf("%s",b)>0){
t=i=0;
while(i<8){
d=r[i+8]%8;
p=r[i++]%8;
t|=((b[p]|b[p+d]|b[p+d*2])&18)%3;
}
printf("%c\n","dxo"[t]);
}
}
問67 The Number of Island
#include<stdio.h>
#include<set>
#include<iostream>
const int SIZE=12;
int main(){
char nowP;
while(1){
std::set<long long int> spentsNo;
std::set<long long int>::reverse_iterator rIt;
spentsNo.insert(0);
long long int ansAdd=0;
long long int oldRowMemo[SIZE]={0};
for(int r=0;r<SIZE;r++){
long long int nowRowMemo[SIZE]={0};
for(int c=0;c<SIZE;c++){
scanf("%c",&nowP);
if(nowP=='0'){
oldRowMemo[c]=nowRowMemo[c]=0;
continue;
}
long long int max=0;
if(0<c){
max=nowRowMemo[c-1];
}
if(0<r){
max=max>oldRowMemo[c]?max:oldRowMemo[c];
}
if(max==0){
rIt=spentsNo.rbegin();
max=(*rIt)+1;
spentsNo.insert(max);
}
nowRowMemo[c]=max;
long long int t=nowRowMemo[c-1];
if(0<c&&t>0&&t<max){
spentsNo.erase(t);
}
t=oldRowMemo[c];
if(0<r&&t>0&&t<max){
spentsNo.erase(t);
}
oldRowMemo[c]=max;
}
scanf("%c",&nowP);//改行読み込み
//いらないデータの掃除
std::set<long long int> nowRowSet,dellNo;
for(int i=0;i<SIZE;i++){
nowRowSet.insert(nowRowMemo[i]);
}
for(rIt=spentsNo.rbegin();rIt!=spentsNo.rend();rIt++){
if(nowRowSet.find((*rIt))==nowRowSet.end()&&(*rIt)>0){
dellNo.insert((*rIt));
}
}
ansAdd+=dellNo.size();
for(rIt=dellNo.rbegin();rIt!=dellNo.rend();rIt++){
spentsNo.erase((*rIt));
}
}
std::cout<<spentsNo.size()-1+ansAdd<<"\n";
if(scanf("%c",&nowP)==EOF)break;
}
}
68 Enclose Pins with a Rubber Band
#include<stdio.h>
#include<math.h>
double calcCos(double x0,double y0,double x1,double y1,double dx0,double dy0){
double dx1=x1-x0;
double dy1=y1-y0;
double len0=hypot(dx0,dy0);
double len1=hypot(dx1,dy1);
double naiseki=dx0*dx1+dy0*dy1;
return naiseki/(len0*len1);
}
void calc(int n){
double xs[101],ys[101],downY=1001,leftX=1001,oldDx=1,oldDy=0;
int nowP,oldP,startP,count=0;
//問題で言及されてる内容からいろいろ手抜き処理で記述
//言及がなければ無限ループになる可能性あり
for(int i=0;i<n;i++){
scanf("%lf,%lf",&xs[i],&ys[i]);
if((ys[i]<downY)||(ys[i]==downY&&xs[i]<leftX)){
downY=ys[i];
leftX=xs[i];
startP=oldP=i;
}
}
while(count<2||nowP!=startP){
double cosMax=-1,cosTemp;
for(int i=0;i<n;i++){
if(i==oldP)continue;
cosTemp=calcCos(xs[oldP],ys[oldP],xs[i],ys[i],oldDx,oldDy);
if(cosTemp>cosMax){
nowP=i;
cosMax=cosTemp;
}
}
oldDx=xs[nowP]-xs[oldP];
oldDy=ys[nowP]-ys[oldP];
oldP=nowP;
count++;
}
printf("%d\n",n-count);
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
calc(n);
}
}
問69 Drawing Lots II
各場所に一本だけ線を足した場合を各々でシミュレーションするのがコードも短くなってよいのですが。
数万列*数万行になっても定数を変えるだけでBigO（列数*行数）で計算が終わるように記述してみました。
一本線を足す場合だとBigO(行数＾２*列数)となります。
#include<stdio.h>
#include<string.h>
#include<algorithm>
struct S{
int row,col,hit;
bool operator<(const S& s)const{
if(hit!=s.hit)return hit>s.hit;
return row<s.row;
}
};
S minS(const S& s1,const S& s2){
return s2<s1?s2:s1;
}
void search(int n){
int m,atari,d;
char row[12];
scanf("%d %d %d",&m,&atari,&d);
S s,memo[2][12];
s.hit=0;
s.row=d+1;
for(int i=1;i<=n;i++){
s.hit=(i==m);
memo[0][i]=s;
s.hit=0;
memo[1][i]=s;
}
for(int i=0;i<d;i++){
scanf("%s",&row[1]);
row[0]=row[n]='0';
for(int col=1;col<n;col++){
//横線を引かない
if(row[col]=='1'){
std::swap(memo[0][col],memo[0][col+1]);
std::swap(memo[1][col],memo[1][col+1]);
}
//横線を引けた
if(row[col-1]=='0'&&row[col]=='0'&&row[col+1]=='0'){
s=memo[0][col];
s.row=i+1;
s.col=col;
memo[1][col+1]=minS(s,memo[1][col+1]);
s=memo[0][col+1];
s.row=i+1;
s.col=col;
memo[1][col] =minS(s,memo[1][col]);
}
}
}
if(memo[0][atari].hit==1){
printf("0\n");
}else if(memo[1][atari].hit==1){
s=memo[1][atari];
printf("%d %d\n",s.row,s.col);
}else{
printf("1\n");
}
}
int main(){
int n;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
search(n);
}
}
Combination of Number Sequences
解法
平凡な動的計画法でテーブル化して解きました。
#include<stdio.h>
#include<string.h>
const int MAX=330;
const int BIT_LIMIT=1024;
int memo[2][BIT_LIMIT][MAX+1],ans[11][MAX+1];
int main(){
memset(memo,0,sizeof(memo));
memo[0][0][0]=1;
memset(ans,0,sizeof(ans));
for(int i=1;i<=10;i++){
int now =(i+1)%2;
int next=i%2;
for(int j=0;j<BIT_LIMIT;j++){
for(int k=0;k<=9;k++){
int b=1<<k;
if((b&j)>0)continue;
for(int l=0;l<=MAX-k*i;l++){
memo[next][j|b][l+k*i]+=memo[now][j][l];
}
}
}
for(int j=0;j<BIT_LIMIT;j++){
for(int l=0;l<=MAX;l++){
ans[i][l]+=memo[next][j][l];
}
}
memset(memo[now],0,sizeof(memo[now]));
}
int n,s;
while(scanf("%d %d",&n,&s)!=EOF){
if(n>10 || s>MAX){
printf("0\n");
}else{
printf("%d\n",ans[n][s]);
}
}
}
最終更新：2014年02月02日 14:48
