課題 1.5 情報オリンピック予選問題(2013年度第13回ＪＯＩ予選問題2)

<問題>

• 20XX年に東京で世界的なスポーツ大会が開かれることになった．プログラミングコンテストはスポーツとして世界で楽しまれており，競技として採用される可能性がある．採用される競技を決める審査委員会について調べたところ，次のようなことが分かった．

• 審査委員会のために，候補となる N 個の競技を面白い方から順番に並べたリストが作成された．リストの上から i 番目には i 番目に面白い競技が書かれている．それを競技 i とする．さらに競技 i の開催に必要な費用 Ai が書かれている．

• また，審査委員会は委員 1 から委員 M までの M 人の委員で構成されている．委員 j は自分の審査基準 Bj をもっており，開催に必要な費用が Bj 以下の競技のうち最も面白いものに 1 票を投票した．

• どの委員の審査基準に対しても，少なくとも 1 つの競技は開催に必要な費用が審査基準以下であった．したがって，委員は全員 1 票を投票した．

• 最も多く票を獲得した競技は 1 つだけであった．
  競技のリストと委員の情報が与えられたとき，最も多く票を獲得した競技の番号を求めるプログラムを作成せよ．
  

<入力>

• 入力は 1 + N + M 行からなる．

• 1 行目には整数 N, M (1 ≦ N ≦ 1000，1 ≦ M ≦ 1000) が書かれており，それぞれ競技の数，委員の数を表す．

• 続く N 行のうちの i 行目 (1 ≦ i ≦ N) には整数 Ai (1 ≦ Ai ≦ 1000) が書かれており， 競技 i の開催に必要な費用 Ai を表す．

• 続く M 行のうちの j 行目 (1 ≦ j ≦ M) には整数 Bj (1 ≦ Bj ≦ 1000) が書かれており，委員 j の審査基準 Bj を表す．

• 与えられる入力データにおいては，どの委員も必ず 1 票を投票し，最も多く票を獲得した競技は 1 つであることが保証されている.
  

<出力>

• 最も多く票を獲得した競技の番号を 1 行で出力せよ．また,出力の最後には,改行を入れる．

<入出力例>

解答例 (制限時間は60分)

#include <stdio.h>

int main(void) {
    int N,M;
    int A[1000], Bj;
    int C[1000];  /* 獲得票数 */
    int i, j;
    int maxi, maxp;

    scanf("%d %d", &N, &M); /* 競技数、審査員数 */

    /* 配列Aにランク順に各競技の費用。配列Cの初期化も同時に */
    for (i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        C[i]=0;
    }


    /* 審査員の判定情報を読み込む。この値を超えない競技に1票 */
    for (j = 0; j < M; j++){
        scanf("%d", &Bj);
        for (i = 0; i < N; i++) { /* 各競技のランク順 A[0]から順にチェック */
            if (A[i] <= Bj) { /* Bjを超えていない競技A[i] */
                C[i]++; /* 1票入れて、ループを抜ける */
                break;
            }
        }
    }

    maxi = 0;  /* 暫定一位の競技。配列の添え字 */
    maxp = C[0]; /* 暫定一位の得票数 */

    /* 最大得票数の競技番号、配列の添え字を求める */
    for (i = 1; i < N; i++) {
        if (maxp < C[i]) {
            maxi = i;
            maxp = C[i];
        }
    }

    /* 配列の先頭は0から。競技は1種目からなので、出力調整 */
    printf("%d\n", maxi+1);

    return 0;
}