読者です 読者をやめる 読者になる 読者になる

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, A 解答

A: 被験者の選定

問題

n個の整数が与えられる。任意のペアについて最小の差の絶対値を求め、出力せよ。

解法

二重ループで全てのペアについて差を求める。または、小さい順に並び替えて、隣り合うペアのみ差を求める。

1問目なので詳しく書くと、最も基礎的なプログラムである入出力と、最も基礎的なアルゴリズムであるソーティング、この2点を問うている。

入出力

プログラミングコンテストでは標準入力・標準出力を使うのが基本。しかし国内予選では異なる形式をとっている。
入力データをダウンロードし、ソースコードと出力データの2つをアップロードする。この提出を2回連続で成功するとACになるが、このとき、ソースコードが完全に同一のファイルである必要がある。なので、ソースコードに入力データを貼り付ける事はできない。ファイル入出力はできると思う。
実行ファイルがa.out、入力がinput.txtのとき、output.txtを作りたかったらターミナルで

$ ./a.out < input.txt > output.txt

こんな感じ?
小技としてteeコマンドを使うと出力を確認しながらoutput.txtを生成するとか。

$ ./a.out < input.txt | tee output.txt
ソート

この問題では必須というわけではないが。
重要なアルゴリズムであるが普通のプログラミング言語(ICPCで使えるプログラミング言語は全て)標準ライブラリに搭載されている。中身を理解する必要はないが使い方は勝手知ったるソート関数。

コード

#include<cstdio>
#include<algorithm>
using namespace std;

int N, A[1111];
int main() {
    while (scanf("%d", &N), N) {
	for (int i=0; i<N; i++)
	    scanf("%d", A+i);

	sort(A, A+N);

	int ans = A[1] - A[0];
	for (int i=0; i<N-1; i++) 
	    ans = min(ans, A[i+1] - A[i]);

	printf("%d\n", ans);
    }
    return 0;
}

日記

この問題が解けないチームは

  1. 参加し忘れた
  2. 事前テストに出ておらずシステムの使い方を間違えた
  3. パスワードを紛失した
  4. マシンが爆発した

こんなところなんですかねえ。