C++/Rust解答例 星座探し - 日本情報オリンピック2008予選より第四項

備忘録 C++, Rustでの解答

問題の概要

https://atcoder.jp/contests/joi2008yo/tasks/joi2008yo_d
与えられたm個の座標と同じ位置関係を保った物を、与えられるn個の座標の中に見つける。
これらを重ね合わせるために必要な平行移動の量を、空白区切りで出力する。

制約

• 
• 
• 

入力

1行目に座標の個数、2行目から個の座標が入力される。
その後、座標の個数が渡され、その次の行から個の座標が座標がそれぞれ空白区切りで入力される。

解き方

なんとなく最古の遺跡と似ているが、ベクトルのような数学知識は不要。

シンプルに考えれば全ての平行移動可能性を試せば良いが、当然これは計算量が多すぎる。
与えられた星座()の星のうち一つを選択し、与えられた写真()の星一つ一つに当てはめていけば計算量が大幅に抑えられる。
その後、あらかじめ保存したmの位置関係をnに適用していき、全ての星があればこれを出力する。
一つでも見つからない星があればbreakして良いし、星座が見付かればその時点でbreakしても良い。
これをサボらなければ実行時間はかなり短かくなる。

サンプルコード

今回も同じ手法で実装しているが、日を跨いで書いたので若干手順が異なる。

C++

#include <bits/stdc++.h>
using namespace std;

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

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

  sort(starrysky.begin(), starrysky.end());
  vector<int> p(2), base(2), ans(2);

  for (int i = 0; i < n; i++) {
    p[0] = starrysky[i][0], p[1] = starrysky[i][1];
    for (int j = 0; j < m - 1; j++) {
      p[0] += distance[j][0];
      p[1] += distance[j][1];

      if (binary_search(starrysky.begin(), starrysky.end(), p)) {
        if (j == m - 2) {
            ans[0] = starrysky[i][0] - constellation[0][0];
            ans[1] = starrysky[i][1] - constellation[0][1];
        }
      } else {
        break;
      }
    }
  }
  cout << ans[0] << " " << ans[1] << endl;
}

Rust

use std::io;
fn readstdin() -> String {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    input
}

fn split(v: String) -> Vec<i32> {
    v.split_whitespace()
        .map(|n| i32::from_str_radix(n, 10).unwrap())
        .collect()
}

fn main() {
    let m: usize = readstdin().trim().parse().unwrap();
    let mut constellation: Vec<Vec<i32>> = Vec::new();
    for _ in 0..m {
        constellation.push(split(readstdin()));
    }
    let n: usize = readstdin().trim().parse().unwrap();
    let mut starrysky: Vec<Vec<i32>> = Vec::new();
    for _ in 0..n {
        starrysky.push(split(readstdin()));
    }
    starrysky.sort();

    let mut distance: Vec<Vec<i32>> = Vec::new();
    for i in 0..m - 1 {
        distance.push(vec![
            constellation[i + 1][0] - constellation[i][0],
            constellation[i + 1][1] - constellation[i][1],
        ])
    }

    'end: for i in 0..n {
        let mut p: Vec<i32> = vec![starrysky[i][0], starrysky[i][1]];
        'next: for j in 0..distance.len() {
            p[0] += distance[j][0];
            p[1] += distance[j][1];

            if starrysky.binary_search(&p).is_ok() {
                if j == distance.len() - 1 {
                    println!("{} {}", starrysky[i][0] - constellation[0][0], starrysky[i][1] - constellation[0][1]);
                    break 'end;
                }
            } else {
                break 'next;
            }
        }
    }
}

コードの部分解説

取り立てて言う事はない。
ここでは星座の星の位置関係を0と1、1と2、といった形で計算しているが、全て0基準としても良い