xxxasdfghjk999のブログ

iroiro

AtCoder-Typical DP Contest B問題をやりました

プログラミング備忘録

前回に続いてB問題も解いてみました。
問題文以下
B: ゲーム - Typical DP Contest | AtCoder

Problem Statement
すぬけ君とすめけ君がゲームをしている。最初に、二つの山がある。左の山には A 個の物が積まれており、上から i 番目のものの価値は ai である。左の山には B 個の物が積まれており、上から i 番目のものの価値は bi である。すぬけ君とすめけ君は、すぬけ君からはじめて交互に次の操作を繰り返す。

    両方の山が空であれば、ゲームを終了する。
    片方の山が空であれば、空でないほうの山の一番上のものをとる。
    両方の山が空でなければ、好きなほうの山を選び、一番上のものをとる。

両者が最善を尽くしたとき、すぬけ君の取るものの価値の合計を求めよ。
Constraints

    1≤A,B≤1000
    1≤ai,bi≤1000

Input Format
入力は以下の形式で標準入力から与えられる。

A B
a1…aA
b1…bB

ソースは続きから

続きを読む

AtCoder-Typical DP Contest A問題を解きました

プログラミング備忘録

AtCoderのTypical DP ContestのA問題を解いてみました

AtCoderというのは、毎週アルゴリズム系のプログラミングコンテストを開催している所謂競プロの主催者です。
このコンテストの問題は、コンテスト後も公開されているので練習がてら解くことができます。
その中でもTypical DP Contestというのは、動的計画法(Dynamic Programming)と呼ばれるアルゴリズムを用いて
解ける典型的な問題を集めたコンテストとなっています。といえども、初心者のうちは、DPで自分でパラメータを設定することが難しく、典型的とはいってもなかなか骨のある問題集となっています。

今回解いたのはTypical DP のA問題です。問題文は以下
A: コンテスト - Typical DP Contest | AtCoder

Problem Statement
N 問の問題があるコンテストがあり、i 問目の問題の配点は pi 点である。コンテスタントは、
この問題の中から何問か解き、解いた問題の配点の合計が得点となる。
このコンテストの得点は何通り考えられるか。
Constraints

    1≤N≤100
    1≤pi≤100

Input Format
入力は以下の形式で標準入力から与えられる。

N
p1p2…pN

書いたソースは続きより

続きを読む

6/25のTOEICの結果

6/25に受けたTOEICの結果が帰ってきました。

続きを読む

生きる意味

a

続きを読む

キュー

備忘録プログラミング

キュー

#include<stdio.h>
#include<stdlib.h>
typedef struct cell{
  int id;
  struct cell *next;
}Cell;

typedef struct que{
  Cell* front;
  Cell* rear;
}Queue;

Queue *make_queue()
{
  Queue *que = malloc(sizeof(Queue));
  que->front = NULL;
  que->rear = NULL;
  return que;
}
int enqueue(Queue *que,int item)
{
  Cell *cel = malloc(sizeof(Cell));
  cel->next = NULL;
  cel->id = item;
  if(!(que->rear)){
    que->front = cel;
    que->rear = cel;
  }else{
    que->rear->next = cel;
    que->rear = cel;
    return 1;
  }
  return 0;
}

Cell* dequeue(Queue *que)
{
  Cell* cel = que->front;
  if(que->front)
    que->front = que->front->next;
  if(que->front == NULL)
    que->rear = NULL;
  return cel;
}

int main()
{
  Queue *q = make_queue();
  int i;
  Cell* c;
  for(i=0;i<10;i++)
    enqueue(q,i);
  for(;c=dequeue(q);)
    printf("%d\n",c->id);
  return 0;

}

実行結果

キュー

ぎゅっとeeeeeがおわりました！！！

もう夏休み気分
うれしーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー

双方向連結リストのインサートソートの書き直し

プログラミング備忘録

前記事で使ったダブルポインタを利用して書き換えました

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAX 30
typedef struct link_tag{
  struct link_tag *next;
  struct link_tag *prev;
  int id;
}linked_list;
void delete_element(linked_list*,int);
void insert_sort(linked_list**);
void insert_list(linked_list*,linked_list*);
void sub_sort(linked_list**,linked_list*);
void regist_element(linked_list**,linked_list*);
int count_list(linked_list*);
linked_list* head_point(linked_list*);
linked_list* create_element(int);
int main()
{
  int i;
  linked_list *head=NULL,*p;
  srand((unsigned)time(NULL));
  for(i=0;i<MAX;i++)
    regist_element(&head,create_element(rand()%MAX));
  for(p=head,i=1;p;p=p->next,i++)
    printf("%d : %d\n",i,p->id);
  printf("sorted : \n");
  insert_sort(&head);
  for(p=head,i=1;p;i++,p=p->next)
    printf("%d : %d\n",i,p->id);
  printf("\n");
  return 0;
}

int count_list(linked_list *list)
{
  int i=0;
  while(list){
    i++;
    list = list->next;
  }
  return i;
}
linked_list* create_element(int id)
{
  linked_list* new;
  if(!(new = (linked_list*)malloc(sizeof(linked_list)))){
    fprintf(stderr,"failed secure memory\n");
    exit(1);
  }
  new->next = NULL;
  new->prev = NULL;
  new->id = id;
  return new;
}
void regist_element(linked_list **former,linked_list* latter)
{
  linked_list *p;
  if(*former == NULL){
    *former = latter;
    return;
  }
  p = *former;
  while(p->next)
    p = p->next;
  p->next = latter;
  latter->prev = p;
}

void insert_sort(linked_list **head)
{
  linked_list *p,*n;
  p = (*head)->next;
  (*head)->next = NULL;
  while(p){
    n = p->next;
    sub_sort(head,p);
    p = n;
  }
}

void sub_sort(linked_list **head,linked_list *el)
{
  linked_list *p = *head;
  if(p->id > el->id){
    el->next = *head;
    (*head)->prev = el;
    *head = el;
    return;
  }
  while(p->next){
    if(p->next->id < el->id)
        p = p->next;
    else
      break;
  }
    insert_list(p,el);
}

void insert_list(linked_list* p,linked_list* t)
{
  if(p->next){
    p->next->prev = t;
  }
  t->next = p->next;
  p->next = t;
  t->prev = p;
}

実行結果

メイン関数のfor文をいつもとは変わった書き方をしてみました