質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.20%

ABC111のCを解きたい

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 473
退会済みユーザー

退会済みユーザー

前提・実現したいこと

https://atcoder.jp/contests/abc111/tasks/arc103_a
この問題をときたいです。
youtubeの解説放送は以下の動画のおおよそ26:27~です
https://www.youtube.com/watch?v=fYS-rAUSD5o&t=1927s

※C言語の文法がわからないとかではないです

発生している問題・エラーメッセージ

エラーは出ません。
サンプル以外のテストケース全てで間違いとされます。
テストケースがわからないので、こういうときにこのコードだとまずいよ
というケースを教えていただけると幸いです。
シンプルにおかしいところでも構いません。

該当のソースコード

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

int frequency(int idx, int n, int* pv, int Arr[][2]){
    int tmp = pv[0];
    int idxDarr = 0;
    int cnt = 0;
    while(idx < n){
        if(tmp != pv[idx]){
            idxDarr++;
            cnt = 1;
            Arr[idxDarr][0] = pv[idx];
            Arr[idxDarr][1] = cnt;
            tmp = pv[idx];
        }else{
            Arr[idxDarr][0] = pv[idx];
            cnt++;
            Arr[idxDarr][1] = cnt;   
        }
        idx += 2;
    }
    if(idx == 0) return 0;
    else return 1;
}

int compDown(const void* a, const void* b){
    int* pa = (int*)a;
    int* pb = (int*)b;
    return *(pb+1) - *(pa+1);
}

