会津大学オンラインジャッジ 問126

Puzzle

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0126
数独で間違った回答の間違ってる部分にチェックをつける問題。


行、列　３*３で数えて２つ以上重なってるものに*をつけるだけです。
結構エレガントに書けた気はするがショートコーダーから見たらきっとこのコードは長い。
７００バイト１２位、特にショートコードを狙ったわけでもないのでまあまあの順位に思えるが。
１位は２６４バイトなので２位以下か１位かという区別しか意味がない。



#include<stdio.h>
#include<string.h>

void check(){
      int rows[9][10],cols[9][10],cell33[3][3][10];
      int board[9][9],num;
      memset(cell33,0,sizeof(cell33));
      memset(rows,0,sizeof(rows));
      memset(cols,0,sizeof(cols));
   
      for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                  scanf("%d",&num);
                  rows[i][num]++;
                  cols[j][num]++;
                  cell33[i/3][j/3][num]++;
                  board[i][j]=num;
            }
      }
      for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
                  int num=board[i][j];
                  if(rows[i][num]>1||cols[j][num]>1||cell33[i/3][j/3][num]>1){
                        printf("*%d",num);
                  }else{
                        printf(" %d",num);
                  }
            }
            printf("\n");
      }
}

int main(){
      int n;
      scanf("%d",&n);
      for(int i=0;i<n;i++){
            check();
            if(i+1<n)printf("\n");
      }
}

会津大学オンラインジャッジ 問125

Day Count
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0125
２つの日付の間の日数をこたえる問題。


ネット上に転がっていた日数計算公式をそのまま採用。
http://ufcpp.net/study/algorithm/o_days.html



#include<stdio.h>
int calcDays(int y,int m,int d){
if(m<=2){
--y;
m+=12;
}
int dy=365*(y-1);
int c=y/100;
int dl=(y>>2)-c+(c>>2);
int dm=(m*979-1033)>>5;
return dy+dl+dm+d-1;
}

int main(){
int y,m,d,y1,m1,d1;
while(scanf("%d %d %d %d %d %d",&y,&m,&d,&y1,&m1,&d1)!=EOF){
if(y1==-1)break;
printf("%d\n",calcDays(y1,m1,d1)-calcDays(y,m,d));
}
}

会津大学オンラインジャッジ 問124

League Match Score Sheet

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0124
サッカー試合のスコアを計算する問題。


#include<stdio.h>
#include<string>
#include<iostream>
#include<queue>

struct S{
std::string name;
int score,no;
bool operator<(const S& s)const{
if(score!=s.score)return score<s.score;
return no>s.no;
}
};

void rank(int n){
S s;
int v,loss,b;
std::priority_queue<S> pq;
for(int i=0;i<n;i++){
std::cin>>s.name>>v>>loss>>b;
s.no=i;
s.score=v*3+b;
pq.push(s);
}
while(pq.empty()==false){
s=pq.top();
pq.pop();
std::cout<<s.name<<","<<s.score<<"\n";
}

}

int main(){
int n,c=0;
while(scanf("%d",&n)!=EOF){
if(n==0)break;
if(c>0)printf("\n");
rank(n);
c++;
}
}

会津大学オンラインジャッジ 問123

Speed Skating Badge Test

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0123
スピードスケートのランク付けを行う問題。
500ｍでＡＡランクなら1000ｍでＡＡＡをとっても意味がない。
これを利用して1000m判定のｒ２の検証を減らします。
こういう簡単な判定では意味がありませんが重たい判定ではこういう小手先のテクニックもすこしは役に立つかもしれません。
まあその前にバイナリサーチを導入するとは思いますが。


#include<stdio.h>

int main(){
char kekka[8][4]={
"AAA",
"AA",
"A",
"B",
"C",
"D",
"E",
"NA"};
double M500[8] ={35.5,37.5,40,43,50,55,70};
double M1000[8]={71,77,83,89,105,116,148};
double t500,t1000;
while(scanf("%lf %lf",&t500,&t1000)!=EOF){
int r1=7,r2=7;
for(int i=0;i<7;i++){
if(t500<M500[i]){
r1=i;
break;
}
}
for(int i=r1;i<7;i++){
if(t1000<M1000[i]){
r2=i;
break;
}
}
printf("%s\n",kekka[r2]);
}
}

会津大学オンラインジャッジ 問122

Summer of Phyonkichi
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

カエルのぴょんきちが夏を乗り切れるかをこたえる問題。
動的計画法で十分です。



#include<stdio.h>
#include<set>
#include<stdlib.h>

struct S{
int x,y;
bool operator<(const S& s)const{
if(x!=s.x)return x<s.x;
return y<s.y;
}
};

void search(int x,int y){
S s1;
s1.x=x;
s1.y=y;
std::set<S> sets[2];
sets[0].insert(s1);
int n;
scanf("%d",&n);
int dx[]={ 2, 2, 2, 1, 1, 0, 0,-1,-1,-2,-2,-2};
int dy[]={ 1, 0,-1, 2,-2, 2,-2, 2,-2, 1, 0,-1};
int sx,sy,now,next;
for(int i=0;i<n;i++){
scanf("%d %d",&sx,&sy);
now =i%2;
next=(i+1)%2;
for(std::set<S>::iterator it=sets[now].begin();it!=sets[now].end();it++){
s1=(*it);
for(int j=0;j<12;j++){
s1.x+=dx[j];
s1.y+=dy[j];
if(0<=s1.x||s1.x<=9||0<=s1.y||s1.y<=9){
if(abs(sx-s1.x)<=1&&abs(sy-s1.y)<=1){
sets[next].insert(s1);
}
}
s1.x-=dx[j];
s1.y-=dy[j];
}
}
sets[now].clear();
}
printf("%s\n",sets[next].empty()==false?"OK":"NA");
}

