会津大学オンラインジャッジALDS 問0~20まで
Getting Started - Insertion Sort
挿入ソートのステップを表示していく問題。
解法
挿入ソートが何をしているかイメージできたら何の問題もない問題です。
要は数字列を左から整列していき、右へ進むだけです。
右で新しい数字が来たら左にさかのぼって入れる位置を決め、そこまでにいる数を全て右へ一つずつずらします。
#include<stdio.h>
static const int N = 1000;
void trace(int A[], int n){
int i;
for ( i = 1; i <= n; i++ ){
if ( i > 1 ) printf(" ");
printf("%d", A[i]);
}
printf("\n");
}
int main(){
int n, i, j;
int A[N+1];
scanf("%d", &n);
for ( i = 1; i <= n; i++ ) scanf("%d", &A[i]);
trace(A, n);
for(int j=2;j<=n;j++){
int key=A[j];
i=j-1;
while(i > 0 && A[i]>key){
A[i+1]=A[i];
i--;
}
A[i+1]=key;
trace(A,n);
}
return 0;
}
Getting Started - Greatest Common Divisor
#include<stdio.h>
int gcd(int a,int b){
int c;
while(a!=0){
c=a;
a=b%a;
b=c;
}
return b;
}
int main(){
int a,b;
scanf("%d %d",&a,&b);
printf("%d\n",gcd(a,b));
}
Getting Started - Prime Numbers
#include<stdio.h>
#include<vector>
std::vector<int> prime_list;
void calc_prime_list(){
int is_prime[10001]={0};
for(int i=2;i<400;i++){
if(is_prime[i]==1)continue;
for(int j=i*2;j<10001;j+=i){
is_prime[j]=1;
}
}
for(int i=2;i<10001;i++){
if(is_prime[i]==0)prime_list.push_back(i);
}
}
bool prime_check(int n){
for(int i=0;i<prime_list.size();i++){
int p=prime_list[i];
if(p*p>n)break;
if(n%p==0)return false;
}
return true;
}
int main(){
calc_prime_list();
int n,ans=0,num;
scanf("%d",&n);
while(n--){
scanf("%d",&num);
ans+=prime_check(num);
}
printf("%d\n",ans);
}
Sort I - Bubble Sort
#include<stdio.h>
void print(int A[],int n){
for(int i=1;i<n;i++)printf("%d ",A[i]);
printf("%d\n",A[n]);
}
int main(){
int A[102],n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=1;i<=n;i++){
for(int j=n;j>i;j--){
if(A[j]<A[j-1]){
int t=A[j-1];
A[j-1]=A[j];
A[j]=t;
ans++;
}
}
}
print(A,n);
printf("%d\n",ans);
}
Sort I - Selection Sort
#include<stdio.h>
void print(int A[],int n){
for(int i=1;i<n;i++)printf("%d ",A[i]);
printf("%d\n",A[n]);
}
int main(){
int A[102],n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=1;i<=n;i++){
int mini=i;
for(int j=i;j<=n;j++){
if(A[j]<A[mini]){
mini=j;
}
}
if(i!=mini){
int t=A[i];
A[i]=A[mini];
A[mini]=t;
ans++;
}
}
print(A,n);
printf("%d\n",ans);
}
Sort I - Stability
解法
バブルソートは無条件で安定なので常にStableです。
選択ソートは左側を決めてそれと入れ替える数を右側で探す際。
最初に入れ替える数と同じ数が出会った場所をPとし。
そのPより右側で最も小さい数が見つかった場合安定でなくなります。
#include<stdio.h>
#include<algorithm>
#include<string.h>
void print(char A[37][3],int n){
for(int i=1;i<n;i++)printf("%s ",A[i]);
printf("%s\n",A[n]);
}
void BubbleSort(char A[37][3],int n){
for(int i=1;i<=n;i++){
for(int j=n;j>i;j--){
if(A[j][1]<A[j-1][1]){
std::swap(A[j-1][0],A[j][0]);
std::swap(A[j-1][1],A[j][1]);
}
}
}
print(A,n);
printf("Stable\n");//バブルソートは常に安定
}
void SelectionSort(char A[37][3],int n){
bool isStable=true;
for(int i=1;i<=n;i++){
int mini=i,p;
p=mini;
for(int j=i;j<=n;j++){
if(A[j][1]<A[mini][1]){
mini=j;
}else if(A[j][1]==A[i][1]&&i==p){
p=j;
}
}
if(i!=mini){
std::swap(A[i][0],A[mini][0]);
std::swap(A[i][1],A[mini][1]);
if(i<p&&p<mini)isStable=false;
}
}
print(A,n);
printf("%s\n",isStable?"Stable":"Not stable");
}
int main(){
int n;
char A[37][3],B[37][3];
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%s",A[i]);
}
memcpy(B,A,sizeof(A));
BubbleSort(A,n);
SelectionSort(B,n);
}
Elementary data structures - Reverse Polish Notation
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
int main(){
int x,x1,x2;
std::stack<int> Stack;
char s[100];
while( scanf("%s", s) != EOF ){
if ( s[0] == '+' ){
x1=Stack.top();
Stack.pop();
x2=Stack.top();
Stack.pop();
Stack.push(x1+x2);
} else if ( s[0] == '-' ){
x1=Stack.top();
Stack.pop();
x2=Stack.top();
Stack.pop();
Stack.push(x2-x1);
} else if ( s[0] == '*' ){
x1=Stack.top();
Stack.pop();
x2=Stack.top();
Stack.pop();
Stack.push(x1*x2);
} else {
Stack.push(atoi(s));
}
}
printf("%d\n",Stack.top());
return 0;
}
Elementary data structures - Round-Robin Scheduling
解法
queueで回せば一発です。
#include<iostream>
#include<queue>
#include<string>
struct S{
std::string name;
int time;
};
int main(){
int n,q;
std::queue<S> qu;
std::cin>>n>>q;
S s;
for(int i=0;i<n;i++){
std::cin>>s.name>>s.time;
qu.push(s);
}
int time=0;
while(qu.empty()==false){
s=qu.front();
qu.pop();
if(s.time-q<=0){
time+=s.time;
std::cout<<s.name<<" "<<time<<"\n";
}else{
time+=q;
s.time-=q;
qu.push(s);
}
}
}
Elementary data structures - Doubly Linked List
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node{
unsigned int key;
struct node *next;
struct node *prev;
};
typedef struct node * NodePointer;
NodePointer nil;
NodePointer listSearch(int key){
/* your code */
NodePointer cur=nil->next;
while(1){
if(cur==nil)return cur;
if(cur->key==key)return cur;
cur=cur->next;
}
}
void init(){
nil = malloc(sizeof(struct node));
nil->next = nil;
nil->prev = nil;
}
void printList(){
NodePointer cur = nil->next;
int isf = 1;
while(1){
if ( cur == nil ) break;
if ( isf == 0) printf(" ");
printf("%d", cur->key);
cur = cur->next;
isf = 0;
}
printf("\n");
}
void deleteNode(NodePointer t){
/* your code */
NodePointer cur ,prev;
if(t!=nil){
cur=t->next;
prev=t->prev;
prev->next=cur;
cur->prev=prev;
if(t->next==nil){
nil->prev=prev;
prev->next=nil;
}
free(t);
}
}
void deleteFirst(){
NodePointer t = nil->next;
if ( t == nil ) return;
deleteNode(t);
}
void deleteLast(){
/* your code */
NodePointer cur=nil->prev;
if(cur==nil)return;
deleteNode(cur);
}
void delete(int key){
/* your code */
NodePointer t;
t=listSearch(key);
if(t==nil)return ;
deleteNode(t);
}
void insert(int key){
NodePointer x;
x = malloc(sizeof(struct node));
x->key = key;
/*
your code
*/
if(nil->next==nil){
nil->prev=x;
}
x->next=nil->next;
x->prev=nil;
nil->next->prev=x;
nil->next=x;
}
int main(){
int key, n, i;
int size = 0;
char com[20];
int np = 0, nd = 0;
scanf("%d", &n);
init();
for ( i = 0; i < n; i++ ){
scanf("%s", com);
if ( com[0] == 'i' ) {
scanf("%d",&key);
insert(key); np++; size++;
}
else if ( com[0] == 'd' ) {
if (strlen(com) > 6){
if ( com[6] == 'F' ) deleteFirst();
else if ( com[6] == 'L' ) deleteLast();
} else {
scanf("%d",&key);
delete(key); nd++;
}
size--;
}
}
printList();
return 0;
}
Search - Search I
#include<stdio.h>
#include<algorithm>
int main(){
int S[10001],T[501],n,q,ans=0,p1=0,p2=0;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&S[i]);
scanf("%d",&q);
for(int i=0;i<q;i++)scanf("%d",&T[i]);
std::sort(S,S+n);
std::sort(T,T+q);
while(p1<n&&p2<q){
if(S[p1]==T[p2]){
ans++;
p1++;
p2++;
}else if(S[p1]<T[p2]){
p1++;
}else{
p2++;
}
}
printf("%d\n",ans);
}
Search - Search II
#include<stdio.h>
#include<algorithm>
int main(){
int S[100001],T[50001],n,q,ans=0,p1=0,p2=0;
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&S[i]);
scanf("%d",&q);
for(int i=0;i<q;i++)scanf("%d",&T[i]);
std::sort(T,T+q);
while(p1<n&&p2<q){
if(S[p1]==T[p2]){
ans++;
p1++;
p2++;
}else if(S[p1]<T[p2]){
p1++;
}else{
p2++;
}
}
printf("%d\n",ans);
}
Search - Search III
まあそのstd::setを使えば一発だったんだけど。
一応ハッシュテーブルの学習用問題だと考えて計算。
ハッシュ関数の作りが適当なのはここだけの秘密、ただしい32ビットハッシュ関数の作り方ってどんなんだろう?
AOJやっててよかったことは今のところ何もないので、評価値が下がろうが気にしない。
#include<stdio.h>
#include<string.h>
#include<list>
const int LIMIT =((1<<16)+33);
std::list<int> hashTable[LIMIT];
int h1(char *str){
int p,p1,num,result=0;
char c;
for(p=0;p<strlen(str);p++){
c=str[p];
num=0;
if(c=='A')num=0;
if(c=='C')num=1;
if(c=='G')num=2;
if(c=='T')num=3;
p1=(p%8)*2;
result=((num<<p1)^result);
}
return result%LIMIT;
}
int h2(char *str){
int num,result=0,b=1;
char c;
for(int p=0;p<strlen(str);p++){
c=str[p];
num=1;
if(c=='A')num=1;
if(c=='C')num=2;
if(c=='G')num=3;
if(c=='T')num=4;
result+=num*b;
b*=5;
}
return result;
}
bool find(char *str){
int H1=h1(str);
int H2=h2(str);
for(std::list<int>::iterator it=hashTable[H1].begin();it!=hashTable[H1].end();it++){
if(H2==(*it))return true;
}
return false;
}
void insert(char *str){
if(find(str)==false){
hashTable[h1(str)].push_front(h2(str));
}
}
int main(){
int n;
char str[14],com[10];
scanf("%d",&n);
while(n--){
scanf("%s %s",com,str);
if(com[0]=='i'){
insert(str);
}else{
printf("%s\n",find(str)?"yes":"no");
}
}
}
Recursion / Divide and Conquer - Brute Force
#include<stdio.h>
#include<string.h>
int main(){
int n,q,a,sum=0,m;
bool memo[40001];
memset(memo,0,sizeof(memo));
memo[0]=true;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a);
for(int j=sum;j>=0;j--){
memo[j+a]=memo[j+a]||memo[j];
}
sum+=a;
}
scanf("%d",&q);
for(int i=0;i<q;i++){
scanf("%d",&m);
printf("%s\n",memo[m]?"yes":"no");
}
}
Recursion / Divide and Conquer - Merge Sort
マージソートを実装する問題。
指定通り記述するだけです。
マージソートは一番小さい単位まで分解してその中身をソート済みにする。
戻ってきた時に、ソート済みの両側を小さいほうからマージしていく。
イメージができていれば簡単な問題。
#include<stdio.h>
#include<string.h>
const int SENTINEL=2147483647 ;
int count=0;
void Merge(int* A,int left,int mid,int right){
int n1=mid-left;
int n2=right-mid;
int *L=new int[n1+1];
int *R=new int[n2+1];
for(int i=0;i<=n1-1;i++)L[i]=A[left+i];
for(int i=0;i<=n2-1;i++)R[i]=A[mid+i];
int i=0,j=0;
L[n1]=R[n2]=SENTINEL;
for(int k=left;k<=right-1;k++){
count++;
if(L[i]<=R[j]){
A[k]=L[i];
i++;
}else{
A[k]=R[j];
j++;
}
}
delete []L;
delete []R;
}
void Merge_Sort(int *A,int left,int right){
if(left+1<right){
int mid=(left+right)/2;
Merge_Sort(A,left,mid);
Merge_Sort(A,mid,right);
Merge(A,left,mid,right);
}
}
int main(){
int n;
int *A=new int[500001];
scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&A[i]);
Merge_Sort(A,0,n);
for(int i=0;i<n;i++){
if(i>0)printf(" ");
printf("%d",A[i]);
}
printf("\n%d\n",count);
delete []A;
}
Recursion / Divide and Conquer - Koch Curve
#include<stdio.h>
#include<math.h>
int n;
const double toR=M_PI/180.0;
void saiki(double px,double py,double len,double r,int deep){
if(deep==n){
if(px<0)px=-px;
if(py<0)py=-py;
printf("%lf %lf\n",px,py);
return ;
}
double nx,ny,len1;
len1=len/3.0;
saiki(px,py,len1,r,deep+1);
nx=px+len1*cos(r*toR);
ny=py+len1*sin(r*toR);
saiki(nx,ny,len1,r+60,deep+1);
nx+=len1*cos((r+60)*toR);
ny+=len1*sin((r+60)*toR);
saiki(nx,ny,len1,r-60,deep+1);
nx+=len1*cos((r-60)*toR);
ny+=len1*sin((r-60)*toR);
saiki(nx,ny,len1,r,deep+1);
}
int main(){
scanf("%d",&n);
saiki(0,0,100,0,0);
double a=100,b=0;
printf("%lf %lf\n",a,b);
}
Sort II - Counting Sort
小さいほうから尺取虫法的に積み上げていって。
最後に引きながら位置を決定していく。
4 4 4 1 1 1 5 5
ソート後
1 1 1 4 4 4 5 5
なら
4を含む4までの数は6回数えられてるから6,5,4か所目に入るというのを最後の処理でやっている。
なるほどいろいろな手を考えるものだと感心。
#include<stdio.h>
#include<math.h>
const int LIMIT=2000001;
int C[10001];
int n;
int A[LIMIT],B[LIMIT];
void Counting_Sort(int *A,int *B,int k){
for(int i=0;i<=k;i++)C[i]=0;
for(int j=1;j<=n;j++){
C[A[j]]++;
}
for(int i=1;i<=k;i++){
C[i]+=C[i-1];
}
for(int j=n;j>=1;j--){
B[C[A[j]]]=A[j];
C[A[j]]--;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
Counting_Sort(A,B,10000);
for(int i=1;i<=n;i++){
if(i>1)printf(" ");
printf("%d",B[i]);
}
printf("\n");
}
Sort II - Partition
#include<stdio.h>
#include<math.h>
const int LIMIT=100001;
int Partition(int *A,int p,int r){
int x=A[r];
int i=p-1;
for(int j=p;j<=r-1;j++){
if(A[j]<=x){
i++;
int t=A[i];
A[i]=A[j];
A[j]=t;
}
}
int t=A[i+1];
A[i+1]=A[r];
A[r]=t;
return i+1;
}
int main(){
int A[LIMIT],n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
int result=Partition(A,1,n);
for(int i=1;i<result;i++){
if(i>1)printf(" ");
printf("%d",A[i]);
}
printf(" [%d]",A[result]);
for(int i=result+1;i<=n;i++){
printf(" %d",A[i]);
}
printf("\n");
}
Sort II - Quick Sort
クイックソートは定義通り、あと順番が違ってるかは番号割り振ってそれが入れ替わっていたらに変更。
#include<stdio.h>
#include<math.h>
#include<set>
struct S{
int n,no;
char c;
bool operator<=(const S &s)const{
return n<=s.n;
}
};
const int LIMIT=100001;
S A[LIMIT];
int Partition(S *A,int p,int r){
S x=A[r];
int i=p-1;
for(int j=p;j<=r-1;j++){
if(A[j]<=x){
i++;
S t=A[i];
A[i]=A[j];
A[j]=t;
}
}
S t=A[i+1];
A[i+1]=A[r];
A[r]=t;
return i+1;
}
void Quicksort(S *A,int p,int r){
if(p<r){
int q=Partition(A,p,r);
Quicksort(A,p,q-1);
Quicksort(A,q+1,r);
}
}
int main(){
S s;
int n;
char c;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%c%c %d",&c,&A[i].c,&A[i].n);
A[i].no=i;
}
Quicksort(A,1,n);
bool isStable=true;
for(int i=1;i<n;i++){
if(A[i].n==A[i+1].n&&A[i].no>A[i+1].no)isStable=false;
}
printf("%s\n",isStable?"Stable":"Not stable");
for(int i=1;i<=n;i++){
printf("%c %d\n",A[i].c,A[i].n);
}
}
Tree - Rooted Trees
#include<stdio.h>
#define MAX 100005
#define NIL -1
/*
p: parent
l: left-child
r: right sibling
*/
struct Node{ int p, l, r,d;};
struct Node T[MAX]; // Tree
int depth[MAX];
/*
*/
void print(int u){
/*
*/
printf("node %d: parent = %d, depth = %d, ",u,T[u].p,T[u].d);
if(T[u].p==-1){
printf("root, [");
}else if(T[u].l==NIL){
printf("leaf, [");
}else{
printf("internal node, [");
}
int p=T[u].l;
while(p!=NIL){
if(p==T[u].l)printf("%d",p);
else printf(", %d",p);
p=T[p].r;
}
printf("]\n");
}
void calc_depth(int deep,int p){
T[p].d=deep;
if(T[p].l==NIL)return;
for(p=T[p].l;p!=NIL;p=T[p].r){
calc_depth(deep+1,p);
}
}
int main(){
int i, j, d, v, c, l,n;
scanf("%d", &n);
for ( i = 0; i < n; i++ ) {
T[i].p = T[i].l = T[i].r = NIL;
}
for ( i = 0; i < n; i++ ){
scanf("%d %d", &v, &d);
int old=0;
for ( j = 0; j < d; j++ ){
scanf("%d", &c);
T[c].p=v;
if(j==0){
T[v].l=c;
}else{
T[old].r=c;
}
old=c;
}
}
int p;
for(int i=0;i<n;i++)if(T[i].p==-1)p=i;
calc_depth(0,p);
for ( i = 0; i < n; i++ ) print(i);
return 0;
}
Tree - Binary Trees
#include<stdio.h>
const int LIMIT=100001;
const int NIL=-1;
struct node{
int p,right,left,depth,height,sibling;
};
node Tree[LIMIT];
int calc_depthAndHeight(int p,int deep){
if(Tree[p].left==NIL&&Tree[p].right==NIL){
Tree[p].depth=deep;
Tree[p].height=0;
return 1;
}else{
int h1=-1,h2=-1,h3;
if(Tree[p].left!=NIL)h1=calc_depthAndHeight(Tree[p].left,deep+1);
if(Tree[p].right!=NIL)h2=calc_depthAndHeight(Tree[p].right,deep+1);
h3=h1>h2?h1:h2;
Tree[p].height=h3;
Tree[p].depth=deep;
return h3+1;
}
}
void print(int n){
for(int i=0;i<n;i++){
printf("node %d: parent = %d, sibling = %d, ",i,Tree[i].p,Tree[i].sibling);
int degree=(Tree[i].left!=-1)+(Tree[i].right!=-1);
printf("degree = %d, depth = %d, height = %d, ",degree,Tree[i].depth,Tree[i].height);
if(Tree[i].p==-1){
printf("root\n");
}else if(degree==0){
printf("leaf\n");
}else{
printf("internal node\n");
}
}
}
int main(){
int n,l,r,no;
scanf("%d",&n);
for(int i=0;i<n;i++)Tree[i].p=Tree[i].sibling=NIL;
for(int i=0;i<n;i++){
scanf("%d %d %d",&no,&l,&r);
Tree[no].left=l;
Tree[no].right=r;
Tree[l].p=Tree[r].p=no;
Tree[l].sibling=r;
Tree[r].sibling=l;
}
int p=0;
for(int i=0;i<n;i++)if(Tree[i].p==NIL)p=i;
int t=calc_depthAndHeight(p,0);
print(n);
}
最終更新:2014年01月17日 03:27