int main(void){
    int n;
    scanf("%d", &n);
    int v[n];
    for(int i = 0; i < n; i++){scanf("%d", &v[i]);}
    int oddTrg, evenTrg;

    int oddArr[n/2][2];
    int evenArr[n/2][2];
    for(int i = 0; i < n/2; i++){for(int j = 0; j < 2; j++){oddArr[i][j] = 0;}}
    for(int i = 0; i < n/2; i++){for(int j = 0; j < 2; j++){evenArr[i][j] = 0;}}
    //奇数番目、偶数番目それぞれの、数字とその個数の二次元配列をつくる
    int oddNum = frequency(0, n, v, oddArr);
    int evenNum = frequency(1, n, v, evenArr);
    //個数の大きい順に並び替える
    qsort(oddArr, n/2, 2*sizeof(int), compDown);
    qsort(evenArr, n/2, 2*sizeof(int), compDown);
    //並び替えれてるかのチェックに使う
    /*for(int i = 0; i < n/2; i++){for(int j = 0; j < 2; j++){printf("%d ", oddArr[i][j]);}printf("\n");}
    printf("----------\n");
    for(int i = 0; i < n/2; i++){for(int j = 0; j < 2; j++){printf("%d ", evenArr[i][j]);}printf("\n");}*/

    int ans = -1;;
    //数字の種類が1種類の時の処理も書かないといけなさそう
    if(oddNum == 0 && evenNum == 0){
        if(oddArr[0][0] == evenArr[0][0]){ans = n/2;}
        else{ans = 0;}
    }
    else if((oddNum == 1) && (evenNum == 0)){
        //ans = n/2;
        if(oddArr[0][0] == evenArr[0][0]){ans = n/2 - oddArr[1][1];}
        else{ans = n/2 - oddArr[0][1];}
    }
    else if((oddNum == 0) && (evenNum == 1)){
        //ans = n/2;
        if(oddArr[0][0] == evenArr[0][0]){ans = n/2 - evenArr[1][1];}
        else{ans = n/2 - evenArr[0][1];}
    }
    //数字の種類が奇数番目偶数番目共に2種類以上の時用の処理
    if(ans == -1){
        if(oddArr[0][0] != evenArr[0][0]){
            ans = n - (oddArr[0][1]+evenArr[0][1]);
        }
        else{
            if(oddArr[0][1] > evenArr[0][1]){
                ans = n - (oddArr[0][1] + evenArr[1][1]);
            }
            else if(oddArr[0][1] == evenArr[0][1]){
                if(oddArr[1][1] >= evenArr[1][1]){
                    ans = n - (oddArr[1][1] + evenArr[0][1]);
                }else{
                    ans = n - (oddArr[0][1] + evenArr[1][1]);
                }
            }
            else{
                ans = n - (oddArr[1][1]+evenArr[0][1]);
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+1

frequency関数に2点問題があります。

  1. 連続していないと同一数値とみなさない  
    1 x 3 x 1 x => [[1,1],[3,3],[1,1]]

  2. 数列の最後の数値を無視している  
    x 2 x 3 x 4 => [[2,1],[3,1],[0,0]]

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/06 15:56

    回答ありがとうございます!
    降順にソートしてからじゃないと、おっしゃるように数えれないですね・・・。
    本当にありがとうございます。
    それをやってから、ある数字の個数を数える という流れがよさそうですので
    書き直します。
    本当に助かりました。

    キャンセル

  • 2019/05/06 16:38

    ちゃんと動きました。
    本当にありがとうございます!

    キャンセル

  • 2019/05/06 16:40

    アイデアとしては、数値の種類が10^5までしかない
    int[100000]でも400kb
    頻度情報だけとってから変換していくのもありですね

    キャンセル

0

[] だらけで見難かったのでマップ自作でしてみました. 性能は二の次です.

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

/**** value sorted map ****/
typedef struct {
  int key;
  int value;
} MAP_ENTRY;

typedef struct {
  int size;
  MAP_ENTRY *entries;
} MAP;

void init_map(MAP *map) {
  map->size = 0;
  map->entries = NULL;
}

int get_value(MAP *map, int key) {
  MAP_ENTRY *entry = map->entries;
  for(int i=0; i<map->size; i++, entry++) if(entry->key == key) return entry->value;
  return -1; //無し
}

void set_value(MAP *map, int key, int value) {
  MAP_ENTRY *entry = map->entries;
  for(int i=0; i<map->size; i++, entry++) {
    if(entry->key == key) {
      for(; entry>map->entries; entry--) {
        if((entry-1)->value >= value) break; //valueの大きい順
        memcpy(entry, entry-1, sizeof(MAP_ENTRY));
      }
      entry->key = key;
      entry->value = value;
      break;
    }
  }
}

void add_entry(MAP *map, int key, int value) {
  MAP_ENTRY *new_entries = (MAP_ENTRY *)malloc(sizeof(MAP_ENTRY)*(map->size+1));
  MAP_ENTRY *old_entries = map->entries;
  map->entries = new_entries;

  int flag = 0;
  if(old_entries != NULL) {
    for(int i=0; i<map->size; i++) {
      if(flag == 0 && old_entries[i].value < value) { //valueの大きい順
        new_entries->key = key;
        new_entries->value = value;
        new_entries++;
        flag = 1; //今後 if 文に入らないよう
      }
      memcpy(new_entries++, &old_entries[i], sizeof(MAP_ENTRY));
    }
    free(old_entries);
  }
  if(flag == 0) {
    new_entries->key = key;
    new_entries->value = value;
  }

  map->size ++;
}

int get_size(MAP *map) {
  return map->size;
}

MAP_ENTRY *get_entry(MAP *map, int index) {
  return &map->entries[index];
}

/**** main ****/
int main(void) {
  MAP first, second;

  init_map(&first);
  init_map(&second);

  //入力
  int n;
  scanf("%d", &n);
  for(int i=0, key=0; i<n; i++) {
    MAP *map = (i%2 ? &second : &first);
    scanf("%d", &key);
    int value = get_value(map, key);
    if(value == -1) {
      add_entry(map, key, 1);
    } else {
      set_value(map, key, value+1);
    }
  }

//並び替えれてるかのチェックに使う
printf("first size=%d----------\n", first.size);
for(int i=0; i<first.size; i++) printf("%d %d\n", first.entries[i].key, first.entries[i].value);
printf("second size=%d----------\n", second.size);
for(int i=0; i<second.size; i++) printf("%d %d\n", second.entries[i].key, second.entries[i].value);


  int first_size = get_size(&first);
  int second_size = get_size(&second);

  //使用数値決定
  MAP_ENTRY *first_entry = get_entry(&first, 0);
  MAP_ENTRY *second_entry = get_entry(&second, 0);

  if(first_entry->key == second_entry->key) {
    if(first_size <= 1 && second_size <= 1) { //全て同じ数値
      printf("----------\n");
      printf("%d\n", second_entry->value);
      exit(0);
    }
    if((first_size >= 2 && second_size >= 2 && first_entry->value < second_entry->value) ||
       (first_size >= 2 && second_size <= 1)) {
      first_entry = get_entry(&first, 1);
    } else {
      second_entry = get_entry(&second, 1);
    }
  }

  //カウント
  int ans = 0;
  for(int i=0; i<first_size; i++) {
    MAP_ENTRY *entry = get_entry(&first, i);
    if(entry->key != first_entry->key) ans+=entry->value;
  }
  for(int i=0; i<second_size; i++) {
    MAP_ENTRY *entry = get_entry(&second, i);
    if(entry->key != second_entry->key) ans+=entry->value;
  }
  printf("----------\n");
  printf("%d\n", ans);

  return 0;
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.20%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる