「AOJ Problem Set from ALDS1問 0～19」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
会津大学オンラインジャッジ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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B
ｇｃｄを実装する問題。
指定通り実装するだけです。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
与えられた数列の中に素数が何個あるか答える問題。
解法
1億までの数しか数列に現れないので、10000までの素数で試し割すれば素数かどうか判別できます。
10000までの素数の列は篩で求めます。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A
指定通りソートを記述するだけ。
数列の右端から初めて左端へ進みながら小さい数を選んで左右を入れ替えていく。
すると最初の右から左への一巡で、一番小さい数が左端にくる。
あとはそれから左端一個除いた部分で同じ処理を繰り返しこれを繰り返すと最後は全部ソートされる。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B
選択ソートを実装しソートの交換回数をこたえる問題。
選択ソートはまず配列を全部見て、一番小さいものを左端に持ってくる。
すると左端は一個でソートされ一番小さいものが左端に来て、残りは未ソートです。
2個めから全部精査しその中で一番小さいものを左から2番目に持ってくれば。
左は一番小さいものが左端に、その次に小さいのが左から2番目とこれを繰り返せばすべてソートされます。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C
バブルソートと選択ソートを行いそれがソート結果が安定であったかどうか判定する問題。
解法
バブルソートは無条件で安定なので常に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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_A
逆ポーランド記法の数式を処理する問題。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B
コンピュータのタスク処理手順を題材にした問題。
解法
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);
}
}
}
会津大学オンラインジャッジ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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_B
ｇｃｄを実装する問題。
指定通り実装するだけです。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_1_C
与えられた数列の中に素数が何個あるか答える問題。
解法
1億までの数しか数列に現れないので、10000までの素数で試し割すれば素数かどうか判別できます。
10000までの素数の列は篩で求めます。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A
指定通りソートを記述するだけ。
数列の右端から初めて左端へ進みながら小さい数を選んで左右を入れ替えていく。
すると最初の右から左への一巡で、一番小さい数が左端にくる。
あとはそれから左端一個除いた部分で同じ処理を繰り返しこれを繰り返すと最後は全部ソートされる。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_B
選択ソートを実装しソートの交換回数をこたえる問題。
選択ソートはまず配列を全部見て、一番小さいものを左端に持ってくる。
すると左端は一個でソートされ一番小さいものが左端に来て、残りは未ソートです。
2個めから全部精査しその中で一番小さいものを左から2番目に持ってくれば。
左は一番小さいものが左端に、その次に小さいのが左から2番目とこれを繰り返せばすべてソートされます。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_C
バブルソートと選択ソートを行いそれがソート結果が安定であったかどうか判定する問題。
解法
バブルソートは無条件で安定なので常に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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_A
逆ポーランド記法の数式を処理する問題。
#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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B
コンピュータのタスク処理手順を題材にした問題。
解法
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
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C
双方向リンクリストをCで実装する問題。
ポインタ苦手。
#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;
}
