座標圧縮って何?- イマノ君AtCoder学習日記#1

AtCoder

どうやらイマノ君はAtCoderというプログラミングコンテストに参加しているみたいです。
その解説にあった座標圧縮がわからないとのこと。

座標圧縮とはいらない部分を切り落とすこと

イマノ君
イマノ君

ユウ兄!最近 AtCoder 始めたんだけど、わからないことばっかりで困ってる!助けて!

ユウ兄
ユウ兄

お!新しいことにチャレンジするのは素晴らしいですね。

どこがわからないんですか?

イマノ君
イマノ君

解説に 座標圧縮 って書いてあるんだけどこれがよくわからないんだ…

ユウ兄
ユウ兄

それでは今回は座標圧縮について説明しましょうか!

座標圧縮って何?

ユウ兄
ユウ兄

早速ですが、座標圧縮というのは不要な部分を切り落とすことで必要な情報の処理を早くすることです。

イマノ君
イマノ君

いらない部分だけを切り落とすんだね!

ユウ兄
ユウ兄

そうです!

無駄な部分がなくなるため、探索などを行う際に高速化が可能なんですね。

実際の問題を解いてみる

イマノ君
イマノ君

ABC213-C を解いてたからこれの解説がいい!

ユウ兄
ユウ兄

わかりました。それではその問題を使いましょう。

ユウ兄
ユウ兄

座標圧縮ではある数列Aに対して通常以下の順で処理を行います。

1. Aをソートした数列をBとする

2. Bの重複した値を消す

3. Aの全要素についてBの何番目かを調べる

イマノ君
イマノ君

切り落とすだけじゃダメなの…?

ユウ兄
ユウ兄

そうなんです。主に座標圧縮は探索するのが目的なので元の数列のどこにあるかが重要なんです。

ユウ兄
ユウ兄

この手順をそのまま実装すると以下のようなコードになると思います。

今回は Python で実装していますよ。

import numpy
from sys import stdin

_, _, n = map(int, input().split())
row = numpy.empty(n, dtype=int)
col = numpy.empty(n, dtype=int)
for i in range(n):
  a, b = map(int, stdin.readline().split())
  row[i] = a
  col[i] = b
  
row_sorted = numpy.sort(numpy.unique(row))
col_sorted = numpy.sort(numpy.unique(col))

for i in range(n):
  print(numpy.where(row_sorted==row[i])[0][0]+1, numpy.where(col_sorted==col[i])[0][0]+1)
イマノ君
イマノ君

あれでもこのコードだと時間かかりすぎみたいだよ…?

ユウ兄
ユウ兄

そうなんです。

ただ単に手順をなぞるだけだと座標圧縮自体に時間がかかりすぎてしまうんですね。

ユウ兄
ユウ兄

numpy.sort, numpy.unique と numpy.whereに時間がかかりすぎているところが問題です。

ユウ兄
ユウ兄

そこで set関数をうまく使って重複を消しつつ、辞書に記録することで時間短縮を図ります。

すると以下の模範解答と同じコードになるはずです。( AtCoderのページにも同じものがあります。 )

H,W,N=map(int,input().split())
X,Y=[],[]
for i in range(N):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)

Xdict = {x:i+1 for i,x in enumerate(sorted(list(set(X))))}
Ydict = {y:i+1 for i,y in enumerate(sorted(list(set(Y))))}

for i in range(N):
  print(Xdict[X[i]], Ydict[Y[i]])
イマノ君
イマノ君

すごくスマートに書けるんだね!

まとめ

ユウ兄
ユウ兄

座標圧縮というのは不要な部分を切り落とすことで必要な情報の処理を早くすることでした。

イマノ君
イマノ君

数列のコピーをとって、同じものを消す。

その後に元の数列のどこにあるかを対応づけるんだよね!

ユウ兄
ユウ兄

はいそうです!

その際に Python では set 関数と辞書をうまく使って高速化していましたね。

イマノ君
イマノ君

次からはうまく解けそう!

ユウ兄ありがとう!

コメント

タイトルとURLをコピーしました