int main(){
int x,y;
while(scanf("%d %d",&x,&y)!=EOF){
if(x==0&&y==0)break;
search(x,y);
}
}

会津大学オンラインジャッジ問121

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121

セブンパズルを題材にした問題。



平凡な問題なので平凡なコードで平凡な順位。

平凡な問題と考え
平凡なコードで理解をし
平凡なコードの手順を考え
平凡なコードを実装し
平凡なコードを提出し
平凡な結果を期待し
平凡な順位に落ち着く。
私こそミスター平凡。


完全ハッシュ関数を実装すればもう少し早くはなるとおもいます。



#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>

struct S{
int zeroP,count;
int board[8];
bool operator<(const S& s)const{
for(int i=0;i<8;i++){
if(board[i]!=s.board[i])return board[i]<s.board[i];
}
return false;
}
};

int main(){
int moves[8][3]={{0,1,4},
{0,2,5},
{1,6,3},
{2,7,3},
{0,5,4},
{1,4,6},
{2,5,7},
{3,6,7}};
S s,s2;
s.zeroP=0;
s.count=0;
for(int i=0;i<8;i++){
s.board[i]=i;
}
std::map<S,int> memo;
std::queue<S> qu;
qu.push(s);
while(qu.empty()==false){
s=qu.front();
qu.pop();
if(memo.find(s)!=memo.end())continue;
memo[s]=s.count;
s.count++;

for(int i=0;i<3;i++){
s2=s;
s2.zeroP=moves[s.zeroP][i];
if(s.zeroP==s2.zeroP)continue;
std::swap(s2.board[s.zeroP],s2.board[s2.zeroP]);
if(memo.find(s2)!=memo.end())continue;
qu.push(s2);
}
}
while(1){
if(scanf("%d",&s.board[0])==EOF)break;
for(int i=1;i<8;i++){
scanf("%d",&s.board[i]);
}
printf("%d\n",memo[s]);
}
}

プロジェクトオイラー 失敗作 問258

プロジェクトオイラー問258を解くコードを書こうとして失敗しました。


解法
数字列を2000個ごとで一行として、その行から次の行を求める漸化式を考えます。
漸化式を立てると一行先を求める漸化式の係数から2行先を求める漸化式の係数が。
2行先を求める漸化式の係数から4行先がと求まります。
以後同じ処理を繰り返すことで2倍2倍で増える先の行を求める漸化式が手に入ります。
がこれは10＾18をそのまま愚直に求めるのより単純計算200万倍速いだけで、ループ処理が入るのでさらに遅くなり、コードを実行したところ正しい答えが出るまで23時間もかかりました。
私の使ってるパソコンかＢＣＣ5.5どちらが悪いのかわかりませんがコンパイル結果のＭｏｄ演算が妙に遅いということを加味してもこれは恥ずべき結果です。




#include<stdio.h>
#include<iostream>
#include<string.h>
#include<vector>


const int LIMITER=2000;
const __int64 MOD=20092010;

struct Vec{
__int64 es[LIMITER];
void add_and_mult(Vec& v,int t){
for(int i=0;i<LIMITER;i++){
es[i]=(es[i]+v.es[i]*t)%MOD;
}
}
void reset(){
memset(es,0,sizeof(es));
}
};

int main(){
std::vector<Vec> dp[2];
Vec v1,v2,v3;
__int64 row=pow(10,18);
row=row/LIMITER;
std::cout<<row<<"\n";
v1.reset();
for(int i=0;i<LIMITER;i++){
dp[1].push_back(v1);
}

for(int i=0;i+1<LIMITER;i++){
v1.reset();
v1.es[i]=v1.es[i+1]=1;
dp[0].push_back(v1);
}
v1.reset();
v1.es[0]=v1.es[1]=v1.es[LIMITER-1]=1;
dp[0].push_back(v1);

__int64 rowData[2][LIMITER];
for(int i=0;i<LIMITER;i++)rowData[0][i]=1;
__int64 add,ans=1;
int turn=0;
int point=0;
while(row>0){
std::cout<<"\n row="<<row<<" ";
if(row%2==1){
int now=point;
int next=(point+1)%2;
int now1=turn%2;
memset(rowData[next],0,sizeof(rowData[next]));
for(int i=0;i<LIMITER;i++){
for(int j=0;j<LIMITER;j++){
add=(rowData[now][j]*dp[now1][i].es[j])%MOD;
rowData[next][i]=(rowData[next][i]+add)%MOD;
}
}
std::cout<<" ans="<<rowData[next][0];
point=(point+1)%2;
ans=rowData[next][0];
}
int now=turn%2;
int next=(turn+1)%2;
for(int i=0;i<LIMITER;i++){
dp[next][i].reset();
for(int j=0;j<LIMITER;j++){
if(dp[now][i].es[j]==0)continue;
dp[next][i].add_and_mult(dp[now][j],dp[now][i].es[j]);
}
}
turn++;
row/=2;
}
std::cout<<"\n lastAns="<<ans;
}