ABC111のCを解きたい

Question

前提・実現したいこと

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/ツールのバージョンなど）

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

Answer 1

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

1. 連続していないと同一数値とみなさない

1 x 3 x 1 x => [[1,1],[3,3],[1,1]]

1. 数列の最後の数値を無視している

x 2 x 3 x 4 => [[2,1],[3,1],[0,0]]

Comments

[退会済みユーザー]

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

[退会済みユーザー]

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

[asm]

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

Answer 2

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

#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;
}