純ブログ

ちょっとプログラミングしてる人のブログです。

日本情報オリンピック 2013-2014 予選に参加した

日記 プログラミング コンテスト

12 月 15 日 13 時から 3 時間行われた，日本情報オリンピックの予選に参加しました。 本選に出場できるのは高校/高専 2 年生までですが，予選には誰でも参加できるので参加してみました。

使用環境

問題 1 : 平均点 (Average Score)

やるだけの問題。開始 5 分後ぐらいに提出しました。

#include <iostream>
using namespace std;

int main()
{
    int a, sum = 0;
    for (int i = 0; i < 5; ++i) {
        cin >> a;
        sum += a >= 40 ? a : 40;
    }
    cout << sum/5 << endl;
    return 0;
}

問題 2 : 投票 (Vote)

これもやるだけ。……の割には 15 分ぐらいかかりました。

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

int main()
{
    int N, M, A[1000], B[1000], v[1000] = {}, max = 0, res;
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> B[i];
        int j = 0;
        while (B[i] < A[j]) ++j;
        ++v[j];
    }
    max = v[0]; res = 1;
    for (int i = 1; i < N; ++i) {
        if (v[i] > max) max = v[i], res = i+1;
    }
    cout << res << endl;
    return 0;
}

問題 3 : 超都観光 (Super Metropolis)

最初，幅優先探索で書いたところ，入力データ 3 で計算が終わらない。その後，2 つの観光スポット（交差点）の南北方向の距離と東西方向の距離から計算できることに気づきました。実装して入出力例と一致することを確認して，一応，入力データ 1 を手計算してみたところ，プログラムの出力と一致したので提出しました。

#include <iostream>
#include <utility>
#include <algorithm>
#include <cmath>
using namespace std;

typedef pair<int, int> P;
const int INF = 1e8;
const int dx[] = {1, 0, -1, 0, 1, -1}, dy[] = {0, 1, 0, -1, 1, -1};

int main()
{
    int W, H, N, x, y, res = 0;
    P p[1000];
    
    cin >> W >> H >> N;
    for (int i = 0; i < N; ++i) {
        cin >> x >> y;
        p[i] = make_pair(x, y);
    }
    
    //p[i]からp[i+1]への最小の道
    for (int i = 0; i < N-1; ++i) {
        int ddx = p[i].first - p[i+1].first;
        int ddy = p[i].second - p[i+1].second;
        
        if (ddx*ddy >= 0) res += max(abs(ddx), abs(ddy));
        else res += abs(ddx) + abs(ddy);
    }
    cout << res << endl;
    
    return 0;
}

ここまでで 1 時間 45 分。

問題 4 : 部活のスケジュール表 (Schedule)

数え上げの問題。 諦める。

問題 5 : タクシー (Taxis)

眺める。やらない。

問題 6 : 小籠包 (Xiao Long Bao)

眺める。やらない。

結果

提出した分がすべて正解だとしたら 3 [問] x 5 [ケース/問] x 20 [点/ケース] = 300 [点]。

1, 2年生の時は 2 完しかできなかったので，3 問解けて良かった（小並感）。

(2014/12/11 追記) いまさらですが，3 完していました。