ログインしてさらにmixiを楽しもう

コメントを投稿して情報交換!
更新通知を受け取って、最新情報をゲット!

情報オリンピックコミュのIOI2005を自分でやったソースを貼るトピ

  • mixiチェック
  • このエントリーをはてなブックマークに追加
練習がてら間違いがあっても貼ってみて意見交換をしませんか。

一行目は必ず問題名を入れましょう。
間違いがあるならばそれについて書きましょう。
もし他の人のソースに気付いたことがあればどんどんコメントしましょう。

スキルアップのためがんばってレッツコーディング★

コメント(10)

参考URL:

問題(日本語訳)
http://219.117.234.210/ioi/2005/problems.html

問題(英語)
http://contest.ioi2005.pl/user.phtml?op=zadania

入力データ
http://contest.ioi2005.pl/testdata/

生徒の解答例(ちょんぼ)
http://contest.ioi2005.pl/user.phtml?op=solutions

あとうpろだがあると楽かなあ?
// Imo_Birthday.cpp
// ※タブを残すためタブは全角空白に置き換えています
#include <cstdio>
#include <algorithm>
using namespace std;

int main(void) {
  int i, j, m, n; int *p, *q;

  scanf("%d", &n); p = new int[n]; q = new int[n];
  for (i = 0; i < n; i++) {
    scanf("%d", &j);
    p[i] = (i + j) % n; q[i] = (n + i - j) % n;
  }
  sort(p, p + n); sort(q, q + n);
  m = q[0] - q[n - 1] + n; j = p[0] - p[n - 1] + n;
  for (m = (j < m ? m : j), i = 1; i < n; i++) {
    if (m < p[i] - p[i - 1]) m = p[i] - p[i - 1];
    if (m < q[i] - q[i - 1]) m = q[i] - q[i - 1];
  }
  printf("%d\n", n / 2 - m / 2);
  return 0;
}
// Imo_Mean.c
#include <stdio.h>
int main(void) {int i,j,n,a,b,c;scanf("%d%d%d",&n,&b,&j);a=b+b-j;for(i=2;i<n;i++){
scanf("%d",&j);if(j<b)b=j;c=a;a=j+j-b;b=j+j-c;}printf("%d\n",b-a+1);return 0;}
import java.io.*;

public class Mean {
  public static void main(String[] args) throws Exception {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int count = Integer.parseInt(in.readLine());
    
    long min = Long.MIN_VALUE, max = Long.MAX_VALUE;
    long sum = 0, prevIn = 0;
    for(int i=1; i <= count; i++) {
      long curIn = Long.parseLong(in.readLine());
      if(i % 2 == 1) {
        // 奇数回目
        sum += -prevIn + curIn;
        max = Math.min(max, sum);
      } else {
        // 偶数回目
        sum += prevIn - curIn;
        min = Math.max(min, sum);
      }
      //System.out.println("sum = " + sum);
      //System.out.println("max = " + max + ", min = " + min);
      prevIn = curIn;
    }
    if(max >= min)
      System.out.println("" + (max - min + 1));
    else
      System.out.println(0);
  }
}
↑
アルゴリズムで悩むところは全くないのですが、
いかにミスしないかという、センター試験的問題ですね。

Imoくんの解答に関して
・[1, 5, 7, -1] だと0にならずに、負の答えが出るよ。
・a, b は long long(64ビット) にしないと、オーバーフローするケースがあると思う。
#include<stdio.h>

