AtCoder 第７回日本情報オリンピック 予選（過去問）

A - おつり

問題概要

• 1000円札を出すと、お釣りが最小枚数で返される
• 支払う金額が与えられたとき、最小枚数のお釣りを計算する
• 使用できる硬貨：500円, 100円, 50円, 10円, 5円, 1円
• 目標は、お釣りに含まれる硬貨の最小枚数を求める

制約

• 入力：1以上1000未満の整数が与えられる
• 出力：最小枚数の硬貨数を出力

解説

• 1000円から支払った金額を引いてお釣り額を計算
• 500円硬貨から順番に、お釣りをその硬貨で払える最大枚数分だけ支払い、残りのお釣り額を更新
• 最後に、支払った硬貨の合計枚数を出力

実装例（C++）

#include <iostream>
#include <vector>

using namespace std;


int main() {
    int charge;
    cin >> charge;

    int change = 1000 - charge;

    vector<int> coin_types = {500, 100, 50, 10, 5, 1};

    int cnt = 0;
    for (int coin_type: coin_types) {
        cnt += change / coin_type;
        change %= coin_type;
    }

    cout << cnt << endl;

    return 0;
}

計算量

常に6種類の硬貨を使用するため，計算量は O(1) 。

B - JOIとIOI

問題概要

• 与えられた文字列の中に「JOI」または「IOI」という連続する3文字が何回現れるかを計算する

制約

• 文字列の長さは最大で10,000文字
• 文字はアルファベットの大文字のみ

解説

• 単純に入力文字列を全探索する
• （コードを見た方がわかりやすい）

実装例（C++）

#include <iostream>

using namespace std;


int main () {
    string s;
    cin >> s;

    int joi_ans = 0;
    int ioi_ans = 0;
    for (int i = 0; i < s.size() - 2; i++) {
        if (s[i] == 'J' && s[i+1] == 'O' && s[i+2] == 'I') {
            joi_ans++;
        }
        if (s[i] == 'I' && s[i+1] == 'O' && s[i+2] == 'I') {
            ioi_ans++;
        }
    }

    cout << joi_ans << endl;
    cout << ioi_ans << endl;

    return 0;
}

計算量

• 1回のループで文字列の各文字を処理するため、時間計算量は O(n)

D - 星座探し

問題概要

• 与えられた星座の座標をもとに、写真に写っている星の中から同じ形の星座を探し出す問題
• 星座は平行移動されているだけで、大きさや向きは変わらない
• 写真には星座以外の余分な星が含まれている場合がある
• 平行移動すべき量を求める

制約

• 星座を構成する星の数 m: 1 ≦ m ≦ 200
• 写真に写っている星の数 n: 1 ≦ n ≦ 1000
• 星の座標: 0 ≦ x, y ≦ 1000000

解説

• 星の座標が 10^6 * 10^6 のため，座標の全探索で解くことはできない
• 工夫した全探索をする → 存在する星の位置で全探索
  • 写真1の星座の最初の星を基準に、写真の1つ目の星の位置を一致させる
  • 写真1,2の星を一致させるための平行移動量（x方向、y方向の移動量）を計算する
  • 計算した移動量を元に、他の星座の星を平行移動し、写真に写っている星と一致するかどうかを確認する
  • もしすべての星が一致すれば、その平行移動量が答えである

実装例（C++）

#include <iostream>
#include <vector>

using namespace std;

int main () {
    int m;
    cin >> m;

    vector<vector<int>> m_stars(m, vector<int>(2));
    for (int i = 0; i < m; i++) {
        cin >> m_stars[i][0] >> m_stars[i][1];
    }

    int n;
    cin >> n;

    vector<vector<int>> n_stars(n, vector<int>(2));
    for (int i = 0; i < n; i++) {
        cin >> n_stars[i][0] >> n_stars[i][1];
    }

    for (int i = 0; i < n; i++) {
        int dis_x = n_stars[i][0] - m_stars[0][0];
        int dis_y = n_stars[i][1] - m_stars[0][1];
        int cnt = 0;
        for (int j = 0; j < m; j++) {
            int tmp_x = m_stars[j][0] + dis_x;
            int tmp_y = m_stars[j][1] + dis_y;
            for (int k = 0; k < n; k++) {
                if ((n_stars[k][0] == tmp_x) && (n_stars[k][1] == tmp_y)) {
                    cnt++;
                    break;
                }
            }
        }
        if (cnt == m) {
            cout << dis_x << " " << dis_y << endl;
            break;
        }
    }

    return 0;
}

計算量

• 入力: O(m + n)
• 全体の計算量は O(n × m × n)