プロコン小技
ブログの第一回目がもう4カ月くらい前ということで、三日坊主にすらなれなかったわけですが、卒論を前にして現実逃避がてら復活することになりました。
ということで、本日のネタはプロコンの小技です。
要素の比較
こんな問題があったとします。
問題：
要素数nの数列がm個与えられます。1つの数列の中で要素が重複している場合はYES、そうじゃない場合はNOを出力してください。
例：
input
3
1 2
1 2 1 3
4 5
output
NO
YES
NO
まぁ例えなので、nの範囲がわからんやんけとか数列の各要素の範囲わからんやんけとかmの範囲わからんやんけとか、諸々の突っ込みはなしでお願いします。
この問題を解く時に真っ先に思い浮かぶのは、いわゆる全探索だと思います。
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i==j) continue;
//ここでなんらかの処理
}
}
みたいな。こんなん思いつかんか。まぁどう考えても無駄が多いですね。何度も同じところを比較する羽目になりますし。1つのテストケースの中に要素数1万の数列が10とか入ってたりしてたら確実にダメです。
ではこれをどうすればいいか。これは簡単に解けます。
bool ex[n] (falseに初期化されてると思ってください)
とかを作っておきます。そして、
bool f = false;
for(int i = 0; i < n; i++){
if(ex[数列[i]]){
cout << "YES" << endl;
f = true;
break;
}
ex[数列[i]] = true;
}
if(!f) cout << "NO" << endl;
こんな感じで組みます。
添え字 = 要素
とすることで、定数時間でその要素の有無を確認できるわけですね。線形時間で解けるのでさっきのより早いです。1つのテストケース内に要素数1万の数列が10個あっても余裕で解けます。1万個あってもギリ解けるでしょう。前者のがo(n^2)で後者がo(n)です。
ということで、今回の話の本質は2つです。
- 添え字 = 要素という配列の使い方
- 同じ計算を繰り返さないよう工夫
前者はよく使う手法で、メモリがよほど切迫してない限りはわかりやすい実装をするためにも重要なものです。
後者もかなり重要な手法で、この考え方がDP(動的計画法)につながります。(多分)
皆さん早くて分かりやすい実装を心がけましょう。
今日はここまで。ではまたの機会に。