int main(void){
  int n;
  int min,max;
  int m;
  int ev,od;
  int tmp,i;
  scanf("%d",&n);
  min=-2000000000;
  max=2000000000;
  ev=0;
  while(n>0){
    scanf("%d",&m);
    od=m-ev;
    tmp=od-ev;
    if(tmp<max){
      max=tmp;
    }
    n--;
    if(n==0)break;
    scanf("%d",&m);
    ev=m-od;
    tmp=od-ev;
    if(tmp>min){
      min=tmp;
    }
    n--;
  }
  tmp=max-min+1;
  if(tmp<0)tmp=0;
  printf("%d\n",tmp);
  return 0;
}
↑
オーバーフロー対策していないような雰囲気だな……
0以上mが1兆以下より答えは1兆1以下なので
答えがある場合のm[0]のmin,maxは-1兆から1兆の間に制限されintで答えを書くことに問題はありません。
しかし、最後のほうの
if(tmp<0)tmp=0;
は
if(min>max)tmp=0;
とすべきだったように思います。
さあIOI2005の問題が通信添削課題になってしまった今
このスレは嘆きを書き込むスレとなりました


むずいんだよばかー。
人気が無くなったここに
人気が無いMountainsのコードでも貼り付けますね。

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

typedef struct _tag_lnode {
 int pos;
 int d;
 struct _tag_lnode* next;
} lnode;

lnode* head = NULL;
int n;

void init_list() {
 head = (lnode*)malloc(sizeof(lnode));
 head->pos = 0; head->d = 0;
 head->next = NULL;
}

void modify(int a, int b, int D) {
 lnode *la, *lb, *p, *q;

 la = (lnode*)malloc(sizeof(lnode));
 lb = (lnode*)malloc(sizeof(lnode));
 la->pos = a-1; lb->pos = b; la->d = D;
 la->next = lb;

 p = head;
 while (p->next != NULL && p->next->pos < a) p = p->next;
 q = p;
 while (q->next != NULL && q->next->pos < b) q = q->next;
 lb->next = q->next; lb->d = q->d;
 p->next = la;
 
 return;
}

int ride(int h) {
 lnode* p = head;
 int posy = 0, nextposy, r;

 while (1) {
  if (p->next == NULL) {
   if (p->d == 0 || n <= (r = (n - p->pos) / p->d))
    return n;
   else return r;
  } else {
   nextposy = posy + (p->next->pos - p->pos) * p->d;
   if (nextposy <= h) {
    posy = nextposy;
    p = p->next;
   } else {
    return p->pos + (h - posy) / p->d;
   }
  }
 }
}

void show_list() {
 lnode* p; int i = 0;
 for (p = head; p != NULL; p = p->next) {
  printf("[(%d)%d:%d]->", i++, p->pos, p->d);
 }
 printf("NULL\n");
}

int main() {
 char c;
 int a, b, D, h;
 
 scanf("%d", &n);
 init_list();

 while (1) {
  scanf("%1c", &c);
  switch (c) {
  case 'E':
   return 0;
  case 'I':
   scanf("%d %d %d", &a, &b, &D);
   modify(a, b, D);
   // show_list();
   break;
  case 'Q':
   scanf("%d", &h);
   printf("%d\n", ride(h));
   break;
  }
 }
 
 return 0;
}


mou13.in〜mou19.inあたりの2MB級の入力ファイルには対応していない不良品です。
どうやりゃ打開できるんだー?
あからさまにリストがいけない気がしますね・・。
ああ!こんなことしてたのか!
来るのが遅かった・・・。
だいぶ遅いですが,誤った指摘がされているので正しておきます.

>小林悠さん
m[i] は単調増加数列という記述がありますので [1,5,7,-1] という列は入力として与えられません(第二段落の冒頭部分を参照).それと s[i] が最大値をとるのは M=[0,1G] に対して S=[0,0,2G] とした場合なので 32 ビットでおさまるはずです.

>tosさん
m[i] は単調増加数列なので最低ひとつは解がありますよ.

ログインすると、みんなのコメントがもっと見れるよ

mixiユーザー
ログインしてコメントしよう!

情報オリンピック 更新情報

情報オリンピックのメンバーはこんなコミュニティにも参加しています

星印の数は、共通して参加しているメンバーが多いほど増えます。

人気コミュニティランキング